In Defense of Bureaucracy in the Metric Facility Location Problem

Details In Defense of Bureaucracy in the Metric Facility Location Problem In Defense of Bureaucracy in the Metric Facility Location Problem

2012-02-06

arxiv.org/abs/1202.1231v2

Computer Science

Computer Science and Game Theory

This paper has been withdrawn by the authors. Very similar results were obtained earlier in http://www.softlab.ntua.gr/~fotaki

Scientific paper

Our work is devoted to the metric facility location problem and addresses the selfish behavior of the players. It contributes to the line of work initiated by Procaccia and Tennenholtz [EC09] on approximate mechanism design without money. We explore and argue for an intuitive and simple rule of complexity O(nk),a so-called proportionality mechanism. The mechanism works in k consecutive rounds,each time choosing a random player at whose position to place the next facility; each time the probabilities of players to be picked are distributed proportionally to their distances to the current set of the facilities. Lu et al. [EC10] showed that the proportionality rule is incentive compatible for k=1,2, but fails to be so for k>2. We tweak the model slightly such that for any k, the proportionality mechanism becomes incentive compatible. In the new model we allow the government to be bureaucratic, i.e., to have the power of to force each player to choose from only a specific set of available facilities. In the proportionality mechanism, we force every player that receives a facility at his reported location to connect to exactly that facility. We extend the proportionality mechanism to a more general setting with a private network of facilities already present in the metric space and show that it is truthful as well. We further show that for any fixed k, the proportionality rule achieves in expectation a constant approximation guarantee to the optimal solution; namely at most a ratio of 4k. On the other hand, we show a lower bound of ln k(1+o(1)), and we suspect the truth to be closer to this lower bound. Thus, our work is the first among those on incentive compatible facility location that treats effectively (with a constant factor of approximation) the general case of an arbitrary number of facilities.

Affiliated with

Also associated with

No associations

Rating

In Defense of Bureaucracy in the Metric Facility Location Problem 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 In Defense of Bureaucracy in the Metric Facility Location Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and In Defense of Bureaucracy in the Metric Facility Location Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119986