博弈论与纳什均衡

一、博弈论

1、简介

2、博弈论类型

博弈的分类根据不同的基准也有不同的分类。 一般认为，博弈主要可以分为合作博弈和非合作博弈。合作博弈和非合作博弈的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议，如果有，就是合作博弈， 如果没有，就是非合作博弈。从行为的时间序列性，博弈论进一步分为静态博弈、动态博弈两类：静态博弈是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动；动态博弈是指在博弈中，参与人的行动有先后顺序，且后行动者能够观察到先行动者所选择的行动。通俗的理解：”囚徒困境”就是同时决策的，属于静态博弈；而棋牌类游戏等决策或行动有先后次序的，属于动态博弈。
按照参与人对其他参与人的了解程度分为完全信息博弈和不完全信息博弈。完全博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息。不完全信息博弈是指如果参与人对其他参与人的特征、策略空间及收益函数信息了解的不够准确、或者不是对所有参与人的特征、策略空间及收益函数都有准确的信息，在这种情况下进行的博弈就是不完全信息博弈。
经济学家们所谈的博弈论一般是指非合作博弈，由于合作博弈论比非合作博弈论复杂，在理论上的成熟度远远不如非合作博弈论。
非合作博弈又分为：完全信息静态博弈，完全信息动态博弈，不完全信息静态博弈，不完全信息动态博弈。与上述四种博弈相对应的均衡概念为：纳什均衡（Nash equilibrium），子博弈精炼纳什均衡（subgame perfect Nash equilibrium），贝叶斯纳什均衡（Bayesian Nash equilibrium），精炼贝叶斯均衡（perfect Bayesian equilibrium）。
博弈论还有很多分类，比如：以博弈进行的次数或者持续长短可以分为有限博弈和无限博弈；以表现形式也可以分为一般型（战略型）或者展开型；以博弈的逻辑基础不同又可以分为传统博弈和演化博弈。 [4]

二、纳什平衡

1、简介

纳什平衡（Nash equilibrium），又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称作支配性策略。如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个组合就被定义为纳什平衡。 一个策略组合被称为纳什平衡，当每个博弈者的平衡策略都是为了达到自己期望收益的最大值，与此同时，其他所有博弈者也遵循这样的策略。
讲到GTO，就不得不提到博弈论中非常著名的一个理论：纳什均衡（Nash Equilibrium）。该理论是由著名的经济学家，博弈论创始人，诺贝尔奖获得者约翰·纳什提出的，也就是电影《美丽心灵》的男主角原型。该理论是说：在非合作类博弈中，存在一种策略组合，使得每个参与人的策略是对其他参与人策略的最优反应。如果参与者当前选择的策略形成了“纳什均衡”，那么对于任何一位参与者来说，单方更改自己的策略不会带来任何好处。
约翰·纳什证明了在每个参与者都只有有限种策略选择，并允许混合策略的前提下，纳什均衡一定存在。上边的解释还是有点拗口，这里通过几个例子，更直观的理解一下这个理论。

2、纳什均衡由来

关于纳什平衡的普遍意义和存在性定理的证明等奠定非合作博弈理论发展基础的重要成果，是约翰·纳什在普林斯顿大学攻读博士学位时完成的。实际上，博弈论的研究起始于1944年冯·诺依曼（Von Neumann）和奥斯卡·摩根斯坦（Oscar Morgenstern）合著的《博弈论和经济行为》。然而却是纳什首先用严密的数学语言和简明的文字准确地定义了纳什平衡这个概念，并在包含“混合策略（mixed strategies）”的情况下，证明了纳什平衡在n人有限博弈中的普遍存在性，从而开创了与诺依曼和摩根斯坦框架路线均完全不同的“非合作博弈（Non-cooperative Game）”理论，进而对“合作博弈（Cooperative Game）”和“非合作博弈”做了明确的区分和定义。阿尔伯特·塔克（Albert tucker）教授评价其论文，“这是对博弈理论的高度原创性和重要的贡献。它发展了本身很有意义的n人有限非合作博弈的概念和性质。并且它很可能开拓出许多在两人零和问题以外的，至今尚未涉及的问题。在概念和方法两方面，该论文都是作者的独立创造。”

3、纳什均衡分类

纳什平衡可以分成两类：“纯战略纳什平衡”和“混合战略纳什平衡”。 要说明纯战略纳什平衡和混合战略纳什平衡，要先说明纯战略和混合战略。
所谓纯战略是提供给玩家要如何进行赛局的一个完整的定义。特别地是，纯战略决定在任何一种情况下要做的移动。战略集合是由玩家能够施行的纯战略所组成的集合。而混合战略是对每个纯战略分配一个机率而形成的战略。混合战略允许玩家随机选择一个纯战略。混合战略博弈均衡中要用概率计算，因为每一种策略都是随机的，达到某一概率时，可以实现支付最优。因为机率是连续的，所以即使战略集合是有限的，也会有无限多个混合战略。
当然，严格来说，每个纯战略都是一个“退化”的混合战略，某一特定纯战略的机率为1，其他的则为0。
故“纯战略纳什平衡”，即参与之中的所有玩家都玩纯战略；而相应的“混合战略纳什平衡”，之中至少有一位玩家玩混合战略。并不是每个赛局都会有纯战略纳什平衡，例如“钱币问题”就只有混合战略纳什平衡，而没有纯战略纳什平衡。不过，还是有许多赛局有纯战略纳什平衡（如协调赛局，囚徒困境和猎鹿赛局）。甚至，有些赛局能同时有纯战略和混合战略平衡。

三、博弈论与纳什均衡案例

1、囚犯的困境

假设有两个小偷A和B联手闯入民宅盗窃被抓，警方将两人置于不同的房间进行审讯，并给出如下政策：如果一个犯罪嫌疑人坦白并交出了赃物，两人都会被判有罪。如果另一个犯罪嫌疑人也坦白，则两人各被判刑8年；如果另一个犯罪嫌人抵赖，再加刑2年，而坦白者有功，会被立即释放。如果两人都抵赖，偷窃罪证据不足，但会因私入民宅而各判入狱1年。即：

表中的数字表示A，B各自的判刑结果。博弈论分析中一般都用这样的表来表示。
此时有人会觉得双方都抵赖就好了，但问题是双方被隔离，都会怀疑对方会出卖自己以求自保。两个人都会这么想：假如对方坦白，此时如果我抵赖得坐10年监狱，如果我坦白才坐8年监狱；假如对方抵赖，此时如果我也抵赖会被判1年，如果我坦白可以被释放。综合以上考虑，不管对方坦白与否，对我而言都是坦白划算。此时最后的“纳什均衡”只能是两个人都坦白，共同被判8年刑期。

2、智猪博弈

猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有个踏板，每踩一下踏板，在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果一只猪去踩踏板，另一只猪就有机会抢先吃到另一边落下的食物。但当小猪踩踏板时，大猪会在小猪跑到食槽之前刚好吃光所有的食物；大猪踩动了踏板，则有机会在小猪吃完落下的食物之前跑到食槽，争吃到另一半食物。
那么，两只猪各会采取什么策略？当然是小猪等在食槽边，而大猪不知疲倦地奔忙于踏板和食槽之间。因为，小猪踩踏板将一无所获，不踩踏板反而能吃上食物。对小猪而言，无论大猪是否踩动踏板，不踩踏板总是好的选择。反观大猪，已明知小猪不会去踩动踏板，自己亲自去踩踏板还有点吃的，总比不踩强，所以只好去踩踏板。

3、范式博弈

GOO公司和SAM公司存在利益关系，二者的收益会随着博弈的变化而不断更替。如下图：

双方各有两个可选策略“合作”与“背叛”，格中的四组数据表示四个博弈结局的各自收益，每组数据的第一个数字表示GOO公司的收益，后一个数字表示SAM公司的收益。
现在我们站在GOO公司的角度来思考整个博弈策略。假如SAM选择合作，那么我方合作的收益是3，而我方背叛的收益是5，我方应该选择背叛；假如SAM选择背叛，那么我方合作的收益是 -3，而我方背叛的收益是-1，我方还是应该选择背叛。
同理，SAM公司也会做出相同的选择。最后我们发现，本次博弈的双方都采取了背叛策略，各自的收益都为-1，这是一个比较糟糕的结局，尽管对任何一方来说都不是最糟糕的那种。
但博弈的次数往往不止一次，当二家公司经历了多次背叛策略的博弈之后，发现公式上还有一个（3，3）收益的双赢局面，这个结果显然要好很多，因此二家公司在之后的博弈过程中必然会尝试互建信任，从而驱使双方都选择合作策略。
但假使双方都知道博弈次数是有限的，也许下一次博弈就是最后一次，那么为了避免对方在最后一轮博弈中选择背叛而使我方遭受-3的损失，于是双方都会采取了背叛策略，最后的博弈结果又回到了（-1，-1）。
由此可见，随着次数的变化，博弈的性质也会发生变化，纳什均衡点会发生变化。

4、饿狮博弈

假设有A、B、C、D、E、F六只狮子（强弱从左到右依次排序）和一只绵羊。假设A吃掉绵羊后就会打盹，这时比A稍弱的B就会趁机吃掉A，接着B也会打盹，然后比B稍弱的C就会吃掉B，以此类推。问：狮子A敢不敢吃绵羊？
该题须采用逆向分析法，从最弱的F开始分析，依次前推。假设E睡着了，F肯定会吃掉E，因为在F的后面已没有其它狮子了，不用担心自己被吃掉。继续前推，既然E知道自己睡着会被F吃掉，那么E必然不敢吃睡着了的D。既然E不敢吃掉D，那么D则可以放心去吃睡着的C。依次前推，得出C不吃，B吃，A不吃。所以答案是狮子A不敢吃掉绵羊。

但是，如果我们在狮子F的后面增加了一只狮子G，总数变成7只，用逆向分析法按照上题步骤再推一次，如下图。这次的答案变成了狮子A敢吃掉绵羊。

对比两次博弈我们发现，狮子A敢不敢吃绵羊取决于狮子总数的奇偶性：当总数为奇数时，A敢吃；总数为偶数时，A则不敢吃。因此，总数为奇数和总数为偶数的狮群博弈结果形成了两个稳定的纳什均衡点。

5、硬币正反博弈

假如你和一个美女一起玩个数学游戏。美女提议：让我们各自亮出硬币的一面，如果我们都是正面，那么我给你3元；如果我们都是反面，我给你1元；剩下的情况你给我2元。那么你该不该和这位美女玩这个游戏呢？
这里需要讲一下纳什均衡的分类：
（1）纯战略纳什均衡，也就是说玩家都能够采取固定的策略（比如一直出正面或者一直出反面），使得每人 都赚得最多或亏得最少。
（2）混合战略纳什均衡，是对每个纯战略分配一个机率而形成的战略。混合战略允许玩家随机选择一个纯战略。混合战略纳什均衡中要用概率计算，达到某一概率时，可以实现支付最优。因为概率是连续的，所以即使战略集合是有限的，也会有无限多个混合战略。
在这个游戏中，应该采用混合策略纳什均衡。
假设我们出正面的概率是x，出反面的概率是1-x，美女出正面的概率是y，出反面的概率是1-y。为了使利益最大化，应该在对手出正面或反面的时候我们的收益都相等，即：
3x + (-2)(1-x) = (-2) x + 1(1-x )
解方程得x=3/8；同样，美女的收益：
-3y + 2(1-y) = 2y+ (-1) (1-y)，
解方程同样得y等于3/8。于是，我们就可以算美女每次的期望收益是：
(1-y) (2x-(1-x)) + y(-3x+2(1-x)) = 1/8元
即双方都采取最优策略的情况下，美女平均每次赢1/8元。所以当然不能和她玩这个游戏。其实只要美女采取了（3/8, 5/8）这个方案，不论你采用什么方案，都是不能改变局面的。但是当你也采用最佳策略时，至少可以保证自己输得最少。否则，你会赔掉更多。
参考：纳什均衡_百度百科