nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Inefficiency of Equilibria in Doodle Polls

verfasst von : Barbara M. Anthony, Christine Chung

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a web-based poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a game-theoretic approach to understanding what happens in Doodle polls assuming participants vote sincerely. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, both under lexicographic tie-breaking and randomized tie-breaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.

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

Vorheriges Kapitel On the Complexity of Resilience for Aggregation Queries

Nächstes Kapitel Network Cost-Sharing Games: Equilibrium Computation and Applications to Election Modeling

A sample of over 340,000 polls in a 3-month period in 2011 had a median of about 5 respondents and 12 time slots [17].

Alrawi, D., Anthony, B.M., Chung, C.: How well do Doodle polls do? In: Spiro, E., Ahn, Y.-Y. (eds.) SocInfo 2016. LNCS, vol. 10046, pp. 3–23. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47880-7_1CrossRef

Anthony, B.M., Chung, C.: How bad is selfish Doodle voting?: (extended abstract). In: Proceedings of the 2018 International Conference on Autonomous Agents and Multiagent Systems. AAMAS 2018 (2018)

Brams, S.J., Fishburn, P.C.: Approval Voting. Birkhauser, Boston (1983)

Brams, S.J., Sanver, M.R.: Critical strategies under approval voting: who gets ruled in and ruled out. Elect. Stud. 25(2), 287–305 (2006)CrossRef

Brânzei, S., Caragiannis, I., Morgenstern, J., Procaccia, A.D.: How bad is selfish voting? In: desJardins, M., Littman, M.L. (eds.) Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, pp. 138–144. AAAI Press (2013)

Bredereck, R., Chen, J., Niedermeier, R., Obraztsova, S., Talmon, N.: Teams in online scheduling polls: game-theoretic aspects. In: Singh, S.P., Markovitch, S. (eds.) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, USA, pp. 390–396. AAAI Press (2017)

Caragiannis, I., Procaccia, A.D.: Voting almost maximizes social welfare despite limited communication. Artif. Intell. 175(9–10), 1655–1671 (2011)MathSciNetCrossRef

De Sinopoli, F., Dutta, B., Laslier, J.: Approval voting: three examples. Int. J. Game Theory 35(1), 27–38 (2006)MathSciNetCrossRef

Endriss, U.: Sincerity and manipulation under approval voting. Theory Decis. 74(3), 335–355 (2013)MathSciNetCrossRef

10.

Laslier, J.F., Sanver, M.R.: The basic approval voting game. In: Laslier, J.F., Sanver, M.R. (eds.) Handbook on Approval Voting. WELFARE, pp. 153–163. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02839-7_8CrossRefMATH

11.

Laslier, J.F., Sanver, M.R.: Handbook on Approval Voting. Studies in Choice and Welfare. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02839-7CrossRefMATH

12.

Laslier, J.F.: The leader rule: a model of strategic approval voting in a large electorate. J. Theor. Polit. 21(1), 113–136 (2009)CrossRef

13.

Myerson, R.B., Weber, R.J.: A theory of voting equilibria. Am. Polit. Sci. Rev. 87(1), 102–114 (1993)CrossRef

14.

Obraztsova, S., Polukarov, M., Rabinovich, Z., Elkind, E.: Doodle poll games. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. AAMAS 2017, Sao Paulo, Brazil, pp. 876–884 (2017)

15.

Thompson, D.R., Lev, O., Leyton-Brown, K., Rosenschein, J.: Empirical analysis of plurality election equilibria. In: Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS 2013, St. Paul, MN, pp. 391–398 (2013)

16.

Weber, R.J.: Approval voting. J. Econ. Perspect. 9(1), 39–49 (1995)CrossRef

17.

Zou, J., Meir, R., Parkes, D.: Strategic voting behavior in Doodle polls. In: Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work. CSCW 2015, pp. 464–472. ACM, New York (2015)

Titel: Inefficiency of Equilibria in Doodle Polls
verfasst von: Barbara M. Anthony
Christine Chung
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_48

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"