The Distortion of Distributed Metric Social Choice

Elliot Anshelevich, Aris Filos-Ratsikas, Alexandros A. Voudouris

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

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.
Original languageEnglish
Title of host publicationWeb and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings
EditorsMichal Feldman, Hu Fu, Inbal Talgam-Cohen
Place of PublicationCham
PublisherSpringer, Cham
Pages467-485
Number of pages19
ISBN (Electronic)978-3-030-94676-0
ISBN (Print)978-3-030-94675-3
DOIs
Publication statusPublished - 20 Jan 2022
EventThe 17th Conference on Web and Internet Economics, 2021 - Online
Duration: 14 Dec 202117 Dec 2021
Conference number: 17
https://hpi.de/wine2021/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume13112
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 17th Conference on Web and Internet Economics, 2021
Abbreviated titleWINE 2021
Period14/12/2117/12/21
Internet address

Fingerprint

Dive into the research topics of 'The Distortion of Distributed Metric Social Choice'. Together they form a unique fingerprint.

Cite this