University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Publications

Back to Publications

Author(s) Hoefer, M.
Title Non-cooperative 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