Geodesic
Comparing the manipulability of approval voting and borda
Contributions to game theory and management, Tome 15 (2022), pp. 236-249.

Voir la notice de l'article provenant de la source Math-Net.Ru

The Gibbard-Satterthwaite theorem established that no non-trivial voting rule is strategy-proof, but that does not mean that all voting rules are equally susceptible to strategic manipulation. Over the past fifty years numerous approaches have been proposed to compare the manipulability of voting rules in terms of the probability of manipulation, the domains on which manipulation is possible, the complexity of finding such a manipulation, and others. In the closely related field of matching, Pathak and Sönmez (2013) pioneered a notion of manipulability based on case-by-case comparison of manipulable profiles. The advantage of this approach is that it is independent of the underlying statistical culture or the computational power of the agents, and it has proven fruitful in the matching literature. In this paper, we extend the notion of Pathak and Sönmez to voting, studying the families of $k$-approval and truncated Borda scoring rules. We find that, with one exception, the notion does not allow for a meaningful ordering of the manipulability of these rules.
Keywords: social choice, strategic voting, Borda, scoring rules. 
@article{CGTM_2022_15_a18,
     author = {Daria Teplova and Egor Ianovski},
     title = {Comparing the manipulability of approval voting and borda},
     journal = {Contributions to game theory and management},
     pages = {236--249},
     publisher = {mathdoc},
     volume = {15},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2022_15_a18/}
}
TY  - JOUR
AU  - Daria Teplova
AU  - Egor Ianovski
TI  - Comparing the manipulability of approval voting and borda
JO  - Contributions to game theory and management
PY  - 2022
SP  - 236
EP  - 249
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2022_15_a18/
LA  - en
ID  - CGTM_2022_15_a18
ER  - 
%0 Journal Article
%A Daria Teplova
%A Egor Ianovski
%T Comparing the manipulability of approval voting and borda
%J Contributions to game theory and management
%D 2022
%P 236-249
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2022_15_a18/
%G en
%F CGTM_2022_15_a18
Daria Teplova; Egor Ianovski. Comparing the manipulability of approval voting and borda. Contributions to game theory and management, Tome 15 (2022), pp. 236-249. http://geodesic.mathdoc.fr/item/CGTM_2022_15_a18/

[1] Aleskerov, F. and Kurbanov, E., “Degree of manipulability of social choice procedures”, Current trends in economics, 8, eds. Alkan A., Aliprantis, C. D. and Yannelis, N. C., Springer, Berlin–Heidelberg, 1999, 595–609

[2] Arribillaga, R. P. and Massó, J., “Comparing generalized median voter schemes according to their manipulability”, Theoretical Economics, 11:2 (2016), 547–586 | DOI | MR | Zbl

[3] Arribillaga, R. P. and Massó, J., “Comparing Voting by Committees According to Their Manipulability”, American Economic Journal: Microeconomics, 9:4 (2017), 74–107 | DOI

[4] Barberà, S., Sonnenschein, H. and Zhou, L., “Voting by Committees”, Econometrica, 59:3 (1991), 595–609 | DOI | MR | Zbl

[5] Bartholdi, J. J, Tovey, C. A. and Trick, M. A., “The computational difficulty of manipulating an election”, Social choice and Welfare, 6:3 (1989), 227–241 | DOI | MR | Zbl

[6] Bonkoungou, S. and Nesterov, A., “Comparing school choice and college admissions mechanisms by their strategic accessibility”, Theoretical Economics, 16:3 (2021), 881–909 | DOI | MR | Zbl

[7] Conitzer, V., Sandholm, T. and Lang, J., When are elections with few candidates hard to manipulate?, Journal of the ACM, 54:3 (2007), 14–es | DOI | MR

[8] Decerf, B. and Van der Linden, M., “Manipulability in school choice”, Journal of Economic Theory, 197 (2021) | DOI | MR | Zbl

[9] Dummett, M. and Farquharson, R., “Stability in Voting”, Econometrica, 29:1 (1961), 33–43 | DOI | MR | Zbl

[10] Elkind, E., Lackner, M. and Peters, D., “Structured Preferences”, Trends in Computational Social Choice, ed. Endriss, U., 2017, 187–207 | MR

[11] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L. A. and Rothe, J., “The shield that never was: Societies with single-peaked preferences are more open to manipulation and control”, Information and Computation, 209:2 (2011), 89–107 | DOI | MR | Zbl

[12] Gibbard, A., “Manipulation of Voting Schemes: A General Result”, Econometrica, 41:4 (1973), 587–601 | DOI | MR | Zbl

[13] Kelly, J. S., “Almost all social choice rules are highly manipulable, but a few aren't”, Social choice and Welfare, 10:2 (1993), 161–175 | DOI | MR | Zbl

[14] Moulin, H., “On Strategy-Proofness and Single Peakedness”, Public Choice, 35:4 (1980), 437–455 | DOI

[15] Nitzanà, S., “The vulnerability of point-voting schemes to preference variation and strategic manipulation”, Public Choice, 47:2 (1985), 349–370 | DOI

[16] Pathak, P. A. and Sönmez, T., “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation”, American Economic Review, 103:1 (2013), 80–106 | DOI

[17] Satterthwaite, M. A., “Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions”, Journal of Economic Theory, 10:2 (1975), 187–217 | DOI | MR | Zbl

[18] Walsh, T., Is computational complexity a barrier to manipulation?, Annals of Mathematics and Artificial Intelligence, 62:1–2 (2011), 7–26 | DOI | MR | Zbl