Deferred Acceptance with Compensation Chains
扩展了Gale-Shapley的延迟接受算法，允许双方都能提议，并引入补偿链机制，保证多项式时间内收敛到稳定匹配，且能实现所有稳定匹配，适用于需要兼顾稳定性和公平性的匹配场景。
In a foundational paper, Gale and Shapley (1962) introduced the deferred acceptance algorithm that achieves a stable outcome in a two-sided matching market by letting one side of the market make proposals to the other side. What happens when both sides of the market can propose? In “Deferred Acceptance with Compensation Chains,” Dworczak answers this question by constructing an equitable version of the Gale–Shapley algorithm in which the sequence of proposers can be arbitrary. The main result of the paper shows that the extended algorithm, equipped with so-called compensation chains, is not only guaranteed to converge in polynomial time to a stable outcome, but—in contrast to the original Gale–Shapley algorithm—achieves all stable matchings (as the sequence of proposers vary). The proof of convergence uses a novel potential function. The algorithm may find applications in settings where both stability and fairness are desirable features of the matching process.