Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective

Details Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective

2011-08-08

arxiv.org/abs/1108.1762v2

Computer Science

Computer Science and Game Theory

17 pages. 6 of them in appendix and references

Scientific paper

We consider the problem of locating a public facility on a line, where a set of $n$ strategic agents report their \emph{locations} and a mechanism determines, either deterministically or randomly, the location of the facility. Game theoretic perspectives of the facility location problem advanced in two main directions. The first direction is concerned with the characterization of \emph{strategyproof} (SP) mechanisms; i.e., mechanisms that induce truthful reporting as a dominant strategy; and the second direction quantifies how well various objective functions can be approximated when restricted to SP mechanisms. The current paper provides contributions in both directions. First, we construct a parameterized randomized SP mechanism, and show that all of the previously proposed deterministic and randomized SP mechanisms for the current settings can be formalized as special cases of this mechanism. Second, we give tight results for the approximation ratio of SP mechanisms with respect to the objective of minimizing the sum of squares of distances to the agents (\emph{miniSOS}). Holzman \cite{Holzman1990} provided an axiomatic foundation for this function, showing that it is the unique function that satisfies unanimity, continuity and invariance. We devise a randomized mechanism that gives a 1.5-approximation for the miniSOS function, and show that no other randomized SP mechanism can provide a better approximation. This mechanism chooses the average location with probability 1/2 and a \emph{random dictator} with probability 1/2. For deterministic mechanisms, we show that the median mechanism provides a 2-approximation, and this is tight. Together, our study provides fundamental understanding of the miniSOS objective function and makes a step toward the characterization of randomized SP facility location mechanisms.

Affiliated with

Also associated with

No associations

Rating

Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-190578