Preserving Condorcet Winners under Strategic Manipulation

Authors

  • Sirin Botan University of Amsterdam
  • Ulle Endriss University of Amsterdam

Keywords:

Social Choice / Voting

Abstract

Condorcet extensions have long held a prominent place in social choice theory. A Condorcet extension will return the Condorcet winner as the unique winner whenever such an alternative exists. However, the definition of a Condorcet extension does not take into account possible manipulation by the voters. A profile where all agents vote truthfully may have a Condorcet winner, but this alternative may not end up in the set of winners if agents are acting strategically. Focusing on the class of tournament solutions, we show that many natural social choice functions in this class, such as the well-known Copeland and Slater rules, cannot guarantee the preservation of Condorcet winners when agents behave strategically. Our main result in this respect is an impossibility theorem that establishes that no tournament solution satisfying a very weak decisiveness requirement can provide such a guarantee. On the bright side, we identify several indecisive but otherwise attractive tournament solutions that do guarantee the preservation of Condorcet winners under strategic manipulation for a large class of preference extensions.

Downloads

Published

2021-05-18

How to Cite

Botan, S., & Endriss, U. (2021). Preserving Condorcet Winners under Strategic Manipulation. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5202-5210. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16657

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms