在無向單源網路賽局中的序列賽局平衡

Abstract

在這篇論文里，我們引入了序列賽局[5]的概念，討論當自私的玩家們依照一定次序獨立做決定時整體系統的效能。我們主要在單一終點的無向圖中討論這個賽局。在該模型中，每個玩家都有著自己的起點和共同的終點，他們想要在無向圖中找到一條花費最少的路徑連起他們的起點和重點。經過的每條邊都有特定的費用，而經過這條邊的玩家需要共同承擔該條邊的費用。他們分擔費用的方法可以由系統的協議決定。此外，在序列賽局中，每個玩家依序做決定並且每個當下做 決定的玩家都知道之前行動玩家的決定，並且知道自己的每一個行動後後面玩家的偏好。他們可以據此計算出自己每一個行動的花費然後挑出花費最小的執行。這種每個玩家自私的行為會增加系統的總花費。過去有很多研究是在討論當玩家們同時做決定時，pure Nash[1]下系統的效率。我們則是討論在序列賽局中，當所有玩家依序而非同時做決定時系統的效率。在每條邊的費用由共享這條邊的玩家平分的協議[1]下，我們首先考慮只有2個玩家的狀況，並且證明了SPoA[5]會是7/5。之後我們討論了一種特定的單一重點環狀賽局，SPoA最多是H(n)。對於多個玩家的賽局，我們還給出了一個SPoA = ( log n log log n)的例子說明SPoA的下界。最後我們討論了改變分攤費用的 協議對系統效率的影響，發現在Prim Protocal [16]的協議下，SPoA = 2。

In this thesis we introduce the sequential game, which is concerned with system effectiveness when selfish players take actions in a sequence. And we focus this game on undirected single-sink graph. In our model, players with self-interested purpose want find a path from his source node to the same sink. Each edge has its cost and players sharing the edge will share the cost by some protocol. What's more, in sequential game, players make choices in some order and they have the knowledge of choices former players made as well as the preference of later players. So they can calculate their exact cost on each path and choose the smallest one. Selfish behavior of each player may increase the total cost of the system, and there are a lot of previous work on pure Nash, in which players make decisions at same time. Compared with previous work, we want find the effectiveness of SPE of the sequential game when players make decisions one by one. With Shapley Protoca, we first consider the 2-player case of undirected single-sink sequential game and find the tight bound of SPoA is 7/5 which is even bigger than 4/3 of PoS in pure Nash. For n-player game, we studied the regular ring game and prove the upper bound of SPoA is H(n). We also give a lower bound case of SPoA on general n-player games, which is logn/log(log n). Then we try to find different protocols to improve the efficiency. So we study the Prim Protocal and find the tight bound of SPoA is $2$.