On the Structure of Equilibria in Basic Network Formation

Sotiris E. Nikoletseas, Panagiota N. Panagopoulou, Christoforos L. Raptopoulos, Paul G. Spirakis

Abstract

This paper investigates the structural properties of equilibrium networks in the context of selfish network formation. By analyzing a model where nodes perform edge swaps to minimize communication costs, the authors provide a new characterization of stable network structures. Key contributions include settling a long-standing conjecture regarding the polylogarithmic diameter of equilibrium graphs for dense networks and introducing a "Local Cost" game that guarantees convergence to a stable state in polynomial time through an exact potential function.

Introduction

Large-scale decentralized networks, such as the Internet, emerge from the independent decisions of numerous selfish agents. Modeling these interactions as Network Creation Games allows researchers to quantify the "Price of Anarchy"—the efficiency gap between decentralized equilibria and socially optimal configurations. A fundamental challenge in this domain is understanding the diameter and structural stability of these networks.

Previous models, such as those by Fabrikant et al., often faced computational intractability. This work builds upon a "swap-based" model where nodes improve their position by exchanging a single existing connection for a new one. The authors address critical gaps in the understanding of equilibrium graph topology and the dynamics of stabilization.

Structural Characterization of Sum-Swap Equilibria

The authors focus on the Sum-Swap Equilibrium, where nodes aim to minimize the sum of distances to all other nodes in the network. A central insight is the "Equidistance Property." In a stable network, the distances from any node $z$ to two high-degree nodes $u$ and $v$ must be relatively balanced. If a significant disparity exists—for instance, if $z$ is much closer to $u$ than to $v$—then $v$ may have a selfish incentive to swap an existing edge to connect to $u$ (or a neighbor of $u$), thereby reducing its total distance to the rest of the graph.

Illustration of edge swap scenarios where nodes evaluate potential improvements to their network position.

Using the probabilistic method, the authors demonstrate that in equilibrium, most nodes must be roughly equidistant from high-degree nodes. This symmetry limits the "skewness" of distances across the graph, which is instrumental in bounding the network's diameter.

Diameter Bounds and the $k$-Vicinity

A major result of this research is the partial settlement of a conjecture by Alon et al., which posited that equilibrium graphs have small diameters. The authors prove that for graphs that are sufficiently dense or possess nodes with large $k$-neighborhoods (the set of nodes within distance $k$), the diameter is polylogarithmic.

Specifically, the diameter is bounded by $O(\frac{n}{\Delta^{(k)}} + k)$, where $\Delta^{(k)}$ represents the size of the largest $k$-neighborhood. For dense graphs, this confirms that the diameter remains small ($O(\log^l n)$).

Structural analysis of paths and neighborhoods used to derive diameter bounds in equilibrium networks.

The Local Cost Network Creation Game

Recognizing that global distance calculations require nodes to have perfect knowledge of the entire network, the authors propose a Local Cost model. In this game, a node's utility is derived from the sum of the degrees of its immediate neighbors. This shift from global to local information significantly changes the game's dynamics.

Convergence and Potential Functions

The authors prove that the Local Cost game is an exact potential game. The existence of a global potential function that strictly decreases with every improving swap ensures that the game cannot enter infinite cycles and will always reach an equilibrium. The paper establishes a convergence bound of $O(n^3)$ edge swaps.

Furthermore, the model is robust to limited information. Even if nodes only query a small number of random non-neighbors rather than scanning the entire network, the system still converges to equilibrium in expected polynomial time.

Key Results and Implications

  • Diameter Stability: The work provides rigorous bounds on the diameter of sum-swap equilibria, particularly for dense graphs.
  • Backbone Structures: In the local cost model, any equilibrium graph is shown to contain a "star" graph as a spanning subgraph, ensuring a basic level of connectivity and communication efficiency.
  • Algorithmic Efficiency: The local model offers a computationally feasible alternative to global models, with guaranteed convergence and low informational requirements for the participating agents.

Limitations and Future Directions

While the paper makes significant strides for dense networks, the diameter of equilibrium graphs for very sparse, low-degree networks remains an open question. Additionally, while the local cost model is stable, the exact Price of Anarchy for this specific utility function has yet to be fully characterized. Future research may also extend the local model to $k$-vicinity costs, bridging the gap between purely local and global network formation strategies.

Summary updated

BibTeX
@article{nikoletseas2015structure,
  author = {Sotiris E. Nikoletseas and Panagiota N. Panagopoulou and Christoforos L. Raptopoulos and Paul G. Spirakis},
  title = {{On the Structure of Equilibria in Basic Network Formation}},
  journal = {Theoretical Computer Science},
  year = {2015},
  doi = {10.1016/j.tcs.2015.03.029},
}
Figure