Worst-Case Voting When the Stakes are High

Anson Kahng, Gregory Kehne

[AAAI-22] Main Track
Abstract: We study the additive distortion of social choice functions in the implicit utilitarian model, and argue that it is a more appropriate metric than multiplicative distortion when an alternative that confers significant social welfare may exist (i.e., when the stakes are high). We define a randomized analog of positional scoring rules, and present a rule which is asymptotically optimal within this class as the number of alternatives increases. We then show that the instance-optimal social choice function can be efficiently computed. Next, we take a beyond-worst-case view, bounding the additive distortion of prominent voting rules as a function of the best welfare attainable in an instance. Lastly, we evaluate the additive distortion of a range of rules on real-world election data.

Introduction Video

Sessions where this paper appears

  • Poster Session 2

    Blue 6

  • Poster Session 11

    Blue 6