Publications
Back to Publications
Author(s) 
Hoefer, M. 
Title 
Noncooperative tree creation 
Abstract 
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. 
Download 
Hoefer06.pdf 
Back to Publications
