The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.
Explore Research Products in the PAR It may take a few hours for recently added research products to appear in PAR search results.
Title: Distortion in Social Choice Problems: The First 15 Years and Beyond
The notion of distortion in social choice problems has been defined to measure the loss in efficiency---typically measured by the utilitarian social welfare, the sum of utilities of the participating agents---due to having access only to limited information about the preferences of the agents. We survey the most significant results of the literature on distortion from the past 15 years, and highlight important open problems and the most promising avenues of ongoing and future work.
The notion of distortion in social choice problems has been defined to measure the loss in efficiency - typically measured by the utilitarian social welfare, the sum of utilities of the participating agents - due to having access only to limited information about the preferences of the agents. Here, we provide a comprehensive reading list on the related literature.
Goel, Ashish; Krishnaswamy, Anilesh K.; Munagala, Kamesh(
, EC '17 Proceedings of the 2017 ACM Conference on Economics and Computation)
We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worst-case distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the well-known weighted-tournament rule, achieves a distortion of at most 3 (Anshelevich et al. 2015). We disprove this conjecture by constructing a sequence of instances which shows that the worst-case distortion of Ranked Pairs is at least 5. Our lower bound on the worst-case distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worst-case distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.
Gkatzelis, Vasilis; Latifian, Mohamad; Shah, Nisarg(
, 24th ACM Conference on Economics and Computation)
We study the problem of designing voting rules that take as input the ordinal preferences of n agents over a set of m alternatives and output a single alternative, aiming to optimize the overall happiness of the agents. The 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. Several deterministic and randomized voting rules have been proposed and evaluated for each of these worlds separately, gradually improving the achievable distortion bounds, but none of the known voting rules perform well in both worlds simultaneously.
In this work, we prove that one can in fact achieve the “best of both worlds” by designing new voting rules, both deterministic and randomized, that simultaneously achieve near-optimal distortion guarantees in both distortion worlds. We also prove that this positive result does not generalize to the case where the voting rule is provided with the rankings of only the top-t alternatives of each agent, for t < m, and study the extent to which such best-of-both-worlds guarantees can be achieved.
Anshelevich, Elliot; Filos-Ratsikas, Aris; Jerrett, Christopher; Voudouris, Alexandros A(
, Proceedings of the AAAI Conference on Artificial Intelligence)
We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance between the corresponding points in the space. The goal is to choose a single alternative to (approximately) minimize the social cost (cost of all agents) or the maximum cost of any agent, when only limited information about the preferences of the agents is given. Previous work has shown that the best possible distortion one can hope to achieve is 3 when access to the ordinal preferences of the agents is given, even when the distances between alternatives in the metric space are known. We improve upon this bound of 3 by designing deterministic mechanisms that exploit a bit of cardinal information. We show that it is possible to achieve distortion 1+sqrt(2) by using the ordinal preferences of the agents, the distances between alternatives, and a threshold approval set per agent that contains all alternatives for whom her cost is within an appropriately chosen factor of her cost for her most-preferred alternative. We show that this bound is the best possible for any deterministic mechanism in general metric spaces, and also provide improved bounds for the fundamental case of a line metric.
Suppose that we have $n$ agents and $n$ items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their matched items is as small as possible. However, instead of having direct access to distances in the metric, we only have each agent's ranking of the items in order of distance. Given this limited information, what is the minimum possible worst-case approximation ratio (known as the \emph{distortion}) that a matching mechanism can guarantee?
Previous work by \citet{CFRF+16} proved that the (deterministic) Serial Dictatorship mechanism has distortion at most $2^n - 1$. We improve this by providing a simple deterministic mechanism that has distortion $O(n^2)$. We also provide the first nontrivial lower bound on this problem, showing that any matching mechanism (deterministic or randomized) must have worst-case distortion $\Omega(\log n)$.
In addition to these new bounds, we show that a large class of truthful mechanisms derived from Deferred Acceptance all have worst-case distortion at least $2^n - 1$, and we find an intriguing connection between \emph{thin matchings} (analogous to the well-known thin trees conjecture) and the distortion gap between deterministic and randomized mechanisms.
Anshelevich, Elliot, Filos-Ratsikas, Aris, Shah, Nisarg, and Voudouris, Alexandros A. Distortion in Social Choice Problems: The First 15 Years and Beyond. Retrieved from https://par.nsf.gov/biblio/10295647. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track. . Web. doi:10.24963/ijcai.2021/589.
Anshelevich, Elliot, Filos-Ratsikas, Aris, Shah, Nisarg, & Voudouris, Alexandros A. Distortion in Social Choice Problems: The First 15 Years and Beyond. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track., (). Retrieved from https://par.nsf.gov/biblio/10295647. https://doi.org/10.24963/ijcai.2021/589
Anshelevich, Elliot, Filos-Ratsikas, Aris, Shah, Nisarg, and Voudouris, Alexandros A.
"Distortion in Social Choice Problems: The First 15 Years and Beyond". Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track. (). Country unknown/Code not available. https://doi.org/10.24963/ijcai.2021/589.https://par.nsf.gov/biblio/10295647.
@article{osti_10295647,
place = {Country unknown/Code not available},
title = {Distortion in Social Choice Problems: The First 15 Years and Beyond},
url = {https://par.nsf.gov/biblio/10295647},
DOI = {10.24963/ijcai.2021/589},
abstractNote = {The notion of distortion in social choice problems has been defined to measure the loss in efficiency---typically measured by the utilitarian social welfare, the sum of utilities of the participating agents---due to having access only to limited information about the preferences of the agents. We survey the most significant results of the literature on distortion from the past 15 years, and highlight important open problems and the most promising avenues of ongoing and future work.},
journal = {Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track.},
author = {Anshelevich, Elliot and Filos-Ratsikas, Aris and Shah, Nisarg and Voudouris, Alexandros A.},
editor = {null}
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.