Designing Optimal Voting Rules

A central task in voting is to aggregate the ranked preferences of voters over a set of alternatives (candidates) to select a winning alternative. However, despite centuries of research, the natural question of which voting rule is “best” has remained elusive. A recent approach from computer science offers hope. By proposing a natural quantitative measure of the “efficiency” of a voting rule, called distortion, it allows us to define and seek the most efficient voting rule.

In a series of joint works, we resolve several open questions on identifying the most efficient voting rules. Our results naturally extend to taking partial preference rankings as input and/or selecting multiple winning alternatives as output. Stretching this one step further, we also use this framework to design optimal ballot formats, which elicit minimal preference information from voters to make efficient decisions. Finally, we also initiate the study of a quantitative measure of fairness of a voting rule, called proportional fairness, and identify the fairest voting rule for aggregating ranked preferences.

No prior knowledge of voting theory is required and I will point out many important open questions throughout the talk.

Results covered in the talk:

Utilitarian distortion: Preprint, Preprint

Optimal ballot design via utilitarian distortion: NeurIPS'19, EC'20

Metric distortion: FOCS'20, AAAI'22

Nisarg Shah is an assistant professor of computer science at the University of Toronto. He has been recognized as AI's 10 to Watch by IEEE Intelligent Systems in 2020. He is also the winner of the 2016 IFAAMAS Victor Lesser Distinguished Dissertation Award and the 2014-2015 Facebook PhD Fellowship. Shah conducts research at the intersection of computer science and economics, addressing issues of fairness, efficiency, elicitation, and incentives that arise when humans are affected by algorithmic decision-making. His recent work develops theoretical foundations for fairness in fields such as voting, resource allocation, and machine learning. He has co-developed two not-for-profit websites, Spliddit.org and RoboVote.org (temporarily unavailable), which have helped more than 200,000 users make provably fair and optimal decisions in their everyday lives. He earned his PhD in computer science at Carnegie Mellon University and was a postdoctoral fellow at Harvard University.