On the Distortion of Single Winner Elections with Aligned Candidates
Fotakis, Dimitris; Gourvès, Laurent (2022), On the Distortion of Single Winner Elections with Aligned Candidates, Autonomous Agents and Multi-Agent Systems, 36, 2. 10.1007/s10458-022-09567-5
TypeArticle accepté pour publication ou publié
External document linkhttps://hal.archives-ouvertes.fr/hal-03839733
Journal nameAutonomous Agents and Multi-Agent Systems
MetadataShow full item record
National Technical University of Athens, Zografos, Greece
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.
Subjects / KeywordsDistortion; Single Winner Election; Obnoxious Facility
Showing items related by title and author.
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
Fotakis, Dimitris; Gourvès, Laurent; Mathieu, Claire; Srivastav, Abhinav (2018) Communication / Conférence
Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Monnot, Jérôme; Xia, Lirong (2012) Article accepté pour publication ou publié
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2017) Communication / Conférence
Fotakis, Dimitris; Gourvès, Laurent; Kasouridis, Stelios; Pagourtzis, Aris (2020) Communication / Conférence