Inefficiency of Equilibria in Doodle Polls

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

Chung, Christine

Anthony, Barbara M.

2019-09-18

2019-09-18

2018-11-16

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

https://collections.southwestern.edu/s/suscholar/item/244

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.

English

Springer, Cham

Doodle polls

Nash equilibria

Approval voting

Article