跳到主要內容

臺灣博碩士論文加值系統

(35.173.42.124) 您好!臺灣時間:2021/07/26 14:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:鍾偉韶
研究生(外文):Wei-Shao Chung
論文名稱:單一終點網路設計賽局的價格穩定性
論文名稱(外文):The price of stability in single-sink network design game
指導教授:陳和麟
口試委員:于天立呂學一魏宏宇
口試日期:2015-07-22
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:43
中文關鍵詞:賽局理論網路設計價格穩定性連接賽局奈許平衡
外文關鍵詞:Game TheoryNetwork DesignPrice of StabilityNash EquilibriumConnection Game
相關次數:
  • 被引用被引用:0
  • 點閱點閱:130
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文裡我們討論網路設計賽局,這種賽局探討的是整體系統效能與個體行為間的關係。這個賽局模型的架構是在一個圖裡有許多獨立的玩家,每個玩家都有著自己的起點和終點,並想找到一條路徑連在一起。經過每條邊都要支付特定的費用,而費用是由使用該邊的玩家們共同承擔。每個玩家都是自私的並希望盡可能地降低自己的花費。而這樣的行為可能會造成社會成本的增加。網路設計賽局主要就是探討這樣的行為會對整個系統帶來多大影響,並試圖降低系統的損失。

我們考慮其中一種網路設計賽局,單一終點環狀賽局。這種賽局的拓撲是環狀的,並且所有玩家都想連到一個共同的目標。我們證明了在這種賽局底下,PoS會是4/3。之後我們又考慮了,在這個賽局底下,如果玩家有更多選擇,會對系統帶來多少影響,這影響是正面還是負面的。我們之後證明了,當玩家有多一個選擇時,在一些條件下PoS最多會是5/3。

In this thesis we introduce the network design game, which is concerned with the relationship between the the system performance and a large number of individuals in the network. In the model of this game, there are many independent players in a graph and want to find a path from a source node to their destination node. Each edge has its cost and the players who go through the edge would share the cost. All the players want to optimize their cost and do not care about the others. This selfish behavior may increase the social cost of the network. so the lost of the social cost between the quality at a Nash equilibrium and the quality at a optimum is a interesting topic in network design game.

We consider a specific case in network design game, single-sink ring network design game. In this game, the topology of the graph is a ring and all the players have the same destination. Then we prove that the price of stability in this game is 4/3. We further consider that what if players have more options. We add an option for the players in single-sink ring network, and prove that there is a upper bound of price of stability in some conditions, which is 5/3.

Contents iv
List of Figures v
List of Tables vi
1 Introduction 1
1.1 Network design game 1
1.2 Related work 2
1.3 Our Results 4
2 Model 7
2.1 Shapley Network design game 7
2.2 Price of stability (PoS) 9
3 Main Result 11
3.1 Ring structure network 11
3.2 Theta-structure network 27
Bibliography 41

[1] E.Anshelevich, A. Dasgupta, E.Tardos, T.Wexler, Near-Optimal Network Design with Selfish Agents. In Theory of Computing, 4(1):77-109, 2008.
[2] E.Anshelevich, A. Dasgupta, J. Kleinberg, E.Tardos, T.Wexler, T. Roughgarden The Price of Staility for Network Design with Fair Cost Allocation, In SIAM Jouranl on
Computing, pages 1602-1623, 2008.
[3] C. Papadimitriou, Algorithms, Games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, pages 749-753, 2001.
[4] V. Bilo, M. Flammini, L. Moscardelli, The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, In 2013 IEEE 54th
Annual Symposium on Foundations of Computer Science (FOCS), pages 638-647,2013.
[5] A. Fanelli, D. Leniowski, G. Monaco, P. Sankowski, The ring design game with fair cost allocation, In Internet and Network Economics, volume 7695, pages 546-552,2012.

[6] J. Li, An O( logn/
loglogn) upper bound on the price of stability for undirected Shapley network design games, In Information Processing Letters, volume 109, pages 876-878, 2009.
[7] H.-L. Chen, T. Roughgarden, G. Valiant, Designing network protocols for good equilibria, In SIAM Journal on Computing, 39(5):pages 1799-1832, 2010.
[8] R. Rosenthal, A class of games possessing pure-strategy Nash equilibria, In International Journal of Game Theory, volume 2, pages 65-67, 1973.
[9] A. Robert, Subjectivity and correlation in randomized strategies, In Journal of Mathematical Economics, volume 1, pages 67-96, 1974.
[10] A. Robert, A. Brandenburger, Epistemic Conditions for Nash Equilibrium, In Econometric, volume 63, pages 1161-1180, 1995.
[11] D. Braess, A. Nagurney, TWakolbinger On a Paradox of Traffic Planning, In Transportation Science, volume 39, pages 446-450, 2005.
[12] J. R. Correa, A. Schulz, N. Stier-Moses, Selfish Routing in Capacitated Network, In Mathematics of Operations Research, volume 29, pages 961-976, 2004.
[13] V. Bilo, I. Caragiannis, A. Fanelli, G. Monaco, Improved Lower Bounds on the Price of Stability of Undirected Network Design Games, In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), LNCS 6386, Springer, pages 90-101, 2010. Extended version to appear in Theory of Computing Systems.
[14] A. Fiat, H. Kaplan, M. Levy, S. Olonetsky, R. Shabo, On the price of stability
for designing undirected networks with fair cost allocations. In Proceedings of the 33rd Annual International Colloquium on Automata, Languages, and Programming
(ICALP), volume 4051 of Lecture Notes in Computer Science, pages 608-618, 2006.
[15] Y. Kawase, K. Makino, Nash Equilibria with Minimum Potential in Undirected Broadcast Games, In Proceedings of the 6th International Workshop on Algorithms
and Computation (WALCOM), LNCS 7157, Springer, pages 217-228, 2012.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top