Equilibria in Doodle Polls under Three Tie-Breaking Rules

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 approval voting assuming participants vote sincerely. While our instances are framed in the context of the Doodle poll application, the results apply more broadly to approval voting. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, under lexicographic tie-breaking, random candidate, and random voter 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.