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