网格经济学模型.pptx

Grid Computing 9-2The Grid EconomyLu WeinaNetwork and Information Center, USTCweinalu 2007.4.262007-4-261Outline INTRODUCTION 网格经济学模型 定价、计费和付费机制 几个相关项目 博弈论2007-4-262Resource Management and Scheduling资源消费者：资源消费者：Have work to do and needs to be met资源提供者：资源提供者：Have resources and dictate access to them2007-4-263Resource Management and Scheduling 网格资源提供者网格资源提供者Grid Resource Provider (GRP) ：为了：为了吸引资源消费者，它们将提供具有竞争性服务入口，吸引资源消费者，它们将提供具有竞争性服务入口，从而使它拥有的资源得到最大程度的使用从而使它拥有的资源得到最大程度的使用 网格资源消费者网格资源消费者Grid Resource Consumer (GRC) ：在：在其需要的时间限制内，希望能用最少的资源使用费用其需要的时间限制内，希望能用最少的资源使用费用来解决它提出的问题。来解决它提出的问题。2007-4-264Resource Management and Scheduling System-centric policies (traditional approach) 目的是获得系统范围性能的最优化目的是获得系统范围性能的最优化 由一个调度部件基于成本函数决定哪个任务在哪个资源上运由一个调度部件基于成本函数决定哪个任务在哪个资源上运行行 Legion, Condor , AppLeSPST, NetSolve, PUNCH Do not take resource access cost (price) into consideration 用户不想以高价购买而想通过协商定价用户不想以高价购买而想通过协商定价 User-centric policies 目的是获得用户基于目的是获得用户基于QoS 需求的效用的最大化需求的效用的最大化 需要由经济学原则来驱动需要由经济学原则来驱动2007-4-265Resource Management and Scheduling 基于经济的方法基于经济的方法 调度策略是在运行时动态制定的，由终端用户需求直接或间调度策略是在运行时动态制定的，由终端用户需求直接或间接驱动。接驱动。 终端用户以付费为代价终端用户以付费为代价,取代了传统的以运行应用所需要的软取代了传统的以运行应用所需要的软件和硬件成本为代价件和硬件成本为代价 价格策略基于供求价格策略基于供求2007-4-266Grid Economy: Methodology for Managing Supply-and-Demand for Resources and Encouraging Resource Sharing2007-4-267Why Economics in Grid 在网格系统的实际应用中，大量的资源不是无偿使用在网格系统的实际应用中，大量的资源不是无偿使用的，要吸引资源的拥有者加入网格，就必须保证他们的，要吸引资源的拥有者加入网格，就必须保证他们的利益，的利益， 这就需要经济学理论作支持。这就需要经济学理论作支持。 网格是一个异构的、动态的分布式环境，对资源的使网格是一个异构的、动态的分布式环境，对资源的使用和供应都是在不断的变化之中。通过引入经济学，用和供应都是在不断的变化之中。通过引入经济学，特别是基于价格的市场机制，由价格浮动来反映资源特别是基于价格的市场机制，由价格浮动来反映资源供需情况的变化，通过供需均衡实现资源优化分配，供需情况的变化，通过供需均衡实现资源优化分配，能够很好地表现网格的动态特征。能够很好地表现网格的动态特征。 网格环境下的资源分配涉及到消费者、生产者的个体网格环境下的资源分配涉及到消费者、生产者的个体行为，微观经济学中的一些模型正好与之配合。行为，微观经济学中的一些模型正好与之配合。2007-4-268Outline INTRODUCTION 网格经济学模型网格经济学模型 定价、定价、计费和付费机制计费和付费机制 几个相关项目几个相关项目 博弈论2007-4-269网格信息服务器（GIS） 记录了网格中可用资源的信息记录了网格中可用资源的信息,在网格环境中起中介和在网格环境中起中介和仲裁的作用仲裁的作用 网格资源消费者欲寻找合适的资源网格资源消费者欲寻找合适的资源,必须先向网格信息必须先向网格信息服务器查询服务器查询,获得适合自己条件的资源的信息获得适合自己条件的资源的信息,然后再与然后再与资源提供者进行交互。资源提供者进行交互。 网格资源提供者想要出售资源网格资源提供者想要出售资源,必须先向网格信息服务必须先向网格信息服务器注册器注册,资源消费者才可能找到这个资源。资源消费者才可能找到这个资源。 网格信息服务器还负责协调网格货币的流通。网格信息服务器还负责协调网格货币的流通。2007-4-2610网格经济模型的特点资源作为一种商品资源作为一种商品,其价格主要由该商品的供求状况所决定。其价格主要由该商品的供求状况所决定。GRC和和GRP都可以来提出进行资源分配交易。都可以来提出进行资源分配交易。GRP和和GRC都致力于最大化他们自己的效用函数。都致力于最大化他们自己的效用函数。GRP提供资源时可以定义资源价格提供资源时可以定义资源价格,价格有可能具有多个参数来反价格有可能具有多个参数来反映资源的实际情况。映资源的实际情况。网格计算环境必须提供合适的底层网格计算环境必须提供合适的底层,包括安全、信息、远程资源的包括安全、信息、远程资源的透明存取和信息服务等使我们能够将透明存取和信息服务等使我们能够将GRP和和GRC联系在一起。联系在一起。2007-4-2611常见模型 现有的用于网格资源交易管理的经济模型主要现有的用于网格资源交易管理的经济模型主要有有: 商品市场模型, 牌价模型, 议价模型议价模型, 投标模型, 拍卖模型,按比例分配资源模型按比例分配资源模型, 垄断模型等垄断模型等等。等。2007-4-2612商品市场模型由由GRP决定使用资源的价格决定使用资源的价格,根据资源的使用量对网格资源消费者根据资源的使用量对网格资源消费者进行收费进行收费资源价格的制定应该能够使资源的供求关系达到均衡。资源价格的制定应该能够使资源的供求关系达到均衡。根据定价策略分成两种：根据定价策略分成两种： 价格不变：对供求变化不敏感价格不变：对供求变化不敏感 基于供求关系：当需求增加或者供给减少时基于供求关系：当需求增加或者供给减少时,价格会增加直到价格会增加直到市场达到新的供求均衡。市场达到新的供求均衡。2007-4-2613商品市场模型2007-4-2614商品市场模型 优点：资源消费者可以清楚地看到所有在网格中的资优点：资源消费者可以清楚地看到所有在网格中的资源和使用价格信息源和使用价格信息, 以便消费者根据自己的以便消费者根据自己的QoS需求来需求来寻找合适的资源提供者。寻找合适的资源提供者。 缺点：由于价格是按照供求情况事先确定好的缺点：由于价格是按照供求情况事先确定好的, 也不考也不考虑到资源的利用效率虑到资源的利用效率,不管最后的服务质量是否达到要不管最后的服务质量是否达到要求求, 使用价格是不会改变的使用价格是不会改变的, 所以缺乏一定的灵活性。所以缺乏一定的灵活性。2007-4-2615牌价模型 牌价模型和商品价格模型很相似，区别是，为了吸引牌价模型和商品价格模型很相似，区别是，为了吸引新的消费者去建立市场共享或鼓励使用者考虑使用更新的消费者去建立市场共享或鼓励使用者考虑使用更便宜的时间而发布专门的告示。在这种情况下，代理便宜的时间而发布专门的告示。在这种情况下，代理不直接和不直接和GSP协商价格，而是使用牌价，通常这些价协商价格，而是使用牌价，通常这些价格比一般情况下的价格都更便宜。格比一般情况下的价格都更便宜。2007-4-2616牌价模型2007-4-2617招标模型 分布式环境中用于服务协商的最广泛的模型。分布式环境中用于服务协商的最广泛的模型。 一般步骤：一般步骤： l. 消费者通告它的请求消费者通告它的请求, 同时从同时从GSP中邀请竞标。中邀请竞标。 2. 感兴趣的感兴趣的GSP评估这个请求，并提交竞标价。评估这个请求，并提交竞标价。 3. 代理对各个代理对各个GSP的竞标价进行评价，接着和最合的竞标价进行评价，接着和最合适的适的GSP签订协议。签订协议。 4. 代理和代理和GSP进行私下的协商，并使用资源。进行私下的协商，并使用资源。2007-4-2618招标模型 优点是，如果被选择的优点是，如果被选择的GSP不能够提交一个令人满意不能够提交一个令人满意的服务结果，它可以向别的的服务结果，它可以向别的GSP寻找服务。寻找服务。 招标模型允许不经过协商而直接签订合同。这种模型招标模型允许不经过协商而直接签订合同。这种模型可以简化协议和提高某些服务的效率。可以简化协议和提高某些服务的效率。2007-4-2619拍卖模型 在拍卖模型中在拍卖模型中, 处理的是一个处理的是一个GRP对多个对多个GRC的情况的情况,其中主要有三类角色其中主要有三类角色:资源提供者资源提供者,资源资源消费者以及协调者。协调者是主持拍卖过程的消费者以及协调者。协调者是主持拍卖过程的角色角色,设定了一系列买方和卖方都认可的规则。设定了一系列买方和卖方都认可的规则。2007-4-2620拍卖模型2007-4-2621拍卖模型 拍卖模型拍卖模型 上升拍卖（英式拍卖）上升拍卖（英式拍卖） 下降拍卖（荷兰式拍卖）下降拍卖（荷兰式拍卖） 第一价格密封拍卖第一价格密封拍卖 第二价格密封拍卖（第二价格密封拍卖（Vickrey拍卖）拍卖） .2007-4-2622拍卖模型 从某种程度上来说保护了网格资源提供者从某种程度上来说保护了网格资源提供者GRP,对于对于GRP来说比较有优势来说比较有优势,也能让一些非也能让一些非常有能力的常有能力的GRP贡献出更好的资源贡献出更好的资源,让消费者让消费者使用。但使用此类模型可能导致竞价过高使用。但使用此类模型可能导致竞价过高,超过超过网格资源代理网格资源代理GRB所能承受的范围。这个模型所能承受的范围。这个模型并不需要对全局价格信息有过多了解并不需要对全局价格信息有过多了解,比较容易比较容易实施。实施。2007-4-2623Outline OVERVIEW 网格经济学模型网格经济学模型 定价、定价、计费和付费机制计费和付费机制 几个相关项目几个相关项目 博弈论2007-4-2624定价、计费、付费在网格经济环境中，资源拥有者和使用者都希望能获得最大的收在网格经济环境中，资源拥有者和使用者都希望能获得最大的收益。当有许多的益。当有许多的GSP提供相似的价格时，它们将需要一个竞争性提供相似的价格时，它们将需要一个竞争性的定价结构来吸引用户，高效率地使用资源和最大化收益。的定价结构来吸引用户，高效率地使用资源和最大化收益。被用户应用所消费的资源需要记账并被计费，所以应有不同的付被用户应用所消费的资源需要记账并被计费，所以应有不同的付费机制。费机制。GSP使用使用GridBank等的系统，这些系统作为中间人协调服务计费等的系统，这些系统作为中间人协调服务计费的工作。的工作。2007-4-2625如何确定价格 一个简单的定价方案是采用固定价格模型一个简单的定价方案是采用固定价格模型 基于不同参数的定价方案包括如下几种基于不同参数的定价方案包括如下几种: 统一定价模型统一定价模型 竞争性经济模型竞争性经济模型 使用时间使用时间 .2007-4-2626结算和付费的服务事项 用户的应用有不同的资源需求，这依赖于其执用户的应用有不同的资源需求，这依赖于其执行的计算和解决问题时使用的算法。如下的资行的计算和解决问题时使用的算法。如下的资源消费需要进行记账和付费源消费需要进行记账和付费. CPU使用时间和系统时间使用时间和系统时间 内存内存 最大的常驻编排尺寸页面大小最大的常驻编排尺寸页面大小 页错误页错误 使用的存储器使用的存储器 消费的网络带宽消费的网络带宽 信号接收信号接收 获取的软件和库获取的软件和库2007-4-2627付费机制 一个基于计算经济的网格框架需要支持不同的一个基于计算经济的网格框架需要支持不同的付费机制，它们包括付费机制，它们包括 预先付费预先付费 先使用后付费先使用后付费 基于承认的基于承认的 使用像使用像 GridBank这样的中介机构这样的中介机构2007-4-2628Outline INTRODUCTION 资源作为一种商品格经济学模型资源作为一种商品格经济学模型 定价、定价、计费和付费机制计费和付费机制 几个相关项目几个相关项目 博弈论2007-4-2629Compute Power Market CPM 计算力市场是网格环境下基于市场机制的资源和计算力市场是网格环境下基于市场机制的资源和作业调度系统，它特别是针对低端个人计算设备设计作业调度系统，它特别是针对低端个人计算设备设计的。传送元计算环境到一个计算市场，通过闲置的资的。传送元计算环境到一个计算市场，通过闲置的资源租用计算力，存贮，和特殊服务在计算市场中解决源租用计算力，存贮，和特殊服务在计算市场中解决问题。问题。CPM主要由市场，资源消费者，资源提供者和主要由市场，资源消费者，资源提供者和它们的相互作用组成。它支持商品市场模型、合约模它们的相互作用组成。它支持商品市场模型、合约模型、拍卖模型。型、拍卖模型。2007-4-2630GESA GESA即网格经济学服务框架即网格经济学服务框架(Grid Economic Services Architecture),是是Global Grid Forum (GGF) 的一个工作的一个工作组计划，目标是在组计划，目标是在GGF所提出的开放网格服务架构所提出的开放网格服务架构OGSA之上制定关于网格经济学服务架构的一些标准之上制定关于网格经济学服务架构的一些标准和规范。其包括了网格经济学服务接口和规范。其包括了网格经济学服务接口(Grid Economic Services Interface ,GESI)、可交易网格服务、可交易网格服务(Chargeable G rid Services ,CGS)和网格银行服务和网格银行服务(Grid Banking Services ,GBS)几个关键项目几个关键项目2007-4-2631G-Commerce G-Commerce是美国田纳西大学的研究项目，是美国田纳西大学的研究项目，使用市场经济学中的商品市场和拍卖模型在网使用市场经济学中的商品市场和拍卖模型在网格中进行动态资源分配。在格中进行动态资源分配。在G-Commerce中资中资源的价值是根据供需变化而变，对比了采用不源的价值是根据供需变化而变，对比了采用不同市场策略时的市场均衡，消费者效用和资源同市场策略时的市场均衡，消费者效用和资源提供者效用提供者效用.2007-4-2632Gridbus / EcoGrid 澳大利亚的澳大利亚的Buyya深入探讨了网格环境中的基于经济学深入探讨了网格环境中的基于经济学的分布式资源管理和调度问题，并设计了一系列应用组的分布式资源管理和调度问题，并设计了一系列应用组件件, 构架了一个通用的网格经济学框架构架了一个通用的网格经济学框架GRACE(GRid Architecture for Computational Economy） GRACE是一个基于经济学模型的分布式、可计算的经是一个基于经济学模型的分布式、可计算的经济学体系框架，用于在网格环境中进行资源交易。它利济学体系框架，用于在网格环境中进行资源交易。它利用了目前的一些网格系统如用了目前的一些网格系统如Globus, Legion等提供的大等提供的大量、成熟、可重用的中间件，例如资源协同分配服务量、成熟、可重用的中间件，例如资源协同分配服务DUROC、认证和安全服务、认证和安全服务GSl等等，并进行了扩展，等等，并进行了扩展，补充负责资源交易的中间件，如网格市场服务补充负责资源交易的中间件，如网格市场服务GMS、网格交易服务器网格交易服务器 GTS和用于电子支付的和用于电子支付的GBank等等。等等。2007-4-2633GRACE架构2007-4-2634GRACEGRACE架构中定义了一个网格资源经纪人架构中定义了一个网格资源经纪人(GRB)层，负责资源层，负责资源发现、选择和绑定等关键任务。其中作业控制代理负责接收用户发现、选择和绑定等关键任务。其中作业控制代理负责接收用户作业作业;网格浏览器和资源调度器用于资源发现和选择网格浏览器和资源调度器用于资源发现和选择;交易管理器交易管理器负责与每个网格服务提供者的交易管理器进行资源价格协商负责与每个网格服务提供者的交易管理器进行资源价格协商:部署部署代理则将作业与实际资源进行绑定。代理则将作业与实际资源进行绑定。网格中间件层负责提供认证、网格中间件层负责提供认证、QOS保障等基本服务，这些功能可保障等基本服务，这些功能可以直接使用现有的以直接使用现有的Globus或其他网格系统的相关中间件。或其他网格系统的相关中间件。网格市场服务网格市场服务GMS类似于公告板，网格资源提供者可以在上面发类似于公告板，网格资源提供者可以在上面发布自己的资源相关信息，使得网格资源代理布自己的资源相关信息，使得网格资源代理GRB可以进行资源查可以进行资源查找和选择。找和选择。2007-4-2635GRACE 网格服务提供者层中的资源分配采用一些包括网格服务提供者层中的资源分配采用一些包括MOSIX 、LSF与与Condor那样的队列系统进行本地资源管理。那样的队列系统进行本地资源管理。 在在GRACE架构中交易管理器居于核心地位，架构中交易管理器居于核心地位，GRB完完成资源选择后，其内部的交易管理器就会与对应的资成资源选择后，其内部的交易管理器就会与对应的资源提供者，也就是网格服务提供者源提供者，也就是网格服务提供者GSP的交易管理器的交易管理器进行通信，讨论对资源的使用问题，最主要的也就是进行通信，讨论对资源的使用问题，最主要的也就是价格问题。价格问题。GRACE架构中提出了固定价格、拍卖、垄架构中提出了固定价格、拍卖、垄断等多种经济学模型，提供了多种可选择的价格协商断等多种经济学模型，提供了多种可选择的价格协商机制。机制。2007-4-2636GRACE Nimrod-G 是是GRACE框架下的网格资源代理框架下的网格资源代理GRB原型，使用原型，使用Nimrod-G作为作为GRACE架构中架构中的网格资源代理效果显著。的网格资源代理效果显著。 定价算法基于两项最为重要的定价算法基于两项最为重要的QoS需求来设计需求来设计，即作业运行时间，即作业运行时间(runtime)和预算和预算(budget) 。2007-4-2637参考文献“The Grid economy ” Rajkumar Buyya, David Abramson, Srikumar Venugopal“Grid Resource Allocation and Control Using Computational Economies” R. Wolski, J. Brevik, J. Plank and T.Bryan“Economic Models for Resource Management and Scheduling in Grid Computing” R. Buyya, D.Abramson, J. Giddy and H. StockingerGrid Economy Comes of Age:Gridbus Technologies for Service-Oriented Cluster and Grid Computing R.Buyya Nimrod-G:An Architecture for a Resource Management and Scheduling System in a Global Computational Grid R.Buyya,D.Abramson,J.Giddy “Auctions for Network Resource Sharing,”A. Lazar and N. Semret“A Market-Oriented Grid Directory Service for Publication and Discovery of Grid Service Providers and their Services,” J. Yu, S. Venugopal, and R. Buyya“A Grid Service Brokerfor Scheduling Distributed Data-Oriented Applications on Global Grids,” S. Venugopal, R. Buyya, and L. Winton, 2007-4-2638博弈论weinalu 2007.4.262007-4-2639博弈论 （game theory）：也叫对策论，所分析的是两个或两个以上的比赛者或参与者选择能够共同影响每一参加者的行动或策略的方式以及相应的均衡问题。博弈论博弈论2007-4-2640 博弈论的指导思想：假设你的对手在研究你的策略，并采取追求自身最大利益行动的时候，你如何选择最有效的策略。 策略选择策略选择（dominant strategy）：无论其他博弈者采用何种战略，该博弈者的策略总是最好的。2007-4-2641（dominant equilibrium）：在两个（或全部）博弈者都采用占优策略时的结果。（Nash equilibrium）：在其他博弈者的策略给定时，没有一方还能改善自己的获利的境况。2007-4-2642智猪博弈智猪博弈 猪圈里有两只猪，一只比较大，一只比较小。猪圈狭猪圈里有两只猪，一只比较大，一只比较小。猪圈狭长，猪食槽在一头，猪食按钮在另一头，按一下会有长，猪食槽在一头，猪食按钮在另一头，按一下会有8个单位的猪食落进槽里。由于按钮和食槽距离较远，个单位的猪食落进槽里。由于按钮和食槽距离较远，按按钮的体力耗费相当于按按钮的体力耗费相当于2个单位的食物。若大猪先到个单位的食物。若大猪先到，大猪吃，大猪吃7个单位，小猪只能吃个单位，小猪只能吃1个单位；若同时到，个单位；若同时到，大猪吃大猪吃5个单位，小猪吃个单位，小猪吃3个单位；若小猪先到，大猪个单位；若小猪先到，大猪小猪各吃小猪各吃4个单位个单位2007-4-26433，12，47，-10，0按按按按等待等待等待等待小猪小猪大猪大猪智猪博弈的纳什均衡智猪博弈的纳什均衡：（：（按，等待）按，等待）小猪的占优策略：等待小猪的占优策略：等待大猪无占优策略大猪无占优策略2007-4-2644 答案是：小猪将舒舒服服地等在食槽边，而大答案是：小猪将舒舒服服地等在食槽边，而大猪则为一点残羹不知疲倦地奔忙于按钮和食槽猪则为一点残羹不知疲倦地奔忙于按钮和食槽之间之间 。 “小猪躺着大猪跑小猪躺着大猪跑”的现象是由于故事中的游的现象是由于故事中的游戏规则所导致的。规则的核心指标是：每次落戏规则所导致的。规则的核心指标是：每次落下的事物数量和按钮与投食口之间的距离。下的事物数量和按钮与投食口之间的距离。2007-4-2645改变方案 改变方案一：减量方案。投食仅原来的一半分改变方案一：减量方案。投食仅原来的一半分量。结果是小猪大猪都不去按按钮了。小猪去量。结果是小猪大猪都不去按按钮了。小猪去按，大猪将会把食物吃完；大猪去按，小猪将按，大猪将会把食物吃完；大猪去按，小猪将也会把食物吃完。谁去按按钮，就意味着为对也会把食物吃完。谁去按按钮，就意味着为对方贡献食物，所以谁也不会有按按钮的动力了方贡献食物，所以谁也不会有按按钮的动力了。 如果目的是想让猪们去多按按钮，这个游戏规如果目的是想让猪们去多按按钮，这个游戏规则的设计显然是失败的。则的设计显然是失败的。 2007-4-2646 改变方案二：增量方案。投食为原来的一倍分量。结改变方案二：增量方案。投食为原来的一倍分量。结果是小猪、大猪都会去按按钮。谁想吃，谁就会去按果是小猪、大猪都会去按按钮。谁想吃，谁就会去按按钮。反正对方不会一次把食物吃完。小猪和大猪相按钮。反正对方不会一次把食物吃完。小猪和大猪相当于生活在物质相对丰富的当于生活在物质相对丰富的“共产主义共产主义”社会，所以社会，所以竞争意识却不会很强。竞争意识却不会很强。 对于游戏规则的设计者来说，这个规则的成本相当高对于游戏规则的设计者来说，这个规则的成本相当高（每次提供双份的食物）；而且因为竞争不强烈，想（每次提供双份的食物）；而且因为竞争不强烈，想让猪们去多按按钮的效果并不好。让猪们去多按按钮的效果并不好。 2007-4-2647 改变方案三：减量加移位方案。投食仅原来的改变方案三：减量加移位方案。投食仅原来的一半分量，但同时将投食口移到按钮附近。结一半分量，但同时将投食口移到按钮附近。结果呢，小猪和大猪都在拼命地抢着按按钮。等果呢，小猪和大猪都在拼命地抢着按按钮。等待者不得食，而多劳者多得。每次的收获刚好待者不得食，而多劳者多得。每次的收获刚好消费完。消费完。 对于游戏设计者，这是一个最好的方案。成本对于游戏设计者，这是一个最好的方案。成本不高，但收获最大。不高，但收获最大。 2007-4-2648 原版的原版的“智猪博弈智猪博弈”故事给了竞争中的弱者（故事给了竞争中的弱者（小猪）以等待为最佳策略的启发。但是对于社小猪）以等待为最佳策略的启发。但是对于社会而言，因为小猪未能参与竞争，小猪搭便车会而言，因为小猪未能参与竞争，小猪搭便车时的社会资源配置的并不是最佳状态。为使资时的社会资源配置的并不是最佳状态。为使资源最有效配置，规则的设计者是不愿看见有人源最有效配置，规则的设计者是不愿看见有人搭便车的。而能否完全杜绝搭便车的。而能否完全杜绝“搭便车搭便车”现象，现象，就要看游戏规则的核心指标设置是否合适了。就要看游戏规则的核心指标设置是否合适了。2007-4-2649斗鸡博弈斗鸡博弈 假设有两个人举着火棍从独木桥的两假设有两个人举着火棍从独木桥的两端走向中央进行火拼，每个人都有两端走向中央进行火拼，每个人都有两种战略：继续前进，或退下阵来。若种战略：继续前进，或退下阵来。若两个人都继续前进，则两败俱伤；若两个人都继续前进，则两败俱伤；若一方前进另一方退下来，前进者取得一方前进另一方退下来，前进者取得胜利，退下来的丢了面子；若两人都胜利，退下来的丢了面子；若两人都退下来，两人都丢面子。退下来，两人都丢面子。2007-4-2650-3，-32，00，20，0进进进进退退退退乙乙甲甲斗鸡博弈有两个纳什均衡：斗鸡博弈有两个纳什均衡：如果一方进，另一方的最优战略就是退。如果一方进，另一方的最优战略就是退。2007-4-2651囚徒困境 两个嫌疑犯（和）作案后被警察抓住，隔离审讯两个嫌疑犯（和）作案后被警察抓住，隔离审讯；警方的政策是；警方的政策是“坦白从宽，抗拒从严坦白从宽，抗拒从严”，如果两人都，如果两人都坦白则各判年；如果一人坦白另一人不坦白，坦白坦白则各判年；如果一人坦白另一人不坦白，坦白的放出去，不坦白的判年；如果都不坦白则因证的放出去，不坦白的判年；如果都不坦白则因证据不足各判据不足各判1年。年。2007-4-2652 坦白坦白不坦白不坦白坦白坦白-8,-80,-10不坦白不坦白-10,01,1Nash Equilibrium 2007-4-2653三方对决2007-4-26542007-4-2655三方对决之分析 假如张三先向李四开枪并打中对方假如张三先向李四开枪并打中对方，他等于他等于签下自己的死亡保证书签下自己的死亡保证书，因为接下来轮到王五因为接下来轮到王五，而他是百发百中而他是百发百中。王五不可能放弃向张三开枪王五不可能放弃向张三开枪的机会的机会，因为开枪将使他得到自己的最佳结果因为开枪将使他得到自己的最佳结果。所以所以，张三向李四开枪不是吸引人的选择张三向李四开枪不是吸引人的选择。 假如张三先向王五开枪并打中对方假如张三先向王五开枪并打中对方，接下来接下来轮到李四轮到李四，李四会向张三开枪李四会向张三开枪，李四的精确度李四的精确度是是80，所以张三活命的机会只有所以张三活命的机会只有20。2007-4-2656 到到目前为止目前为止，上述选择没有一个显得很有吸引上述选择没有一个显得很有吸引力力。张三的最佳策略是什么呢张三的最佳策略是什么呢？ 实际上实际上，他的最佳策略是向空中开枪他的最佳策略是向空中开枪！若是这若是这样样，李四就会向王五开枪李四就会向王五开枪，假如他没打中假如他没打中，王王五将向李四开枪并打死李四五将向李四开枪并打死李四。于是进入第二轮于是进入第二轮，又轮到张三开枪了又轮到张三开枪了；由于只剩下一个对手由于只剩下一个对手，他至少有他至少有30的概率保住性命的概率保住性命，因为这是他打因为这是他打中剩下这个对手的概率中剩下这个对手的概率。2007-4-2657 这个案例也说明一个道理：弱者可能通过放这个案例也说明一个道理：弱者可能通过放弃自己的第一个成功机会取得更好的结果弃自己的第一个成功机会取得更好的结果。 因此因此，你的幸存机会不仅取决于你自己的本，你的幸存机会不仅取决于你自己的本事，还要看你威胁到的人。一个没有威胁到事，还要看你威胁到的人。一个没有威胁到任何人的弱者，可能由于较强的对手相互残任何人的弱者，可能由于较强的对手相互残杀而幸存下来。王五是最厉害的神枪手，但杀而幸存下来。王五是最厉害的神枪手，但在此案例中的幸存概率却最低，只有在此案例中的幸存概率却最低，只有14。李四有李四有56的取胜机会；张三的最佳策略使的取胜机会；张三的最佳策略使他能以他能以30的精确度换取的精确度换取41.2的幸存概率的幸存概率。2007-4-2658 经典博弈论经典博弈论 剪刀、石头、布剪刀、石头、布 性别战性别战 . 演化博弈论演化博弈论 鹰鸽博弈鹰鸽博弈 雪堆博弈雪堆博弈 .2007-4-2659参考文献张维迎，张维迎，博弈论与信息经济学博弈论与信息经济学，上海三联书店，上海三联书店，1996美美Fudenberg、法法Tirole，博弈论博弈论，中国人民大学出版，中国人民大学出版，2002年（原著年（原著1991）法法Laffont、Martimort，激励理论激励理论(第一卷第一卷)：委托：委托代理模型代理模型，中国人民大学出版社，中国人民大学出版社，2002年年王则柯，王则柯，博弈论平话博弈论平话，中国，中国经济出版社经济出版社A Game Theoretic Framework for Incentives in P2P SystemsPricing Differentiated Services : A Game - Theoretic Approach Robust Incentive Techniques for Peer-to-Peer NetworksConsidering Altruism in Peer-to-Peer Internet Streaming Broadcast基于博弈论框架的基于博弈论框架的p2p激励模型激励模型2007-4-2660 Thank you! 2007-4-2661