Approximate mechanism design for distributed facility location

DOI10.1007/978-3-030-85947-3_4MaRDI QIDQ2670905zbMATH OpenOpenAlexFDO

Authors Aris Filos-Ratsikas, Alexandros A. Voudouris

Publication date 1 June 2022

Full work available at URL https://arxiv.org/abs/2007.06304

zbMATH Keywords

distortionfacility locationmechanism design

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Mechanism design theory (91B03)

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.

Recommendations

• On the power of deterministic mechanisms for facility location games
• Strategy-proof mechanisms for facility location games with many facilities
• Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L_p Norm of Costs
• The distortion of distributed metric social choice
• Approximation strategy-proof mechanisms for obnoxious facility location on a line

Cites work

• Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L_p Norm of Costs
• Approximating optimal social choice under metric preferences
• Heterogeneous facility location without money
• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• Mechanisms for obnoxious facility game on a path
• Obnoxious facility game with a bounded service range
• Optimal social choice functions: a utilitarian view
• Ordinal approximation for social choice, matching, and facility location problems given candidate positions
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Randomized social choice functions under metric preferences
• Strategy-proof location on a network
• Subset selection via implicit utilitarian voting
• The distortion of distributed voting
• Winner-imposing strategyproof mechanisms for multiple facility location games

Cited in

(17)

• Mechanism design for locating a facility under partial information
• scientific article; zbMATH DE number 7071987 (Why is no real title available?)
• Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L_p Norm of Costs
• The distortion of distributed metric social choice
• The distortion of distributed metric social choice
• Heterogeneous facility location with limited resources
• Tight distortion bounds for distributed metric voting on a line
• On Discrete Truthful Heterogeneous Two-Facility Location
• Truthful ownership transfer with expert advice
• The distortion of distributed facility location
• Truthful two-facility location with candidate locations
• Revisiting the distortion of distributed voting
• Mechanism design for building optimal bridges between regions
• Truthful two-facility location with candidate locations
• Improved metric distortion via threshold approvals
• Constrained distributed heterogeneous two-facility location problems with max-variant cost
• Constrained distributed heterogeneous two-facility location problems with max-variant cost

This page was built for publication: Approximate mechanism design for distributed facility location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670905)