Computational Aspects of Multi-Winner Approval Voting

Abstract

We study computational aspects of three prominent voting rules that use approval ballots to select multiple winners. These rules are proportional approval voting, reweighted approval voting, and satisfaction approval voting. Each rule is designed with the intention to compute a representative winning set. We show that computing the winner for proportional approval voting is NP-hard, closing an open problem (Kilgour, 2010). As none of the rules we examine are strategy-proof, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots of the other agents.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 137 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.