-
Title
-
Inefficiency of Equilibria in Doodle Polls
-
Description
-
This is an Accepted manuscript of an article published In: Kim D., Uma R., Zelikovsky A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science, vol 11346. Springer, Cham.
DOI https://doi.org/10.1007/978-3-030-04651-4_48
-
Creator
-
Chung, Christine
-
Anthony, Barbara M.
-
Date
-
2019-09-18
-
Date Available
-
2019-09-18
-
Date Issued
-
2018-11-16
-
Identifier
-
Anthony B.M., Chung C. (2018) Inefficiency of Equilibria in Doodle Polls. In: Kim D., Uma R., Zelikovsky A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science, vol 11346. Springer, Cham
-
uri
-
https://collections.southwestern.edu/s/suscholar/item/244
-
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.
-
Language
-
English
-
Publisher
-
Springer, Cham
-
Subject
-
Doodle polls
-
Nash equilibria
-
Approval voting
-
Type
-
Article
