CaltechAUTHORS
Published July 2015 | Version Submitted
Journal Article Open

LP-Based Covering Games with Low Price of Anarchy

Creators

  • 1. ROR icon California Institute of Technology
  • 2. ROR icon Czech Technical University in Prague
  • 3. ROR icon London School of Economics and Political Science

Abstract

We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. This is in contrast to all previously studied covering games, where the price of anarchy grows linearly with the size of the game. Both the game design and the price of anarchy results are based on structural properties of the linear programming relaxations. For linear costs we also exhibit simple best response dynamics that converge to Nash equilibria in linear time.

Additional Information

© 2014 Springer Science+Business Media New York. Received: 20 May 2014; accepted: 4 October 2014; published online: 19 October 2014. Georgios Piliouras was supported by AFOSR project FA9550-09-1-0538, while working at the School of Electrical & Computer Engineering, Georgia Institute of Technology. Tomáš Valla was supported by the Centre of Excellence – Institute for Theoretical Computer Science (project P202/12/G061 of GA ČR), and by the GAUK Project 66010. László A. Végh was supported by NSF Grant CCF-0914732, while working at the College of Computing, Georgia Institute of Technology. We would like to thank Jarik Nešetřil for inspiring us to work on this problem and for a generous support in all directions.

Attached Files

Submitted - 1203.0050v1.pdf

Files

1203.0050v1.pdf

Files (251.5 kB)

Name Size
md5:cd82f59932eeb8fae8d6c1418a384aab
251.5 kB Preview Download

Additional details

Identifiers

Eprint ID
58883
DOI
10.1007/s00224-014-9587-z
Resolver ID
CaltechAUTHORS:20150714-134012322

Related works

Describes
10.1007/s00224-014-9587-z (DOI)
http://arxiv.org/abs/1203.0050 (URL)

Funding

Air Force Office of Scientific Research (AFOSR)
FA9550-09-1-0538
Centre of Excellence Institute for Theoretical Computer Science
P202/12/G061
GAUK Project 66010
NSF
CCF-0914732

Dates

Created
2015-07-15
Created from EPrint's datestamp field
Updated
2021-11-10
Created from EPrint's last_modified field