大家早安、午安、晚安，今天我先从机器学习的学习中休息一下，来了解一些常见的博弈论模型，然后继续学习机器学习等。以下博弈论的介绍来自网络。
1、博弈论概念
博弈论(Game Theory)，博弈论是指研究多个个体或团队之间在特定条件制约下的对局中利用相关方的策略，而实施对应策略的学科。有时也称为对策论，或者赛局理论，是研究具有斗争或竞争性质现象的理论和方法，它是应用数学的一个分支，既是现代数学的一个新分支，也是运筹学的一个重要学科。目前在生物学、经济学、国际关系学、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。主要研究公式化了的激励结构（游戏或者博弈（Game））间的相互作用。
2、博弈论分类
图1
3、部分博弈论术语解释
1）合作博弈和非合作博弈
合作博弈和非合作博弈的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议，如果有，就是合作博弈，如果没有，就是非合作博弈。
2）静态博弈和动态博弈
从决策行为的时间序列来看，博弈可以分为静态博弈和动态博弈。静态博弈是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动；动态博弈是指在博弈中，参与人的行动有先后顺序，且后行动者能够观察到先行动者所选择的行动。通俗的理解："囚徒困境"就是同时决策的，属于静态博弈；而棋牌类游戏等决策或行动有先后次序的，属于动态博弈。
3）完全信息博弈和不完全信息博弈
按照参与人对其他参与人的了解程度分为完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数(也叫支付)有准确的信息。不完全信息博弈是指如果参与人对其他参与人的特征、策略空间及收益函数信息了解的不够准确、或者不是对所有参与人的特征、策略空间及收益函数都有准确的信息，在这种情况下进行的博弈就是不完全信息博弈。
此外，非合作博弈又分为：完全信息静态博弈，完全信息动态博弈，不完全信息静态博弈，不完全信息动态博弈。与上述四种博弈相对应的均衡概念为：纳什均衡(Nash equilibrium)，子博弈精炼纳什均衡（subgame perfect Nash equilibrium），贝叶斯纳什均衡(Bayesian Nash equilibrium)，精炼贝叶斯纳什均衡(perfect Bayesian Nash equilibrium)。其中，博弈中涉及的‘均衡’的概念，指的是一种相关量处于稳定值。
4）纳什均衡(Nash Equilibrium)
在一策略组合中，所有的参与者面临这样一种情况，当其他人不改变策略时，他此时的策略是最好的。也就是说，此时如果他改变策略他的支付将会降低。在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。纳什均衡点存在性证明的前提是“博弈均衡偶”概念的提出。所谓“均衡偶”是在二人零和博弈中，当局中人A采取其最优策略a*,局中人B也采取其最优策略b*,如果局中人B仍采取b*,而局中人A却采取另一种策略a，那么局中人A的支付不会超过他采取原来的策略a*的支付。这一结果对局中人B亦是如此。
5）均衡偶
一对策略a*(属于策略集A)和策略b*（属于策略集B）称之为均衡偶，对任一策略a(属于策略集A)和策略b（属于策略集B），总有：偶对（a, b*）≤偶对(a*,b*)≥偶对（a*，b）
6）纳什定理
任何具有有限纯策略的二人博弈至少有一个均衡偶。这一均衡偶就称为纳什均衡点。但纳什均衡点定义只局限于任何局中人不想单方面变换策略，而忽视了其他局中人改变策略的可能性，因此，在很多情况下，纳什均衡点的结论缺乏说服力，研究者们形象地称之为“天真可爱的纳什均衡点”。
4、部分具有代表性的博弈模型
1）智猪博弈/完全信息静态博弈(Boxed pigs Game)
智猪博弈是纳什提出的，假设猪圈里有一头大猪、一头小猪。猪圈的一头有猪食槽，另一头安装着控制猪食供应的按钮，按一下按钮会有10个单位的猪食进槽，但是谁按按钮就会首先付出2个单位的成本，若大猪先到槽边，大小猪吃到食物的收益比是9∶1；同时到槽边，收益比是7∶3；小猪先到槽边，收益比是6∶4。
图2 智猪博弈
在这个过程中，小猪有占优策略，大猪木有，小猪等待对它自己是最优的。
2）囚徒困境/非合作博弈（完全信息的静态博弈、纳什均衡）
1950年，由就职于兰德公司的梅里尔·弗勒德（Merrill Flood）和梅尔文·德雷希尔（Melvin Dresher）拟定出相关困境的理论，后来由顾问艾伯特·塔克（AlbertTucker）以囚徒方式阐述，并命名为“囚徒困境”。经典的囚徒困境如下：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检控对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监10年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（相关术语称互相“背叛”），则二人同样判监8年。
图3 囚徒困境
囚徒到底应该选择哪一项策略，才能将自己个人的刑期缩至最短？两名囚徒由于隔绝监禁，并不知道对方选择；而即使他们能交谈，还是未必能够尽信对方不会反口。就个人的理性选择而言，检举背叛对方所得刑期，总比沉默要来得低。试设想困境中两名理性囚徒会如何作出选择：若对方沉默时，背叛会让我获释，所以会选择背叛；若对方背叛指控我，我也要指控对方才能得到较低的刑期，所以也是会选择背叛。二人面对的情况一样，所以二人的理性思考都会得出相同的结论——选择背叛。背叛是两种策略之中的支配性策略。因此，这场博弈中唯一可能达到的纳什均衡，就是双方参与者都背叛对方，结果二人同样服刑8年。
3）海萨尼转换(the Harsanyi transformation，将不完全信息静态博弈转换为完全但不完美的静态博弈、贝叶斯纳什均衡)
人的支付函数类型是不清楚的。如果一些局中人不知道另一些局中人的支付函数，或支付函数不是共同知识，局中人就不知道他在与谁博弈，博弈的规则是没有定义的。因而在1967年以前，博弈论专家认为此时博弈的结构特征是不确定的，无法进行分析。海萨尼提出了一种处理不完全信息博弈的方法，即引入一个虚拟的局中人——“自然”。自然首先行动，它决定每个局中人的特征。每个局中人知道自己的特征，但不知道别的局中人特征。这种方法将不完全信息静态博弈变成一个两阶段动态博弈，第一个阶段是自然N的行动选择，第二阶段是除N外的局中人的静态博弈。这种转换被称为“海萨尼转换”，这个转换把“不完全信息”转变成为完全但不完美信息，从而可以用分析完全信息博弈的方法进行分析。“不完美信息”指的是，“自然”作出了它的选择，但其他参与人并不知道它的具体选择是什么，仅知道各种选择的概率分布。
在上述转换的基础上，海萨尼提出了贝叶斯纳什均衡(Bayesian Nash equilibrium)。对此，可以作如下解释：在不完全信息静态博弈中，参与人同时行动，没有机会观察到别人的选择。给定其他参与人的战略选择，每个参与人的最优战略依赖于自己的类型。由于每个参与人仅知道其他参与人有关类型的分布概率，而不知道其真实类型，因而，他不可能知道其他参与人实际上会选择什么战略。但是，他能够正确地预测到其他参与人的选择与其各自的有关类型之间的关系。因此，该参与人的决策目标就是：在给定自己的类型，以及给定其他参与人的类型与战略选择之间关系的条件下，使得自己的期望效用最大化。贝叶斯纳什均衡是一种类型依赖型战略组合。在给定自己的类型和其他参与人类型的分布概率的条件下，这种战略组合使得每个参与人的期望效用达到了最大化。
4）Stackelberg竞争(双寡头模型，完全且完美动态信息博弈)
Stackelberg leadership model是经济学中双寡头模型之一。它以德国经济学家Heinrich von Stackelberg的名字命名，在1934年出版的 "Marktform und Gleichgewicht" 中被阐述。用博弈论的语言说，这个博弈的两个参与者分别是leader和follower，它们进行的是数量竞争。leader先行选择产量，follower观察到leader的选择后再作选择。举栗子：某个地域，A本来处于垄断地位，利润是10亿，然后B是创业公司，想进入该市场，这期间可能的双方的利润变化如下：
图4 博弈树-利润分布
图5
在图5中，B采用的是倒推法（逆推法），不难发现，在图4中存在两个纳什均衡点：B不进入(A为10，B为0)、B进入且A不阻拦(AB均为4)。但是依据图5的分析，A最理智的行为是不阻挠，辣么，因为A的威胁是不可置信的，针对这一的现象，泽尔腾引入了子博弈完美纳什均衡的概念，目的就是将这些不可置信威胁战略的纳什均衡从均衡中剔除，比如去掉‘B不进入(A为10，B为0)’这样的均衡点。子博弈完美纳什均衡要求均衡战略的行为规则在每一个信息集上是最优的，也就是要去掉那些不可置信的威胁。
5）信号博弈(不完全信息的动态博弈、子精炼纳什均衡)
信号博弈是一种由一个发送者（S）和另一个接收者（R）所组成的非完全信息的动态博弈。一开始这个发送者有一个给定的类型（t），接着发送者会观察这个没有其他人（好比说接收者）知道的类型，去从讯息堆 M = {m1, m2, m3,..., mj} 中选择送出一个讯息（m），接着接收者会观察这个讯息后从他可行的动作中 A = {a1, a2, a3,...., ak} 选一个作为反应动作（a），这里要注意的是接收者除了讯息之外其他都无法得知（如发送者的类型t），接着根据（t, m, a）的组合来决定双方会获得的报酬或回报。这类型的博弈比如公交车上的小偷与乘客之间的博弈。小偷向乘客释放了谁反抗就殴打谁的信号，而乘客觉得小偷的信号是可信的，可能会议如下的几种情况：
图6
根据图6中的情况发现，对于乘客来说，小偷的威胁是可信的，因此，不反抗是最优的策略；对于小偷来说，乘客的不反抗下的不殴打策略最优。这一博弈的结果直接导致出现了不良的社会风气，纵容了小偷的违法行为。这就是一种信号博弈。
其实，在这个栗子中，如果我们能够提高乘客反抗时可能获取的利益，比如反抗会让乘客获得道德满足，辣么，这个不好的事情就会变得有转机，比如可能会获得如图7所示的博弈树：
图7
在图7中，因为出现了道德这样的信念，那么乘客结合自己的道德观，再次进行不一样的取舍，‘乘客反抗、小偷被打’出现的可能性更大。此时，这样的决策称为精炼贝叶斯均衡（也叫精炼贝叶斯纳什均衡）。没懂，那我借用知乎以为大牛的科普版解释：
图8 精炼贝叶斯均衡
举栗子说明一下：
图9 精炼贝叶斯均衡
6）重复博弈（Repeated Games）
其实，通俗来说，如果是一锤子买卖，辣么，大家都无所顾忌了，肯定是尽可能的谋求自己利益最大化，不惜欺骗等；但是，如果是来日方长的这种交易，辣么，大家在博弈中，就会有所顾忌，可能是薄利多销这种方式了，保证让大家继续合作下去。
重复博弈是指同样结构的博弈重复许多次，其中的每次博弈称为“阶段博弈”（stage games）。重复博弈是动态博弈中的重要内容，它可以是完全信息的重复博弈，也可以是不完全信息的重复博弈。在重复博弈中，每次博弈的条件、规则和内容都是相同的, 但由于有一个长期利益的存在, 因此各博弈方在当前阶段的博弈中要考虑到不能引起其它博弈方在后面阶段的对抗、报复或恶性竞争, 即不能象在一次性静态博弈中那样毫不顾及其它博弈方的利益。有时, 一方做出一种合作的姿态, 可能使其它博弈方在今后阶段采取合作的态度, 从而实现共同的长期利益。
以下我们用一个产品定价的例子讨论重复博弈，给出了一次性完全信息静态博弈的收益矩阵。
A、B两个参与人都有两种定价待选择：定高价或定低价。如果两个参与人都定低价，则每个参与人的收益均为20个单位；如果两人都定高价，则每人的收益均为30个单位；如果其中某一参与人定低价，而另一参与人定高价，则定低价的参与人有占有更多的市场份额获得40个单位的收益，定高价的参与人由于失去一部分市场份额而只获得10个单位的收益。显然，在这个一次性完全信息静态博弈中，两个参与人均有占优策略，占优策略均衡为A、B双方都定低价。
如果A、B之间的定价博弈是多次进行的，那么，问题就不是如此简单了。我们先来分析博弈重复次数为无限时的情况。
如果A、B双方都选择合作，都保持定高价，则双方在每个阶段的收益均为30个单位，记为(30，30，30，…)；如果A、B中有一方(如A)采取投机行为，在实际定价中选择不与对方合作，在第一阶段就通过选择定价策略使得选择高价策略的对手B受损，则受损的一方B一定会在第二阶段及其以后的定价中也选择低价策略，加以报复，这样一来，首先选择不合作的一方A在个阶段的收益为(40，20，20，…)，显然，其总收益远远小于合作、维持高价情况下的总收益。因为，首选选择不合作的一方A，只是在第一阶段获得了“额外”收益，但在以后个阶段的收益将因为对手B的报复性选择而减少，并且，重复若干此后，首先选择不合作的一方A将得不偿失。
在这里，B选择的策略称为“冷酷策略”(grim strategies)。冷酷策略是指重复博弈中的任何参与人的一次性不合作将引起其他参与人的永远不合作，从而导致所有参与人的收益减少。因此，所有参与人具有维持合作的积极性。我们再来讨论博弈重复次数为有限时的情况。
重复次数有限博弈与重复次数无限博弈之间的惟一区别，是所有参与人都可以明确无误地了解重复的次数，即可以准确地预测到最后一个阶段博弈。而在最后阶段的博弈中，任何一个参与人选择不合作，不会导致其他参与人的报复。因此，所有参与人都会在最后阶段的博弈中选择自己的占优策略，那就是不合作。上例中，在最后阶段博弈中选择低价是所有参与人的占优策略。
既然所有参与人都会在最后阶段选择不合作，那么，在倒数第二阶段博弈中任何参与人也就没有必要担心由于自己选择不合作，导致其他参与人在最后阶段博弈中的报复。因此所有参与人在倒数第二阶段博弈中，也都会选择不合作。即在倒数第二阶段博弈中，所有参与人都会选择占优策略。
由此类推，可以得出以下结论：在阶段性博弈存在惟一的纳什均衡时，阶段博弈的纳什均衡解就是重复次数有限博弈的唯一子博弈精炼纳什均衡解。即重复次数有限博弈的每个阶段的均衡解都是一次性博弈的纳什均衡解。注意，上述推论成立的前提条件是阶段性博弈纳什均衡的惟一性。
7)合作博弈（财产分配、Shapley值）
合作博弈与非合作博弈想对称，是一种参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。合作博弈强调的是集体理性，其最重要的两个概念是‘联盟’和‘分配’。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益，每个参与者从联盟中分配到的收益不小于单独经营所得收益。具体关于合作博弈的内容，请参考合作博弈
Shapley值（夏普里值）？据说，如果说纳什均衡是非合作博弈的核心的话，Shapley值就是合作博弈的核心，这么重要？！！
考虑这样一个联盟博弈：有一个三人财产分配问题：假定财产为100万元，这100万在三人之间进行分配。a拥有50%的决定权，b拥有40%的决定权，c拥有10%的决定权。规定，当超过50%的同意时，才能获得整个财产，否则三人将一无所获。辣么，咋办哩
图10 Shapley值
那么，如何计算边际贡献呢，夏普里给出了这样的计算形式：
图11 夏普里值的计算
根据夏普里值定义，所有排列的顺序是等可能的。而在每一个排列下，每个参与者对这个排列的联盟有一个边际贡献。在投票博弈中，这个值反映的是参与者与其他参与者结成联盟的可能性，因此夏普里值反映的是参与者的权利。
博弈论初步知识先到这里，本次只是简单讲网络知识收集汇总，希望能帮点小忙哈~~
网友评论