Promoting Fairness and Priority in Selecting k-Winners Using IRV

We investigate the problem of finding winner(s) given a large number of users' (voters') preferences casted as ballots, one from each of the m users, where each ballot is a ranked order of preference of up to ℓ out of n items (candidates). Given a group protected attribute with k different values and a priority that imposes a selection order among these groups, the goal is to satisfy the priority order and select a winner per group that is most representative. It is imperative that at times the original users' preferences may require further manipulation to meet these fairness and priority requirement. We consider manipulation by modifications and formalize the margin finding problem under modification problem. We study the suitability of Instant Run-off Voting (IRV) as a preference aggregation method and demonstrate its advantages over positional methods. We present a suite of technical results on the hardness of the problem, design algorithms with theoretical guarantees and further investigate efficiency opportunities. We present exhaustive experimental evaluations using multiple applications and large-scale datasets to demonstrate the effectiveness of IRV, and efficacy of our designed solutions qualitatively and scalability-wise.