請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/72688
標題: | 可分割賽局的效率分析 Efficiency Analysis of the Atomic Splittable Games |
作者: | Yu Hao You 游育豪 |
指導教授: | 陳和麟(Ho-Lin Chen) |
關鍵字: | 壅塞賽局,可分割賽局,非原子聯盟賽局,奈許平衡,對稱式賽局,多分類賽局, Congestion Games,Atomic Splittable Games,Nonatomic Coalition Games,Price of Anarchy,Nash equilibrium,Symmetric Games,Multi-class Games, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 壅塞賽局在算法賽局領域中是個被廣泛討論的課題,多位玩家有各自可選擇的資源,以達成各自的需求(像是到達目的地),而每個資源的壅塞程度,會根據該資源的延遲函數,讓每位玩家需要付出相對應的成本。此模型能應用在許多有壅塞概念的賽局上,像是交通、網路、資源分配等。我們探討其中的可分割賽局的模型,每位玩家可以控制一定的流量,但可以分割這些流量,使用不同的資源,可以應用在貨運分配、市場合作或壟斷等問題。
在算法賽局中,主要會用奈許均衡與最佳解的比率,稱為 PoA (Price of Anarcy),用這個指標去衡量一個賽局的效率好壞。在過去的論文中,討論可分割賽局 PoA 的文獻有限,即使只限制在多項式的延遲,PoA上界也非常高。 在這篇論文中,主要聚焦在對稱式的可分割賽局。首先,我們討論對稱式的奈許均衡,於是我們新定義了一個衡量對稱均衡的指標,稱為 SymmPoA (Symmetric PoA),來表示對稱式均衡的不效率程度。我們給出了可分割賽局上指標 SymmPoA 的上界,以及在多項式延遲函數時,一個確切不變的上界,比起之前的 PoA 上界,有顯著的降低。此外,我們也討論在哪些條件下,SymmPoA 上界也是原本的 PoA 上界。 最後一小部分,則是將可分割賽局推廣至多分類賽局,使得每個資源的延遲對不同玩家的影響程度可以不同。例如在道路交通上,不同的壅塞程度,對汽車、機車的影響程度不同。我們給出一個多分類可分割賽局的 PoA 上界,並套用在一個簡單的線性優先的特例。 Congestion games are one of the most well-studied class of models in algorithmic game theory. In this paper, we study the atomic splittable congestion games. Our work mostly focuses on the case where the game is symmetric. First, we focus on the symmetric equilibria and define a new notion called symmetric price of anarchy to describe the inefficiency of such equilibria. We derive an upper-bound for the symmetric price or anarchy and analyze the upper-bound when the latency functions are polynomials with non-negative coefficients. We also prove that our upper-bound on the symmetric price of anarchy is also an upper-bound for the price of anarchy when some particular conditions are satisfied. Finally, we generalize the model to the multi-class, give an general PoA upper-bound and derive the upper-bound in linear-priority case. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/72688 |
DOI: | 10.6342/NTU201901003 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 369.46 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。