Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings
研究了法律分配和效率调整的延迟接受机制（EADAM）两种扩展模型，通过建立与稳定分配的紧密联系，利用旋转等结构工具设计了快速算法，优化线性函数并求解EADAM结果，提升了实际应用性。
Since the seminal work of Gale and Shapley, stable assignments have received widespread attention for their mathematical elegance and broad applicability. However, in applications such as the school choice problem, in which public schools are often perceived as commodities and only students’ welfare matters, enforcing stability implies a loss of efficiency for the students. In “Legal assignments and fast EADAM with consent via classical theory of stable matchings,” Faenza and Zhang study two extensions of the traditional model—legal assignments and efficiency adjusted deferred acceptance mechanism (EADAM)—that strive to regain this loss in efficiency. The authors establish a tight connection between legal and stable assignments, which allows them to use critical structural tools of stable matchings, such as the concept of rotations, to design provably fast algorithms for (1) optimizing linear functions over the set of legal assignments and (2) finding the outcome of EADAM. These algorithmic results greatly improve the applicability of both extensions as witnessed by a complexity analysis and experimental results.