Filos-Ratsikas, Aris 
ORCID: 0000-0001-7868-8114 and Voudouris, Alexandros A
(2021)
Approximate mechanism design for distributed facility location.
In: Symposium on Algorithmic Game Theory, Aarhus, Denmark.
|
Text
2007.06304v3.pdf - Author Accepted Manuscript Download (410kB) | Preview |
Abstract
We consider a single-facility location problem, where agents are positioned on the real line and are partitioned into multiple disjoint districts. The goal is to choose a location (where a public facility is to be built) so as to minimize the total distance of the agents from it. This process is distributed: the positions of the agents in each district are first aggregated into a representative location for the district, and then one of the district representatives is chosen as the facility location. This indirect access to the positions of the agents inevitably leads to inefficiency, which is captured by the notion of distortion. We study the discrete version of the problem, where the set of alternative locations is finite, as well as the continuous one, where every point of the line is an alternative, and paint an almost complete picture of the distortion landscape of both general and strategyproof distributed mechanisms.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | cs.GT, cs.GT |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Mar 2022 09:12 |
| Last Modified: | 18 Jan 2023 21:11 |
| DOI: | 10.1007/978-3-030-85947-3_4 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3150123 |
Dimensions
Dimensions
