Best-of-Both-Worlds Fairness in Committee Voting with Ordinal Preferences
Working Paper: Title Best-of-Both-Worlds Fairness in Committee Voting with Ordinal Preferences Abstract: Choosing a committee by lottery can improve representation in expectation, but the committee ultimately selected must also be representative. We ask how far these two demands can be combined when voters rank candidates, possibly with ties. We show that every weak-ranking profile admits a lottery satisfying cutoff group fair share (cutoff-GFS) and fractional rank proportional justified representation plus (Rank-PJR+) ex ante, and inclusion proportionality for solid coalitions (IPSC) ex post. Such a lottery can be computed in polynomial time on unrestricted weak rankings. Under strict rankings, IPSC is proportionality for solid coalitions (PSC). In contrast, requiring rank justified representation (Rank-JR) ex post, and hence also Rank-PJR+, can be incompatible with rank individual fair share (Rank-IFS) ex ante, already under strict rankings. We also classify the complexity of exactly...