Forming better stable solutions in Group Formation Games inspired by Internet Exchange Points (IXPs)

Elliot Anshelevich, Wennan Zhu

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:

  1. Connection Cost: A specific cost for agent $i$ to join facility $j$.
  2. Operating Cost Share: A portion of the facility's total operating cost.
  3. 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:

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 tradeoff between the required subsidy $\Delta$ and the Price of Stability (PoS).

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

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. Thus, the players wish to join the same facilities as their "friends", but this is balanced by them not wanting to pay the cost of joining a facility. We first show that the Price of Stability ($PoS$) of this game is at most 2, and more generally there always exists an $\alpha$-approximate equilibrium with cost at most $\frac{2}{\alpha}$ of optimum. We then focus on how better stable solutions can be formed. If we allow agents to pay their neighbors to prevent them from deviating (i.e., a player $i$ voluntarily pays another player $j$ so that $j$ joins the same facility), then we provide a payment scheme which stabilizes the solution with minimum social cost $s^*$, i.e. PoS is 1. In our main technical result, we consider how much a central coordinator would have to pay the players in order to form good stable solutions. Let $\Delta$ denote the total amount of payments needed to be paid to the players in order to stabilize $s^*$, i.e., these are payments that a player would lose if they changed their strategy from the one in $s^*$. We prove that there is a tradeoff between $\Delta$ and the Price of Stability: $\frac{\Delta}{cost(s^*)} \le 1 - \frac{2}{5} PoS$. Thus when there are no good stable solutions, only a small amount of extra payment is needed to stabilize $s^*$; and when good stable solutions already exist (i.e., $PoS$ is small), then we should be happy with those solutions instead. Finally, we consider the computational complexity of finding the optimum solution $s^*$, and design a polynomial time $O(\log n)$ approximation algorithm for this problem.
BibTeX
@inproceedings{anshelevich2021forming,
  author = {Elliot Anshelevich and Wennan Zhu},
  title = {{Forming better stable solutions in Group Formation Games inspired by Internet Exchange Points (IXPs)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=oGirZHgILp3},
}
Figure