The probabilistic serial mechanism with private endowments. (English) Zbl 1230.91088
Summary: A random assignment is ordinally efficient if it is not stochastically dominated with respect to individual preferences over sure objects. When there are no private endowments, the set of ordinally efficient random assignments is characterized by the eating algorithm A. Bogomolnaia and H. Moulin [J. Econ. Theory 100, No. 2, 295–328 (2001; Zbl 1134.91357)]. When there are private endowments, the main requirement is individual rationality; however, the eating algorithm fails to deliver this property. Our contribution is the natural generalization of the eating algorithm for this general class of problems. The family of this generalized eating algorithm characterizes the set of individually rational and ordinally efficient random assignments. A special solution in this family, the individually rational probabilistic serial (PSIR), also achieves a new fairness axiom, no justified-envy. However, it is not immune to strategic manipulation. We show that individual rationality, no justified-envy and strategy-proofness are incompatible.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 90B80 | Discrete location and assignment |
Citations:
Zbl 1134.91357References:
| [1] | Abdulkadiroğlu, Atila; Sönmez, Tayfun, Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701 (1998) · Zbl 1019.91016 |
| [2] | Abdulkadiroğlu, Atila; Sönmez, Tayfun, House allocation with existing tenants, J. Econ. Theory, 88, 233-260 (1999) · Zbl 0939.91068 |
| [3] | Abdulkadiroğlu, Atila; Sönmez, Tayfun, Ordinal efficiency and dominated sets of assignments, J. Econ. Theory, 112, 157-172 (2003) · Zbl 1076.91023 |
| [4] | Abdulkadiroğlu, Atila; Sönmez, Tayfun, School choice: A mechanism design approach, Amer. Econ. Rev., 93, 729-747 (2003) |
| [5] | Birkhoff, Garrett, Tres observaciones sobre el algebra lineal, Univ. Nac. Tucuman Rev. Ser. A, 5, 147-151 (1946) · Zbl 0060.07906 |
| [6] | Bogomolnaia, Anna; Moulin, Hervé, A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) · Zbl 1134.91357 |
| [7] | Bogomolnaia, Anna; Moulin, Hervé, A simple random assignment problem with a unique solution, Econ. Theory, 19, 623-636 (2002) · Zbl 1022.91018 |
| [8] | Crès, Hérve; Moulin, Hervé, Scheduling with opting out: Improving upon random priority, Operations Res., 49, 565-576 (2001) · Zbl 1163.90520 |
| [9] | Gale, David, A theorem on flows in networks, Pacific J. Math., 7, 1073-1082 (1957) · Zbl 0087.16303 |
| [10] | Hylland, Aanund; Zeckhauser, Richard J., The efficient allocation of individuals to positions, J. Polit. Economy, 87, 293-314 (1979) · Zbl 0448.62088 |
| [11] | Kesten, Onur, Why do popular mechanisms lack efficiency in random environments?, J. Econ. Theory, 144, 2209-2226 (2009) · Zbl 1195.91119 |
| [12] | Kojima, Fuhito; Manea, Mihai, Strategy-proofness of the probabilistic serial mechanism in large random assignment problems (2007) · Zbl 1202.91061 |
| [13] | Ma, Jingpeng, Strategy-proofness and strict core in a market with indivisibilities, Int. J. Game Theory, 23, 75-83 (1994) · Zbl 0804.90014 |
| [14] | McLennan, Andrew, Ordinal efficiency and the polyhedral separating hyperplane theorem, J. Econ. Theory, 105, 435-449 (2002) · Zbl 1056.91018 |
| [15] | Pápai, Szilvia, Strategyproof assignment by hierarchical exchange, Econometrica, 68, 1403-1434 (2000) · Zbl 1023.91019 |
| [16] | Pathak, Parag A., Lotteries in student assignments (2006) |
| [17] | Roth, Alvin E., Incentive compatibility in a market with indivisible goods, Econ. Letters, 9, 127-132 (1982) · Zbl 0722.90009 |
| [18] | Roth, Alvin E.; Postlewaite, Andrew, Weak versus strong domination in a market with indivisible goods, J. Math. Econ., 4, 131-137 (1977) · Zbl 0368.90025 |
| [19] | Roth, Alvin E.; Rothblum, Uriel G., Truncation strategies in matching markets: In search of advice for participants, Econometrica, 67, 21-44 (1999) |
| [20] | Roth, Alvin E.; Sönmez, Tayfun; Utku Ünver, M., Kidney exchange, Quart. J. Econ., 119, 457-488 (2004) · Zbl 1064.92029 |
| [21] | Sethuraman, Jay, 2001. A New Solution to the House Allocation Problem with Existing Tenants. Unpublished mimeo. University of Columbia; Sethuraman, Jay, 2001. A New Solution to the House Allocation Problem with Existing Tenants. Unpublished mimeo. University of Columbia |
| [22] | Shapley, Lloyd S.; Scarf, Herbert, On cores and indivisibility, J. Math. Econ., 1, 23-27 (1974) · Zbl 0281.90014 |
| [23] | Sönmez, Tayfun; Ünver, M. Utku, House allocation with existing tenants: An equivalence, Games Econ. Behav., 52, 153-185 (2005) · Zbl 1146.91331 |
| [24] | Svensson, Lars-Gunnar, Strategy-proof allocation of indivisible goods, Soc. Choice Welfare, 16, 557-567 (1999) · Zbl 1066.91571 |
| [25] | Von Neumann, John, A certain zero-sum two-person game equivalent to the optimal assignment problem, (Kuhn, Harold W.; Tucker, Albert W., Contribution to the Theory of Games (1953), Princeton University Press: Princeton University Press Princeton, NJ), 5-12 · Zbl 0050.14105 |
| [26] | Yılmaz, Özgür, Random assignment under weak preferences, Games Econ. Behav., 66, 546-558 (2009) · Zbl 1161.91346 |
| [27] | Zhou, Lin, On a conjecture by gale about one-sided matching problems, J. Econ. Theory, 52, 123-135 (1990) · Zbl 0725.90003 |
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.
