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 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: Delta/cost(s) < 1 - 2 PoS/5. 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.
Introduction
In the physical infrastructure of the internet, Internet Exchange Points (IXPs) serve as critical hubs where Internet Service Providers (ISPs) connect to exchange traffic. This decentralized coordination problem involves a fundamental tension: ISPs want to cluster at the same IXPs to minimize the costs of data transit (the "cost of being apart"), yet they must also account for the individual costs of joining and maintaining these facilities.
This research, presented at AAAI-21, formalizes this behavior as a Group Formation Game. The study provides a rigorous framework for understanding how decentralized agents form groups and explores mechanisms—such as peer-to-peer payments and central subsidies—that can drive these systems toward socially optimal outcomes.
The Group Formation Game Model
The authors define a game with $n$ agents and $m$ facilities. Each agent's cost function is composed of three primary elements:
- Connection Cost: A facility-specific cost for an agent to use a particular IXP.
- Disconnection Cost: A penalty incurred for every "friend" or peer that is not located at the same facility.
- Shared Facility Cost: A share of the fixed cost required to maintain the facility, distributed among its users.
This structure creates a complex coordination environment where the incentive to cluster (to avoid disconnection costs) is balanced against the incentive to separate (to avoid expensive facilities or high shared costs).
Stability and the Price of Efficiency
A central question in algorithmic game theory is the efficiency of stable solutions. The authors focus on the Price of Stability (PoS)—the ratio between the cost of the best possible Nash Equilibrium and the absolute social optimum ($s^*$).
Key Theoretical Bounds
- PoS $\le 2$: The research proves that there always exists a stable solution that is at most twice as expensive as the social optimum. This bound is shown to be tight.
- Unbounded Price of Anarchy: Conversely, the Price of Anarchy (PoA)—the ratio of the worst stable solution to the optimum—is unbounded. Without some level of coordination or selection, the system can settle into highly inefficient states.
- The "Optimistic" Assumption: To derive these bounds, the authors assume agents are "optimistic." When considering a move to a new facility, agents assume they will initially be charged zero in shared facility costs. This strengthens the stability results: if a solution is stable even when agents perceive switching as "free," it remains stable under more realistic, higher-cost pricing rules.
Mechanisms for Optimization: Payments and Peering
While the natural PoS is 2, the paper investigates how external or internal incentives can improve this ratio.
Paid Peering as a Stabilizer
In real-world ISP relations, "paid peering" is a common business practice where one provider pays another to maintain a connection. The authors prove that this is a mathematically sound method for reaching the social optimum. By allowing agents to pay their neighbors to prevent them from deviating, the Price of Stability effectively drops to 1.
The Central Coordinator Tradeoff
If a central coordinator wishes to stabilize the social optimum $s^*$, they may need to provide subsidies (denoted as $\Delta$). The paper's main technical result is a mathematical tradeoff between these payments and the natural stability of the system: $$\frac{\Delta}{cost(s^*)} \le 1 - \frac{2}{5} PoS$$
This formula reveals an intuitive but powerful insight: if the natural Price of Stability is high (meaning the system is prone to very inefficient stable states), it actually requires less relative investment from a coordinator to stabilize the optimum. If the PoS is already low, the system is already close to efficient, and the coordinator can simply accept the existing stable solutions.
Computational Complexity and Algorithms
Finding the absolute social optimum ($s^*$) in this group formation game is proven to be NP-Hard. To address this, the authors utilize Linear Programming (LP) relaxation techniques to develop approximation algorithms:
- General Case: An $O(\log n)$ approximation algorithm.
- Zero Facility Costs: In scenarios where facility costs are negligible, a 2-approximation algorithm is achievable.
Conclusion
This research provides a robust theoretical foundation for the group formation dynamics observed in internet infrastructure. By proving a tight bound on the Price of Stability and demonstrating how payment schemes like paid peering can eliminate inefficiency, the authors offer both a descriptive model of current ISP behavior and a prescriptive framework for central coordinators aiming to optimize network topology. Future work may expand these results by considering coalitional moves (Strong Nash Equilibrium) and dynamic cost structures that fluctuate with traffic volume.
Summary updated