博弈论

博弈论，又称为对策论（Game Theory），它是现代数学的一个新分支，也是运筹学的重要学科。博弈论研究的是具有竞争性质的现象，它考虑博弈中个体的倾向行为与实际行为，研究个体的行为所带来的影响。博弈论最早用于解释经济现象，比如垄断、生产，1944年出版的《博弈论和经济行为》引进了通用博弈的思想。1950年，纳什提出了后来被称为“纳什均衡”的概念。博弈论发展飞快，它成为经济学里广泛使用的数学分析工具之一，在生物、政治、军事、国际关系等学科都有广泛应用。经过前人不断探索，时至今日，博弈论已经发展成为一门比较完善的学科。

通常情况，博弈模型主要由三要素组成：

参与人：参与人是参与到博弈游戏的个体，每个参与人都有自己的决策权，如果参与人只有两位，则称为“两人博弈”，如果有更多的参与者，则称为“多人博弈”。参与人集合设为有限集。
策略：在一场博弈中，参与人可以行使自己的决策权，选择一个实际可行的行动方案，这个行动方案称为“策略”，策略不是凭空想象地，必须从有限的策略空间中选出。每个参与者的策略空间不尽相同，用si表示参与人选择的某个策略，用Si表示参与人的策略空间。
收益（或称效用）：“参与人”执行“策略”获得相应的“收益”，收益一般体现在博弈结束时，每个参与人的收益可能不同，可能有得有失，参与人i执行策略的收益函数用ui(s)表示。

考虑一种简单的情况：两个流浪汉在争夺一块面包（假设流浪汉都是自私的），抢到的收益为+1，没抢到的收益为-1，那么这是一场双人零和博弈，即u1(s)+u2(s)=0，这种博弈最关键的特征是收益的总和为0。两个饥肠辘辘流浪汉，其中任意一人能够填饱肚子，是以另一人的继续挨饿换来的，即一人的收益都来自于另一人的损失。

从社会整体利益角度出发，我们显然更愿意见到正和博弈，正和博弈是指经过博弈后，双方利益都有所增加，或者至少是一方的利益增加，而另一方利益不受损害。正和博弈又叫做合作博弈，它研究参与人采用何种策略来达成合作。与合作博弈相对的是非合作博弈，零和博弈是一种典型的非合作博弈。合作博弈与非合作博弈的重要区别在于前者强调联盟内部的信息互通和存在有约束力的可执行契约。信息互通是形成合作的首要前提和基本条件，能够促使具有共同利益的单个参与人为了同一目标而结成联盟。

纳什均衡

各参与人制定各自的策略，如果最终能达到一种稳定状态，那么就把这种情况叫做纳什均衡（Nash Equilibrium）。它是博弈论的一个重要概念，纳什均衡为博弈论提供了强有力的分析框架。为了解释纳什均衡，首先定义支配性策略：在一场博弈中，无论其他参与人的策略如何，某个参与人一定会选择某个确定的策略，这种策略对于该参与人来说就是支配性策略，显然，对于参与人来说，选择支配性策略是为了达到自己期望收益的最大值。在一场两人博弈中（也可以推广到更多参与人），如果两个博弈的参与人的策略组合分别是各自的支配性策略，那么这个策略组合就被定义为纳什均衡。

纳什均衡是关于博弈将会往什么地步发展的“一致”预测。如果所有参与人都会预测某个特定的稳定状态将会出现，那么每个参与人就没有动力偏离这个均衡。这是基于每个参与人都是自私的，这里的自私不是贬义词，每个参与人仅仅考虑自己的利益最大化，每个参与人都是精明的利己主义者。纳什均衡还有一种通俗的解释：博弈中的任何参与人都不可能通过单一地改变自己的策略从而提高自己的收益，这种稳定状态就叫做纳什均衡。

Stackelberg Game

Stackelberg Game，即斯塔克尔伯格模型，是一个两阶段的完全信息动态博弈。StackelbergGame由德国经济学家斯塔克尔伯格（H. Von Stackelberg）提出，最开始是为了解释企业间不对称的竞争问题。在经典博弈中，各方是同时选择策略的，以企业为例，企业甲在选择策略时并不知道企业乙的策略，反之亦然。但斯塔克尔伯格观察到，在市场上的企业并不是同时选择策略的，企业有大小之分、有上下游之分、有话语权大小之分，各企业在市场上的地位并不是对称的，通常来说，小企业先观察到大企业的行为，再选择自己的策略。大企业与小企业可以看做一种主从关系，大企业作为领导者（Leader）具有领导优势，能够在博弈之中占据先机或者有利位置，跟随者（Follower）在领导者之后做出决策。所以Stackelberg Game也可以看做非对称博弈，博弈中每一个参与人的地位不尽相同。

对于求解Stackelberg Game，最常用的方法是逆向归纳法（backward induction），逆向归纳法是一个逻辑严密的方法，它从博弈的最后阶段开始，依次往回逆向推导，直至博弈的所有阶段推导完毕。在掌握完全信息的动态博弈中，先做决策的参与人肯定会考虑跟随者的决策。于是，只有在最后阶段的参与人才能不用考虑跟随者的决策而做出当前情况下自己的最优选择。当他的决策确定后，倒数第二阶段参与人的策略也可确定，因为他的跟随者——最后阶段的参与人已经做出了最优决策，于是倒数第二阶段的参与者可以根据这个信息作出自己的最优决策。按照这样，一步步逆向推导，直到第一阶段推导完毕。逆向归纳法可以在任何完美信息下的有限次博弈中使用，“有限次”指的是阶段数有限、策略空间有限。按照前文的数学描述，在最终阶段，在给定历史信息的情况下，参与人为了利益最大化会采取某种最优策略，再往回推到阶段，确定这一阶段参与人的最优策略，只需要给定阶段采取行动的参与人在历史信息下将采取之前推导出来的某种最优策略即可。当用逆向归纳法确定所有阶段所有参与人的策略时，我们可以建立一个策略组合，并且很容易证明这是一个纳什均衡。

不难看出，逆向归纳法其实就是求解子博弈完美纳什均衡的最简便的方法，从最后一个子博弈开始，依次往回递推即可。

海盗分赃

海盗分赃问题有许多版本，这里我们选择“过半原则、海盗都是贪婪且狠毒的”这一版本

有五个臭名昭著的海盗共同抢到了100枚金币，为了分配这100枚金币，他们按抽签的顺序依次提出方案：一号海盗提出一种分配方案，然后五人举手表决，超出半数同意方案才算通过（如果恰好一半同意则不算通过），这100枚金币就按一号海盗提出的分配方案分配；如果没有通过，一号海盗就会被扔进大海喂鲨鱼，再由二号海盗提出一种分配方案，然后四人举手表决，以此类推。海盗都是贪婪且狠毒的，即海盗在保证自己利益最大化的情况下更愿意看到其他海盗被扔进大海，假设每个海盗都是理性的、自私的、惜命的，且极度厌恶损失，海盗之间没有任何信任可言（不存在沟通结盟的情况），同时，每个海盗都知道其他海盗也是这样的人。那么，一号海盗要如何分配方案才能保命并且使自己的利益最大化？

海盗分赃是典型的完美信息的有限次动态博弈问题，我们可以使用逆向归纳法解决：

假设一、二、三号海盗都被扔进大海了，这时只剩四号、五号海盗，因为此时只剩两人，无论四号提出什么方案，五号只需要否决即可独吞所有金币，就算四号想保命而一分不取，五号也会狠毒地致四号于死地，所以金币分配方案必然是(0, 0, 0, 0, 100)。
往回反推，假设一号、二号海盗死亡，三号海盗是绝顶聪明的，他明白如果自己的方案不成功，在下一阶段，四号海盗肯定会死，如果自己的方案成功，四号海盗不用死，所以三号海盗无论提出什么方案，四号海盗都会支持自己，出于利益最大化的考虑，三号海盗可以给自己分配100枚金币，由于四号的支持，再加上自己的同意，该方案超出半数会通过，此时的方案是(0, 0, 100, 0, 0)。
再往回推，假设一号死亡，二号海盗也是绝顶聪明的，他预料到了：如果自己死亡，三号海盗的方案肯定会成功且能拿到所有金币，所以三号海盗肯定拉拢不了了，但现在是四个人，超出半数同意需要三票，所以二号海盗需要拉拢四号、五号海盗，如何拉拢？只需要给他们各自1枚金币即可，对于四号、五号海盗来说，这种情况会比三号海盗的方案要好，如果二号海盗的方案不成功，那自己可就什么也拿不到了，所以四号、五号会同意二号海盗的做法。故当前的方案是(0, 98, 0, 1, 1)。
再往回推，一号海盗在脑海里计算了一番，想拉拢二号海盗至少得给他99枚金币，而三号海盗在二号海盗的方案那什么也捞不到，所以一号海盗只需要花1枚金币拉拢三号海盗即可，此时是五人，除了一号他自己，还需要一人的支持，一号海盗可以选择四号、五号其中的一位进行拉拢，此时的拉拢必须要给他2枚金币，因为末位的海盗可以计算出自己在二号海盗方案里的收益为1枚金币，如果此时一号海盗只给1枚金币，出于海盗贪婪且狠毒的性格，在利益相同的情况下，末位的海盗是很乐意见到其他海盗被扔进大海喂鲨鱼的。所以一号海盗的方案是(97, 0, 1, 2, 0)或(97, 0, 1, 0, 2)。这就是一号海盗最后的方案，保命的同时最多可以获得97枚金币