Strategy-proof and envy-free mechanisms for house allocation. (English) Zbl 1530.91253
Summary: We consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. There are inherent trade-offs between competing notions of efficiency, fairness and incentives in such assignment mechanisms. It is, therefore, natural to consider mechanisms that satisfy two of these three properties in their strongest notions, while trying to improve on the third dimension. In this paper, we are motivated by the following question: Is there a strategy-proof and envy-free random assignment mechanism more efficient than equal division?
Our contributions in this paper are twofold. First, we further explore the incompatibility between efficiency, fairness, and strategy-proofness within random assignment mechanisms. We define a new notion of efficiency that is weaker than ex-post efficiency and prove that any strategy-proof and envy-free mechanism must sacrifice efficiency even in this very weak sense. Next, we introduce a new family of mechanisms called rank exchange mechanisms that are strategy-proof and envy-free and stochastically dominate equal division. Further, we show that rank exchange mechanisms characterize the set of neutral, strategy-proof, and envy-free mechanisms that also satisfy a natural separability axiom that may be of independent interest.
Our contributions in this paper are twofold. First, we further explore the incompatibility between efficiency, fairness, and strategy-proofness within random assignment mechanisms. We define a new notion of efficiency that is weaker than ex-post efficiency and prove that any strategy-proof and envy-free mechanism must sacrifice efficiency even in this very weak sense. Next, we introduce a new family of mechanisms called rank exchange mechanisms that are strategy-proof and envy-free and stochastically dominate equal division. Further, we show that rank exchange mechanisms characterize the set of neutral, strategy-proof, and envy-free mechanisms that also satisfy a natural separability axiom that may be of independent interest.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
References:
| [1] | Abdulkadiroğlu, Atila; Sönmez, Tayfun, 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, Atila; Sönmez, Tayfun, School choice: a mechanism design approach, Am. Econ. Rev., 93, 3, 729-747 (2003) |
| [3] | Azevedo, Eduardo M.; Budish, Eric, Strategy-proofness in the large, Rev. Econ. Stud., 86, 1, 81-116 (2019) · Zbl 1409.91115 |
| [4] | Bade, Sophie, Fairness and group-strategyproofness clash in assignment problems, J. Econ. Theory, 165, 257-262 (2016) · Zbl 1371.91116 |
| [5] | Basteck, Christian, Fair solutions to the random assignment problem, J. Math. Econ., 79, 163-172 (2018) · Zbl 1418.91262 |
| [6] | Basteck, Christian; Ehlers, Lars, Strategy-proof and envy-free random assignment, J. Econ. Theory, 209, Article 105618 pp. (2023) · Zbl 1518.91097 |
| [7] | Birkhoff, Garrett, Three observations on linear algebra, Univ. Nac. Tacuman, Rev. Ser. A, 5, 147-151 (1946) · Zbl 0060.07906 |
| [8] | Bogomolnaia, Anna; Heo, Eun Jeong, Probabilistic assignment of objects: characterizing the serial rule, J. Econ. Theory, 147, 5, 2072-2082 (2012) · Zbl 1247.91089 |
| [9] | Bogomolnaia, Anna; Moulin, Hervé, A new solution to the random assignment problem, J. Econ. Theory, 100, 2, 295-328 (2001) · Zbl 1134.91357 |
| [10] | Budish, Eric, The combinatorial assignment problem: approximate competitive equilibrium from equal incomes, J. Polit. Econ., 119, 6, 1061-1103 (2011) |
| [11] | Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul, Designing random allocation mechanisms: theory and applications, Am. Econ. Rev., 103, 2, 585-623 (2013) |
| [12] | Chambers, Christopher P., Consistency in the probabilistic assignment model, J. Math. Econ., 40, 8, 953-962 (2004) · Zbl 1117.90319 |
| [13] | Che, Yeon-Koo; Kojima, Fuhito, Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78, 5, 1625-1672 (2010) · Zbl 1203.91201 |
| [14] | Chen, Yan; Sönmez, Tayfun, Improving efficiency of on-campus housing: an experimental study, Am. Econ. Rev., 92, 5, 1669-1686 (2002) |
| [15] | Foley, Duncan K., Resource allocation and the public sector, Yale Econ. Essays, 7, 1, 45-98 (1967) |
| [16] | Gale, David, College Course Assignments and Optimal Lotteries (1987), University of California at Berkeley |
| [17] | Harless, Patrick, Efficient rules for probabilistic assignment, J. Math. Econ., 84, 107-116 (2019) · Zbl 1427.91180 |
| [18] | Harless, Patrick; Phan, William, Efficient mixtures of priority rules for assigning objects, Games Econ. Behav., 132, 73-89 (2022) · Zbl 1483.91103 |
| [19] | Hashimoto, Tadashi; Hirata, Daisuke; Kesten, Onur; Kurino, Morimitsu; Ünver, M. Utku, Two axiomatic approaches to the probabilistic serial mechanism, Theor. Econ., 9, 1, 253-277 (2014) · Zbl 1395.91264 |
| [20] | Heo, Eun Jeong, The extended serial correspondence on a rich preference domain, Int. J. Game Theory, 43, 2, 439-454 (2014) · Zbl 1307.91104 |
| [21] | Heo, Eun Jeong, Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization, J. Math. Econ., 54, 40-47 (2014) · Zbl 1308.91095 |
| [22] | Heo, Eun Jeong; Yılmaz, Özgür, A characterization of the extended serial correspondence, J. Math. Econ., 59, 102-110 (2015) · Zbl 1320.91099 |
| [23] | Hylland, Aanund; Zeckhauser, Richard, The efficient allocation of individuals to positions, J. Polit. Econ., 87, 2, 293-314 (1979) · Zbl 0448.62088 |
| [24] | Jackson, Matthew O.; Kremer, Ilan, Envy-freeness and implementation in large economies, Rev. Econ. Des., 11, 3, 185-198 (2007) · Zbl 1136.91515 |
| [25] | Kesten, Onur, Why do popular mechanisms lack efficiency in random environments?, J. Econ. Theory, 144, 5, 2209-2226 (2009) · Zbl 1195.91119 |
| [26] | Kesten, Onur; Kurino, Morimitsu; Nesterov, Alexander S., Efficient lottery design, Soc. Choice Welf., 48, 1, 31-57 (2017) · Zbl 1392.91130 |
| [27] | Kojima, Fuhito; Manea, Mihai, Incentives in the probabilistic serial mechanism, J. Econ. Theory, 145, 1, 106-123 (2010) · Zbl 1202.91061 |
| [28] | Liu, Qingmin; Pycia, Marek, Ordinal efficiency, fairness, and incentives in large markets, (Fairness, and Incentives in Large Markets. Fairness, and Incentives in Large Markets, 2016, August 1 (2016)) |
| [29] | Martini, Giorgio, Strategy-proof and fair assignment is wasteful, Games Econ. Behav., 98, 172-179 (2016) · Zbl 1394.91251 |
| [30] | Mennle, Timo; Seuken, Sven, An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms, (Proceedings of the Fifteenth ACM Conference on Economics and Computation (2014)), 37-38 |
| [31] | Mennle, Timo; Seuken, Sven, Partial strategyproofness: relaxing strategyproofness for the random assignment problem, J. Econ. Theory, 191, Article 105144 pp. (2021) · Zbl 1458.91110 |
| [32] | Moulin, Hervé, Fair division in the Internet age, Annu. Rev. Econ., 11, 407-441 (2019) |
| [33] | Muller, Eitan; Satterthwaite, Mark A., The equivalence of strong positive association and strategy-proofness, J. Econ. Theory, 14, 2, 412-418 (1977) · Zbl 0402.90004 |
| [34] | Nesterov, Alexander S., Fairness and efficiency in strategy-proof object allocation mechanisms, J. Econ. Theory, 170, 145-168 (2017) · Zbl 1400.91261 |
| [35] | Noda, Shunya, Large matchings in large markets with flexible supply (2018), Available at SSRN 3215670 |
| [36] | Pápai, Szilvia, Strategyproof assignment by hierarchical exchange, Econometrica, 68, 6, 1403-1433 (2000) · Zbl 1023.91019 |
| [37] | Pycia, Marek; Ünver, M. Utku, Incentive compatible allocation and exchange of discrete resources, Theor. Econ., 12, 1, 287-329 (2017) · Zbl 1396.91327 |
| [38] | Robertson, Jack; Webb, William, Cake-Cutting Algorithms: Be Fair If You Can (1998), AK Peters/CRC Press · Zbl 0939.91001 |
| [39] | Roth, Alvin E.; Sönmez, Tayfun; Ünver, M. Utku, Pairwise kidney exchange, J. Econ. Theory, 125, 2, 151-188 (2005) · Zbl 1081.92023 |
| [40] | Satterthwaite, Mark A.; Sonnenschein, Hugo, Strategy-proof allocation mechanisms at differentiable points, Rev. Econ. Stud., 48, 4, 587-597 (1981) · Zbl 0476.90003 |
| [41] | Shapley, Lloyd; Scarf, Herbert, On cores and indivisibility, J. Math. Econ., 1, 1, 23-37 (1974) · Zbl 0281.90014 |
| [42] | Edward Su, Francis, Rental harmony: Sperner’s lemma in fair division, Am. Math. Mon., 106, 10, 930-942 (1999) · Zbl 1010.05077 |
| [43] | Svensson, Lars-Gunnar, Queue allocation of indivisible goods, Soc. Choice Welf., 11, 4, 323-330 (1994) · Zbl 0812.90034 |
| [44] | Svensson, Lars-Gunnar, Strategy-proof allocation of indivisible goods, Soc. Choice Welf., 16, 4, 557-567 (1999) · Zbl 1066.91571 |
| [45] | von Neumann, John, A certain zero-sum two-person game equivalent to the optimal assignment problem, (Contributions to the Theory of Games, vol. 2 (1953)), 5-12 · Zbl 0050.14105 |
| [46] | Zhang, Jun, Efficient and fair assignment mechanisms are strongly group manipulable, J. Econ. Theory, 180, 167-177 (2019) · Zbl 1419.91403 |
| [47] | Zhou, Lin, 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.
