2011/08/08 by Michal Feldman, Feldman, Michal, Yoav Wilf +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1108.1762
openalex publication_date 2011/08/08 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
We consider the problem of locating a public facility on a line, where a set\nof n strategic agents report their \locations and a mechanism\ndetermines, either deterministically or randomly, the location of the facility.\nGame theoretic perspectives of the facility location problem advanced in two\nmain directions. The first direction is concerned with the characterization of\n\strategyproof (SP) mechanisms; i.e., mechanisms that induce truthful\nreporting as a dominant strategy; and the second direction quantifies how well\nvarious objective functions can be approximated when restricted to SP\nmechanisms. The current paper provides contributions in both directions. First,\nwe construct a parameterized randomized SP mechanism, and show that all of the\npreviously proposed deterministic and randomized SP mechanisms for the current\nsettings can be formalized as special cases of this mechanism. Second, we give\ntight results for the approximation ratio of SP mechanisms with respect to the\nobjective of minimizing the sum of squares of distances to the agents\n(\miniSOS). Holzman citeHolzman1990 provided an axiomatic foundation\nfor this function, showing that it is the unique function that satisfies\nunanimity, continuity and invariance. We devise a randomized mechanism that\ngives a 1.5-approximation for the miniSOS function, and show that no other\nrandomized SP mechanism can provide a better approximation. This mechanism\nchooses the average location with probability 1/2 and a \random dictator\nwith probability 1/2. For deterministic mechanisms, we show that the median\nmechanism provides a 2-approximation, and this is tight. Together, our study\nprovides fundamental understanding of the miniSOS objective function and makes\na step toward the characterization of randomized SP facility location\nmechanisms.\n