Filos-Ratsikas, Aris and Voudouris, Alexandros (2024) Revisiting the distortion of distributed voting. Theory of Computing Systems, 68 (5). pp. 1138-1159. DOI https://doi.org/10.1007/s00224-024-10171-1
Filos-Ratsikas, Aris and Voudouris, Alexandros (2024) Revisiting the distortion of distributed voting. Theory of Computing Systems, 68 (5). pp. 1138-1159. DOI https://doi.org/10.1007/s00224-024-10171-1
Filos-Ratsikas, Aris and Voudouris, Alexandros (2024) Revisiting the distortion of distributed voting. Theory of Computing Systems, 68 (5). pp. 1138-1159. DOI https://doi.org/10.1007/s00224-024-10171-1
Abstract
We consider a setting with agents that have preferences over alternatives and are partitioned into disjoint districts. The goal is to choose one alternative as the winner using a mechanism which first decides a representative alternative for each district based on a local election with the agents therein as participants, and then chooses one of the district representatives as the winner. Previous work showed bounds on the distortion of a specific class of deterministic plurality-based mechanisms depending on the available information about the preferences of the agents in the districts. In this paper, we first consider the whole class of deterministic mechanisms and show asymptotically tight bounds on their distortion. We then initiate the study of the distortion of randomized mechanisms in distributed voting and show bounds based on several informational assumptions, which in many cases turn out to be tight. Finally, we also experimentally compare the distortion of many different mechanisms of interest using synthetic and real-world data.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Distortion; Districts; Mechanism design; Randomization |
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: | 12 Apr 2024 14:56 |
Last Modified: | 08 Nov 2024 16:01 |
URI: | http://repository.essex.ac.uk/id/eprint/38079 |
Available files
Filename: s00224-024-10171-1.pdf
Licence: Creative Commons: Attribution 4.0