On the equivalence of strategy-proofness and upper contour strategy-proofness for randomized social choice functions

Roy, Souvik and Sadhukhan, Soumyarup (2020): On the equivalence of strategy-proofness and upper contour strategy-proofness for randomized social choice functions.

Abstract

We consider a weaker notion of strategy-proofness called upper contour strategy-proofness (UCSP) and investigate its relation with strategy-proofness (SP) for random social choice functions (RSCFs). Apart from providing a simpler way to check whether a given RSCF is SP or not, UCSP is useful in modeling the incentive structures for certain behavioral agents. We show that SP is equivalent to UCSP and elementary monotonicity on any domain satisfying the upper contour no restoration (UCNR) property. To analyze UCSP on multi-dimensional domains, we consider some block structure over the preferences. We show that SP is equivalent to UCSP and block monotonicity on domains satisfying the block restricted upper contour preservation property. Next, we analyze the relation between SP and UCSP under unanimity and show that SP becomes equivalent to UCSP and multi-swap monotonicity on any domain satisfying the multi-swap UCNR property. Finally, we show that if there are two agents, then under unanimity, UCSP alone becomes equivalent to SP on any domain satisfying the swap UCNR property. We provide applications of our results on the unrestricted, single-peaked, single-crossing, single-dipped, hybrid, and multi-dimensional domains such as lexicographically separable domains with one component ordering and domains under committee formation.

• Item Type: MPRA Paper
• Language: English
• Keywords: strategy-proofness; upper contour strategy-proofness; unanimity; elementary monotonicity; block monotonicity; multi-swap monotonicity
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D81 - Criteria for Decision-Making under Risk and Uncertainty

References

[1] Gabriel Carroll. When are local incentive constraints sufficient? Econometrica, 80 (2):661–686, 2012.

[2] Shurojit Chatterji and Huaxia Zeng. On random social choice functions with the tops-only property. Games and Economic Behavior, 109:413–435, 2018.

[3] Shurojit Chatterji, Souvik Roy, Soumyarup Sadhukhan, Arunava Sen, and Huaxia Zeng. Restricted probabilistic fixed ballot rules and hybrid domains. 2020.

[4] Wonki Jo Cho. Incentive properties for ordinal mechanisms. Games and Economic Behavior, 95:168–177, 2016.

[5] Youngsub Chun and Kiyong Yun. Upper-contour strategy-proofness in the probabilistic assignment problem. Social Choice and Welfare, pages 1–21, 2019.

[6] Bhaskar Dutta, Hans Peters, and Arunava Sen. Strategy-proof probabilistic mecha- nisms in economies with pure public goods. Journal of Economic Theory, 106(2): 392–416, 2002.

[7] Lars Ehlers, Hans Peters, and Ton Storcken. Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences. Journal of Economic Theory, 105(2):408–434, 2002.

[8] Allan Gibbard. Manipulation of schemes that mix voting with chance. Econometrica: Journal of the Econometric Society, pages 665–681, 1977.

[9] Jean-Michel Grandmont. Intermediate preferences and the majority rule. Econometrica: Journal of the Econometric Society, pages 317–330, 1978.

[10] Ujjwal Kumar, Souvik Roy, Arunava Sen, Sonal Yadav, and Huaxia Zeng. Local global equivalence in voting models: A characterization and applications. 2020. URL https: //docs.google.com/viewer?a=v&pid=sites&srcid= ZGVmYXVsdGRvbWFpbnxodWF4aWF6ZW5nfGd4OmExOTBmZWRmZmIxZTI5Nw.

[11] Dipjyoti Majumdar and Arunava Sen. Ordinally bayesian incentive compatible voting rules. Econometrica, 72(2):523–540, 2004.

[12] Debasis Mishra. Ordinal bayesian incentive compatibility in restricted domains. Journal of Economic Theory, 163:925–954, 2016.

[13] Hans Peters, Souvik Roy, Arunava Sen, and Ton Storcken. Probabilistic strategy- proof rules over single-peaked domains. Journal of Mathematical Economics, 52: 123–127, 2014.

[14] Hans Peters, Souvik Roy, Soumyarup Sadhukhan, and Ton Storcken. An extreme point characterization of strategy-proof and unanimous probabilistic rules over binary restricted domains. Journal of Mathematical Economics, 69:84–90, 2017.

[15] Hans Peters, Souvik Roy, and Soumyarup Sadhukhan. Unanimous and strategy-proof probabilistic rules for single-peaked preference profiles on graphs. Accepted in Mathematics of Operations Research, 2020.

[16] Marek Pycia and M Utku Unver. Decomposing random mechanisms. Journal of Mathematical Economics, 61:21–33, 2015.

[17] Souvik Roy and Soumyarup Sadhukhan. A characterization of random min–max domains and its applications. Economic Theory, 68(4):887–906, 2019.

[18] Souvik Roy and Soumyarup Sadhukhan. A unified characterization of randomized strategy-proof rules. ISI working paper, 2020.

[19] Alejandro Saporiti. Strategy-proofness and single-crossing. Theoretical Economics, 4(2):127–163, 2009.

[20] Shin Sato. A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one. Journal of Economic Theory, 148(1):259–278, 2013.