2023/07/14 by Ioannis Caragiannis, Caragiannis, Ioannis, Karl Fehrs +1 · 1 citation
Social Sciences · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Political Conflict and Governance #Political Systems and Governance
paper · doi:10.48550/arxiv.2307.07350
openalex publication_date 2023/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\em Distortion is a well-established notion for quantifying the loss of social welfare that may occur in voting. As voting rules take as input only ordinal information, they are essentially forced to neglect the exact values the agents have for the alternatives. Thus, in worst-case electorates, voting rules may return low social welfare alternatives and have high distortion. Accompanying voting rules with a small number of cardinal queries per agent may reduce distortion considerably. To explore distortion beyond worst-case conditions, we use a simple stochastic model according to which the values the agents have for the alternatives are drawn independently from a common probability distribution. This gives rise to so-called \em impartial culture electorates. We refine the definition of distortion so that it is suitable for this stochastic setting and show that, rather surprisingly, all voting rules have high distortion \em on average. On the positive side, for the fundamental case where the agents have random \em binary values for the alternatives, we present a mechanism that achieves approximately optimal average distortion by making a \em single cardinal query per agent. This enables us to obtain slightly suboptimal average distortion bounds for general distributions using a simple randomized mechanism that makes one query per agent. We complement these results by presenting new tradeoffs between the distortion and the number of queries per agent in the traditional worst-case setting.