博弈论简单支付矩阵共25页文档

2.2最小化最大原则最小最大原则（minimax principle）是证明随机算法运行时间下界的一个通用技巧，只能用于对所有输入和随机选择，都可以在有限时间内中止的算法最小最大原则使用博弈论中的概念，我们首先对博弈论进行介绍。

博弈论博弈论（game theory）是研究多个理性个体间博弈过程和结果的理论，一个简单的博弈通常可以由一个收益/支付矩阵（payoff matrix）!表示，考虑两人间有先后次序的石头剪子布博弈:支付矩阵上的元!!"∈!表示行决策者Roberta选择策略#，列决策者Charles 选择策略$时，Charles付给Roberta 的钱数/收益/数目…剪刀布石头剪刀01-1布-101石头1-1RobertaCharlesØ这是一个双人零和博弈（two-person zero-sum game），即两个人的净收益总和为0Ø进一步假设这是一个零信息博弈，即没有博弈者知道对手的策略。

自然地，行博弈者想最大化支付值，列博弈者想最小化博弈值Ø如果R 选择策略i，他得到的支付值是min"!!"，此时R 的最优策略是(#=max $min"!!"，这是R 支付给C 值的下界Ø如果C选择策略j，他得到的支付值是m,-!!!"，此时C 的最优策略是(%=m#.m,-!!"，这是C 支付给R 值的上界剪刀布石头剪刀01-1布-101石头1-10RobertaCharles一般有，max*min+),+≤m<=-m>?,),+，当@.=@/=V时，称它为博弈的一个解值，对应的策略称为博弈的解、鞍点、最优策略。

对于有界的博弈，令B,D分别表示R 和C 的最优策略，有@=)01。

注意，博弈可能不只有一个最优策略，也就是说解不只一个。

混合策略前面的讨论是针对于单一策略，当可能的策略为一个概率分布时，我们称其为混合策略，此时行决策者在分布p =(H %,…,H 2)上进行决策，H ,表示选择策略<的概率，列决策者在分布K =(K %,…,K 3)上进行决策，K +表示选择策略L 的概率。

博弈论算法一、博弈的战略式表述及纳什均衡的定义在博弈论里，一个博弈可以用两种不同的方式来表述：一种是战略式表述（strategic form representation ），另一种是扩展式表述（或译为“展开式表述”）（extensive form representation ）。

从分析的角度看，战略式表述更适合于静态博弈，而扩展式表述更适合于讨论动态博弈。

1.1博弈的战略式表述战略式表述又称为标准式表述（normal form representation ）。

在这种表述中，所参与人同时选择各自的战略，所有参与人选择的战略一起决定每个参与人的支付。

战略式表述给出：1.博弈的参与人集合：(),1,2,,i n ∈ΓΓ=。

2.每个参与人的战略空间：,1,2,,i S i n =。

3.每个参与人的支付函数：12(,,,),1,2,,i n u s s s i n =。

我们用()11,,;,,n n G S S u u =代表战略式表述博弈。

例如在两个寡头产量博弈里，企业是参与人，产量是战略空间，利润是支付;战略式表述博弈为：{}121122120, 0; (,), (,)G q q q q q q ππ=≥≥ (1.1)这里i q 、i π别表示第i 个企业的产量和利润。

1.2纳什均衡的定义有n 个参与人的战略式表述博弈()11,,;,,n n G S S u u =，战略组合{}1,,,,i n s s s s ****=是一个纳什均衡。

如果对于每一个i 、i s *是给定其他参与人选择{}111,,,,,i i i n s s s s s *****--+=的情况下第个参与人的最优战略，即(,)(,),,i i i i i i i i u s s u s s s S i***--≥∀∈∀ (1.2)或者用另一种表述方式，i s *是下述最大化问题的解:111argmax (,...,,,,...,),1,2,..., ;i i i i i n i i s u s s s s s i n s S *****-+∈=∈(1.3)我们用这个定义来检查一个特定的战略组合是否是一个纳什均衡。

华为在阿根廷电信设备市场上的竞争博弈华为技术冇限公司是一家总部位于中国广东省除圳市的生产销售电信设备的员工持股 的民营科技公司，经过数十年的发展，成为全球最人的电信网络解决方案提供商，全球第二 人电信基站设备供应商，同时也是全球第六人手机厂商，其海外市场的利润占到其总利润的 75%：在华为进入阿根廷电信设备市场之前,阿根廷的电信设备市场山岌鼻信、阿尔卡特- 朗讯以及阿根廷本土设备供应商三家共同分享市场份额，接下來，我们将分析其不同条件下 的博弈结果： 1、完全信息情况下的静态轉弈A 、纳什均衡：我们将上述三家公司统称为原有垄断者•，华为称为虎视眈眈的潜在进入 者，原冇垄断者想要保住自己现冇的垄断地位，就会想要阻止潜在进入者进入，在这个博弈 中，原有垄断者有两种选择：一是进行斗争，打价格战；二是不斗争，默许其进入从而共同 竞争，具体的支付矩阵结果表示如下：不斗争 斗争根据纳什均衡的定义：各个参与者所做的是在给定其他参与者的策略是所能够做出的瑕 好的一组策略。

当潜在进入者选择进入时，原有垄断者的最优选择是不斗争，获彳'J 70单位 的利润；同样的，原有垄断者选择不斗争的情况2潜在进入者的最优选择是进入，获得 20单位的利润，从而获得一个要求纳什均衡的均衡（进入，不斗争），同理可以得出另一个 纳什均衡（不进入，斗争）。

B 、占优策略：现假设华为公司已经获得了阿根廷电信集团的经营许町证，在严格管制 情况下二者都不能以低于成本的价格进行价格战，同时禁止出现单一寡头垄断的情形，（各 自均有止的利润）在这两种情况卜考虎两者是否进行价格战的情况，具体支付矩阵如卜•所示: 原有垄断者对于潜在进入者而言，不论原有垄断者是否进行价格战，潜在进入者的占优策略都是进 行价格战，因为在原有垄断者定低价时，潜在进入者定低价可以获得额外的20单位利润， 在原有垄断者定高价时，潜在进入者定低价町以获得额外的10单位利润，从而确定华为必 将进行价格战，在完全信息情况卜，原何垄断者会将自己豐于潜在进入者的位豐进行决策, 从而决定自己也要进行价格战，否则会失去更多的利润。