Core Anchors and Their Completions: Fair Lotteries and Anchored Rules
New Working Paper:
https://cgi.cse.unsw.edu.au/~haziz/grp-core.pdf
Title: Core Anchors and Their Completions: Fair Lotteries and Anchored Rules
Abstract
We study lotteries over fixed-size committees under approval preferences. We prove that group resource proportionality (GRP) ex ante is compatible with core stability ex post, via a polynomial-time construction whose support has size at most one more than the number of candidates. The key is a core anchor: an affordable partial committee whose every completion lies in the core. Core anchors always exist and can be computed in polynomial time. Randomized completion gives the best-of-both-worlds guarantee, while deterministic completion yields anchored rules, a new family of core-stable rules that can target any objective. For coverage and maximin support, their guarantees exceed those of both local and global harmonic-entropy rules of Becker et al. (2026). Finally, although strict Droop-core committees can be computed in polynomial time, for every fixed $\delta>0$, ex-post justified representation at quota $n/(k+\delta)$ is incompatible with ex-ante positive share.
Keywords: Approval-based committee voting, Core stability, Group
resource proportionality, Randomized social choice
Comments