Nash Equilibria for Connection Games on directed Graphs

"Diplomarbeit" supervised by
Prof. Dr. rer. nat. Burkhard Monien

Karsten Tiemann

Department of Computer Science,
University of Paderborn (Germany)

Paderborn, February 2004.


This work was initiated by professor Monien's reference to the paper "Near-Optimal Network Design with Selfish Agents." [Ans03] published by E. Anshelevich, A. Dasgupta, E. Tardos and T. Wexler on the STOC 2003. In this publication the authors introduce a "simple network design game that models how independent selfish agents can build or maintain a large network".

This network design game is also called connection game. In such a game we have an undirected graph, some players and for each player a subset of the graph vertices as his terminals. The graph edges have costs and every player wants to pay as little as possible for edges in the graph. Nevertheless he usually has to pay for some of them since he must ensure that his terminals are connected by a subgraph of fully paid edges.

The preparation for this thesis began with some considerations about the question in which direction a further research based on [Ans03] should point. Since the work published on the STOC concentrates on connection games on undirected graphs we decided to work on such games on directed graphs.

The first thing you will read in the introduction of this work is our definition of connection games on directed graphs. Later on you will see that we consider these new games mainly under the same point of views the [Ans03]-authors considered for their games. This means that we do a lot of work on so-called Nash equilibria (situations developing when the players act selfishly) and their relation to optimal solutions in order to gain some knowledge of the social costs emerging when players act selfishly in comparison with the social costs of optimal solutions that can only by guaranteed if a central authority coordinates the players.

You will see that there are connection games having no Nash equilibrium. Therefore we consider in addition whether it is possible to determine in polynomial time for a given game whether or not it has a Nash equilibrium. The authors of [Ans03] were able to proof for their game on undirected graphs the NP-hardness of this Nash existence question. Now we show that this question is also NP-hard for our new games on directed graphs. In addition we proof that the Nash existence problem for games on directed graphs is even NP-hard if two player games are considered.