View in EDS

Winner-imposing strategyproof mechanisms for multiple Facility Location games

Saved in:
Bibliographic Details
Title: Winner-imposing strategyproof mechanisms for multiple Facility Location games
Authors: Fotakis, Dimitris1 fotakis@cs.ntua.gr, Tzamos, Christos2 tzamos@mit.edu
Source: Theoretical Computer Science. Feb2013, Vol. 472, p90-103. 14p.
Subjects: Facility location problems, Metric spaces, Approximation theory, Algorithms, Cost control, Computer networks, Artificial Intelligence (Book : Berlatsky), Proportional control systems
Abstract: Abstract: 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 -Facility Location and Facility Location with a uniform facility opening cost, instead of a bound of 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 Lu et al. (2010) [18], is stategyproof for the -Facility Location game, and achieves an approximation ratio of at most , for any . For the Facility Location game, we show that the winner-imposing version of the randomized online algorithm of Meyerson (2001) [21], which has an approximation ratio of , is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof -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. [Copyright &y& Elsevier]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Abstract: 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 -Facility Location and Facility Location with a uniform facility opening cost, instead of a bound of 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 Lu et al. (2010) [18], is stategyproof for the -Facility Location game, and achieves an approximation ratio of at most , for any . For the Facility Location game, we show that the winner-imposing version of the randomized online algorithm of Meyerson (2001) [21], which has an approximation ratio of , is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof -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. [Copyright &y& Elsevier]
ISSN:03043975
DOI:10.1016/j.tcs.2012.11.036