Computer Science – Computer Science and Game Theory
Scientific paper
2012-02-29
Computer Science
Computer Science and Game Theory
Scientific paper
We present a new class of vertex cover and set cover games. 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 -- in contrast to all previously studied covering games, where the price of anarchy cannot be bounded by a constant (e.g. [6, 7, 11, 5, 2]). In particular, we describe a vertex cover game with a price of anarchy of 2. The rules of the games capture the structure of the linear programming relaxations of the underlying optimization problems, and our bounds are established by analyzing these relaxations. Furthermore, for linear costs we exhibit linear time best response dynamics that converge to these almost optimal Nash equilibria. These dynamics mimic the classical greedy approximation algorithm of Bar-Yehuda and Even [3].
Piliouras Georgios
Valla Tomas
Vegh Laszlo A.
No associations
LandOfFree
LP-based Covering Games with Low Price of Anarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with LP-based Covering Games with Low Price of Anarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LP-based Covering Games with Low Price of Anarchy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345722