LFCS Seminar: Friday, 10 November - Mohamad Latifian

Title:            Best of Both Distortion Worlds

Abstract:

 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. To quantify the extent to which voting rules can optimize over the cardinal preferences given access only to the ordinal ones, prior work has used the distortion measure, i.e., the worst-case approximation ratio between a voting rule's performance and the best performance achievable given the cardinal preferences.

The work on the distortion of voting rules has been largely divided into two worlds: utilitarian distortion and metric distortion. In the former, the cardinal preferences of the agents correspond to general utilities and the goal is to maximize a normalized social welfare. In the latter, the agents' cardinal preferences correspond to costs given by distances in an underlying metric space and the goal is to minimize the (unnormalized) social cost. This notion has gained a lot of attention over the past decade and several deterministic and randomized voting rules have been proposed and evaluated for each of these worlds separately, gradually improving the achievable distortion bounds.

In this talk, I will introduce the notion of distortion in two different worlds and go over the literature. After that, I will talk about our paper “Best of Both Distortion Worlds” which is a joint work with Vasilis Gkatzelis and Nisarg Shah and appeared in EC ’23. In this work, we show that none of the known voting rules perform well in both worlds simultaneously and we answer the question of whether one can achieve the best of both worlds by designing new voting rules that achieve optimal distortion guarantees in both distortion worlds.