Best of Both Worlds: Fair Lotteries over Core Committees
New Working Paper: https://cgi.cse.unsw.edu.au/~haziz/grp-core.pdf Title: Best of Both Worlds: Fair Lotteries over Core Committees Abstract We study lotteries over fixed-size committees under approval preferences. We prove that ex ante property of group resource proportionality (GRP) is compatible with core stability ex post, and that such a lottery can be computed in polynomial time with support of size at most one more than the number of candidates. This strengthens several earlier best-of-both-worlds guarantees for committee voting. Although strict Droop-core committees can be computed in polynomial time, we show that any fixed reduction below the Hare quota makes even ex-post justified representation incompatible with ex-ante positive share. Keywords : Approval-based committee voting, Core stability, Group resource proportionality, Randomized social choice