Abstract
We study a coordination game motivated by the formation of Internet Exchange Points (IXPs), in which agents choose which facilities to join. Joining the same facility as other agents you communicate with has benefits, but different facilities have different costs for each agent. We show that the Price of Stability (PoS) of this game is at most 2. We then explore how better stable solutions can be formed via payment schemes. We provide a payment scheme between agents that stabilizes the social optimum ($PoS = 1$). Furthermore, we analyze the subsidy $\Delta$ a central coordinator must provide to stabilize the optimum, proving a tradeoff: $\frac{\Delta}{cost(s^*)} \le 1 - \frac{2}{5} PoS$. Finally, we present an $O(\log n)$ approximation algorithm for finding the optimum solution.
Introduction
In the infrastructure of the internet, Internet Service Providers (ISPs) seek to exchange traffic efficiently. Joining an Internet Exchange Point (IXP) allows ISPs to communicate at high speeds for low costs. However, each IXP has its own connection costs and operating expenses that must be shared. This creates a coordination problem where ISPs want to be where their "friends" (peers) are to minimize disconnection costs, while simultaneously avoiding high facility premiums. This paper models this scenario as a Group Formation Game and investigates the efficiency of its stable outcomes.
The Group Formation Game Model
The model consists of $n$ agents and $m$ facilities. Each agent $i$ faces a cost structure comprising:
- Connection Cost: A specific cost for agent $i$ to join facility $j$.
- Operating Cost Share: A portion of the facility's total operating cost.
- Disconnection Penalty: A cost incurred for every "friend" (neighbor in a communication graph) who is not in the same facility.
Agents act strategically to minimize their individual costs. We analyze the Price of Anarchy (PoA)—the ratio of the worst equilibrium to the social optimum—and the Price of Stability (PoS)—the ratio of the best equilibrium to the social optimum.
Stability and Efficiency
A key finding is that while the Price of Anarchy can be unbounded (meaning some equilibria are catastrophically inefficient), the Price of Stability is at most 2. This holds even under "optimistic" assumptions where agents assume they will pay zero facility costs when considering a move. This result suggests that natural coordination can lead to reasonably efficient outcomes, at most twice as expensive as the global optimum.
Stabilization Mechanisms
To improve upon the natural PoS, the paper explores two payment mechanisms:
Paid Peering
In practice, ISPs often pay each other to exchange traffic. The authors prove that if agents are allowed to pay their neighbors to prevent them from deviating (up to the amount they would save by staying together), the social optimum $s^*$ can always be stabilized. In this regime, the Price of Stability drops to 1.
Central Coordinator Subsidies
If a central authority (e.g., a regulator) wants to ensure the social optimum is a Nash Equilibrium, they may need to provide subsidies. Let $\Delta$ be the total payment required to stabilize $s^*$. These are payments that an agent would lose if they changed their strategy.
The research reveals a fascinating tradeoff between the existing efficiency of the game and the cost to improve it. As shown in Figure 1, if the game's natural PoS is high (inefficient), the relative amount of subsidy needed to reach the optimum is actually lower.
The technical result $\frac{\Delta}{cost(s^*)} \le 1 - \frac{2}{5} PoS$ quantifies this: when good stable solutions do not exist, a relatively small intervention can stabilize the optimum. Conversely, if the PoS is already small, the system is already efficient enough that the high cost of further stabilization might not be justified.
Computational Complexity
Finding the social optimum $s^*$ is NP-Hard, as it relates to the multi-way cut problem. To address this, the authors developed a polynomial-time approximation algorithm using Linear Programming (LP) relaxation and randomized rounding, achieving an $O(\log n)$ approximation ratio.
Conclusion
This work provides a theoretical foundation for understanding IXP formation. By bounding the Price of Stability and demonstrating how simple payment mechanisms—both decentralized (paid peering) and centralized (subsidies)—can drive the system toward efficiency, the paper offers valuable insights for network design and policy. Future work may extend these static models to dynamic environments with fluctuating traffic and costs.
Summary updated