Strategic network formation through peering and service agreements

• 成果类型: Article
• 署名作者: Anshelevich, Elliot; Shepherd, F. B.; Wilfong, Gordon
• 署名单位: Rensselaer Polytechnic Institute; McGill University; AT&T
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2011.01.002
• 发表日期: 2011
• 页码: 17-38
• 关键词: Network formation; Contract formation; Price of anarchy; Price of stability; Algorithmic game theory

摘要

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. (C) 2011 Elsevier Inc. All rights reserved.