Stable committees always exist in approval voting systems
Existence of the Core in Approval-Based Committee Elections
Computer Science and Game Theory
Summary
Finding fair groups to represent people in elections is a tricky problem. The paper shows that there is always a stable committee that no group would want to replace, based on approval voting where people approve multiple choices. To prove this, the authors created a new method that measures fairness using ideas like entropy, and any best solution found this way is stable. This means it’s possible to efficiently find committees that keep everyone happy in a fair way.
approval votingcommittee electionscore stabilitygroup fairnessmulti-winner electionsentropylocal optimapolynomial time
Authors
Patrick Becker, Matthias Greger, Dominik Peters
Abstract
We settle the main open question in the theory of approval-based multi-winner elections: we show that there always exists a committee in the core. The core is a stability and group fairness concept. The proof introduces a new voting rule that optimizes an entropy-like objective function over committees and payment systems. All local optima of this objective function lie in the core, which implies that a core committee can be found in polynomial time.