Strategyproof facility location for concave cost functions
From MaRDI portal
Publication:334934
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.
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
Cites work
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- Algorithmic Game Theory
- An introduction to strategy-proof social choice functions
- Approximately optimal mechanism design via differential privacy
- Locating libraries on a street
- On the power of deterministic mechanisms for facility location games
- Scheduling without payments
- Strategy-proof location on a network
- Strategy-proof mechanisms for facility location games with many facilities
- Strategyproof approximation of the minimax on networks
- Winner-imposing strategyproof mechanisms for multiple facility location games
Cited in
(22)- Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs
- Strategyproof approximation of the minimax on networks
- The capacity constrained facility location problem
- Strategyproof mechanisms for 2-facility location games with minimax envy
- Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
- Winner-imposing strategyproof mechanisms for multiple facility location games
- The distortion of distributed facility location
- Truthful two-facility location with candidate locations
- Characterization of truthful mechanisms for one-dimensional single facility location game with payments
- Truthful two-facility location with candidate locations
- Strategy-proof mechanisms for facility location games with many facilities
- Strategy-proof mechanism for obnoxious facility location on a line
- Strategyproof mechanisms for \(2\)-facility location games with minimax envy
- Facility location games with distinct desires
- Heterogeneous facility location with limited resources
- Approximation strategy-proof mechanisms for obnoxious facility location on a line
- Strategyproof facility location for three agents on a circle
- Mechanism design with strategic mediators
- On the power of deterministic mechanisms for facility location games
- Optimal group manipulation in facility location problems
- Strategyproof facility location in perturbation stable instances
- Mechanism design for facility location with fractional preferences and minimum distance
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)
