The Distortion of Distributed Metric Social Choice

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

doi:10.1007/978-3-030-94676-0_26

The Distortion of Distributed Metric Social Choice

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings
Editors	Michal Feldman, Hu Fu, Inbal Talgam-Cohen
Place of Publication	Cham
Publisher	Springer
Pages	467-485
Number of pages	19
ISBN (Electronic)	978-3-030-94676-0
ISBN (Print)	978-3-030-94675-3
DOIs	https://doi.org/10.1007/978-3-030-94676-0_26
Publication status	Published - 20 Jan 2022
Event	The 17th Conference on Web and Internet Economics, 2021 - Online Duration: 14 Dec 2021 → 17 Dec 2021 Conference number: 17 https://hpi.de/wine2021/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Volume	13112
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 17th Conference on Web and Internet Economics, 2021
Abbreviated title	WINE 2021
Period	14/12/21 → 17/12/21
Internet address	https://hpi.de/wine2021/

Access to Document

10.1007/978-3-030-94676-0_26Licence: All Rights Reserved

https://link.springer.com/chapter/10.1007/978-3-030-94676-0_26Licence: All Rights Reserved

Cite this

Anshelevich, E., Filos-Ratsikas, A., & Voudouris, A. A. (2022). The Distortion of Distributed Metric Social Choice. In M. Feldman, H. Fu, & I. Talgam-Cohen (Eds.), Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings (pp. 467-485). (Lecture Notes in Computer Science; Vol. 13112). Springer. https://doi.org/10.1007/978-3-030-94676-0_26

Anshelevich, Elliot ; Filos-Ratsikas, Aris ; Voudouris, Alexandros A. / The Distortion of Distributed Metric Social Choice. Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings. editor / Michal Feldman ; Hu Fu ; Inbal Talgam-Cohen. Cham : Springer, 2022. pp. 467-485 (Lecture Notes in Computer Science).

@inproceedings{c3294a4432464554beb79ffc444a2a6c,

title = "The Distortion of Distributed Metric Social Choice",

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.",

author = "Elliot Anshelevich and Aris Filos-Ratsikas and Voudouris, {Alexandros A.}",

note = "Funding Information: This work was partially supported by NSF awards CCF-1527497 and CCF-2006286. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; The 17th Conference on Web and Internet Economics, 2021, WINE 2021 ; Conference date: 14-12-2021 Through 17-12-2021",

year = "2022",

month = jan,

day = "20",

doi = "10.1007/978-3-030-94676-0_26",

language = "English",

isbn = "978-3-030-94675-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "467--485",

editor = "Michal Feldman and Hu Fu and Inbal Talgam-Cohen",

booktitle = "Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings",

address = "United Kingdom",

url = "https://hpi.de/wine2021/",

}

Anshelevich, E, Filos-Ratsikas, A & Voudouris, AA 2022, The Distortion of Distributed Metric Social Choice. in M Feldman, H Fu & I Talgam-Cohen (eds), Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings. Lecture Notes in Computer Science, vol. 13112, Springer, Cham, pp. 467-485, The 17th Conference on Web and Internet Economics, 2021, 14/12/21. https://doi.org/10.1007/978-3-030-94676-0_26

The Distortion of Distributed Metric Social Choice. / Anshelevich, Elliot; Filos-Ratsikas, Aris; Voudouris, Alexandros A.
Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings. ed. / Michal Feldman; Hu Fu; Inbal Talgam-Cohen. Cham: Springer, 2022. p. 467-485 (Lecture Notes in Computer Science; Vol. 13112).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The Distortion of Distributed Metric Social Choice

AU - Anshelevich, Elliot

AU - Filos-Ratsikas, Aris

AU - Voudouris, Alexandros A.

N1 - Conference code: 17

PY - 2022/1/20

Y1 - 2022/1/20

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-94676-0_26

DO - 10.1007/978-3-030-94676-0_26

M3 - Conference contribution

SN - 978-3-030-94675-3

T3 - Lecture Notes in Computer Science

SP - 467

EP - 485

BT - Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings

A2 - Feldman, Michal

A2 - Fu, Hu

A2 - Talgam-Cohen, Inbal

PB - Springer

CY - Cham

T2 - The 17th Conference on Web and Internet Economics, 2021

Y2 - 14 December 2021 through 17 December 2021

ER -