Condorcet’s paradox is a cornerstone in social choice theory. It points out that in some elections, no matter which candidate wins, a majority of voters will prefer a different candidate. In these scenarios, what can we do to guarantee the support of a majority?

 

Elkind, Lang, and Saffidine proposed the idea of electing multiple candidates so that a voter only prefers a different candidate if the voter prefers this candidate to every elected candidate. Under this view, we hope that the “committee” of elected candidates wins a majority support against every candidate. We can clearly guarantee this property if all the candidates are elected, but what is the minimum number of candidates that need to be elected?

 

This talk is based on joint work with Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, and Adrian Vetta.

Kangning is an Assistant Professor of Computer Science at Rutgers University. Prior to joining Rutgers, he received his PhD from Duke University and spent postdoctoral time at the Simons Institute and at Stanford University. He does research in the area of economics and computation, especially in social choice, mechanism design, and information design. His research has been recognized with Best Paper Awards at SODA 2024 and WINE 2018 as well as dissertation awards from ACM SIGecom and Duke CS.