Caragiannis, Ioannis and Shah, Nisarg and Voudouris, Alexandros A (2022) The metric distortion of multiwinner voting. Artificial Intelligence, 313. p. 103802. DOI https://doi.org/10.1016/j.artint.2022.103802
Caragiannis, Ioannis and Shah, Nisarg and Voudouris, Alexandros A (2022) The metric distortion of multiwinner voting. Artificial Intelligence, 313. p. 103802. DOI https://doi.org/10.1016/j.artint.2022.103802
Caragiannis, Ioannis and Shah, Nisarg and Voudouris, Alexandros A (2022) The metric distortion of multiwinner voting. Artificial Intelligence, 313. p. 103802. DOI https://doi.org/10.1016/j.artint.2022.103802
Abstract
We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the q-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: The distortion is unbounded when q≤k/3, asymptotically linear in the number of agents when k/3<q≤k/2, and constant when q>k/2
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Distortion; Mutliwinner voting; Social choice |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 11 Oct 2022 08:40 |
Last Modified: | 30 Oct 2024 20:52 |
URI: | http://repository.essex.ac.uk/id/eprint/33648 |
Available files
Filename: 1-s2.0-S0004370222001424-main.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0