On Swap Convexity of Voting Rules


  • Svetlana Obraztsova Nanyang Technological University
  • Edith Elkind University of Oxford
  • Piotr Faliszewski AGH University of Science and Technology




Obraztsova et al. (2013) have recently proposed an intriguing convexity axiom for voting rules. This axiom imposes conditions on the shape of the sets of elections with a given candidate as a winner. However, this new axiom is both too weak and too strong: it is too weak because it defines a set to be convex if for any two elements of the set some shortest path between them lies within the set, whereas the standard definition of convexity requires all shortest paths between two elements to lie within the set, and it is too strong because common voting rules do not satisfy this axiom. In this paper, we (1) propose several families of voting rules that are convex in the sense of Obraztsova et al.; (2) put forward a weaker notion of convexity that is satisfied by most common voting rules; (3) prove impossibility results for a variant of this definition that considers all, rather than some shortest paths.




How to Cite

Obraztsova, S., Elkind, E., & Faliszewski, P. (2020). On Swap Convexity of Voting Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1910-1917. https://doi.org/10.1609/aaai.v34i02.5560



AAAI Technical Track: Game Theory and Economic Paradigms