Martin Hoefer
In this paper we consider the connection game, a simple network
design game with independent selfish agents that was introduced by
(Anshelevich et al, STOC 2003). Our study concerns an important
subclass of tree games, in which every feasible network is
guaranteed to be connected. It generalizes the class of single-source
games considered before. We focus on the existence, quality, and
computability of pure-strategy exact and approximate Nash
equilibria.
For tree connection games, in which every player holds two terminals,
we show that there is a Nash equilibrium as cheap as the optimum
network. In contrast, for single-source games, in which every player
has at most three terminals, the price of stability is at least
k-2, and it is NP-complete to decide the existence of a Nash
equilibrium. Hence, we propose polynomial time algorithms for
computing approximate Nash equilibria, which provide relaxed stability
and cost efficiency guarantees. For the case of two terminals per
player, there is an algorithm to find a (2+ε,1.55)-approximate
Nash equilibrium. It can be generalized to an algorithm to find a
(3.1+ε,1.55)-approximate Nash equilibrium for general tree
connection games. This improves the guarantee of the only previous
algorithm for the problem, which returns a
(4.65+ε,1.55)-approximate Nash equilibrium. Tightness results
for the analysis of all algorithms are derived. Our algorithms use a
novel iteration technique for trees that might be of independent
interest.
This work is an extension of an
extended abstract in MFCS 2006
and part of an extended abstract in ISAAC 2006.
| Download: |
|