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). 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 bounds on the prices of anarchy and stability. We also focus on the quality of equilibria achievable through centralized incentives.