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). 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.
Download Hoefer07.pdf

Back to Publications