Revisiting the Distortion of Distributed Voting

Aris Filos-Ratsikas, Alexandros A. Voudouris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems
Place of PublicationRichland, SC
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems
Pages1391–1399
Number of pages18
ISBN (Electronic)9781450394321
DOIs
Publication statusPublished - 30 May 2023
EventThe 22nd International Conference on Autonomous Agents and Multiagent Systems, 2023 - London, United Kingdom
Duration: 29 May 20232 Jun 2023
Conference number: 22
https://aamas2023.soton.ac.uk/

Conference

ConferenceThe 22nd International Conference on Autonomous Agents and Multiagent Systems, 2023
Abbreviated titleAAMAS 2023
Country/TerritoryUnited Kingdom
CityLondon
Period29/05/232/06/23
Internet address

Fingerprint

Dive into the research topics of 'Revisiting the Distortion of Distributed Voting'. Together they form a unique fingerprint.

Cite this