Obviously Strategy-proof Implementation of Assignment Rules: A New Characterization

Mandal, Pinaki and Roy, Souvik (2020): Obviously Strategy-proof Implementation of Assignment Rules: A New Characterization.

Abstract

We consider assignment problems where individuals are to be assigned at most one indivisible object and monetary transfers are not allowed. We provide a characterization of assignment rules that are Pareto efficient, non-bossy, and implementable in obviously strategy-proof (OSP) mechanisms. As corollaries of our result, we obtain a characterization of OSP-implementable fixed priority top trading cycles (FPTTC) rules, hierarchical exchange rules, and trading cycles rules. Troyan (2019) provides a characterization of OSP-implementable FPTTC rules when there are equal number of individuals and objects. Our result generalizes this for arbitrary values of those.

• Item Type: MPRA Paper
• Language: English
• Keywords: Assignment problem; Obvious strategy-proofness; Pareto efficiency; Non-bossiness; Indivisible goods
• 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] Itai Ashlagi and Yannai A Gonczarowski. Stable matching mechanisms are not obviously strategy-proof. Journal of Economic Theory, 177:405–425, 2018.

[2] Sophie Bade and Yannai A Gonczarowski. Gibbard-satterthwaite success stories and obvious strategyproofness. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 565–565. ACM, 2017.

[3] Yan Chen and Tayfun Sonmez. School choice: an experimental study. Journal of Economic theory, 127(1):202–231, 2006.

[4] Avinatan Hassidim, Assaf Romm, and Ran I Shorrer. "strategic" behavior in a strategy-proof environment. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 763–764, 2016.

[5] Avinatan Hassidim, Deborah Marciano, Assaf Romm, and Ran I Shorrer. The mechanism is truthful, why aren't you? American Economic Review, 107(5):220–24, 2017.

[6] Shengwu Li. Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257–87, 2017.

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

[8] Marek Pycia and Peter Troyan. A theory of simplicity in games and mechanism design. Available at SSRN 2853563, 2019.

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

[10] Alex Rees-Jones. Suboptimal behavior in strategy-proof mechanisms: Evidence from the residency match. Games and Economic Behavior, 108:317–330, 2018.

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

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

[13] Ran I Shorrer and Sandor Sovago. Obvious mistakes in a strategically simple college admissions environment: Causes and consequences. Available at SSRN 2993538, 2018.

[14] Clayton Thomas. Classification of priorities such that deferred acceptance is obviously strategyproof. arXiv preprint arXiv:2011.12367, 2020.

[15] Peter Troyan. Obviously strategy-proof implementation of top trading cycles. International Economic Review, 60(3):1249–1261, 2019.