Strategic Network Formation through Peering and Service Agreements

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, enterprise networks, residential customers). This system is at the heart of Internet connectivity. In our model we are given a network topology of nodes and links where the nodes act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but may have to pay their neighbors for links incident to them. We incorporate some of the qualities of Internet business relationships, including customer-provider and peering contracts. We show that every Nash equilibrium can be represented by a circulation flow of utility with certain constraints. This allows us to prove that the price of stability is at most 2 with respect to a natural objective function, but that prices of anarchy and stability can both be unbounded with respect to social welfare. We thus focus on the quality of equilibria achievable through centralized incentives, and 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. Key words: network formation, contract formation, price of anarchy, price of stability, algorithmic game theory JEL: C72, D85 1. Introduction The formation of the Internet marked a step away from centrally planned and controlled networks to networks that employ distributed traffic routing control.