Overview

A single-winner voting rule takes as input the ordinal preferences of agents over the alternatives and outputs a single alternative, aiming to optimize the overall happiness of the agents. In voting with ranked ballots input to the voting rule is each agent’s ranking of the alternatives from most to least preferred, yet the agents have more refined (cardinal) preferences that capture the intensity with which they prefer one alternative over another. The notion of distortion was introduced in 2006 by Procaccia and Rosenschein to quantify the extent to which voting rules can optimize over the cardinal preferences given access only to the ordinal ones. Distortion captures the worst-case approximation ratio between a voting rule’s performance and the best performance achievable given the cardinal preferences. The notion of distortion became very popular in the past decade as it gives quantitative answers to fundamental questions in voting theory, and it has been considered in different settings. In this talk, I will introduce this notion under different assumptions and talk about our new results in various social choice scenarios, spanning from rudimentary single-winner voting protocols to voting with other elicitation methods and even realms like matching and participatory budgeting. I’ll conclude the talk with some of the challenges that we face in this area of research. No prior knowledge of the area is required.