Tighter bounds for facility games

Pinyan Lu, Yajun Wang, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In one dimensional facility games, public facilities are placed based on the reported locations of the agents, where all the locations of agents and facilities are on a real line. The cost of an agent is measured by the distance from its location to the nearest facility. We study the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location. In this paper, we use the total cost of agents as social welfare function. We study two extensions of the simplest version as in [9]: two facilities and multiple locations per agent. In both cases, we analyze randomized strategy-proof mechanisms, and give the first lower bound of 1.045 and 1.33, respectively. The latter lower bound is obtained by solving a related linear programming problem, and we believe that this new technique of proving lower bounds for randomized mechanisms may find applications in other problems and is of independent interest. We also improve several approximation bounds in [9], and confirm a conjecture in [9].

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - 5th International Workshop, WINE 2009, Proceedings
Pages137-148
Number of pages12
DOIs
StatePublished - Dec 1 2009
Externally publishedYes
Event5th International Workshop on Internet and Network Economics, WINE 2009 - Rome, Italy
Duration: Dec 14 2009Dec 18 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5929 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Workshop on Internet and Network Economics, WINE 2009
CountryItaly
CityRome
Period12/14/0912/18/09

Fingerprint

Game
Welfare
Lower bound
Costs
Approximation
Real Line
Linear programming
Strategy

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Lu, P., Wang, Y., & Zhou, Y. (2009). Tighter bounds for facility games. In Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings (pp. 137-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5929 LNCS). https://doi.org/10.1007/978-3-642-10841-9_14

Tighter bounds for facility games. / Lu, Pinyan; Wang, Yajun; Zhou, Yuan.

Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. 2009. p. 137-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5929 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lu, P, Wang, Y & Zhou, Y 2009, Tighter bounds for facility games. in Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5929 LNCS, pp. 137-148, 5th International Workshop on Internet and Network Economics, WINE 2009, Rome, Italy, 12/14/09. https://doi.org/10.1007/978-3-642-10841-9_14
Lu P, Wang Y, Zhou Y. Tighter bounds for facility games. In Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. 2009. p. 137-148. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-10841-9_14
Lu, Pinyan ; Wang, Yajun ; Zhou, Yuan. / Tighter bounds for facility games. Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. 2009. pp. 137-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f4640998020e4fc79b26b9a2f00affb2,
title = "Tighter bounds for facility games",
abstract = "In one dimensional facility games, public facilities are placed based on the reported locations of the agents, where all the locations of agents and facilities are on a real line. The cost of an agent is measured by the distance from its location to the nearest facility. We study the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location. In this paper, we use the total cost of agents as social welfare function. We study two extensions of the simplest version as in [9]: two facilities and multiple locations per agent. In both cases, we analyze randomized strategy-proof mechanisms, and give the first lower bound of 1.045 and 1.33, respectively. The latter lower bound is obtained by solving a related linear programming problem, and we believe that this new technique of proving lower bounds for randomized mechanisms may find applications in other problems and is of independent interest. We also improve several approximation bounds in [9], and confirm a conjecture in [9].",
author = "Pinyan Lu and Yajun Wang and Yuan Zhou",
year = "2009",
month = "12",
day = "1",
doi = "10.1007/978-3-642-10841-9_14",
language = "English (US)",
isbn = "3642108407",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "137--148",
booktitle = "Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings",

}

TY - GEN

T1 - Tighter bounds for facility games

AU - Lu, Pinyan

AU - Wang, Yajun

AU - Zhou, Yuan

PY - 2009/12/1

Y1 - 2009/12/1

N2 - In one dimensional facility games, public facilities are placed based on the reported locations of the agents, where all the locations of agents and facilities are on a real line. The cost of an agent is measured by the distance from its location to the nearest facility. We study the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location. In this paper, we use the total cost of agents as social welfare function. We study two extensions of the simplest version as in [9]: two facilities and multiple locations per agent. In both cases, we analyze randomized strategy-proof mechanisms, and give the first lower bound of 1.045 and 1.33, respectively. The latter lower bound is obtained by solving a related linear programming problem, and we believe that this new technique of proving lower bounds for randomized mechanisms may find applications in other problems and is of independent interest. We also improve several approximation bounds in [9], and confirm a conjecture in [9].

AB - In one dimensional facility games, public facilities are placed based on the reported locations of the agents, where all the locations of agents and facilities are on a real line. The cost of an agent is measured by the distance from its location to the nearest facility. We study the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location. In this paper, we use the total cost of agents as social welfare function. We study two extensions of the simplest version as in [9]: two facilities and multiple locations per agent. In both cases, we analyze randomized strategy-proof mechanisms, and give the first lower bound of 1.045 and 1.33, respectively. The latter lower bound is obtained by solving a related linear programming problem, and we believe that this new technique of proving lower bounds for randomized mechanisms may find applications in other problems and is of independent interest. We also improve several approximation bounds in [9], and confirm a conjecture in [9].

UR - http://www.scopus.com/inward/record.url?scp=76749093740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=76749093740&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10841-9_14

DO - 10.1007/978-3-642-10841-9_14

M3 - Conference contribution

AN - SCOPUS:76749093740

SN - 3642108407

SN - 9783642108402

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 137

EP - 148

BT - Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings

ER -