Optimized Distortion and Proportional Fairness in Voting

Soroush Ebadian, Anson Kahng, Dominik Peters () and Nisarg Shah
Additional contact information
Soroush Ebadian: DCS - Department of Computer Science [University of Toronto] - University of Toronto
Anson Kahng: Department of Computer Science [Rochester] - University of Rochester [USA]
Dominik Peters: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique
Nisarg Shah: DCS - Department of Computer Science [University of Toronto] - University of Toronto

Post-Print from HAL

Abstract: A voting rule decides on a probability distribution over a set of m alternatives, based on rankings of those alternatives provided by agents. We assume that agents have cardinal utility functions over the alternatives, but voting rules have access to only the rankings induced by these utilities. We evaluate how well voting rules do on measures of social welfare and of proportional fairness, computed based on the hidden utility functions. In particular, we study the distortion of voting rules, which is a worst-case measure. It is an approximation ratio comparing the utilitarian social welfare of the optimum outcome to the social welfare produced by the outcome selected by the voting rule, in the worst case over possible input profiles and utility functions that are consistent with the input. The previous literature has studied distortion with unit-sum utility functions (which are normalized to sum to 1), and left a small asymptotic gap in the best possible distortion. Using tools from the theory of fair multi-winner elections, we propose the first voting rule which achieves the optimal distortion Θ(√ m) for unit-sum utilities. Our voting rule also achieves optimum Θ(√ m) distortion for a larger class of utilities, including unit-range and approval (0/1) utilities. We then take a similar worst-case approach to a quantitative measure of the fairness of a voting rule, called proportional fairness. Informally, it measures whether the influence of cohesive groups of agents on the voting outcome is proportional to the group size. We show that there is a voting rule which, without knowledge of the utilities, can achieve an O(log m)-approximation to proportional fairness, which is the best possible approximation. As a consequence of its proportional fairness, we show that this voting rule achieves O(log m) distortion with respect to the Nash welfare, and selects a distribution that is approximately stable by being an O(log m)-approximation to the core, making it interesting for applications in participatory budgeting.

Date: 2022-07
New Economics Papers: this item is included in nep-cdm, nep-des, nep-pol and nep-upt
Note: View the original document on HAL open archive server: https://hal.science/hal-03834512v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in EC '22: The 23rd ACM Conference on Economics and Computation, Jul 2022, Boulder, United States. pp.563-600, ⟨10.1145/3490486.3538339⟩

Downloads: (external link)
https://hal.science/hal-03834512v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-03834512

DOI: 10.1145/3490486.3538339

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().