Deferred Acceptance with Compensation Chains
| العنوان: | Deferred Acceptance with Compensation Chains |
|---|---|
| المؤلفون: | Piotr Dworczak |
| المصدر: | EC |
| بيانات النشر: | Institute for Operations Research and the Management Sciences (INFORMS), 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | Class (set theory), Matching (statistics), Mathematical optimization, Matching (graph theory), Computer science, Stability (learning theory), 0102 computer and information sciences, Characterization (mathematics), 010501 environmental sciences, Management Science and Operations Research, 01 natural sciences, Outcome (game theory), Compensation (engineering), 0502 economics and business, Economics, 050207 economics, 0101 mathematics, Set (psychology), 0105 earth and related environmental sciences, Matching market, 05 social sciences, 010102 general mathematics, Stable marriage problem, Computer Science Applications, If and only if, 010201 computation theory & mathematics |
| الوصف: | 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. |
| تدمد: | 1526-5463 0030-364X |
| الوصول الحر: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::28ffc10fe6892a87905a385ce4b7cd7fTest https://doi.org/10.1287/opre.2020.2042Test |
| حقوق: | CLOSED |
| رقم الانضمام: | edsair.doi.dedup.....28ffc10fe6892a87905a385ce4b7cd7f |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 15265463 0030364X |
|---|