Strategyproof facility location for concave cost functions
From MaRDI portal
Publication:334934
DOI10.1007/S00453-015-0026-6zbMATH Open1348.91198DBLPjournals/algorithmica/FotakisT16arXiv1305.3333OpenAlexW1129656128WikidataQ59818366 ScholiaQ59818366MaRDI QIDQ334934FDOQ334934
Authors: Dimitris Fotakis, Christos Tzamos 
Publication date: 1 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Abstract: We consider k-Facility Location games, where n strategic agents report their locations on the real line, and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost, which is group strategyproof and achieves a bounded approximation ratio for all k and n, for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost. To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with k > 2 facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k. On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser, which applies to instances with k facilities and n = k+1 agents, and for any given concave cost function, is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost.
Full work available at URL: https://arxiv.org/abs/1305.3333
Recommendations
- Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs
- Strategy-proof mechanisms for facility location games with many facilities
- On the power of deterministic mechanisms for facility location games
- Winner-imposing strategyproof mechanisms for multiple facility location games
- Constrained heterogeneous facility location games with max-variant cost
Social choice (91B14) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Discrete location and assignment (90B80)
Cites Work
- Title not available (Why is that?)
- Algorithmic Game Theory
- Winner-imposing strategyproof mechanisms for multiple facility location games
- Approximately optimal mechanism design via differential privacy
- Strategyproof approximation of the minimax on networks
- Strategy-proof location on a network
- Locating libraries on a street
- An introduction to strategy-proof social choice functions
- Scheduling without payments
- Strategy-proof mechanisms for facility location games with many facilities
- On the power of deterministic mechanisms for facility location games
Cited In (22)
- The capacity constrained facility location problem
- Characterization of truthful mechanisms for one-dimensional single facility location game with payments
- Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs
- Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
- Approximation strategy-proof mechanisms for obnoxious facility location on a line
- Mechanism design with strategic mediators
- Strategyproof mechanisms for \(2\)-facility location games with minimax envy
- Strategyproof mechanisms for 2-facility location games with minimax envy
- Strategy-proof mechanism for obnoxious facility location on a line
- Strategyproof facility location for three agents on a circle
- Strategyproof approximation of the minimax on networks
- Facility location games with distinct desires
- Winner-imposing strategyproof mechanisms for multiple facility location games
- Strategyproof facility location in perturbation stable instances
- Truthful two-facility location with candidate locations
- Optimal group manipulation in facility location problems
- The distortion of distributed facility location
- Heterogeneous facility location with limited resources
- Mechanism design for facility location with fractional preferences and minimum distance
- Strategy-proof mechanisms for facility location games with many facilities
- On the power of deterministic mechanisms for facility location games
- Truthful two-facility location with candidate locations
Uses Software
This page was built for publication: Strategyproof facility location for concave cost functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334934)
