跳到主要內容

臺灣博碩士論文加值系統

(34.204.176.71) 您好!臺灣時間:2024/11/10 20:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:游育豪
研究生(外文):Yu Hao You
論文名稱:可分割賽局的效率分析
論文名稱(外文):Efficiency Analysis of the Atomic Splittable Games
指導教授:陳和麟
指導教授(外文):Ho-Lin Chen
口試委員:呂學一魏宏宇陳俊全
口試委員(外文):Hsueh-I LuHung-Yu WeiChiun-Chuan Chen
口試日期:2019-07-19
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:40
中文關鍵詞:壅塞賽局可分割賽局非原子聯盟賽局奈許平衡對稱式賽局多分類賽局
DOI:10.6342/NTU201901003
相關次數:
  • 被引用被引用:0
  • 點閱點閱:257
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
壅塞賽局在算法賽局領域中是個被廣泛討論的課題,多位玩家有各自可選擇的資源,以達成各自的需求(像是到達目的地),而每個資源的壅塞程度,會根據該資源的延遲函數,讓每位玩家需要付出相對應的成本。此模型能應用在許多有壅塞概念的賽局上,像是交通、網路、資源分配等。我們探討其中的可分割賽局的模型,每位玩家可以控制一定的流量,但可以分割這些流量,使用不同的資源,可以應用在貨運分配、市場合作或壟斷等問題。
在算法賽局中,主要會用奈許均衡與最佳解的比率,稱為 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.
誌謝 ii
摘要 iv
Abstract vi
List of Figures ix
List of Tables x
1 Introduction 1
2 Preliminaries 6
2.1 Models 6
2.1.1 Congestion Games 6
2.1.2 Atomic Splittable Ccongestion Games (ASG) 7
2.1.3 Multi-class Atomic Splittable Congestion Games (Multi-class ASG) 8
2.2 Some Useful Characteristics 10
3 Bounding for the Symmetric Single-Class Games 12
3.1 SymmPoA Bound 12
3.1.1 With General Latency Functions 13
3.1.2 With Monomial and Polynomial Latency Functions 17
3.2 From SymmPoA Bound to PoA Bound 23
4 Bounding for the General Single-class Games 29
5 Bounding for the Multi-Class Games 31
6 Conclusions and Future Works 36
Bibliography 38
[1] S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM Journal on Computing, 40(5):1211–1233, 2011.
[2] E. Altman, T. Basar, T. Jimenez, and N. Shimkin. Competitive routing in networks with polynomial costs. IEEE Transactions on automatic control, 47(1):92–96, 2002.
[3] E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602–1623, 2008.
[4] B. Awerbuch, Y. Azar, and A. Epstein. The price of routing unsplittable flow. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 57–66. ACM, 2005.
[5] U. Bhaskar and P. R. Lolakapuri. Equilibrium computation in atomic splittable routing games. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[6] S.-F. Cheng, D. M. Reeves, Y. Vorobeychik, and M. P. Wellman. Notes on equilibria in symmetric games. 2004.
[7] G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 67–73. ACM, 2005.
[8] R. Cominetti, J. R. Correa, and N. E. Stier-Moses. The impact of oligopolistic competition in networks. Operations Research, 57(6):1421–1437, 2009.
[9] A. Epstein, M. Feldman, and Y. Mansour. Efficient graph topologies in network routing games. Games and Economic Behavior, 66(1):115–125, 2009.
[10] D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2-3):226–239, 2005.
[11] T. Harks. Stackelberg strategies and collusion in network games with splittable flow. Theory of Computing Systems, 48(4):781–802, 2011.
[12] A. Hayrapetyan, É. Tardos, and T. Wexler. The effect of collusion in congestion games. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 89–98. ACM, 2006.
[13] P. Kleer and G. Schäfer. Potential function minimizers of combinatorial congestion games: Efficiency and computation. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 223–240. ACM, 2017.
[14] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science, pages 404–413. Springer, 1999.
[15] A. Orda, R. Rom, and N. Shimkin. Competitive routing in multi-user communication networks. In IEEE INFOCOM’93 The Conference on Computer Communications, Proceedings, pages 964–971. IEEE, 1993.
[16] A. Pigou. The economics of welfare. Routledge, 2017.
[17] T. Pradeau, F. Meunier, and R. Gupta. Bounding the price of anarchy for games with player-specific cost functions. 2014.
[18] R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2(1):65–67, 1973.
[19] T. Roughgarden. The price of anarchy is independent of the network topology. Journal of Computer and System Sciences, 67(2):341–364, 2003.
[20] T. Roughgarden. Selfish routing and the price of anarchy , volume 174. MIT press Cambridge, 2005.
[21] T. Roughgarden and F. Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317–342, 2015.
[22] T. Roughgarden and É. Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236–259, 2002.
[23] T. Roughgarden and É. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and economic behavior, 47(2):389–403, 2004.
[24] C. Wan. Coalitions in nonatomic network congestion games. Mathematics of Operations Research, 37(4):654–669, 2012.
[25] J. G. Wardrop. Road paper. some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers, 1(3):325–362, 1952.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top