New method balances fair committee picks before and after voting
Best-of-Both Worlds Proportionality in Structured Committee Elections
Computer Science and Game Theory
Summary
Choosing committees that represent voters fairly is hard because people want fairness both before and after the committee is chosen. The authors study elections where voters have structured preferences and show that some fairness ideas can’t both happen at once. They offer a new way of turning partial (fractional) committee choices into actual committees, keeping strong fairness guarantees before and almost after the final choice. Their approach works well in settings where voter preferences follow a certain structured pattern called antichain single-peakedness.
What this means in practice
- •For electoral system designers: Produce election procedures that deliver fair representation both in expected outcomes and actual selected committees for structured voter preferences.
- •For online recommendation teams: Build algorithms that fairly select diverse sets of options reflecting user preferences with strong fairness both in expectation and in final outputs.
Authors
Dimitris Avramidis, Mark de Berg, Ulrike Schmidt-Kraepelin
Abstract
We study randomized committee elections with additive preferences, where we seek best-of-both-worlds proportionality. That is, we strive for strong guarantees for the selection probabilities ex ante and each realized committee ex post. We focus on structured preferences and introduce antichain single-peakedness, a restricted domain generalizing single-peaked additive preferences as well as several well-studied approval domains. Our approach first computes a fractional committee and then decomposes it through a rounding rule called systematic rounding. Among profile-oblivious rounding rules, we characterize systematic rounding as the unique rule satisfying natural quota guarantees, and thereby the only promising rule for our two-step approach. We show that ex-ante core stability is incompatible with ex-post justified representation $JR$, even under single-peaked preferences. However, applying systematic rounding to certain fractional allocations that form so-called Lindahl equilibria yields ex-ante core stability and ex-post core stability up to one. Alternatively, we retain exact ex-post proportionality and approximate the ex-ante core using two parameters: $α$ raises the utility gain required for a deviation, while $β$ reduces the coalition's proportional share. We establish the tight threshold $αβ$=2. Below it, ex-post JR is incompatible even under single-peaked preferences; at and above it, adapting a fractional rule called BestRepresentative [Pierczyński and Skowron, 2022] and applying systematic rounding to its output yields ex-ante $α, β$-fractional core stability and ex-post PJR under antichain single-peaked preferences.