This paper contributes to the application of game theory to network design. The objective is to investigate the extent to which useful connected subnetworks can be constructed on, say, the Internet, by selfish participants. Hoefer defines and studies various kinds of tree connection games (TCGs), with most of the results derived for single source games (SSGs) and path TCG (PTCG). A TCG is specified by a finite number of players, an undirected graph, and an assignment of some subset of vertices to each player. These sets may overlap. The graph is equipped with a nonnegative cost function. Also, a TCG has a set of requirements that enforce connectivity. Each player seeks to connect his or her vertices at minimum cost. The cooperative nature of TCG is enforced through two provisions: first, an edge is bought--that is, included in the tree--if the sum of the contributions of all players to that edge at least equals its cost, and, second, a player would rather have his or her vertices connected than disconnected.

The fundamental game theory concept is a Nash equilibrium (NE), a state in which no player can unilaterally reduce his or her cost (sum of contributions over all vertices) by choosing a different set of contributions. A social optimum tree--not defined in the paper--is undoubtedly a tree with the lowest total edge cost. The set of contributions for each edge associated to a player is called his or her strategy.

The results of the paper are mainly for SSG, where each player has a designated source vertex and wishes to connect it to his or her other vertices, and PTCG, where there are two distinguished vertices in each player’s set and he or she is to create a path between them.

An approximate NE is given by two parameters, alpha and beta. The stability parameter alpha is the factor by which each player can unilaterally reduce his or her cost, by using a different strategy; the approximation parameter beta is the ratio of the achieved tree cost to the social optimum tree cost. An approximate NE TCG is designated by the pair (alpha,beta). For example, for (1,beta), we have an NE TCG, although an NE TCG can still be distinguished, according to beta. The full optimum NE corresponds to (1,1).

There are numerous interesting technical lemmas in the paper, but here are some of the main results:

• Theorem 1: For each social optimum tree T^* in a PTCG, there is an exact NE that buys T^*.
• Theorem 3: It is NP-hard to decide whether a given SSG has an NE. This reduction is directly from 3-SAT.
• Theorem 4 concerns PTCG: For any social optimum tree T^* for a given PTCG, there exists a (2,1) NE that buys T^*. For any epsilon > 0, a (2 + epsilon, 1.55) NE can be computed in polynomial time. We point out that there is a 1/epsilon penalty factor in the time bound.

There is a distinction drawn in the paper between computational methods that assume a social optimum (or beta-optimum) tree as given, and those that work from scratch. There are also tightness results on alpha for general TCG. The paper will be of considerable technical interest, but not all terms are well defined.