DSpace Repository

Inefficiency of Equilibria in Doodle Polls

Show simple item record

dc.contributor.author Chung, Christine
dc.contributor.author Anthony, Barbara M.
dc.date.accessioned 2019-09-18T19:31:26Z
dc.date.available 2019-09-18T19:31:26Z
dc.date.issued 2018-11-16
dc.identifier.citation 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 en_US
dc.identifier.uri http://hdl.handle.net/11214/229
dc.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 en_US
dc.description.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. en_US
dc.language.iso en_US en_US
dc.publisher Springer, Cham en_US
dc.subject Doodle polls en_US
dc.subject Nash equilibria en_US
dc.subject Approval voting en_US
dc.title Inefficiency of Equilibria in Doodle Polls en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search


Browse

My Account

Links