We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e.g., Autonomous Systems, enterprises, residential customers). This system is at the heart of Internet connectivity. Connection contracts are local between two entities and may either be of peer-peer or a customer-provider variety. Entities bid (or demand payment) for the formation of these contracts, and in the resulting network some traffic is routed and other traffic dropped. As often occurs in practice, we also include a mechanism that penalizes providers if they drop traffic emanating from one of their customers. By incorporating some of the qualities of Internet business relationships, we hope that our model will have predictive value.

For a natural objective function, we prove that the price of stability is at most 2. With respect to social welfare, however, the prices of anarchy and stability can both be unbounded, leading us to consider how much we must perturb the system to obtain good stable solutions. We thus focus on the quality of Nash equilibria achievable through centralized incentives: solutions created by an ``altruistic entity" (e.g., the government) able to increase individual payouts for successfully routing a particular demand. We show that if every payout is increased by a factor of 2, then there is a Nash equilibrium as good as the original centrally defined social optimum. Finally, we give a characterization of Nash equilibria as flows of utility with certain constraints, which helps to visualize the structure of stable solutions and provides us with useful proof techniques.

This is joint work with Bruce Shepherd and Gordon Wilfong