Abstract
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost $\alpha$. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in $n$ for all values of $\alpha$ in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in $n$. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of $\alpha$ (at most $n$ polylog $n$). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of $\alpha$ and $\infty$). We prove the first assemblage of upper and lower bounds for this context, establishing nontrivial tight bounds for many ranges of $\alpha$, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of $\alpha$, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.
Introduction
In network design, there is a fundamental tension between creation costs (the price to build a link) and usage costs (the time or distance spent routing through the network). Network creation games model this by treating each node as a selfish agent trying to minimize its own total cost. The central metric for evaluating these systems is the Price of Anarchy (PoA): the ratio between the cost of the worst possible stable network (an equilibrium) and the cost of the most efficient network a central planner could build (the social optimum).
Prior to this research, finding tight bounds for the PoA in "cooperative" models—where players can share the cost of an edge—remained an open challenge. Furthermore, most existing research assumed a "complete host graph," meaning any two nodes could be connected for a flat fee. This paper tackles the cooperative model and investigates the impact of restricted "host graphs," reflecting real-world physical or budget constraints.
Methodology
The authors employ theoretical game theory and graph theory proofs, introducing several key methodological contributions:
- Collaborative Equilibrium: They utilize a notion of equilibrium that sits between a standard Nash Equilibrium and a Strong Nash Equilibrium. In a collaborative equilibrium, a coalition of players can coordinate to change their strategy on only a single edge at a time.
- Region Growing: To prove upper bounds on the diameter of equilibrium graphs, the authors adapt "region growing" techniques from approximation algorithms. They demonstrate that if a graph doesn't expand quickly enough, a group of nodes would have a selfish incentive to collaborate and build a new edge to reduce their usage costs.
- Lower Bound Constructions: To prove that the PoA can be high in general graphs, the authors construct specific "bad" equilibrium graphs where agents are trapped in inefficient configurations because no small group can afford to improve the network independently.
Key Insights
- Cooperation Lowers the Ceiling: By allowing nodes to share costs, the "stalemate" of the unilateral model (where one node must pay for the whole edge) is broken. This allows for more efficient structures, leading to the first polylogarithmic PoA bound ($O(\log^k n)$) rather than polynomial ($O(n^k)$).
- The "Small World" Connection: For the most natural range of edge costs, equilibrium graphs naturally form "small world" structures with polylogarithmic diameters.
- Host Graphs Matter: The transition from a complete host graph to a general host graph is significant. In complete graphs, the PoA is likely very small (constant or polylog). In general graphs, the authors prove it can be polynomial, showing that restricted connectivity options significantly amplify the inefficiency of selfish behavior.
Summary of Results
The paper provides a comprehensive table of bounds for various models and ranges of the edge cost $\alpha$.
Key findings include:
- Complete Graphs (Cooperative): The Price of Anarchy is proven to be polylogarithmic in $n$ for all values of $\alpha$. Specifically, for $\alpha = O(n)$, the PoA is $O(\log^{1+\log 5} n)$.
- General Host Graphs: The authors established the first tight bounds for this model, proving the PoA can be as high as $\Omega(\min\{\frac{\alpha}{n}, \frac{n^2}{\alpha}\})$. This confirms that non-uniform creation costs make the Price of Anarchy much worse.
- Diameter: For the cooperative model on complete graphs, the diameter of any equilibrium graph is $O(\text{polylog } n)$ for the most natural ranges of $\alpha$.
Limitations and Future Work
While this paper makes significant strides in the cooperative model, the unilateral model (where one node pays for an edge) still has a significant gap between the best known lower bound ($\Omega(1)$) and upper bound ($2^{O(\sqrt{\log n})}$) on complete graphs. The authors also conjecture that the PoA for complete graphs might actually be a constant, though proving this remains an open challenge. Finally, the speed of convergence for bidding dynamics under more complex models remains a topic for further exploration.
Summary updated