Approval-Based Apportionment

  • Markus Brill Technische Universität Berlin
  • Paul Gölz Carnegie Mellon University
  • Dominik Peters Carnegie Mellon University
  • Ulrike Schmidt-Kraepelin Technische Universität Berlin
  • Kai Wilker Technische Universität Berlin

Abstract

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.

Published
2020-04-03
Section
AAAI Technical Track: Game Theory and Economic Paradigms