×

Fairness and efficiency in strategy-proof object allocation mechanisms. (English) Zbl 1400.91261

Summary: I consider the problem of allocating \(N\) indivisible objects among \(N\) agents according to their preferences when transfers are absent and an outside option may exist. I study the tradeoff between fairness and efficiency in the class of strategy-proof mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness, and (3) ordinal efficiency and equal division lower bound. Result 1 is the first impossibility result for this setting that uses ex-post efficiency; results 2 and 3 are more practical than similar results in the literature. In addition, for \(N=3\), I give two characterizations of the celebrated random serial dictatorship mechanism: it is the unique strategy-proof, ex-post efficient mechanism that (4) provides agents that have the same ordinal preferences with assignments not dominated by each other (weak envy-freeness among equals), or (5) provides agents that have the same cardinal preferences with assignments of equal expected utility (symmetry). These results strengthen the characterization by A. Bogomolnaia and H. Moulin [ibid. 100, No. 2, 295–328 (2001; Zbl 1134.91357)]; result 5 implies the impossibility result by L. Zhou [ibid. 52, No. 1, 123–135 (1990; Zbl 0725.90003)].

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
91B68 Matching models
PDFBibTeX XMLCite
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, 689-701 (1998) · Zbl 1019.91016
[2] Abdulkadiroğlu, A.; Sönmez, T., School choice: a mechanism design approach, Am. Econ. Rev., 93, 3, 729-747 (2003)
[3] Abdulkadiroğlu, A.; Sönmez, T., Ordinal efficiency and dominated sets of assignments, J. Econ. Theory, 112, 1, 157-172 (2003) · Zbl 1076.91023
[4] Abdulkadiroğlu, A.; Sönmez, T., Matching Markets: Theory and Practice (2010)
[5] Athanassoglou, S.; Sethuraman, J., House allocation with fractional endowments, Int. J. Game Theory, 40, 3, 481-513 (2011) · Zbl 1274.91328
[6] Arnsperger, C., Envy-freeness and distributive justice, J. Econ. Surv., 8, 2, 155-186 (1994)
[8] Aziz, H.; Gaspers, S.; Mackenzie, S.; Walsh, T., Fair assignment of indivisible objects under ordinal preferences, (Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems (May 2014), International Foundation for Autonomous Agents and Multiagent Systems), 1305-1312
[10] Bogomolnaia, A.; Moulin, H., A new solution to the probabilistic assignment problem, J. Econ. Theory, 100, 2, 295-328 (2001) · Zbl 1134.91357
[11] Budish, E.; Che, Y. K.; Kojima, F.; Milgrom, P., Designing random allocation mechanisms: theory and applications, Am. Econ. Rev., 103, 2, 585-623 (2013)
[12] Carroll, G., A general equivalence theorem for allocation of indivisible objects, J. Math. Econ., 51, 163-177 (2014), ISO 690 · Zbl 1296.91173
[13] Che, Y. K.; Kojima, F., Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78, 5, 1625-1672 (2010) · Zbl 1203.91201
[14] Chen, Y.; Sönmez, T., Improving efficiency of on-campus housing: an experimental study, Am. Econ. Rev., 1669-1686 (2002)
[15] Coles, P.; Cawley, J.; Levine, P. B.; Niederle, M.; Roth, A. E.; Siegfried, J., The job market for new economists: a market design perspective, J. Econ. Perspect., 24, 4, 187-206 (2010)
[17] Erdil, A., Strategy-proof stochastic assignment, J. Econ. Theory, 151, 146-162 (2014) · Zbl 1296.91174
[18] Foley, D. K., Resource allocation and the public sector, Yale Econ. Essays, 7, 1, 45-98 (1967), Spring 1967, 7 fig., 13 ref
[19] Gale, D., College Course Assignments and Optimal Lotteries (1987), University of California at Berkeley
[20] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 9-15 (1962) · Zbl 0109.24403
[21] Hashimoto, T.; Hirata, D.; Kesten, O.; Kurino, M.; Ünver, M. U., Two axiomatic approaches to the probabilistic serial mechanism, Theor. Econ., 9, 1, 253-277 (2014) · Zbl 1395.91264
[23] Horowitz, J. K.; McConnell, K. E., A review of WTA/WTP studies, J. Environ. Econ. Manag., 44, 3, 426-447 (2002) · Zbl 1032.91624
[24] Hylland, A.; Zeckhauser, R., The efficient allocation of individuals to positions, J. Polit. Econ., 87, 2, 293-314 (1979), ISO 690
[25] Kesten, O., Why do popular mechanisms lack efficiency in random environments?, J. Econ. Theory, 144, 5, 2209-2226 (2009) · Zbl 1195.91119
[27] Kesten, O.; Yazici, A., The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods, Econ. Theory, 50, 2, 463-488 (2012) · Zbl 1246.91033
[28] Knuth, D., An exact analysis of stable allocation, J. Algorithms, 20, 431-442 (1996) · Zbl 0852.68034
[29] Kojima, F.; Manea, M., Incentives in the probabilistic serial mechanism, J. Econ. Theory, 145, 1, 106-123 (2010) · Zbl 1202.91061
[33] Mennle, T.; Seuken, S., An Axiomatic Approach to Characterizing and Relaxing Strategyproofness of One-Sided Matching Mechanisms. Extended Abstract, (Proceedings of the Fifteenth ACM Conference on Economics and Computation (2014), ACM), 37-38
[34] Moulin, H., Cooperative Microeconomics: A Game-Theoretic Introduction (2014)
[35] Pathak, P. A.; Sethuraman, J., Lotteries in student assignment: an equivalence result, Theor. Econ., 6, 1, 1-17 (2011) · Zbl 1231.91360
[37] Pycia, M.; Ünver, M. U., Incentive compatible allocation and exchange of discrete resources, Theor. Econ., 12, 1, 287-329 (2017) · Zbl 1396.91327
[38] Roth, A. E., The evolution of the labor market for medical interns and residents: a case study in game theory, J. Polit. Econ., 991-1016 (1984)
[39] Roth, A. E.; Sönmez, T.; Utku Ünver, M., Kidney exchange, Q. J. Econ., 119, 2, 457-488 (2004) · Zbl 1064.92029
[40] Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 1, 23-37 (1974) · Zbl 0281.90014
[41] Thomson, W., Fair Allocation Rules, Handbook of Social Choice and Welfare, vol. 2, 393-506 (2007)
[42] Zhou, L., On a conjecture by Gale about one-sided matching problems, J. Econ. Theory, 52, 1, 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.