Winner-imposing strategyproof mechanisms for multiple facility location games.(English)Zbl 1282.91126

Summary: We study facility location games, where a number of facilities are placed in a metric space based on locations reported by strategic agents. A mechanism maps the agents’ locations to a set of facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may even misreport their location. We are interested in mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and approximate the optimal social cost. We focus on the closely related problems of $$k$$-facility location and facility location with a uniform facility opening cost, instead of a bound of $$k$$ on the number of facilities. In the former, the social cost is the agents’ total connection cost, while in the latter, the social cost is the sum of the total connection cost and the total facility opening cost.
We mostly study mechanisms that are winner-imposing, in the sense that they allocate facilities to agents and require that each agent allocated a facility should connect to it. We prove that the winner-imposing version of the proportional mechanism, proposed by P. Lu et al. [in: Proceedings of the 11th ACM Conference on Electronic Commerce, 315–324, ACM, New York (2010; doi:10.1145/1807342.1807393)], is stategyproof for the $$k$$-facility location game, and achieves an approximation ratio of at most $$4k$$, for any $$k \geq 1$$. For the facility location game, we show that the winner-imposing version of the randomized online algorithm of A. Meyerson [“Online facility location”, in: 42nd IEEE Symposium on foundations of computer science (Las Vegas, NV, 2001), 426–431, IEEE Computer Soc., Los Alamitos, CA (2001)], which has an approximation ratio of 8, is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof $$O(\log n)$$-approximate mechanism for the facility location game on the line. We also consider oblivious winner-imposing mechanisms for location games on continuous metric spaces, and show that they are strategyproof iff they are locally strategyproof, i.e. no agent can benefit by reporting a location arbitrarily close to her true location.

MSC:

 91B32 Resource and cost allocation (including fair division, apportionment, etc.) 90B80 Discrete location and assignment 91A80 Applications of game theory 68W25 Approximation algorithms
Full Text: