無向圖多播賽局的穩定成本之研究

Abstract

在一無向圖中，若干玩家從各自的起始點出發，選擇成本最低的路徑通往某一共用的終點，這樣的賽局被稱為多播網路設計賽局，或簡稱為多播賽局。其中，每位玩家選擇的路徑中，每一條邊的成本由所有使用該邊的玩家均分。在這類網路設計賽局中，我們特別關心穩定成本（賽局的均衡態較系統最佳態多出的成本）此一指數。Bilò 等人證明了對廣播賽局（多播賽局的特例，圖中每個頂點都有玩家）而言，穩定成本為一常數，儘管對於一般的多播賽局而言，仍未找到顯著低於O(log n)的上界，其中n 為玩家數。Freeman 等人試著延伸Bilò 等人的方法以證明在類二分圖中的穩定成本亦為常數，然而論述細節多有缺漏，其證明是不嚴格的。本論文針對多播賽局的穩定成本進行研究，試著完備Freeman 等人的證明，並且將其推廣以適用於更一般性的圖。

In multicast network design games, a set of agents choose paths from their source locations to a common sink, trying to minimize their individual costs, in which the cost of an edge is equally shared among the agents using it. One of the main problems in this field is the price of stability (PoS) of such games. For the special case of broadcast games (every non-sink vertex has an agent), Bilò et al. have given a constant upper bound, closing the problem asymptotically, while, in general, no significantly sub-logarithmic bound is known for multicast games. Freeman et al. extended the methodology introduced by Bilò et al. and claimed a constant bound for multicast games on quasi-bipartite graph, while the proof is not concrete, since some detailed assumptions fail to be true. In this paper, we research on the PoS of multicast network design games, trying to complete the arguments by Freeman et al. and extend them to cover a more general sort of graphs.