research-article

On the distortion of single winner elections with aligned candidates

Authors:

Dimitris Fotakis,

Laurent GourvèsAuthors Info & Claims

Autonomous Agents and Multi-Agent Systems, Volume 36, Issue 2

https://doi.org/10.1007/s10458-022-09567-5

Published: 01 October 2022 Publication History

Abstract

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.

References

[1]

Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. A., (2020). Peeking behind the ordinal curtain: Improving distortion via cardinal queries. In Proceedings of the 34th AAAI conference on artificial intelligence, pages 1782–1789.

[2]

Anshelevich E, Bhardwaj O, Elkind E, Postl J, and Piotr S Approximating optimal social choice under metric preferences Artificial Intelligence 2018 264 27-51

[3]

Anshelevich, E., Bhardwaj, O., & Postl. J., (2015). Approximating optimal social choice under metric preferences. In Proceedings of the 29th AAAI conference on artificial intelligence, pages 777–783.

[4]

Anshelevich, E., Filos-Ratsikas, A., Shah, N., & Voudouris, A. A., (2021). Distortion in social choice problems: The first 15 years and beyond. In Proceedings of the 30th international joint conference on artificial intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 4294–4301.

[5]

Anshelevich E and John P Randomized social choice functions under metric preferences Journal of Artificial Intelligence Research 2017 58 797-827

[6]

Anshelevich, E., Zhu, W., (2018). Ordinal approximation for social choice, matching, and facility location problems given candidate positions. In Web and Internet Economics - 14th International conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings, pages 3–20.

[7]

Bartholdi J and Trick MA Stable matching with preferences derived from a psychological model Operations Research Letters 1986 5 4 165-169

[8]

Black D On the rationale of group decision-making Journal of Political Economy 1948 56 1 23-34

[9]

Boutilier C, Caragiannis I, Haber S, Tyler L, Procaccia AD, and Sheffet O Optimal social choice functions: A utilitarian view Artificial Intelligence 2015 227 190-213

[10]

Bredereck R, Chen J, and Woeginger GJ A characterization of the single-crossing domain Social Choice and Welfare 2013 41 4 989-998

[11]

Byrka J, Pensyl TW, Rybicki B, Srinivasan A, and Trinh K An improved approximation for k-median and positive correlation in budgeted optimization ACM Transactions on Algorithms 2017 13 2 23:1-23:31

[12]

Caragiannis I, Nath S, Procaccia AD, and Shah Nisarg Subset selection via implicit utilitarian voting Journal of Artificial Intelligence Research 2017 58 123-152

[13]

Charikar, M., & Ramakrishnan, P., (2022). Metric distortion bounds for randomized social choice. In Proceedings of the 2022 ACM-SIAM Symposium on discrete algorithms, SODA 2022, virtual conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2986–3004.

[14]

Chen J, Pruhs K, and Woeginger GJ The one-dimensional euclidean domain: finitely many obstructions are not enough Social Choice and Welfare 2017 48 2 409-432

[15]

Chen, X., Li, M., & Wang, C., (2020). Favorite-candidate voting for eliminating the least popular candidate in a metric space. In The thirty-fourth AAAI conference on artificial intelligence, AAAI 2020, The thirty-second innovative applications of artificial intelligence conference, IAAI 2020, The Tenth AAAI symposium on educational advances in artificial intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1894–1901.

[16]

Cheng Y, Wei Y, and Zhang Guochuan Strategy-proof approximation mechanisms for an obnoxious facility game on networks Theoretical Computer Science 2013 497 154-163

[17]

Church RL and Drezner Z Review of obnoxious facilities location problems Computers & Operations Research 2022 138

[18]

Doignon JP and Falmagne Jean-Claude A polynomial time algorithm for unidimensional unfolding representations Journal of Algorithms 1994 16 2 218-233

[19]

Elkind, E., & Faliszewski, P., (2014). Recognizing 1-Euclidean preferences: an alternative approach. In Proceedings of the 7th international symposium on algorithmic game theory (SAGT 2014), pages 146–157.

[20]

Elkind, E., Faliszewski, P., & Slinko, A. M., (2012). Clone structures in voters’ preferences. In Proceedings of the 13th ACM conference on electronic commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 496–513.

[21]

Enelow JM and Hinich MJ The spatial theory of voting: An introduction 1984 Delhi Cambridge University Press

[22]

Bruno Escoffier, Jérôme Lang, & Meltem Öztürk. (2018). Single-peaked consistency and its complexity. In ECAI 2008 - 18th european conference on artificial intelligence, Patras, Greece, July 21-25, 2008, Proceedings, pages 366–370.

[23]

Feldman, M., Fiat, A., & Golomb, I., (2016). On voting and facility location. In Proceedings of the 2016 ACM Conference on economics and computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 269–286.

[24]

Gkatzelis, V., Halpern, D., & Shah, N., (2020). Resolving the optimal metric distortion conjecture. In 61st IEEE annual symposium on foundations of computer science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1427–1438.

[25]

Goel, A., Hulett, R., & Krishnaswamy, A. K., (2018). Relating metric distortion and fairness of social choice rules. In Proceedings of the 13th workshop on economics of networks, systems and computation, NetEcon@SIGMETRICS 2018, Irvine, CA, USA, June 18, 2018, page 4:1.

[26]

Gross, S., Anshelevich, E., & Xia, L., (2017). Vote until two of you agree: mechanisms with small distortion and sample complexity. In Proceedings of the 31st AAAI conference on artificial intelligence, pages 544–550. AAAI Press.

[27]

Hosseini, S., & Moharerhaye Esfahani, A. (2009). Obnoxious facility location (pp. 315–345). Physica-Verlag Heidelberg.

[28]

Karlin, Samuel. (1968). Total Positivity. Stanford University Press.

[29]

Kempe, D., (2020). An analysis framework for metric voting based on LP duality. In Proceedings of the 34th AAAI conference on artificial intelligence (AAAI 2020), pages 2079–2086. AAAI Press.

[30]

Kempe, D., (2020). Communication, distortion, and randomness in metric voting. In Proceedings of the 34th AAAI conference on artificial intelligence (AAAI 2020), pages 2087–2094. AAAI Press.

[31]

Knoblauch V Recognizing one-dimensional euclidean preference profiles Journal of Mathematical Economics 2010 46 1 1-5

[32]

Mandal, D., Shah, N., & David, P., (2020). Woodruff. Optimal communication-distortion tradeoff in voting. In EC ’20: The 21st ACM conference on economics and computation, virtual event, hungary, July 13-17, 2020, pages 795–813.

[33]

Mei L, Ye D, and Zhang G Mechanism design for one-facility location game with obnoxious effects on a line Theoretical Computer Science 2018 734 46-57

[34]

Mei L, Ye D, and Zhang Y Approximation strategy-proof mechanisms for obnoxious facility location on a line Journal of Combinatorial Optimization 2018 36 2 549-571

[35]

Mirrlees JA An exploration in the theory of optimal income taxation Review of Economic Studies 1971 38 175-208

[36]

Munagala, K., & Wang, K., (2019). Improved metric distortion for deterministic social choice rules. In Proceedings of the 2019 ACM conference on economics and computation, EC 2019, pages 245–262.

[37]

Procaccia, A. D., & Jeffrey, S. (2006). Rosenschein. The distortion of cardinal preferences in voting. In Cooperative Information Agents X, 10th international workshop, CIA 2006, Edinburgh, UK, September 11-13, 2006, Proceedings, pages 317–331.

[38]

Tamir A Obnoxious facility location on graphs SIAM Journal on Discrete Mathematics 1991 4 4 550-567

[39]

Vijay V Vazirani 2001 Approximation algorithms Springer

[40]

Zvi D and Hamacher HW Facility Location Applications and Theory 2004 Berlin Springer

[41]

Zwicker WS Introduction to the theory of voting Handbook of computational social choice 2016 Cambridge Cambridge University Press 23-56

Cited By

Fotakis DGourvès LAgmon NAn BRicci AYeoh W(2023)On the Distortion of Single Winner Elections with Aligned CandidatesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598791(1409-1411)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598791

Recommendations

On the Distortion of Single Winner Elections with Aligned Candidates
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

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 ...
Distortion in Attribute Approval Committee Elections
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

In attribute approval elections, the task is to select sets of winning candidates, while each candidate satisfies a variety of attributes in different categories (e.g., academic degree, work experience, location). Every voter specifies, which attributes ...
The metric distortion of multiwinner voting
Abstract
We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances between agents and alternatives are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Autonomous Agents and Multi-Agent Systems

Autonomous Agents and Multi-Agent Systems Volume 36, Issue 2

Oct 2022

919 pages

ISSN:1387-2532

Issue’s Table of Contents

© Springer Science+Business Media, LLC, part of Springer Nature 2022.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2022

Accepted: 25 May 2022

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fotakis DGourvès LAgmon NAn BRicci AYeoh W(2023)On the Distortion of Single Winner Elections with Aligned CandidatesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598791(1409-1411)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598791

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents