On two competing mechanisms for priority-based allocation problems.(English)Zbl 1125.91019
Summary: We consider the priority-based allocation problem: there is a set of indivisible objects with multiple supplies (e.g., schools with seats) and a set of agents (e.g., students) with priorities over objects (e.g., proximity of residence area). We study two well-known and competing mechanisms. The agent-optimal stable mechanism (AOSM) allots objects via the deferred acceptance algorithm. The top trading cycles mechanism (TTCM) allots objects via Gale’s top trading cycles algorithm. We show that the two mechanisms are equivalent, or TTCM is fair (i.e., respects agents’ priorities), or resource monotonic, or population monotonic, if and only if the priority structure is acyclic. Furthermore, if AOSM fails to be efficient (consistent) for a problem, TTCM also fails to be fair (consistent) for it. However, the converse is not necessarily true.
MSC:
| 91A20 | Multistage and repeated games |
| 91A44 | Games involving topology, set theory, or logic |
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 91B68 | Matching models |
Cite
Full Text:DOI
References:
| [1] | Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701 (1998) ·Zbl 1019.91016 |
| [2] | Abdulkadiroğlu, A.; Sönmez, T., House allocation with existing tenants, J. Econ. Theory, 88, 233-260 (1999) ·Zbl 0939.91068 |
| [3] | Abdulkadiroğlu, A.; Sönmez, T., School choicea mechanism design approach, Amer. Econ. Rev., 93, 729-747 (2003) |
| [4] | Balinski, M.; Sönmez, T., A tale of two mechanismsstudent placement, J. Econ. Theory, 84, 73-94 (1999) ·Zbl 0916.90008 |
| [5] | Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) ·Zbl 1134.91357 |
| [6] | Dubins, L. E.; Freedman, D. A., Machiavelli and the Gale-Shapley algorithm, Amer. Math. Monthly, 88, 485-494 (1981) ·Zbl 0449.92024 |
| [7] | Ehlers, L.; Klaus, B.; Pápai, S., Strategy-proofness and population monotonicity for house allocation problems, J. Math. Econ., 38, 329-339 (2002) ·Zbl 1010.90034 |
| [8] | Ehlers, L.; Klaus, B., Resource monotonicity for house allocation problems, Int. J. Game Theory, 32, 545-560 (2004) ·Zbl 1098.91080 |
| [9] | Ehlers, L., Coalitional strategy-proof house allocation, J. Econ. Theory, 105, 298-317 (2002) ·Zbl 1021.91035 |
| [10] | Ergin, H., Consistency in house allocation problems, J. Math. Econ., 34, 77-97 (2000) ·Zbl 1145.91360 |
| [11] | Ergin, H., Efficient resource allocation on the basis of priorities, Econometrica, 70, 2489-2497 (2002) ·Zbl 1141.91563 |
| [12] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) ·Zbl 0109.24403 |
| [13] | O. Kesten, Coalitional strategy-proofness and resource monotonicity for house allocation problems, Mimeo, University of Rochester, 2003.; O. Kesten, Coalitional strategy-proofness and resource monotonicity for house allocation problems, Mimeo, University of Rochester, 2003. ·Zbl 1211.91179 |
| [14] | O. Kesten, A new principle for indivisible good allocation problems, Mimeo, University of Rochester, 2003.; O. Kesten, A new principle for indivisible good allocation problems, Mimeo, University of Rochester, 2003. |
| [15] | O. Kesten, On two kinds of manipulation in two-sided matching markets, Mimeo, University of Rochester, 2004.; O. Kesten, On two kinds of manipulation in two-sided matching markets, Mimeo, University of Rochester, 2004. |
| [16] | Pápai, S., Strategy-proof assignment by hierarchical exchange, Econometrica, 68, 1403-1433 (2000) ·Zbl 1023.91019 |
| [17] | Roth, A.; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, J. Math. Econ., 4, 131-137 (1977) ·Zbl 0368.90025 |
| [18] | Roth, A.; Sotomayor, M., Two-sided Matching (1990), Cambridge University Press: Cambridge University Press New York ·Zbl 0726.90003 |
| [19] | Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 23-28 (1974) ·Zbl 0281.90014 |
| [20] | Thomson, W., The consistency principle, (Ichiishi, T.; Neyman, A.; Tauman, Y., Game Theory and Applications (1990), Academic Press: Academic Press New York), 187-215 ·Zbl 0724.90091 |
| [21] | Thomson, W., Population monotonic allocation rules, (Barnett, W. A.; Moulin, H.; Salles, M.; Schofield, N., Social Choice, Welfare and Ethics (1995), Cambridge University Press: Cambridge University Press Cambridge) ·Zbl 0881.90013 |
| [22] | W. Thomson, The theory of fair allocation, book manuscript, 2000.; W. Thomson, The theory of fair allocation, book manuscript, 2000. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
