In the past decade many advancements have been made in the field of classical game theory, a broad research area that studies the behaviour of rational and selfish agents interacting in a well defined environment. This renewed interest has been largely driven by the explosive growth of the Internet, a complex network that brings together millions of users and computers each desiring to send, share and receive huge amounts of data.
The problems of how to connect these users and how to efficiently transmit their data could be loosely defined as network design problems. This is a well studied area within the field of combinatorial optimization, which seeks to minimize the cost of accomplishing a specific goal given finite resource constraints.
For a motivating example, consider an Internet Service Provider (ISP) that wishes to provide cable Internet service to a remote town. Given a list of businesses and households in the town that wish to receive this service, the ISP would like to determine how to lay new cables to service the new customers while minimizing the cost of laying the cable. In the broad terms of combinatorial optimization, the service provider wishes to accomplish the goal of connecting all the new customers while minimizing the cost of laying the cable, constrained by building restrictions from local and regional governments.
Contents
1 Introduction
- 1.1 Network Design Problems
1.2 Network Design Games
1.3 Cost-Sharing Mechanisms
1.4 Primal Dual Algorithms
- 1.4.1 AKR Algorithm
1.4.2 GW Algorithm
2 Algorithms for Network Design Games
- 2.1 Death-time concept
2.2 Single-node Multi-player Edge-Cover Game
- 2.2.1 Primal-dual method
2.2.2 Analysis: Cost Recovery
2.2.3 Analysis: Cross-monotonic Cost-Sharing Method
2.3 Multi-player Multi-node Edge Cover Game
- 2.3.1 Primal-Dual Method
2.3.2 Analysis: Cost Recovery
2.3.3 Analysis: Cross-monotonic Cost-Sharing Method
2.4 Downwards Monotone Set Cover Game
- 2.4.1 Downwards Monotone Cut Requirements
2.4.2 A Lazy Primal-Dual Method
2.4.3 Analysis: Cost Recovery
2.4.4 Analysis: Cross-monotonic Cost-Sharing Method
2.5 Even Parity Connection Game
- 2.5.1 Primal-Dual Method
2.5.2 Analysis: Cost Recovery
2.5.3 Analysis: Cross-monotonic Cost-Sharing Method
3 Discussion
- 3.1 Future Work
- 3.1.1 Lifted Cut Relaxation
3.1.2 Competitive Conjectures
3.2 Conclusions
Bibliography
Download
PDF Ebook Cross-monotonic Cost Sharing Methods for Network Design Games
