|
Presented at: AAMAS 2022 Location: Virtual Duration: 3 hours (breaks included) Slides: PDF Video recording: |
Presented at: IJCAI 2022 Location: In-person, Messe Wien Exhibition & Congress Center, Vienna, Austria Duration: 2 hours Slides: PDF |
Abstract
The tutorial will focus on the distortion framework, in both its utilitarian and metric formulations, primarily within the context of voting. It will begin with a brief introduction to voting theory and motivations for studying the distortion framework. The tutorial will cover deterministic and randomized single-winner voting rules for aggregating ranked ballots that achieve (near) optimal distortion in both frameworks. Several extensions will be presented, such as aggregating ballots that are more or less informative than ranked ballots, designing optimal ballots via the information-distortion tradeoff, and designing voting rules for other types of outcomes (e.g., committee selection, participatory budgeting, and social welfare functions). Several open questions will be presented throughout the tutorial. The tutorial will conclude with a brief survey of applications of the distortion framework in settings beyond voting such as matching, resource allocation, and graph theoretical problems.
Background and takeaways
No prior background of social choice theory or the distortion framework will be necessary. Basic knowledge of computer science and mathematics (e.g., probability), equivalent to high school education and early years of an undergraduate computer science degree, will be expected. Audience unfamiliar with the area can expect to take away a detailed understanding of an exciting new research direction in social choice theory. Researchers actively working in the area can expect to take away a list of challenging open questions.
Outline
- Intro: The tutorial begins with a brief introduction to voting theory and the classical axiomatic approach to analyzing and designing voting rules. The distortion framework is then motivated against this backdrop.
- Part I (Utilitarian Distortion): The first part focuses on the utilitarian formulation of the distortion framework, which is how the framework was originally introduced. In the canonical setting, n voters express ranked preferences over m candidates, these preferences are consistent with voters' underlying cardinal utility functions, the voting rules select a single candidate either deterministically or randomly, and they are evaluated based on their worst-case approximation ratio to utiltiarian social welfare (aka distortion).
- The tutorial first covers optimal distortion bounds achievable by deterministic and randomized voting rules, with focus on the computability of the so-called instance-optimal rules.
- Subsequently, distortion bounds for various extensions are presented, such as aggregating partially ranked ballots, aggregating ranked ballots with additional information, designing ballots that achieve optimal information-distortion tradeoff, designing rules for committee election, participatory budgeting, and ranked output, and formulating distortion with respect to different classes of utility functions or approximation objectives.
- Part II (Metric Distortion): The second part focuses on the alternative metric distortion framework, in which voters and candidates are assumed to be part of an underlying metric space and voters' ranked preferences are consistent with their distances to the candidates. Voting rules are judged based on their worst-case approximation ratio to the social cost objective.
- As with Part I, the tutorial first covers results on optimal distortion bounds achievable by deterministic and randomized voting rules, as well as computability of instance-optimal rules. Then, results for the same extensions as above are presented.
- Part III (Other Applications): The third part concludes the tutorial with a brief survey of the applications of the distortion framework to other problems such as distributed elections, matching, resource allocation, and graph theoretical problems.