Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L p Norm of Costs

Itai Feigenbaum (), Jay Sethuraman () and Chun Ye ()
Additional contact information
Itai Feigenbaum: Department of Mathematics and Computer Science, Lehman College, Bronx, New York 10468; Program in Computer Science, CUNY Graduate Center, New York, New York 10016
Jay Sethuraman: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Chun Ye: Amazon.com, Seattle, Washington 98109

Mathematics of Operations Research, 2017, vol. 42, issue 2, 434-447

Abstract: This 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 L p 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 2 1−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.

Keywords: mechanism design; approximation; facility location; randomized algorithms; median (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0810 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:2:p:434-447

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().