Martin Hoefer
We study a general class of non-cooperative games coming from
combinatorial covering and facility location problems. A game for
k players is based on an integer programming formulation. Each
player wants to satisfy a subset of the constraints. Variables
represent resources, which are available in costly integer units and
must be bought. The cost can be shared arbitrarily between players.
Once a unit is bought, it can be used by all players to satisfy
their constraints. In general the cost of pure-strategy Nash
equilibria in this game can be prohibitively high, as both prices of
anarchy and stability are in Θ(k). In addition, deciding the
existence of pure Nash equilibria is NP-hard. These results extend
to recently studied single-source connection games. Under certain
conditions, however, cheap Nash equilibria exist: if the integrality
gap of the underlying integer program is 1 and in the case of single
constraint players. In addition, we present algorithms that compute
cheap approximate Nash equilibria in polynomial time.
Full results on single-source games appear in
Martin Hoefer.
Non-cooperative Tree Creation
Algorithmica 53(1), pp. 104-131, 2009.
| Download full version: |
|
The original publication is available at SpringerLink. |
Download proceedings version, © Springer Verlag.
Erratum: In contrast to claims in the original proceedings version,
Theorems 8 and 9 can be shown only for the case of set cover games.
For details see Chapter 4 of my Ph.D. thesis.