Anshelevich, Elliot and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) The distortion of distributed metric social choice. Artificial Intelligence, 308. p. 103713. DOI https://doi.org/10.1016/j.artint.2022.103713
Anshelevich, Elliot and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) The distortion of distributed metric social choice. Artificial Intelligence, 308. p. 103713. DOI https://doi.org/10.1016/j.artint.2022.103713
Anshelevich, Elliot and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) The distortion of distributed metric social choice. Artificial Intelligence, 308. p. 103713. DOI https://doi.org/10.1016/j.artint.2022.103713
Abstract
We consider a social choice setting with agents that are partitioned into disjoint groups, and have metric preferences over a set of alternatives. Our goal is to choose a single alternative aiming to optimize various objectives that are functions of the distances between agents and alternatives in the metric space, under the constraint that this choice must be made in a distributed way: The preferences of the agents within each group are first aggregated into a representative alternative for the group, and then these group representatives are aggregated into the final winner. Deciding the winner in such a way naturally leads to loss of efficiency, even when complete information about the metric space is available. We provide a series of (mostly tight) bounds on the distortion of distributed mechanisms for variations of well-known objectives, such as the (average) total cost and the maximum cost, and also for new objectives that are particularly appropriate for this distributed setting and have not been studied before.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Social choice; Distortion; Mechanism design |
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: | 08 Apr 2022 13:52 |
Last Modified: | 30 Oct 2024 16:32 |
URI: | http://repository.essex.ac.uk/id/eprint/32614 |
Available files
Filename: 1-s2.0-S0004370222000534-main.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0