Martin Hoefer and Piotr Krysta
We consider a simple non-cooperative network creation game, called the connection game in (Anshelevich et al, "Near-optimal network design with selfish agents", STOC 2003). In this paper we present the special case of geometric connection games using Euclidean metric edge costs. The price of anarchy for this restricted class of games is still Θ(k). Hence, we consider the task of minimizing players incentives to deviate from a given optimal solution network. In contrast to general games in small geometric games (2 players and 2 terminals per player) a Nash equilibrium purchasing the optimum network exists. This can be translated into a (1+ε)-approximate Nash equilibrium purchasing the optimum network using some more practical assumptions. In contrast for three or more players there is an asymptotical lower bound of (4/3-ε) on any Nash equilibrium purchasing the optimum network. Furthermore playing the game with best-response strategies yields low-cost Nash equilibria for small games.
| Download: |
|