×

Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences. (English) Zbl 1396.91320

Summary: A fundamental resource allocation setting is the random assignment problem in which agents express preferences over objects that are then randomly allocated to the agents. In 2001, Bogomolnaia and Moulin presented the probabilistic serial (PS) mechanism that is an anonymous, Pareto optimal, and weak strategyproof mechanism when the preferences are considered with respect to stochastic dominance. The result holds when agents have strict preferences over individual objects. It has been an open problem whether there exists a mechanism that satisfies the same properties when agents may have indifference among the objects. We show that for this more general domain, there exists no extension of PS that is ex post efficient and weak strategyproof. The result is surprising because it does not even require additional symmetry or fairness conditions such as anonymity, neutrality, or equal treatment of equals. Our result further demonstrates that the lack of weak SD-strategyproofness of the extended PS mechanism of A.-K. Katta and J. Sethuraman [J. Econ. Theory 131, No. 1, 231–250 (2006; Zbl 1142.90481)] is not a design flaw but is due to an inherent incompatibility of efficiency and strategyproofness of PS in the full preference domain.

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
91B14 Social choice

Citations:

Zbl 1142.90481
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 3, 689-701, (1998) · Zbl 1019.91016
[2] Abdulkadiroğlu, A.; Sönmez, T., House allocation with existing tenants, Journal of Economic Theory, 88, 2, 233-260, (1999) · Zbl 0939.91068
[3] Abraham, D.J., Cechlárová, K., Manlove, D., Mehlhorn, K., 2005. Pareto optimality in house allocation problems. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science (LNCS), vol. 3341, pp. 1163-1175. · Zbl 1115.90049
[4] Aziz, H., Brandt, F., Brill, M., 2013b. On the tradeoff between economic efficiency and strategyproofness in randomized social choice. In: Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). IFAAMAS, pp. 455-462.
[5] Aziz, H.; Brandt, F.; Brill, M., The computational complexity of random serial dictatorship, Economics Letters, 121, 3, 341-345, (2013) · Zbl 1288.91060
[6] Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, Journal of Economic Theory, 100, 2, 295-328, (2001) · Zbl 1134.91357
[7] Bouveret, S., Endriss, U., Lang, J., 2010. Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods. In: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI). pp. 387-392. · Zbl 1211.68378
[8] Brandl, F.; Brandt, F.; Geist, C., Proving the incompatibility of efficiency and strategyproofness via SMT solving, (Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), (2016), AAAI Press), 116-122
[9] Brandl, F.; Brandt, F.; Suksompong, W., The impossibility of extending random dictatorship to weak preferences, Economics Letters, 141, 44-47, (2016) · Zbl 1396.91140
[10] Cho, W. J., Incentive properties for ordinal mechanisms, Games and Economic Behavior, 95, 168-177, (2015) · Zbl 1347.91170
[11] Eberl, M., 2016. A formal proof of the incompatibility of SD-efficiency and SD-strategy-proofness. Bachelor’s thesis, Technische Universität München.
[12] Gärdenfors, P., Assignment problem based on ordinal preferences, Management Science, 20, 331-340, (1973) · Zbl 0326.90006
[13] Gibbard, A., Straightforwardness of game forms with lotteries as outcomes, Econometrica, 46, 3, 595-614, (1978) · Zbl 0371.90128
[14] Katta, A.-K.; Sethuraman, J., A solution to the random assignment problem on the full preference domain, Journal of Economic Theory, 131, 1, 231-250, (2006) · Zbl 1142.90481
[15] Mennle, T.; Seuken, S., An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms, (Proceedings of the 15th ACM Conference on Economics and Computation (ACM-EC), (2014), ACM Press), 37-38
[16] Nesterov, A., 2016. Fairness and efficiency in strategy-proof object allocation mechanisms. · Zbl 1400.91261
[17] Svensson, L.-G., Queue allocation of indivisible goods, Social Choice and Welfare, 11, 323-330, (1994) · Zbl 0812.90034
[18] Svensson, L.-G., Strategy-proof allocation of indivisible goods, Social Choice and Welfare, 16, 4, 557-567, (1999) · Zbl 1066.91571
[19] Young, H. P., Dividing the indivisible, American Behavioral Scientist, 38, 904-920, (1995)
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.