Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Fast Approximation of Centrality and Distances in Hyperbolic Graphs Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Inefficiency of Equilibria in Doodle Polls

Authors : Barbara M. Anthony, Christine Chung

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter On the Complexity of Resilience for Aggregation Queries
next chapter Network Cost-Sharing Games: Equilibrium Computation and Applications to Election Modeling
Footnotes
1
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].
 
Literature
1.
2.
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)
3.
Brams, S.J., Fishburn, P.C.: Approval Voting. Birkhauser, Boston (1983)
4.
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
5.
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)
6.
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)
7.
Caragiannis, I., Procaccia, A.D.: Voting almost maximizes social welfare despite limited communication. Artif. Intell. 175(9–10), 1655–1671 (2011)MathSciNetCrossRef
8.
De Sinopoli, F., Dutta, B., Laslier, J.: Approval voting: three examples. Int. J. Game Theory 35(1), 27–38 (2006)MathSciNetCrossRef
9.
10.
11.
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.
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)
Metadata
Title
Inefficiency of Equilibria in Doodle Polls
Authors
Barbara M. Anthony
Christine Chung
Copyright Year
2018
Book
Combinatorial Optimization and Applications

Print ISBN: 978-3-030-04650-7

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

Copyright Year: 2018

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

Premium Partner

    Image Credits