Theory Lunch This Week (Thursday 3/27, 12:00, GCS 502C)

[Grayson York]

Hi all,

Please join us at theory lunch this week on Thursday 3/27 at 12:00 in GCS 502C, where I will be presenting some joint work with David Kempe. The title and abstract of the work are as follows.

Thanks!

Grayson

Title: Vote Delegation through the Lens of Metric Distortion

Abstract: We study the power of vote delegation in an election in which voters might be poorly informed. More specifically, we study a setting in which an election is run to choose one of two alternatives (such as voting “Yes” or “No” on an issue). Different from prior work, which mostly studied a setting with a correct ground truth about which voters receive independent noisy signals, we consider a setting allowing for idiosyncratic voter preferences: The voters and alternatives are embedded in an unknown metric space, with distance capturing the cost of a voter for an alternative. We model poorly informed voters as placing distances only within an interval whose upper and lower ends are within a factor 𝛼 > 1 of each other; the actual distances are chosen adversarially. However, some voters chosen uniformly at random are correctly informed, meaning that they correctly perceive their own distances to the alternatives. We evaluate the quality of the selected alternative using the framework of metric distortion: the worst-case ratio between the voters’ average distance to the chosen alternative and their average distance to the optimal alternative. The key aspect we seek to understand is whether and to what extent the ability of poorly informed voters to delegate their votes to somewhat like-minded informed voters might reduce the distortion. Note that delegation trades off the benefit of having the vote cast by a more informed voter with the risk that this voter might have different preferences. Without any delegation, the distortion can be as large as Θ(𝛼). Our main result is that whenever the social network is approximately regular, the ability of poorly informed voters to delegate their vote to an informed voter reduces the worst-case distortion to 𝑂 (√︁𝛼)) , and this bound is tight. Thus, vote delegation has the potential to significantly reduce social cost.