Dimensionality and Coordination in Voting: The Distortion of STV

Authors

  • Ioannis Anagnostides Carnegie Mellon University
  • Dimitris Fotakis National Technical University of Athens
  • Panagiotis Patsilinakos National Technical University of Athens

DOI:

https://doi.org/10.1609/aaai.v36i5.20404

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

We study the performance of voting mechanisms from a utilitarian standpoint, under the recently introduced framework of metric-distortion, offering new insights along two main lines. First, if d represents the doubling dimension of the metric space, we show that the distortion of STV is O(d log log m), where m represents the number of candidates. For doubling metrics this implies an exponential improvement over the lower bound for general metrics, and as a special case it effectively answers a question left open by Skowron and Elkind (AAAI '17) regarding the distortion of STV under low-dimensional Euclidean spaces. More broadly, this constitutes the first nexus between the performance of any voting rule and the ``intrinsic dimensionality'' of the underlying metric space. We also establish a nearly-matching lower bound, refining the construction of Skowron and Elkind. Moreover, motivated by the efficiency of STV, we investigate whether natural learning rules can lead to low-distortion outcomes. Specifically, we introduce simple, deterministic and decentralized exploration/exploitation dynamics, and we show that they converge to a candidate with O(1) distortion.

Downloads

Published

2022-06-28

How to Cite

Anagnostides, I., Fotakis, D., & Patsilinakos, P. (2022). Dimensionality and Coordination in Voting: The Distortion of STV. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4776-4784. https://doi.org/10.1609/aaai.v36i5.20404

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms