Worst-Case Voting When the Stakes Are High
Keywords:Game Theory And Economic Paradigms (GTEP)
AbstractWe 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.
How to Cite
Kahng, A., & Kehne, G. (2022). Worst-Case Voting When the Stakes Are High. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5100-5107. https://doi.org/10.1609/aaai.v36i5.20443
AAAI Technical Track on Game Theory and Economic Paradigms