Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Algorithmic Mechanism Design
Asymptotic Optimality
Game Theory
Generalized Metric Space
Is Strategy
Metric Space
Randomized Algorithm
Social Choice
Upper Bound
Lower Bound
Subscribe
Academic
Publications
Asymptotically optimal strategyproof mechanisms for twofacility games
Asymptotically optimal strategyproof mechanisms for twofacility games,10.1145/1807342.1807393,Pinyan Lu,Xiaorui Sun,Yajun Wang,Zeyuan Allen Zhu
Edit
Asymptotically optimal strategyproof mechanisms for twofacility games
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Pinyan Lu
,
Xiaorui Sun
,
Yajun Wang
,
Zeyuan Allen Zhu
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 strategyproof 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 strategyproof 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 twofacility 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 strategyproof 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 strategyproof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategyproof 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. 315324, 2010
DOI:
10.1145/1807342.1807393
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.
(
portal.acm.org
)
(
portal.acm.org
)
(
research.microsoft.com
)
(
research.microsoft.com
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(5)
...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 kMedian, such as 1Median on general metrics and 2Median 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 singlepeaked...
...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 winnerimposing 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 2Facility Location game on the line...
...We consider the winnerimposing version of the Proportional Mechanism [
10
] for the kFacility Location game...
...Strategyproofness. Even though the nonimposing 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 Fotakis
,
et al.
WinnerImposing 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. Procaccia
,
et 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 Alon
,
et al.
Sum of Us: Strategyproof Selection from the Selectors
...Recently, Lu et al. [
3
] improved the lower bound for deterministic strategyproof mechanisms to n−1 2 and designed a 4approximation randomized mechanism in general metric spaces...
...We use the same definitions and notions as in [
3
]...
Yukun Cheng
,
et al.
Mechanisms for Obnoxious Facility Game on a Path
References
(28)
Strategyproof Approximation Mechanisms for Location on Networks
(
Citations: 7
)
Noga Alon
,
Michal Feldman
,
Ariel D. Procaccia
,
Moshe Tennenholtz
Journal:
Computing Research Repository  CORR
, vol. abs/0907.2, 2009
Truthful Mechanisms for OneParameter Agents
(
Citations: 224
)
Aaron Archer
,
Éva Tardos
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 482491, 2001
An introduction to strategyproof social choice functions
(
Citations: 49
)
Salvador Barberà
Journal:
Social Choice and Welfare  SOC CHOICE WELFARE
, vol. 18, no. 4, pp. 619653, 2001
A characterization of strategyproof social choice functions for economies with pure public goods
(
Citations: 58
)
Salvador Barberà
,
Matthew Jackson
Journal:
Social Choice and Welfare  SOC CHOICE WELFARE
, vol. 11, no. 3, pp. 241252, 1994
Strategyproof voting schemes with continuous preferences
(
Citations: 62
)
S. Barberfi
,
B. Peleg
Journal:
Social Choice and Welfare  SOC CHOICE WELFARE
, vol. 7, no. 1, pp. 3138, 1990
Sort by:
Citations
(5)
Online and incremental algorithms for facility location
Dimitris Fotakis
Journal:
Sigact News  SIGACT
, vol. 42, no. 1, pp. 97131, 2011
WinnerImposing Strategyproof Mechanisms for Multiple Facility Location Games
(
Citations: 1
)
Dimitris Fotakis
,
Christos Tzamos
Conference:
Workshop on Internet and Network Economics  WINE
, pp. 234245, 2010
Approximate mechanism design without money
(
Citations: 26
)
Ariel D. Procaccia
,
Moshe Tennenholtz
Conference:
ACM Conference on Electronic Commerce  EC
, pp. 177186, 2009
Sum of Us: Strategyproof Selection from the Selectors
(
Citations: 3
)
Noga Alon
,
Felix A. Fischer
,
Ariel D. Procaccia
,
Moshe Tennenholtz
Journal:
Computing Research Repository  CORR
, vol. abs/0910.4, 2009
Mechanisms for Obnoxious Facility Game on a Path
Yukun Cheng
,
Wei Yu
,
Guochuan Zhang