Approximate Mechanism Design for Distributed Facility Location

Aris Filos-Ratsikas, Alexandros A. Voudouris

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

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.
Original languageEnglish
Title of host publicationAlgorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021, Proceedings
EditorsIoannis Caragiannis, Kristoffer Arnsfelt Hansen
Place of PublicationCham
PublisherSpringer, Cham
Pages49-63
Number of pages15
ISBN (Electronic)978-3-030-85947-3
ISBN (Print)978-3-030-85946-6
DOIs
Publication statusPublished - 14 Sep 2021
EventThe 14th International Symposium on Algorithmic Game Theory, 2021 - Aarhus, Denmark
Duration: 21 Sep 202124 Sep 2021
Conference number: 14
https://events.au.dk/sagt2021/

Publication series

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

Conference

ConferenceThe 14th International Symposium on Algorithmic Game Theory, 2021
Abbreviated titleSAGT 2021
Country/TerritoryDenmark
CityAarhus
Period21/09/2124/09/21
Internet address

Keywords

  • Facility location
  • Mechanism design
  • Distortion

Fingerprint

Dive into the research topics of 'Approximate Mechanism Design for Distributed Facility Location'. Together they form a unique fingerprint.

Cite this