漫画：博弈论系列 之 海盗分金币的故事（附：代码实现）
在面试的过程中，除了常规的算法题目，我们经常也会被问到一些趣味题型来考察思维，尤其以 FLAG（Facebook, LinkedIn, Amazon, Google）等公司为典型。而这类问题的背后，很多都有博弈论的影子。所以在本系列，我将为大家分享一整套需要掌握的博弈论相关知识，希望大家可以喜欢。
PS：本系列将不一定都是算法问题，不是IT行业的小伙伴也可以进行学习，来提高自身分析问题的能力。
01海盗分金币问题海盗们有如下特点：
1.足智多谋，总是采取最优策略。2.贪生怕死，尽量保全自己性命。
3.贪得无厌，希望自己得到越多宝石越好
4.心狠手辣，在自己利益最大的情况下希望越多人死越好。
5.疑心多虑，不信任彼此，尽量确保自身利益不寄希望与别人给自己更大利益。
首先我们很容易会觉得，抽签到第一个提方案的海盗会很吃亏！因为只要死的人够多，那么平均每个人获取的金币就最多，而第一个提方案的人是最容易死的。但是事实是，在满足海盗特点的基础上，第一个提方案的海盗是最赚的，我们一起来分析一下。
假如我们设想只有两个海盗。那么不管第一个说什么，只要第二个人不同意，第二个人就可以得到全部的金币！所以第一个海盗必死无疑，这个大家都能理解。（当然，这样的前提是一号提出方案后不可以马上自己同意，不然如果自己提出给自己全部金币的方案，然后自己支持，这样就是二号必死无疑）
假如现在我们加入第三个海盗，这时候原来的一号成为了二号，二号成为了三号。这时候现在的二号心里会清楚，如果他投死了一号，那么自己必死无疑！所以根据贪生怕死的原则，二号肯定会让一号存活。而此时一号心理也清楚，无论自己提出什么样的方案，二号都会让自己存活，而这时只要加上自己的一票，就有半数通过，所以一号提出方案：把金币都给我。
现在又继续加入了新的海盗！原来的1,2,3号，成为了现在的2,3,4号。这时候新的一号海盗洞悉了奥秘，知道了如果自己死了，二号就可以获取全部的金币，所以提出给三号和四号一人一个金币，一起投死2号。而与此同时，现在的3号和4号获取的要比三个人时多（三个人时自己获取不了任何金币），所以他们会同意这个方案！
现在加入我们的大Boss，最后一个海盗。根据分析，大Boss海盗1号推知出2号的方案后就可以提出(97,0,1,2,0)或者(97,0,1,0,2)的方案。这样的分配方案对现在的3号海盗相比现在的2号的分配方案还多了一枚金币，就会投赞成票，4号或者5号因为得到了2枚金币，相比2号的一枚多，也会支持1号，加上1号自己的赞成票，方案就会通过，即1号提出(97,0,1,2,0)或(97,0,1,0,2)的分配方案，大Boss成功获得了97枚金币。
最终，大Boss一号海盗得到97枚金币，投死了老二和老五，这竟然是我们分析出的最佳方案！这个答案明显是反直觉的，如果你是老大，你敢这样分金币，必死无疑。可是，推理过程却非常严谨，无懈可击，那么问题出在哪里呢？
其实，在"海盗分赃"模型中，任何"分配者"想让自己的方案获得通过的关键是，事先考虑清楚"对手"的分配方案是什么，并用最小的代价获取最大收益，拉拢"对手"分配方案中最不得意的人们。1号看起来最有可能喂鲨鱼，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还收益最大。而5号，看起来最安全，没有死亡的威胁，甚至还能坐收渔人之利，却因不得不看别人脸色行事而只能分得一小杯羹。
不过，模型任意改变一个假设条件，最终结果都不一样。而现实世界远比模型复杂。因为假定所有人都理性，本身就是不理性的。回到“海盗分金”的模型中，只要3号、4号或5号中有一个人偏离了绝对聪明的假设，海盗1号无论怎么分都可能会被扔到海里去了。所以，1号首先要考虑的就是他的海盗兄弟们的聪明和理性究竟靠得住靠不住，否则先分者必定倒霉。
如果某人和一号本身不对眼，就想丢他喂鲨鱼。果真如此，1号自以为得意的方案岂不成了自掘坟墓。再就是俗话所说的“人心隔肚皮”。由于信息不对称，谎言和虚假承诺就大有用武之地，而阴谋也会像杂草般疯长，并借机获益。如果2号对3、4、5号大放烟幕弹，宣称对于1号所提出任何分配方案，他一定会再多加上一个金币给他们。这样，结果又当如何？
通常，现实中人人都有自认的公平标准，因而时常会嘟嚷：“谁动了我的奶酪？”可以料想，一旦1号所提方案和其所想的不符，就会有人大闹。当大家都闹起来的时候，1号能拿着97枚金币毫发无损、镇定自若地走出去吗？最大的可能就是，海盗们会要求修改规则，然后重新分配。当然，大家也可以讲清楚下次再得100枚金币时，先由2号海盗来分…然后是3号……颇有点像美国总统选举，轮流主政。说白了，其实是民主形式下的分赃制。
最可怕的是其他四人形成一个反1号的大联盟并制定出新规则：四人平分金币，将1号扔进大海。这就颇有点阿Q式的革命理想：高举平均主义的旗帜，将富人扔进死亡深渊。
最后，这里也提供一份代码实现，供有兴趣的同学参考（该代码我大概看了一下，但是因为时间的关系，没有跑单测进行验证，特此说明！）
1//java实现
2//本代码由作者 LeonXtp 提供
3//同时，本算法只找出一种解决方案就算完成
4
5public class PirateModel {
6
7 //金币数量
8 private int coinCount;
9 //海盗数量
10 private int pirateCount;
11
12 private PirateModel(int coinCount, int pirateCount) {
13 this.coinCount = coinCount;
14 this.pirateCount = pirateCount;
15 }
16
17 private int[] resolvePuzzle() {
18 return getDistribution(pirateCount);
19 }
20
21 /**
22 * 获取当前海盗数量下，对提出方案的海盗来说，其余海盗每人都得到满足的需求量
23 *
24 * @param currPirateCountTotal 当前的海盗数量
25 * @return 其余海盗每人都得到满足的需求量
26 */
27 private int[] getDistribution(int currPirateCountTotal) {
28 if (currPirateCountTotal == 1) {
29 return new int[]{coinCount};
30 } else {
31 int[] minsufficient = getDistribution(currPirateCountTotal - 1);
32 return getDistributionByMin(minsufficient);
33 }
34 }
35
36 /**
37 * 获取在已知所有其他海盗的最小满足量时的最佳分配方案
38 *
39 * @param othersMinDistribution 已知所有其他海盗的最小满足量
40 * @return 分配方案
41 */
42 private int[] getDistributionByMin(int[] othersMinDistribution) {
43 //总共需要的票数
44 int countToatal = (othersMinDistribution.length + 1) / 2 + 1;
45 int[] finalResolve = new int[othersMinDistribution.length + 1];
46 int[] others = findBestSolution(othersMinDistribution, countToatal - 1);
47
48 int othersSum = 0;
49 for (int i = 0; i < others.length; i++) {
50 finalResolve[i + 1] = others[i];
51 othersSum += others[i];
52 }
53 finalResolve[0] = coinCount - othersSum;
54 return finalResolve;
55 }
56
57 /**
58 * 从数组中找出指定个数的元素，使它们的和最小，然后将那些元素+1
59 * 待完善：本解法不考虑多种方案的情况，只找出一个方案
60 *
61 * @param array 待选择数组
62 * @param count 指定的元素个数
63 * @return +1之后的数组
64 */
65 private int[] findBestSolution(int[] array, int count) {
66 int minTest = 0;
67 int found = 0;
68 Set<Integer> indexSet = new HashSet<>();//保存被分配的海盗的坐标
69 while (found < count) {
70 for (int j = array.length - 1; j >= 0; j--) {
71 if (minTest == array[j]) {
72 found++;
73 indexSet.add(j);
74 }
75 if (found == count) {
76 break;
77 }
78 }
79 minTest++;
80 }
81
82 //将其余的都置为0
83 for (int i = 0; i < array.length; i++) {
84 if (!indexSet.contains(i)) {
85 array[i] = 0;
86 } else if (array[i] < coinCount) {
87 array[i] += 1;
88 }
89 }
90
91 return array;
92 }
93
94 public static void main(String[] args) {
95 PirateModel pp = new PirateModel(100, 5);
96 int[] solution = pp.resolvePuzzle();
97 if (solution[0] < 0) {
98 System.out.println("必死无疑！！！");
99 } else {
100 System.out.println(pp.pirateCount + "人时分配方案：" + Arrays.toString(solution));
101 }
102 }
103
104}
//以上代码输出：5人时分配方案：[97, 0, 1, 0, 2]
看懂了吗？如果看懂了，这里提出一个问题：假如我们将人性考虑在内，同时也进行理性的分析，如果你是老大，又该如何提出这个方案呢？大家在留言区留下自己的回答吧！
每天一道图解算法，如需进群 ↓↓↓
欢迎加微信：llhaohao
温馨提示
小浩算法~
每天一起学习图解漫画算法。
一起刷题，一起成长！
~长按下方二维码进行关注吧~
关注领取 "GeekTime" 全部资源