Algorithmic Perspectives on Instant Runoff Voting

Algorithmic Perspectives on Instant Runoff Voting (via Zoom)

Abstract: Recent years have seen a concerted effort to move from traditional plurality voting to alternative voting systems in the United States, most notably instant runoff voting (IRV, also called ranked-choice voting). IRV exhibits rich and complex interactions with the preferences of voters, many of which are under-explored from a theoretical perspective. My research aims to deepen our understanding of IRV and related voting systems using techniques from the analysis of algorithms. In the first part of the talk, I’ll describe our analysis of a classic one-dimensional model of voter preferences, leading to a novel and striking fact about IRV: if voters are symmetrically distributed and not too concentrated at the extremes, IRV cannot elect an extreme candidate over a moderate. In contrast, we prove plurality can, drawing on connections between plurality voting in one dimension and stick-breaking processes. This finding lends a theoretical basis to the folk wisdom that IRV can benefit moderate candidates. We also formulate a geometric approach to deriving exact winner distributions when voters and candidates are uniformly distributed. The second part of the talk will cover a worst-case analysis of the sensitivity of IRV to the number of candidates voters are allowed to rank (the ballot length). We prove that the election winner can depend almost arbitrarily on the ballot length given a fixed population of voters. We also establish lower bounds on the number of voters needed to achieve these worst cases, with matching constructions.  
This talk is based on joint work with Johan Ugander and Jon Kleinberg.
Bio: Kiran Tomlinson is a fifth-year PhD candidate at Cornell University advised by Jon Kleinberg. His research focuses on human preferences and the mechanisms that depend on them, including voting, discrete choice, and recommender systems. He received his undergraduate degree from Carleton College, where he returned as a visiting instructor in winter and spring 2023. During the summers of 2021 and 2022, he interned at Microsoft with Longqi Yang and Jennifer Neville.