Academic
Publications
Asymptotically optimal strategy-proof mechanisms for two-facility games

Asymptotically optimal strategy-proof mechanisms for two-facility games,10.1145/1807342.1807393,Pinyan Lu,Xiaorui Sun,Yajun Wang,Zeyuan Allen Zhu

Asymptotically optimal strategy-proof mechanisms for two-facility games   (Citations: 5)
BibTex | RIS | RefWorks Download
We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration. This setting was first studied by Procaccia and Tennenholtz [21]. They focused on the facility game where agents and facilities are located on the real line. Alon et al. studied the mechanisms for the facility games in a general metric space [1]. However, they focused on the games with only one facility. In this paper, we study the two-facility game in a general metric space, which extends both previous models. We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds [21, 17]. Notice that there is a matching linear upper bound in the line metric space [21]. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space.
Conference: ACM Conference on Electronic Commerce - EC , pp. 315-324, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In the eld of Algorithmic Game Theory, there has been a signicant recent interest in approximate strategyproof and group strategyproof mechanisms for Facility Location Games, where a number of facilities are placed in a metric space based on the preferences of strategic agents (see e.g., [37, 30, 29, 20])...
    • ...Therefore, recent work mostly focuses on the approximability of some simple special cases of k-Median, such as 1-Median on general metrics and 2-Median on the line, by deterministic and randomized strategyproof mechanisms (see e.g., [37, 30, 29])...

    Dimitris Fotakis. Online and incremental algorithms for facility location

    • ...[19,1,11,10,18]). The related work in Social Choice mostly focuses on locating a single facility on the real line, where the agents’ preferences are single-peaked...
    • ...For locating two facilities on the line, Lu, Sun, Wang, and Zhu [10] improved the lower bound for deterministic 236 D. Fotakis and C. Tzamos...
    • ...In contrast to the observation of [10] that the Proportional Mechanism is not strategyproof for more than two facilities, we prove that its winner-imposing version is strategyproof for any number of facilities (cf...
    • ...Lemma 5). Notably, its approximation ratio is exponentially better than the lower bound of [10, Theorem 3.7] on the best ratio achievable by deterministic strategyproof mechanisms for the 2-Facility Location game on the line...
    • ...We consider the winner-imposing version of the Proportional Mechanism [10] for the k-Facility Location game...
    • ...Strategyproofness. Even though the non-imposing version of the Proportional Mechanism is not strategyproof for k ≥ 3 [10], WIProp is strategyproof for any k...
    • ...Approximation Ratio. To establish the approximation ratio, we extend the ideas of [10, Theorem 4.2] to the case where k ≥ 3...

    Dimitris Fotakiset al. Winner-Imposing Strategyproof Mechanisms for Multiple Facility Locatio...

    • ...Some of our results were improved and generalized in two papers by Lu, Wang, and Zhou [33] and Lu et al. [32]...
    • ...The gap between this result and the lower bound given by Theorem 4.1 is still huge; this gap was very recently closed by Lu et al. [32] (see Section 4.3)...
    • ...Our lower bound was improved to 2 by Lu, Wang, and Zhou [33], and was very recently improved again to (n 1)=2 by Lu et al. [32]...
    • ...Lu et al. [32] complement their deterministic SP lower bound with a surprising randomized SP upper bound of 4, which is obtained via a natural mechanism...
    • ...However, the intuitions behind the positive results given in this section (that is, Theorems 4.3 and 4.5), as well as the randomized mechanism of Lu et al. [32], already collapse even with respect to three facilities...
    • ...Subsequent papers have considered some of the natural extensions of our model, including the setting where the agents are located on a graph or even a general metric space [1, 32]...
    • ...Section 4.1]. Furthermore, it is possible to consider almost any combination of the extensions, e.g., a domain in which agents control multiple locations (as in Section 5) and two facilities must be located (as in Section 4). However, the most challenging technical problem is the extension of the results of Section 4, as well as the subsequent results of [33, 32], to settings with three facilities and beyond...

    Ariel D. Procacciaet al. Approximate mechanism design without money

    • ...Note that Procaccia and Tennenholtz [25], and also subsequent papers [21, 22, 1], deal with a completely different domain, namely facility location...

    Noga Alonet al. Sum of Us: Strategyproof Selection from the Selectors

    • ...Recently, Lu et al. [3] improved the lower bound for deterministic strategy-proof mechanisms to n−1 2 and designed a 4-approximation randomized mechanism in general metric spaces...
    • ...We use the same definitions and notions as in [3]...

    Yukun Chenget al. Mechanisms for Obnoxious Facility Game on a Path

Sort by: