Near-optimal network design with selfish agents

TLDR

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. The game gives each agent a set of terminals to connect, assigns costs to possible edges, and lets agents pay for edges so as to minimize their own cost. We show that deciding whether a Nash equilibrium exists is NP‑complete, but for the special case of connecting a terminal to a common source there is a Nash equilibrium as cheap as the optimal network and a polynomial‑time algorithm for a (1+ε)-approximate equilibrium, while for the general game a 3‑approximate equilibrium as cheap as optimal exists and can be found by a (4.65+ε)-approximate algorithm.

Abstract

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. In our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. Possible edges in the network have costs and each agent's goal is to pay as little as possible. Determining whether or not a Nash equilibrium exists in this game is NP-complete. However, when the goal of each player is to connect a terminal to a common source, we prove that there is a Nash equilibrium as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε)-approximate Nash equilibrium that does not cost much more. For the general connection game we prove that there is a 3-approximate Nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε)-approximate Nash equilibrium that does not cost much more.