Comparing the Manipulability of Approval Voting and Borda

Authors

  • Daria Teplova ITMO University
  • Egor Ianovski HSE University

DOI:

https://doi.org/10.21638/11701/spbu31.2022.18

Abstract

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 Snmez (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 Snmez 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

Downloads

Download data is not yet available.
 

References

Aleskerov, F. and Kurbanov, E. (1999). Degree of manipulability of social choice procedures. In: Alkan A., Aliprantis, C. D. and Yannelis, N. C. (eds.). Current trends in economics, vol. 8, pp. 595–609. Springer: Berlin, Heidelberg

Arribillaga, R. P. and Mass, J. (2016). Comparing generalized median voter schemes according to their manipulability. Theoretical Economics, 11(2), 547–586

Arribillaga, R. P. and Mass, J. (2017). Comparing Voting by Committees According to Their Manipulability. American Economic Journal: Microeconomics, 9(4), 74–107

Barber, S., Sonnenschein, H. and Zhou, L. (1991). Voting by Committees. Econometrica, 59(3), 595–609

Bartholdi, J. J, Tovey, C. A. and Trick, M. A. (1989). The computational difficulty of manipulating an election. Social choice and Welfare, 6(3), 227–241

Bonkoungou, S. and Nesterov, A. (2021). Comparing school choice and college admissions mechanisms by their strategic accessibility. Theoretical Economics, 16(3), 881–909

Conitzer, V., Sandholm, T. and Lang, J. (2007). When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3), 14-es

Decerf, B. and Van der Linden, M. (2021). Manipulability in school choice. Journal of Economic Theory, 197

Dummett, M. and Farquharson, R. (1961). Stability in Voting. Econometrica, 29(1), 33–43

Elkind, E., Lackner, M. and Peters, D. (2017). Structured Preferences. In: Endriss, U. (ed.). Trends in Computational Social Choice, pp. 187–207

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

Gibbard, A. (1973). Manipulation of Voting Schemes: A General Result. Econometrica, 41(4), 587–601

Kelly, J. S. (1993). Almost all social choice rules are highly manipulable, but a few aren't. Social choice and Welfare, 10(2), 161–175

Moulin, H. (1980). On Strategy-Proofness and Single Peakedness. Public Choice, 35(4), 437–455

Nitzan, S. (1985). The vulnerability of point-voting schemes to preference variation and strategic manipulation. Public Choice, 47(2), 349–370

Pathak, P. A. and Snmez, T. (2013). School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation. American Economic Review, 103(1), 80–106

Satterthwaite, M. A. (1975). Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2), 187–217

Walsh, T. (2011). Is computational complexity a barrier to manipulation? Annals of Mathematics and Artificial Intelligence, 62(1–2), 7–26

Downloads

Published

2023-01-27

How to Cite

Teplova , D., & Ianovski , E. (2023). Comparing the Manipulability of Approval Voting and Borda. Contributions to Game Theory and Management, 15, 236–249. https://doi.org/10.21638/11701/spbu31.2022.18

Issue

Vol. 15 (2022)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.