Abstract
Settings in which independent self-interested agents form connections with each other are extremely common and are usually modeled using network formation games. We study a natural extension of network formation games in which the nodes cannot form connections themselves, but instead must do it through an intermediary, paying the intermediary to facilitate these connections. The price charged by the intermediary is determined by its operating costs, which depend on the total volume of connections it facilitates. We investigate the existence and worst-case efficiency (Price of Anarchy) of stable solutions in these settings, specifically when the intermediary uses common pricing schemes like proportional pricing or marginal cost pricing. For both schemes, we prove the existence of stable solutions and characterize their structure. Our main results bound the Price of Anarchy: while marginal cost pricing leads to an upper bound of 2, proportional pricing performs well as long as the intermediary's operating costs are not overly convex.
Introduction
In traditional network formation models, such as the seminal work by Jackson and Wolinsky, agents are assumed to form links directly with one another. However, many real-world systems rely on a third party to facilitate these connections. A prime example is the infrastructure of the Internet: Internet Service Providers (ISPs) often connect via Internet Exchange Points (IXPs). These IXPs are physical data centers that charge fees to cover their infrastructure and operating costs.
This paper addresses the challenge of understanding how an intermediary's pricing policy affects the resulting network. If fees are too high, agents will not connect; if they are structured poorly, the resulting network might be highly inefficient. The research seeks to answer two fundamental questions: Do stable networks exist when an intermediary is involved, and how efficient are these decentralized solutions compared to a socially optimal configuration?
The Model and Pricing Schemes
The authors formulate a game where $n$ nodes choose connection strengths with each other. The intermediary incurs an operating cost $c(y)$ based on the total connection strength $y$ in the system. This cost is passed back to the nodes via a pricing scheme. The paper focuses on two primary mechanisms:
- Proportional Pricing: Each node pays a share of the total cost proportional to its total connection strength.
- Marginal Cost Pricing: Each node pays a rate equal to the derivative of the intermediary's cost function.
A new notion of stability is defined that generalizes "pairwise stability." A solution is considered stable if no pair of nodes can mutually benefit by increasing their connection strength and no single node can benefit by decreasing its strength, accounting for both the direct benefits of connection and the fees paid to the intermediary.
Key Insights and Existence
One of the most significant findings is that a stable solution is guaranteed to exist for any continuous, non-decreasing price function. This implies that even as the intermediary's costs grow in complex ways, the system can always reach an equilibrium.
To prove this, the authors develop a recursive characterization of stable solutions. They show that stable networks are not random configurations but possess a nested structure. One can effectively "grow" a stable network by starting with a high price (where no connections are formed) and gradually lowering the price, making connections "tight" as they hit capacity limits.
Conversely, the authors highlight the danger of "Equal Pricing" schemes, where costs are split equally among all nodes regardless of usage. Such schemes can lead to unbounded inefficiency. High-value users end up being subsidized by low-value users, creating a "tragedy of the commons" where the network grows far beyond what is socially optimal.
The Price of Anarchy
The efficiency of these decentralized networks is measured by the Price of Anarchy (PoA), which compares the cost of the worst-case stable solution to the social optimum.
- Marginal Cost Pricing: The PoA is at most 2. This is a remarkably strong result, suggesting that even without a central coordinator, the decentralized network will never be more than twice as expensive as the theoretical "perfect" network.
- Proportional Pricing: The PoA is bounded by the "degree" of the cost function. If the intermediary's cost is a polynomial of degree $d$ (e.g., $c(y) = y^2$), the PoA is at most $d$. This indicates that the efficiency of proportional pricing is directly tied to the convexity of the intermediary's cost function.
Conclusion and Future Work
This research provides a complete characterization of stable solutions for a large class of pricing schemes, offering a roadmap for how these networks form in practice. However, several avenues for future research remain:
- Non-linear Benefits: The current model assumes linear connection costs/benefits. Real-world networks often exhibit non-linear returns (e.g., Metcalfe's Law), which may alter stability conditions.
- Strategic Intermediaries: The model treats the intermediary as "passive," simply recovering its costs. Future work could explore a strategic intermediary that sets prices to maximize its own profit.
- Convergence Dynamics: While the paper proves that stable states exist, it does not explore the dynamics of how agents actually find these states through natural interaction over time.
Summary updated