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). In addition we present a
generalization called backbone game to model hierarchical
network and backbone link creation between existing network
structures. In contrast to the connection game each player considers a
number of groups of terminals and wants to connect at least one
terminal from each group into a network. In both games we focus on an
important subclass of tree games, in which every feasible
network is guaranteed to be connected.
For tree connection games, in which every player holds 2 terminals, we
show that there is a Nash equilibrium as cheap as the optimum
network. We give a polynomial time algorithm to find a cheap
(2+ε)-approximate Nash equilibrium, which can be generalized
to a cheap (3.1+ε)-approximate Nash equilibrium for the case
of any number of terminals per player. This improves the guarantee of
the only previous algorithm for the problem, which returns a
(4.65+ε)-approximate Nash equilibrium. Tightness results for
the analysis of all algorithms are derived.
For single source backbone games, in which each player wants to connect
one group to a common source, there is a Nash equilibrium as cheap as
the optimum network and a polynomial time algorithm to find a cheap
(1+ε)-approximate Nash equilibrium.
The full version appears 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.