The price of stability in single-sink network design game
Date Issued
2015
Date
2015
Author(s)
Chung, Wei-Shao
Abstract
In this thesis we introduce the network design game, which is concerned with the relationship between the the system performance and a large number of individuals in the network. In the model of this game, there are many independent players in a graph and want to find a path from a source node to their destination node. Each edge has its cost and the players who go through the edge would share the cost. All the players want to optimize their cost and do not care about the others. This selfish behavior may increase the social cost of the network. so the lost of the social cost between the quality at a Nash equilibrium and the quality at a optimum is a interesting topic in network design game. We consider a specific case in network design game, single-sink ring network design game. In this game, the topology of the graph is a ring and all the players have the same destination. Then we prove that the price of stability in this game is 4/3. We further consider that what if players have more options. We add an option for the players in single-sink ring network, and prove that there is a upper bound of price of stability in some conditions, which is 5/3.
Subjects
Game Theory
Network Design
Price of Stability
Nash Equilibrium
Connection Game
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R01921040-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):5610af5ac940ca59e20cab5714ca48eb