Strategyproofness and Proportionality in Party-Approval Multiwinner Elections

Authors

  • Théo Delemazure Paris Dauphine University
  • Tom Demeulemeester KU Leuven
  • Manuel Eberl University of Innsbruck
  • Jonas Israel Technische Universität Berlin
  • Patrick Lederer Technische Universität München

DOI:

https://doi.org/10.1609/aaai.v37i5.25694

Keywords:

GTEP: Social Choice / Voting

Abstract

In party-approval multiwinner elections the goal is to allocate the seats of a fixed-size committee to parties based on the approval ballots of the voters over the parties. In particular, each voter can approve multiple parties and each party can be assigned multiple seats. Two central requirements in this setting are proportional representation and strategyproofness. Intuitively, proportional representation requires that every sufficiently large group of voters with similar preferences is represented in the committee. Strategyproofness demands that no voter can benefit by misreporting her true preferences. We show that these two axioms are incompatible for anonymous party-approval multiwinner voting rules, thus proving a far-reaching impossibility theorem. The proof of this result is obtained by formulating the problem in propositional logic and then letting a SAT solver show that the formula is unsatisfiable. Additionally, we demonstrate how to circumvent this impossibility by considering a weakening of strategyproofness which requires that only voters who do not approve any elected party cannot manipulate. While most common voting rules fail even this weak notion of strategyproofness, we characterize Chamberlin-Courant approval voting within the class of Thiele rules based on this strategyproofness notion.

Downloads

Published

2023-06-26

How to Cite

Delemazure, T., Demeulemeester, T., Eberl, M., Israel, J., & Lederer, P. (2023). Strategyproofness and Proportionality in Party-Approval Multiwinner Elections. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5591-5599. https://doi.org/10.1609/aaai.v37i5.25694

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms