纳什均衡

悠悠 2022-08-19 08:21 208阅读 0赞

约翰·[纳什][Link 1]1948年作为年轻[数学][Link 2]博士生进入[普林斯顿大学][Link 3]。其研究成果见于题为《非[合作博弈][Link 4]》（1950）的[博士论文][Link 5]。该博士论文导致了《n人博弈中的均衡点》（1950）和题为《非合作博弈》（1951）两篇论文的发表。纳什在上述论文中，介绍了合作博弈与非合作博弈的区别。他对非合作博弈的最重要贡献是阐明了[包含][Link 6]任意人数局中人和任意偏好的一种通用解概念，也就是不限于两人[零和博弈][Link 7]。该解概念后来被称为纳什均衡。

##    定义 ##

假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的

[  ][Link 8]

纳什均衡

最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己利益最大化。所有局中人策略构成一个策略 [组合][Link 9] （Strategy Profile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。

纳什均衡达成时，并不意味着博弈双方都处于不动的状态，在顺序博弈中这个均衡是在博弈者连续的动作与反应中达成的。纳什均衡也不意味着博弈双方达到了一个整体的最优状态，以下的囚徒困境就是一个例子。

##    标准定义 ##

纳什均衡的定义：在博弈G=﹛S1,…,Sn：u1,…，un﹜中，如果由各个博弈方的各一个策略组成的某个策论组合（s1\*,…，sn\*）中，任一博弈方i的策论si\*，都是对其余博弈方策略的组合（s1\*,…s\*i-1,s\*i+1,…，sn\*）的最佳对策，也即ui（s1\*,…s\*i-1,si\*,s\*i+1,…，sn\*）≥ui（s1\*,…s\*i-1,sij\*,s\*i+1,…，sn\*）对任意sij∈Si都成立，则称（s1\*,…，sn\*）为G的一个纳什均衡。

##    纳什均衡经典案例：囚徒困境 ##

（1950年， [数学家][Link 10] 塔克任斯坦福大学 [客座教授][Link 11] ，在给一些心理学家作讲演时，讲到两个囚犯的故事。）

假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证

[  ][Link 12]

纳什均衡

据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑8年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。

<table style="margin:5px 0px; padding:0px; line-height:12px; font-family:simsun; border-collapse:collapse; border-spacing:0px; word-wrap:break-word; word-break:break-all; font-size:12px; color:rgb(102,102,102); background-color:rgb(254,254,254)">  囚徒困境博弈  
 <tbody> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> A╲B</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 坦白</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 抵赖</td> 
  </tr> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 坦白</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> -8，-8</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 0，-10</td> 
  </tr> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 抵赖</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> -10，0</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> -1，-1</td> 
  </tr> 
 </tbody> 
</table>

关于案例，显然最好的策略是双方都抵赖，结果是大家都只被判1年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才是 [亚当·斯密][Link 13] 的理论，假设每个人都是“理性的 [经济人][Link 14] ”，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，我抵赖，得坐10年监狱，坦白最多才8年；他要是抵赖，我就可以被释放，而他会坐10年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判8年刑期。

基于 [经济学][Link 15] 中Rational agent的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判8年的结局，纳什均衡”首先对亚当·斯密的“ [看不见的手][Link 16] ”的原理提出挑战：按照斯密的理论，在 [市场经济][Link 17] 中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个 [悖论][Link 18] ：从利己目的出发，结果损人不利己，既不利己也不利他。

##    另一个简单的例子 ##

你正在图书馆枯坐，一位陌生美女主动过来和你搭讪，并要求和你一起玩个数学游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你3元，如果我们都是反面，我给你1元，剩下的情况你给我2元就可以了。”那么该不该和这位姑娘玩这个游戏呢？这基本是废话，当然该。问题是，这个游戏公平吗？

每一种游戏依具其规则的不同会存在两种纳什均衡，一种是纯策略纳什均衡，也就是说玩家都能够采取固定的策略(比如一直出正面或者一直出反面)，使得每人都赚得最多或亏得最少；或者是混合策略纳什均衡，而在这个游戏中，便应该采用混合策略纳什均衡。

<table style="margin:5px 0px; padding:0px; line-height:12px; font-family:simsun; border-collapse:collapse; border-spacing:0px; word-wrap:break-word; word-break:break-all; font-size:12px; color:rgb(102,102,102); background-color:rgb(254,254,254)"> 
 <tbody> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> n\m</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 美女出正面</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 美女出反面</td> 
  </tr> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 你出正面</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> +3，-3</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> -2，+2</td> 
  </tr> 
  <tr> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> 你出反面</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> -2，+2</td> 
   <td align="left" style="margin:0px; padding:0px 10px; font-family:Verdana,宋体,sans-serif; line-height:22px; border:1px solid rgb(221,221,221)"> +1，-1</td> 
  </tr> 
 </tbody> 
</table>

假设我们出正面的概率是x，反面的概率是1-x。为了使利益最大化，应该在对手出正面或反面的时候我们的收益都相等，不然对手总是可以改变正反面出现的概率让我们的总收入减少，由此列出方程就是

**　3x + (-2)\*(1-x)=(-2) \* x + 1\*( 1-x )**

解方程得x=3/8,也就是说平均每八次出示3次正面，5次反面是我们的最优策略。而将x= 3/8代入到收益表达式 3\*x + (-2)\*(1-x) 中就可得到每次的期望收入，计算结果是 -1/8元。

同样，设美女出正面的概率是y，反面的概率是1-y，列方程

**　-3y + 2( 1-y )= 2y + (-1) \* ( 1-y )**

解得y也等于3/8，而美女每次的期望收益则是 2(1-y)- 3y = 1/8元。这告诉我们，在双方都采取最优策略的情况下，平均每次美女赢1/8元。

其实只要美女采取了(3/8,5/8)这个方案，不论你再采用什么方案，都是不能改变局面的。

如果全部出正面，每次的期望收益是 (3+3+3-2-2-2-2-2)/8=-1/8元；

如果全部出反面，每次的期望收益也是(-2-2-2+1+1+1+1+1)/8=-1/8元。

而任 何策略无非只是上面两种策略的线性组合，所以期望还是-1/8元。

但是当你也采用最佳策略时，至少可以保证自己输得最少。否则，你肯定就会被美女采用的策略针对，从而赔掉更多。

[Link 1]: http://baike.baidu.com/view/5457.htm
[Link 2]: http://baike.baidu.com/view/1284.htm
[Link 3]: http://baike.baidu.com/view/20708.htm
[Link 4]: http://baike.baidu.com/view/29599.htm
[Link 5]: http://baike.baidu.com/view/197043.htm
[Link 6]: http://baike.baidu.com/view/407031.htm
[Link 7]: http://baike.baidu.com/view/196849.htm
[Link 8]: http://baike.baidu.com/albums/28460/28460.html#0$8474fbdddbe9a8fc77c63828
[Link 9]: http://baike.baidu.com/view/67312.htm
[Link 10]: http://baike.baidu.com/view/66878.htm
[Link 11]: http://baike.baidu.com/view/171797.htm
[Link 12]: http://baike.baidu.com/albums/28460/28460.html#0$a6aed01bb70ab29aaf5133d9
[Link 13]: http://baike.baidu.com/view/53445.htm
[Link 14]: http://baike.baidu.com/view/249159.htm
[Link 15]: http://baike.baidu.com/view/31551.htm
[Link 16]: http://baike.baidu.com/view/401190.htm
[Link 17]: http://baike.baidu.com/view/17791.htm
[Link 18]: http://baike.baidu.com/view/2464.htm