Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Autonomous Agents and Multi-Agent Systems
Erschienen in: Autonomous Agents and Multi-Agent Systems 2/2022

01.10.2022

On the distortion of single winner elections with aligned candidates

verfasst von: Dimitris Fotakis, Laurent Gourvès

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 2/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel Robust optimization of a bi-objective tactical resource allocation problem with uncertain qualification costs
Nächster Artikel Large-scale agent-based simulations of online social networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
We shall see that these properties hold under the mild assumption that no agent is equidistant from two distinct candidates.
 
2
There is no incentive for a single agent or a group of agents to misreport their true rankings.
 
3
In the present work, the location of the agents and the candidates are private.
 
4
Note that the location of the candidates are public in [6, 15].
 
5
Some previous works do not explicitly specify how to deal with ties probably because the input must contain strict preferences and ties are thus implicitly excluded. However, in [2, 19], the authors clearly state that no agent is equidistant from two candidates. In [24], the authors mention that candidates that are equidistant to an agent can be ranked arbitrarily by the agent.
 
6
Technically, we consider that the distortion is 1 when both its numerator and denominator are 0. The distortion is infinite when its numerator is positive and its denominator is 0.
 
7
Again, we consider that the distortion is 1 when both its numerator and denominator are 0; it is infinite if the denominator is 0 but the numerator is positive.
 
8
The two candidates can even be co-located
 
9
Under Assumption 2, there is a unique leftmost candidate and a unique rightmost candidate on the candidate line. The least preferred candidate of every agent (i.e., the farthest) must be one of them.
 
10
See, for example, [16] and references therein for a similar result on a real line or a path.
 
Literatur
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., & Piotr, S., (2018). Approximating optimal social choice under metric preferences. Artificial Intelligence, 264, 27–51.MathSciNetCrossRefMATH
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., & John, P., (2017). Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 58, 797–827.MathSciNetCrossRefMATH
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., & Trick, M. A. (1986). Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4), 165–169.MathSciNetCrossRefMATH
8.
Black, D. (1948). On the rationale of group decision-making. Journal of Political Economy, 56(1), 23–34.CrossRef
9.
Boutilier, C., Caragiannis, I., Haber, S., Tyler, L., Procaccia, A. D., & Sheffet, O. (2015). Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227, 190–213.MathSciNetCrossRefMATH
10.
Bredereck, R., Chen, J., & Woeginger, G. J. (2013). A characterization of the single-crossing domain. Social Choice and Welfare, 41(4), 989–998.MathSciNetCrossRefMATH
11.
Byrka, J., Pensyl, T. W., Rybicki, B., Srinivasan, A., & Trinh, K. (2017). An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2), 23:1-23:31.MathSciNetCrossRefMATH
12.
Caragiannis, I., Nath, S., Procaccia, A. D., & Shah, Nisarg. (2017). Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58, 123–152.MathSciNetCrossRefMATH
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., & Woeginger, G. J. (2017). The one-dimensional euclidean domain: finitely many obstructions are not enough. Social Choice and Welfare, 48(2), 409–432.MathSciNetCrossRefMATH
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., & Zhang, Guochuan. (2013). Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497, 154–163.MathSciNetCrossRefMATH
17.
Church, R. L., & Drezner, Z. (2022). Review of obnoxious facilities location problems. Computers & Operations Research, 138, 105468.MathSciNetCrossRefMATH
18.
Doignon, J. P., & Falmagne, Jean-Claude. (1994). A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms, 16(2), 218–233.MathSciNetCrossRefMATH
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, J. M., & Hinich, M. J. (1984). The spatial theory of voting: An introduction. Cambridge University Press.MATH
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. (2010). Recognizing one-dimensional euclidean preference profiles. Journal of Mathematical Economics, 46(1), 1–5.MathSciNetCrossRefMATH
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., & Zhang, G. (2018). Mechanism design for one-facility location game with obnoxious effects on a line. Theoretical Computer Science, 734, 46–57.MathSciNetCrossRefMATH
34.
Mei, L., Ye, D., & Zhang, Y. (2018). Approximation strategy-proof mechanisms for obnoxious facility location on a line. Journal of Combinatorial Optimization, 36(2), 549–571.MathSciNetCrossRefMATH
35.
Mirrlees, J. A. (1971). An exploration in the theory of optimal income taxation. Review of Economic Studies, 38, 175–208.CrossRefMATH
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.
39.
Vijay, V. (2001). Vazirani. Approximation algorithms: Springer.
40.
Zvi, D., & Hamacher, H. W. (2004). Facility Location Applications and Theory. Springer.MATH
41.
Zwicker, W. S. (2016). Introduction to the theory of voting. Handbook of computational social choice (pp. 23–56). Cambridge University Press.CrossRef
Metadaten
Titel
On the distortion of single winner elections with aligned candidates
verfasst von
Dimitris Fotakis
Laurent Gourvès
Publikationsdatum
01.10.2022
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 2/2022
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-022-09567-5

Weitere Artikel der Ausgabe 2/2022

Autonomous Agents and Multi-Agent Systems 2/2022 Zur Ausgabe

OriginalPaper

Automated privacy negotiations with preference uncertainty

OriginalPaper

Privacy leakage of search-based multi-agent planning algorithms

OriginalPaper

On nash equilibria in normal-form games with vectorial payoffs

OriginalPaper

Minimality and comparison of sets of multi-attribute vectors

OriginalPaper

Reducing disclosed dependencies in privacy preserving planning

OriginalPaper

Towards explainable interactive multiobjective optimization: R-XIMO

Premium Partner

    Bildnachweise