Network Market Design for Efficient Resource Allocation
2Many systems are characterized by complex (and often strategic) interactions between subsystems. Such systems occur in communication networks, power networks, wireless and sensor networks, etc. The strategic interactions between such subsystems often involve economic issues. This necessitates market-based algorithms for distributed control and optimization. Many network problems share such issues: efficient network resource exchange between service providers, revenue-sharing games between service-providers and content-providers, power-control games in wireless networks, etc. We will begin with a broad overview of work in the last few years on game theory and network pricing: routing games, congestion control and pricing, resource allocation and auctions, and pricing of differentiated services and wireless network pricing. We will then consider the problem of economics-informed designs which align incentives of different agents/subsystems for optimal operation. We will then specifically discuss market design for efficient network resource exchange between Internet service-providers and carriers. We will see that the designed market system is robust to strategic manipulation by the players, i.e., it has zero price of anarchy in the full information case (all Nash equilibria are efficient), and asymptotically zero price of anarchy in the incomplete information case (asymptotic Bayesian Incentive compatibility). Moreover, human-subject economic experiments suggest good performance in real situations as well. Data derived from such experiments can be used to obtain computational models of agents which can be used to study markets with large number of agents.