Strategy-proof stochastic assignment.(English)Zbl 1296.91174
Summary: I study strategy-proof assignment mechanisms where the agents reveal their preference rankings over the available objects. A stochastic mechanism returns lotteries over deterministic assignments, and mechanisms are compared according to first-order stochastic dominance.
I show that non-wasteful strategy-proof mechanisms are not dominated by strategy-proof mechanisms, however non-wastefulness is highly restrictive when the mechanism involves randomization. In fact, the Random Priority mechanism (i.e., the Random Serial Dictatorship), and a recently adopted school choice mechanism, Deferred Acceptance with Random Tie-breaking, are wasteful. I find that both these mechanisms are dominated by strategy-proof mechanisms.
In general, strategy-proof improvement cannot be due to merely reshuffling objects, and therefore must involve assigning more objects.
I show that non-wasteful strategy-proof mechanisms are not dominated by strategy-proof mechanisms, however non-wastefulness is highly restrictive when the mechanism involves randomization. In fact, the Random Priority mechanism (i.e., the Random Serial Dictatorship), and a recently adopted school choice mechanism, Deferred Acceptance with Random Tie-breaking, are wasteful. I find that both these mechanisms are dominated by strategy-proof mechanisms.
In general, strategy-proof improvement cannot be due to merely reshuffling objects, and therefore must involve assigning more objects.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
| 91B68 | Matching models |
Keywords:
random assignment;strategy-proofness;priority based assignment;ordinal efficiency;school choiceCite
References:
| [1] | Abdulkadiroğlu, A.; Pathak, P.; Roth, A., Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match, Amer. Econ. Rev., 99, 1954-1978 (2009) |
| [2] | 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 |
| [3] | Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) ·Zbl 1134.91357 |
| [4] | Bogomolnaia, A.; Moulin, H., Random matching under dichotomous preferences, Econometrica, 72, 1, 257-279 (2004) ·Zbl 1142.91691 |
| [5] | Carroll, G., A general equivalence theorem for allocation of indivisible objects (2013), Stanford University, Mimeo |
| [6] | Che, Y.-K.; Kojima, F., Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78, 5, 1625-1672 (2010) ·Zbl 1203.91201 |
| [7] | Dubins, L.; Freedman, D., Machiavelli and the Gale-Shapley algorithm, Amer. Math. Monthly, 88, 485-494 (1981) ·Zbl 0449.92024 |
| [8] | Ehlers, L., Respecting priorities when assigning students to schools (2006), University of Montreal, Mimeo |
| [9] | Ehlers, L.; Erdil, A., Efficient assignment respecting priorities, J. Econ. Theory, 145, 1269-1282 (2010) ·Zbl 1245.91046 |
| [10] | Erdil, A.; Ergin, H., What’s the matter with tie-breaking? Improving efficiency in school choice, Amer. Econ. Rev., 98, 3, 669-689 (2008) |
| [11] | Ergin, H., Efficient resource allocation on the basis of priorities, Econometrica, 70, 2489-2497 (2002) ·Zbl 1141.91563 |
| [12] | Gale, D.; Shapley, L., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) ·Zbl 0109.24403 |
| [13] | Holmström, B.; Myerson, R., Efficient and durable decision rules with incomplete information, Econometrica, 51, 6, 1799-1819 (1983) ·Zbl 0521.90008 |
| [14] | Kesten, O., School choice with consent, Quart. J. Econ., 125, 1297-1348 (2010) ·Zbl 1197.91153 |
| [15] | Kesten, O.; Kurino, M., On the (im)possibility of improving upon the student-proposing deferred acceptance mechanism (2012), WZB Discussion Paper |
| [16] | Kesten, O.; Ünver, U., A theory of school-choice lotteries (2012), Carnegie Mellon University and Boston College, Mimeo |
| [17] | Kojima, F.; Manea, M., Incentives in probabilistic serial mechanism, J. Econ. Theory, 145, 106-123 (2010) ·Zbl 1202.91061 |
| [18] | Liu, Q.; Pycia, M., Ordinal efficiency, fairness, and incentives in large markets (2013), Columbia University and UCLA, Mimeo |
| [19] | Pathak, P.; Sethuraman, J., Lotteries in student assignment: An equivalence result, Theoretical Econ., 6, 1-17 (2011) ·Zbl 1231.91360 |
| [20] | Peters, H.; Roy, S.; Sen, A.; Storcken, T., Probabilistic strategy-proof rules over single-peaked domains (2013), Maastricht and Indian Statistical Institute: Maastricht and Indian Statistical Institute New Delhi, Mimeo |
| [21] | Pycia, M.; Ünver, U., Decomposing random mechanisms (2012), UCLA and Boston College, Mimeo ·Zbl 1368.91110 |
| [22] | Roth, A., The economics of matching: Stability and incentives, Math. Operations Res., 7, 617-628 (1982) ·Zbl 0496.90008 |
| [23] | Zhou, L., On a conjecture by gale about one-sided matching problems, J. Econ. Theory, 52, 125-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.
