單一終點網路設計賽局的價格穩定性

Abstract

在這篇論文裡我們討論網路設計賽局，這種賽局探討的是整體系統效能與個體行為間的關係。這個賽局模型的架構是在一個圖裡有許多獨立的玩家，每個玩家都有著自己的起點和終點，並想找到一條路徑連在一起。經過每條邊都要支付特定的費用，而費用是由使用該邊的玩家們共同承擔。每個玩家都是自私的並希望盡可能地降低自己的花費。而這樣的行為可能會造成社會成本的增加。網路設計賽局主要就是探討這樣的行為會對整個系統帶來多大影響，並試圖降低系統的損失。 我們考慮其中一種網路設計賽局，單一終點環狀賽局。這種賽局的拓撲是環狀的，並且所有玩家都想連到一個共同的目標。我們證明了在這種賽局底下，PoS會是4/3。之後我們又考慮了，在這個賽局底下，如果玩家有更多選擇，會對系統帶來多少影響，這影響是正面還是負面的。我們之後證明了，當玩家有多一個選擇時，在一些條件下PoS最多會是5/3。

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.