Name
Title | ||
|---|---|---|
Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs |
Abstract | ||
|---|---|---|
AbstractThis paper is concerned with the problem of locating a facility on a line in the presence of strategic agents, also located on that line. Each agent incurs a cost equal to her distance to the facility whereas the planner wishes to minimize the Lp norm of the vector of agent costs. The location of each agent is only privately known, and the goal is to design a strategyproof mechanism that approximates the optimal cost well. It is shown that the median mechanism provides a 21-1/p approximation ratio, and that this is the optimal approximation ratio among all deterministic strategyproof mechanisms. For randomized mechanisms, two results are shown: First, for any integer p larger than 2, no mechanism-from a rather large class of randomized mechanisms-has an approximation ratio better than that of the median mechanism. This is in contrast to the case of p = 2 and p = ∞ where a randomized mechanism provably helps improve the worst case approximation ratio. Second, for the case of 2 agents, the Left-Right-Middle LRM mechanism, first designed by Procaccia and Tennenholtz for the special case of infinity norm, provides the optimal approximation ratio among all randomized mechanisms. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1287/moor.2016.0810 | Periodicals |
Keywords | DocType | Volume |
mechanism design,approximation,facility location,randomized algorithms,median | Journal | 42 |
Issue | ISSN | Citations |
2 | 0364-765X | 1 |
PageRank | References | Authors |
0.37 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Itai Feigenbaum | 1 | 7 | 2.40 |
| Jay Sethuraman | 2 | 439 | 42.32 |
| C. Ye | 3 | 5 | 1.24 |