網路形成賽局之序列無政府價格

Abstract

隨著網路的廣泛應用以及各種不同利益的實體參與，對於網路形成和效率的理解變得越來越重要。本研究探討網路形成遊戲，以分析個體利益和整體網路效能之間的關係。在本篇論文中，我們專注於分析網路形成賽局的序列賽局版本。該賽局模型基於一個圖形結構，其中每條邊都有固定的建立成本，並且在某些節點上有獨立的玩家。每個玩家都有自己的起點和目標終點。在賽局進行過程中，玩家從所有可能的路徑中選擇成本最低的路徑，並且每條邊的成本由使用該邊的玩家平均分擔。

我們關注的是賽局系統的效率，即序列賽局中子網路完美納許均衡（SPNE）與最佳解之間的成本比例（SPoA）。我們觀察到原始賽局模型存在一些問題，例如玩家可能選擇非簡單路徑，這在同時做決策的賽局中是不會發生的情況。這些情況引發了對公平性和合理性的疑慮。因此，我們引入了一個新的限制，限制玩家只能選擇簡單路徑，以解決這些問題。

此外，我們指出先前針對二人單一終點賽局提出的性質在序列賽局中不再適用，這對SPoA的上界分析帶來了挑戰。最後，我們構建了一個特定的實例，展示了在特定情況下的下界，即 Ω(log n)。這個下界可以應用於環狀網路和廣播網路等情境中，並且在這些網路的非序列賽局中，PoS已被證明為常數[7,16]。

The widespread use of networks and the involvement of diverse entities with varying interests highlight the need to understand network formation and efficiency. This study examines network formation games to analyze the relationship between individual benefits and overall network performance. In this thesis, we focus on analyzing the sequential version of the network formation game. The game model is based on a graph structure, where each edge has a fixed construction cost, and there are independent players at certain nodes. Each player has their own starting point and target destination. During the game, players choose a lowest-cost path from all possible paths, and the cost of each edge is shared equally among the players using that edge.

Our main focus is on the efficiency of the game system, specifically the Subgame Perfect Nash Equilibrium (SPNE) and the cost ratio between SPNE and the optimal solution, known as the Sequential Price of Anarchy (SPoA). We observe that the original game model exhibits some issues, such as players potentially choosing non-simple paths, which would not occur in simultaneous decision-making games. These concerns raise questions about fairness and rationality. To address these issues, we introduce a new restriction where players are limited to choosing simple paths.

Furthermore, we point out that properties formulated for two-player single-sink games in previous studies are no longer applicable in the sequential version, posing challenges in analyzing the upper bounds of SPoA. Finally, we construct a specific instance that demonstrates a lower bound of Ω(log n) in a particular case. This lower bound can be applied to ring networks and broadcast networks, where the Price of Stability PoS in non-sequential games has been proven to be constant [7,16].