Strategy-proof Allocation of Indivisible Goods when Preferences are Single-peaked

Mandal, Pinaki and Roy, Souvik (2021): Strategy-proof Allocation of Indivisible Goods when Preferences are Single-peaked.

Abstract

We consider assignment problems where heterogeneous indivisible goods are to be assigned to individuals so that each individual receives at most one good. Individuals have single-peaked preferences over the goods. In this setting, first we show that there is no strategy-proof, non-bossy, Pareto efficient, and strongly pairwise reallocation-proof assignment rule on a minimally rich single-peaked domain when there are at least three individuals and at least three objects in the market. Next, we characterize all strategy-proof, Pareto efficient, top-envy-proof, non-bossy, and pairwise reallocation-proof assignment rules on a minimally rich single-peaked domain as hierarchical exchange rules. We additionally show that strategy-proofness and non-bossiness together are equivalent to group strategy-proofness on a minimally rich single-peaked domain, and every hierarchical exchange rule satisfies group-wise reallocation-proofness on a minimally rich single-peaked domain.

• Item Type: MPRA Paper
• Language: English
• Keywords: Assignment problem; Single-peaked preferences; Strategy-proofness; Pareto efficiency; Non-bossiness; Top-envy-proofness; Strong reallocation-proofness; Pairwise/group-wise reallocation-proofness
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design

References

[1] Sophie Bade. Matching with single-peaked preferences. Journal of Economic Theory, 180:81–99, 2019.

[2] Anastasia Damamme, Aurelie Beynier, Yann Chevaleyre, and Nicolas Maudet. The power of swap deals in distributed resource allocation. 2015.

[3] Lars Ehlers and Bettina Klaus. Efficient priority rules. Games and Economic Behavior, 55(2):372–384, 2006.

[4] Lars Ehlers and Bettina Klaus. Consistent house allocation. Economic Theory, 30(3):561–574, 2007.

[5] Haluk I Ergin. Consistency in house allocation problems. Journal of mathematical economics, 34(1):77–97, 2000.

[6] Mehmet Karakaya, Bettina Klaus, and Jan Christoph Schlegel. Top trading cycles, consistency, and acyclic priorities for house allocation with existing tenants. Journal of Economic Theory, 184:104948, 2019.

[7] Pinaki Mandal and Souvik Roy. Obviously strategy-proof implementation of assignment rules: A new characterization. 2020.

[8] Szilvia Papai. Strategyproof assignment by hierarchical exchange. Econometrica, 68(6):1403–1433, 2000.

[9] Marek Pycia and M Utku Unver. Incentive compatible allocation and exchange of discrete resources. Theoretical Economics, 12(1):287–329, 2017.

[10] Mark A Satterthwaite and Hugo Sonnenschein. Strategy-proof allocation mechanisms at differentiable points. The Review of Economic Studies, 48(4):587–597, 1981.

[11] Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of mathematical economics, 1(1):23–37, 1974.

[12] Lars-Gunnar Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4):557–567, 1999.

[13] Rodrigo A Velez. Consistent strategy-proof assignment by hierarchical exchange. Economic Theory, 56(1):125–156, 2014.