魏宏宇臺灣大學:電機工程學研究所許維哲Hsu, Wei-CheWei-CheHsu2010-07-012018-07-062010-07-012018-07-062009U0001-1508200918015300http://ntur.lib.ntu.edu.tw//handle/246246/188128同儕網路是一種被廣泛應用於各種網路服務的技術，然而同儕網路卻常常遇到"搭便車問題"。有很多機制藉由提供動機給各節點使他們願意貢獻出自己的資源。我們介紹了一個簡單的同儕網路串流系統的模型包含一個服務提供者並利用賽局理論來分析這個模型。此外，我們也找出了這個模型的奈許均衡並證明了其所含的一些性質。而為了解決同儕網路的問題，我們也設計了一個最佳化機制來讓服務提供者的期望效益能夠被最大化，這個機制也能保證個體願意加入服務，同時也願意誠實顯露自己的資訊。我們證明了這些特性，提供了含有服務提供者的同儕網路激勵機制設計一個全新的方向。Peer-to-peer(P2P) networking is a widespread technology for scalable networks which is already applied to various kinds of network service. However, P2P networks always harms suffered from free-rider problem thus there are many mechanism which is aimed to provide incentives for peers to contribute their own resource. We described a simple model for P2P streaming system with a system provider and also use game theory as a tool to formulate and analyze our model. We also found out the Nash equilibria of the game and prove several properties attained to the equilibria. To solve the problem of P2P networks, we proposed a P2P streaming auction model and designed an optimal mechanism for the model, which maximized the expected utility of the service provider while also ensures the individual rationality and incentive compatibility. We proved these properties of the mechanism and thus provide a brand-new orientation of incentive mechanism design for P2P network with service provider.List of Figures 1 Introduction 2.1 Game Theoretic Analysis of P2P Networks . . . . . . . . . . . . . . . . 3.2 Incentive Mechanism Design for P2P Networks . . . . . . . . . . . . . . 3.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Scope of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 P2P Video Streaming System Overview 6.1 Peer-to-peer Video Streaming . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Basic System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Game Formulation 9.1 Brief Introduction to Game Theory . . . . . . . . . . . . . . . . . . . . . 9.2 Game Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Equal Allocation Scheme 13.1 2-Players Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13v.2 n Players Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.3 n+1 Players Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Properties of Nash Equilibrium in Equal Allocation 35.1 Pareto Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36.2 Social Welfare Maximization . . . . . . . . . . . . . . . . . . . . . . . . 37.3 Individual Rationality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Brief Introduction to Incentive Mechanism Design 39.1 Introduction to Mechanism Design . . . . . . . . . . . . . . . . . . . . . 39.2 Desirable Properties of Mechanisms . . . . . . . . . . . . . . . . . . . . 41.2.1 Allocatively Efficient . . . . . . . . . . . . . . . . . . . . . . . . 41.2.2 Individual Rationality . . . . . . . . . . . . . . . . . . . . . . . 41.2.3 Truthfulness Properties . . . . . . . . . . . . . . . . . . . . . . . 42.3 Vickrey-Clarke-Groves Mechanisms . . . . . . . . . . . . . . . . . . . . 42.4 Myerson’s Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Incentive Mechanism of P2P Video Streaming Service 46.1 P2P Auction Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46.2 P2P Streaming Model with Bandwidth Allocation and Payment Decisionrocess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48.3 Truthful Mechanism for Bandwidth Allocation Game . . . . . . . . . . . 49.3.1 Bandwidth Allocation Game . . . . . . . . . . . . . . . . . . . . 49.3.2 Bandwidth Allocation with One Service Quality . . . . . . . . . 50.3.3 Bandwidth Allocation with Two Service Qualities . . . . . . . . . 51 Properties of the Proposed Mechanism 53.1 Truthfulness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Individual Rationality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54.3 Expected Profit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Conclusion 57ibliography 582219625 bytesapplication/pdfen-US同儕網路奈許均衡最佳化機制利益最大化Peer-to-peer(P2P)Nash equilibriumoptimal mechanismprofit maximizationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188128/1/ntu-98-R96921032-1.pdf