The field of Computational Social Choice studies the ways in which the preferences of individuals can be aggregated in order to make collective decisions, like choosing the winner of an election. Algorithms for these problems have wide-ranging applications in democracy, hiring, facility location, reinforcement learning, school choice, and more.
Researchers have sought to develop quantitative approaches to understanding the effectiveness of voting rules. A prominent measure is the notion of distortion: one imagines that the voters’ preferences are derived from some underlying cardinal utilities/costs, and the distortion measures how well a voting rule is able to optimize the total social welfare/cost given only the ordinal preferences.
The pursuit of voting rules with low distortion in each of these models has been an incredibly fruitful endeavor, deepening our understanding of previously studied voting rules, and also leading to the design of a number of novel voting rules. The rapid developments have garnered significant interest, with a workshop at EC 2020, a 2021 survey [AFSV21], tutorials at AAMAS 2022 and IJCAI 2022, a Prominent Paper Award from AIJ in 2022 [BCHLPS15], a Distinguished Paper Award at IJCAI 2022 [KK22], and a Best Paper Award at SODA 2024 [CRWW24].
In this workshop, we showcase some of these exciting recent developments to the FOCS audience, and highlight the enticing open problems that remain.
Session 1. 2:00pm–3:30pm CDT, Sunday, October 27, 2024
David Kempe: Introduction to Distortion in Social Choice (60 minutes) [David's slides]
Daniel Halpern: Optimal Randomized Utilitarian Distortion (30 minutes) [Daniel's slides][EKPS24, BHLS22]
Session 2. 4:00pm–5:00pm CDT, Sunday, October 27, 2024
Fatih Erdem Kizilkaya: Optimal Deterministic Metric Distortion (30 minutes) [Fatih's slides][KK22, KK23, GHS20]
Prasanna Ramakrishnan: Randomized Metric Distortion (30 minutes) [Prasanna's slides][CRWW24, CR22]
U. of Southern California
Harvard University
U. of Southern California
Stanford University
Stanford University
Stanford University
University of Toronto
Rutgers University