Abstract
We revisit the classical object reallocation problem under strict preferences. When attention is constrained to the set of Pareto-efficient rules, it is known that top trading cycles (TTC) is the only rule that is strategyproof and individually-rational. We relax this constraint and consider pair-efficiency. A rule is pair-efficient if it never induces an allocation at which a pair of agents gain from trading their assigned objects. Remarkably, even in the larger set of pair-efficient rules, we find that TTC is still the only rule that is strategyproof and individually-rational.
Pair-efficiency is a minimal efficiency notion, ruling out gainful trades between only pairs of agents. Individual-rationality is a minimal voluntary participation constraint, assuring agents only that they never receive objects worse than their endowments. Therefore, our characterization result, by showing that TTC is the only strategyproof rule satisfying these two minimal conditions, gives strong support to the use of TTC in object reallocation problems.
Our proof technique is based on a metric that measures the level of similarity of an arbitrary rule with TTC. We define our similarity metric by exploiting TTC's procedural nature. In future studies, we believe defining and working with similarity metrics, as done in our paper, can become functional when studying the properties of other procedural rules.
References
[1]
Atila Abdulkadiroglu and Tayfun Sönmez. 1998. Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems. Econometrica, Vol. 66, 3 (may 1998), 689. https://doi.org/10.2307/2998580
[2]
Atila Abdulkadiroglu and Tayfun Sönmez. 1999. House Allocation with Existing Tenants. Journal of Economic Theory, Vol. 88, 2 (1999), 233--260. https://doi.org/10.1006/jeth.1999.2553
[3]
Atila Abdulkadiroglu and Tayfun Sönmez. 2003. School choice: A mechanism design approach. American Economic Review (2003). https://doi.org/10.1257/000282803322157061
[4]
Hidekazu Anno. 2015. A short proof for the characterization of the core in housing markets. Economics Letters, Vol. 126 (jan 2015), 66--67. https://doi.org/10.1016/j.econlet.2014.11.019
[5]
Charles G. Bird. 1984. Group incentive compatibility in a market with indivisible goods. Economics Letters (1984). https://doi.org/10.1016/0165--1765(84)90003-X
[6]
Gabriel Carroll. 2014. A general equivalence theorem for allocation of indivisible objects. Journal of Mathematical Economics, Vol. 51, 1 (2014), 163--177. https://doi.org/10.1016/j.jmateco.2013.12.006
[7]
Özgün Ekici. 2013. Reclaim-proof allocation of indivisible objects. Games and Economic Behavior, Vol. 81 (sep 2013), 1--10. https://doi.org/10.1016/j.geb.2013.03.013
[8]
Özgün Ekici. 2020. Random mechanisms for house allocation with existing tenants. Journal of Mathematical Economics, Vol. 89, xxxx (aug 2020), 53--65. https://doi.org/10.1016/j.jmateco.2020.05.003
[9]
Yuji Fujinaka and Takuma Wakayama. 2018. Endowments-swapping-proof house allocation. Games and Economic Behavior, Vol. 111 (sep 2018), 187--202. https://doi.org/10.1016/j.geb.2018.05.004
[10]
Aanund Hylland and Richard Zeckhauser. 1979. The Efficient Allocation of Individuals to Positions. Journal of Political Economy, Vol. 87, 2 (apr 1979), 293--314. https://doi.org/10.1086/260757
[11]
Jinpeng Ma. 1994. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory, Vol. 23, 1 (mar 1994), 75--83. https://doi.org/10.1007/BF01242849
[12]
Eiichi Miyagawa. 2002. Strategy-Proofness and the Core in House Allocation Problems. Games and Economic Behavior, Vol. 38, 2 (feb 2002), 347--361. https://doi.org/10.1006/game.2001.0858
[13]
Thayer Morrill. 2013. An alternative characterization of top trading cycles. Economic Theory, Vol. 54, 1 (sep 2013), 181--197. https://doi.org/10.1007/s00199-012-0713--3
[14]
Szilvia Papai. 2000. Strategyproof Assignment by Hierarchical Exchange. Econometrica, Vol. 68, 6 (nov 2000), 1403--1433. https://doi.org/10.1111/1468-0262.00166
[15]
Parag A. Pathak and Jay Sethuraman. 2011. Lotteries in student assignment: An equivalence result. Theoretical Economics (2011). https://doi.org/10.3982/te816
[16]
Marek Pycia and M. UtkuÜnver. 2017. Incentive compatible allocation and exchange of discrete resources. Theoretical Economics, Vol. 12, 1 (jan 2017), 287--329. https://doi.org/10.3982/TE2201
[17]
Alvin E. Roth. 1982. Incentive compatibility in a market with indivisible goods. Economics Letters, Vol. 9, 2 (jan 1982), 127--132. https://doi.org/10.1016/0165--1765(82)90003--9
[18]
Alvin E. Roth and Andrew Postlewaite. 1977. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, Vol. 4, 2 (aug 1977), 131--137. https://doi.org/10.1016/0304--4068(77)90004-0
[19]
Alvin E. Roth, T. Sonmez, and M. U. Unver. 2004. Kidney Exchange. The Quarterly Journal of Economics, Vol. 119, 2 (may 2004), 457--488. https://doi.org/10.1162/0033553041382157
[20]
Mark A. Satterthwaite and Hugo Sonnenschein. 1981. Strategy-Proof Allocation Mechanisms at Differentiable Points. The Review of Economic Studies, Vol. 48, 4 (oct 1981), 587. https://doi.org/10.2307/2297198
[21]
James Schummer and Rakesh V. Vohra. 2013. Assignment of arrival slots. American Economic Journal: Microeconomics (2013). https://doi.org/10.1257/mic.5.2.164
[22]
Jay Sethuraman. 2016. An alternative proof of a characterization of the TTC mechanism. Operations Research Letters, Vol. 44, 1 (jan 2016), 107--108. https://doi.org/10.1016/j.orl.2015.11.010
[23]
Lloyd Shapley and Herbert Scarf. 1974. On cores and indivisibility. Journal of Mathematical Economics, Vol. 1, 1 (mar 1974), 23--37. https://doi.org/10.1016/0304--4068(74)90033-0
[24]
Tayfun Sönmez and M. UtkuÜnver. 2010. House allocation with existing tenants: A characterization. Games and Economic Behavior, Vol. 69, 2 (jul 2010), 425--445. https://doi.org/10.1016/j.geb.2009.10.010
[25]
Tayfun Sönmez and M. UtkuÜnver. 2005. House allocation with existing tenants: an equivalence. Games and Economic Behavior, Vol. 52, 1 (jul 2005), 153--185. https://doi.org/10.1016/j.geb.2004.04.008
[26]
Lars Gunnar Svensson. 1994. Queue allocation of indivisible goods. Social Choice and Welfare (1994). https://doi.org/10.1007/BF00183301
[27]
Lars-Gunnar Svensson. 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, Vol. 16, 4 (sep 1999), 557--567. https://doi.org/10.1007/s003550050160
[28]
Koji Takamiya. 2001. Coalition strategy-proofness and monotonicity in Shapley--Scarf housing markets. Mathematical Social Sciences, Vol. 41, 2 (mar 2001), 201--213. https://doi.org/10.1016/S0165--4896(00)00062--7
Index Terms
- Pair-efficient Reallocation of Indivisible Objects
Recommendations
PPS: Privacy-Preserving Strategyproof Social-Efficient Spectrum Auction Mechanisms
Many spectrum auction mechanisms have been proposed for spectrum allocation problem, and unfortunately, few of them protect the bid privacy of bidders and achieve good social efficiency. In this paper, we propose PPS, a Privacy Preserving Strategyproof ...
Reallocation mechanisms
EC '14: Proceedings of the fifteenth ACM conference on Economics and computationWe consider reallocation problems in settings where the initial endowment of each agent consists of a subset of the resources. The private information of the players is their value for every possible subset of the resources. The goal is to redistribute ...
Approximately-strategyproof and tractable multiunit auctions
Special issue: The fourth ACM conference on electronic commerceWe present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multiunit allocation problem. The bidding language allows marginal-decreasing piecewise-constant curves and quantity-based side constraints. We ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
1269 pages
ISBN:9781450391504
DOI:10.1145/3490486
- General Chair:
- David M. Pennock,
- Program Chairs:
- Ilya Segal,
- Sven Seuken
Copyright © 2022 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2022
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
EC '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Upcoming Conference
EC '25
- Sponsor:
- sigecom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 44Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in