无差异法求解循环相克博弈

P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。

1、简介

P对NP问题是Steve Cook于1971年首次提出。"P/NP问题"，这里的P指在多项式时间(Polynomial)里，一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算;NP指非确定性多项式时间(nondeterministic polynomial)，一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题。2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了"P/NP问题" ，并公开了证明文件。

2、排序问题

如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。

3、定义

为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者 no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求从A到B的最短路径，可以转化成:从A到B是否有长度为1的路径?从A到B是否有长度为2的路径?。。。从A到B是否有长度为k的路径?如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如找出无向图的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。这就是P对NP问题。

4、P≠NP论证

如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。

而现在，美国惠普实验室的数学家维奈·迪奥拉里卡围绕一个众所周知的NP问题进行论证，给出了P≠NP的答案。这就是布尔可满足性问题(Boolean Satisfiability Problem)，即询问一组逻辑陈述是否能同时成立或者互相矛盾。迪奥拉里卡声称，他已经证明，任何程序都无法迅速解答这个问题，因此，它不是一个P问题。

如果迪奥拉里卡的答案成立，说明P问题和NP问题是不同的两类问题，这也意味着计算机处理问题的能力有限，很多任务的复杂性从根本上来说也许是无法简化的。

对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的;但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题(Travelling Salesman Problem)，即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有计算机程序可以迅速给出这个答案。

迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可，但随后公布的论文终稿还将接受严格的审查。

（一）

假定大家在任何情况下都会遵守分配规则，即无论几个人都会进行投票，遭否决的提议人均会被扔下海。

那么这就是个简单的非合作动态博弈题目。

逆推法可以轻松解决。

只剩4，5时，4只能提出0，100的分配方案，5可以答应也可以不答应，这就要看4，5之间的人际关系及5的脾气性格等各种因素了。

因为大家都足够聪明，所以4可以预计如果只剩下他们俩时自己的下场，分两种情况：

1. 博弈方4可以保命，虽然不得到宝石，但至少没死。

2. 博弈方4肯定丧命，既得不到宝石，也要送命，得益不是0而是负数。

接着设想只剩3，4，5时的情形，博弈方3也深知5的脾气，即3可以预见在自己方案遭否决而只剩4，5时的情形，所以3要争取4或者5中的一人同意自己的方案，显然巴结4的成本小很多。

由于只剩4，5时的情况有两种，于是3的策略会不同，（次序同上）

1． 博弈方3至少得出1颗宝石，因为如果3提出100，0，0的方案，4没有必要答应，5更不会答应，所以3最少会提出99，1，0的方案

2． 由于4有丧命的危险，此时3可以提出100，0，0的方案，4 也会答应。

不妨依次往下推：

剩博弈方2，3，4，5时（情况的次序同上）

1. 博弈方2最少提出的方案为97，0，2，1以此得到4，5的支持

2. 博弈方2最少提出的方案为98，0，1，1以此得到4，5的支持

最后是博弈方1的方案策略了

1. 博弈方1最少提出97，0，1，0，2的策略以此得到博弈方3和5的支持

2. 博弈方1最少提出97，0，1，2，0或者97，0，1，0，2的策略以此巴结到3号的同时得到4或者5中一个人的支持。

综上所述，

1在不考虑违反规则，

2在不考虑博弈方有冒生命风险去获得宝石，即博弈方的冒险可能性被剔除的情况下，

3在不考虑可能在博弈之前，甚至抽签之前已经形成结盟的情况下，

我们得到了一个动态博弈问题的完美子博弈纳什均衡解，该解在不考虑上述三种情况时是稳定并且有效的，不容置疑。

（二）

在第（一）中最为简单的基础上，我们仅仅多引入违反大家已定规则的可能性。

前提假设为5个人实力相等，即大家如果抢夺大家谁都打不过谁，所以才有了这个题目，如果有个海盗“实力”超凡，也就会成为所谓的“老大”，就没必要大家投票了，该前提假设（一）也适用，只是在（一）中不会产生如在（二）中的影响。

因为实力相当，也就是多数人能打过少数人，所以在5个人，4个人，3个人在场的情况下，谁都不可能违反已定规则。比如1号提的方案遭拒，他拒绝被丢进海，企图违反规则，，但是4个人是不会允许的。同理，4个人，3个人的时候大家违反规则的可能性是没有的。

而当只剩2个人的时候情况就不同了，4号不是傻子，他有能力一搏，5号同样不是傻子，他知道4会放手一搏。在这种情况下，打一架决定收益，则不计受伤的负收益，那么双方由于实力均等，各自的期望得益均为50，于是不如双方不打架直接平分，各得50。

这种情况是有可能发生的，并且是很可能发生的，因为既定规则在只剩2人博弈的时候变得就像道德约束一样，我想，海盗似乎不会因为这种道德约束而选择死亡或者一颗宝石都不要吧。

用逆推法推断，如（一）的方法

博弈方3会选择49，51，0或者49，0，51的方案

博弈方2会选择49，50，0，1或者49，50，1，0的方案

博弈方1的方案为：

97，0，0，1，2或者97，0，0，2，1.

说实话，这种可能性是更大的，因为既定规则在只剩2人博弈时会显得苍白无力，而海盗们都是“聪明”的，都是可以预见到未来的，所以这样的推导是不存在问题的，只是在如果考虑到某个博弈方有可能“冒险”时，或者有结盟存在时，该推导所得的解会被改变。

博弈论中有个均衡的概念叫作“颤抖手均衡”，我不太肯定的把（二）所得的解归为颤抖手均衡，其实它也是一个相对稳定的解。

（三）

我们讨论存在“冒险”行为的该博弈问题。

定义“冒险”为博弈方为了未来利益而愿意放弃眼前利益，即风险收益比。

眼前利益，不仅局限于可以马上得到的宝石，还会牵涉到生命，所以是相当复杂的。

假定，我们必须给出假定，否则根本无从下手。

假定：

1.五个人都是风险中性，举个例子讲就是，比如1提出的方案是给5号50颗宝石，而如（二）分析得到的一样，在剩4，5存在时，5也会得到50颗宝石，那么这两种情况下得到的50颗宝石对于5号来说是无差异的。但是博弈方5到底会怎么选择呢？给出假定2.

2.博弈方在面对两阶段的相同得益时，会选择较前阶段的得益。也就是说，在上述例子中，博弈方5在1提出方案时会投赞成票。为什么这样假设？“折旧”的概念在这里被缩小的，但是从时间机会成本的角度，或者杀人对于博弈方的得益来看，博弈早点结束，宝石早点得到分配对大家都有利，大家可以有多点时间去潇洒，我们排除喜欢浪费时间看杀人的“杀人狂”的存在。

这两个假设在（一）（二）中均未得到应用，所以在（一）（二）的分析中号码前的博弈方会试图用至少多一点的宝石去巴结贿赂其他博弈方，而当有这些假定时，博弈方只需用同样的宝石即可贿赂到其他博弈方。

这两个假设不缺乏道理，此时我甚至有把它运用到（一）（二）中的冲动。

3. 假定每个海盗都会去“冒险”，即为了自己可能得到的最大得益而去让博弈不停的进行下去，以此取得一个自己的最大利益。而当出现这个最大得益时，“冒险”停止，无论在哪轮出现。

这个假定是个很关键的假定，在这3个假定的情况下，我们继续讨论（二）基础上的问题。

在只剩4，5时，大家收益都为50.

所以4，5预计的最大“冒险”得益为50.

3可以巴结4，也可能贿赂5，假设概率各为0.5

那么3会怎么做呢？他提出的方案50，0，50或者50，50，0根据假定是可以得到通过的。

于是3的最大“冒险”得益也为50.

但是在剩下3，4，5的情况下，也就是3提方案的时候，4，5的期望得益均为25，也就是4，5中只有一个人可以得到50.另一个为0，所以4，5实际上不可能希望博弈进行到这一步，但是一旦进行到这一步，方案也是会被通过的，不会再向下进行了。

考虑2提方案的时候，因为3，4，5会去等待最大得益50，于是为了保命，失去性命是会产生负收益的，他只能提出让3，4，5中的两人各得50，分法有3种，不依次说了。2的最大“冒险”收益为保命。

1的方案只要得到通过，2可提前保命，所以1只需再笼络3，4，5中的一个人，给他50宝石，自己留50，于是就得到了解。

综上所述，在大家都把“冒险”进行到极端情况下，博弈方1的方案有三种

50，0，50，0，0或者50，0，0，50，0或者50，0，0，0，50。

可以清晰的看到，其实这种情况下大家是不理智的，3，4，5的期望得益都是50的三分之一，但是他们在面对这样方案提出的时候，又是会被通过的。

将假定3稍微改动下，即假定大家都不会“冒险”去等待可能存在的最大利益，大家的选择原则是根据期望得益而定，分析如下。

4和5在最后一轮的得益会是各自50.

如果进行到3提方案，他会给4，5中其中一个人50，于是4，5在倒数第二轮的期望得益均为25.

因为4，5害怕3提出方案自己的得益会是0，那么2可以提出的最优方案是50，0，25，25.不会有其他情况。

3当然希望可以进行到自己提方案的时候，但是实际是不可能的了。

1只要提出75，0，0，25，0或者75，0，0，0，25的方案，那么4，5中有一个人必然同意，3会同意嘛？如果他不同意，浪费了时间，在2提出50，0，25，25的方案时自己同样得不到宝石，所以在大家都不“冒险”的情况下，1 的方案为：75，0，0，25，0或者75，0，0，0，25。

至于涉及风险利益比率，以及要将生命当作一种条件进行博弈的分析，情况更为复杂，在此不再讨论，只取两种极端情况。至于假定，一定要仔细看一下，没有假定，（三）的分析不成立。

（四）

最后探讨的问题是“结盟问题”，这是我最不愿提及的问题，极为复杂，任何多人博弈在加入不确定的结盟可能时，解会变得既不稳定。

我们单单考虑一下结盟均为“稳定结盟”的情况，即结盟不会因为其他博弈方或者其他联盟的“小恩小惠”瓦解。

不会瓦解的稳定结盟有多少种呢？

5人结盟，不存在。

4人结盟，5种。

3人结盟，另2人结盟，10种，另2人不结盟，10种。

2人结盟，其他3人不结盟，10种；其他3人中有2人结盟，30种。

65种？似乎不多。

但结盟会导致的“分赃权”归属问题将使问题再次复杂化。

3人，4人结盟的分赃权归属不存在疑问。

2组两人联盟存在时，拉拢“破坏者”成为关键，于是30*2=60

2人结盟，其他三人各自为战时，情况也不简单。

2人联盟只需拉拢一人，拉拢成功有3种情形，不成功即另3人达成一致，虽然未结盟，又是一种，10*4=40

所以，其实变成了125种，可能有错误，不确定。

论及可能存在的不稳定联盟时，那可能性趋向无穷。

也许高等的数学知识可以解决，但我力不能及。

这是我跟楼主讨论后的一些分析，希望高手指点！我们志在将这个简单的博弈模型复杂化，考虑的因素多一些。

无差异法求解循环相克博弈相关文章：