海盗分金 (Screwy pirates)

---

[BACK to BLOG] [BACK to HOME]

假设总共有5个海盗，从A到E越来越Senior，总共有x金。每轮由最senior的人出一个分钱提案，如果半数或以上的人同意该提案，则提案通过，否则提案人被杀。所有海盗绝对理智，他们的第一优先级是活下来，第二优先级是拿尽可能多的金子，没有任何其余诉求。

在这个问题中，每次尝试分钱时，每个海盗的心态是：

• 如果到我的轮次时，我的提案必不会被接受，我会接受之前的轮次的提案，以确保自己不用死。
• 在我的提案轮次和那在我之前的轮次中，我会接受能让我比下一个可通过的提案拿到更多钱的提案。

<– Junior Senior –>	A	B	C	D	E
1个	x	亡	亡	亡	亡
2个	0	x	亡	亡	亡
3个	1	0	x-1	亡	亡
4个	0	1	0	x-1	亡
5个	1	0	1	0	x-2

当x>=(N-1)//2时（N为海盗人数），是单纯的分钱问题。逆推得：

• 只剩A时，他能得到全部的钱。
• 剩AB时，B一个人就能投票成功，且B是提议人，因此B拿走全部钱。
• 剩ABC时，因为A到下一轮拿不到钱，因此A不愿意进入下一轮，所以A会同意任何能让他拿到钱的提议。则C提议用1金获得A的投票，自己拿走x-1金，B不得钱。
• 剩ABCD，同理D可通过1金拉拢B，获得x-1金，剩余人不得钱。
• 剩ABCDE，E分别用1金拉拢下一轮无法拿钱的AC，自己拿走x-2金。

更多人的情况均以此类推。

---

对每个人来说，都是在自己是最senior的时候最有利，尽管他们面临死亡可能，但他们有提案权。理论上想要利益最大化，就需要：

• 忽悠住所有比自己的senior的人，让他们的提案无法通过，使得所有比自己senior的人都出局。
• 在比自己senior的人都死掉之后，转而从要拉票的人中最junior的那位开始忽悠，让他们理解上表，也就是如果不拿1金走人，那就连1金也拿不到。

假设我是D，5人时游说的重点是：

• 首先要让最junior的A理解，一旦进展到2人局，他将失去控制结果的能力，并且不论如何游说都一定无法得到钱。因为A一定不会死，所以A的唯一诉求就是拿钱，因此A必定会倾尽一切可能让钱在2人以上时就被分干净。根据上表，在有2人以上时，A最多可以拿到1金，则我可以向A承诺当我做提案人时，给其2金或以上，使其在当前轮次不要投票。
• 另一方面，取得E的信任，让他理解上表，明白自己只需要给AC各一金即可利益最大化，促使他提出没我利好A的提案。
• 最终促使E的提案只能获得CE的选票，而使E出局。

假设我是C，我首先要忽悠D让他完成上述提案，当局面进展到4人时：

• TODO. 重点是利用A的决定忽悠B。

递推。

---

上述问题海盗们主要根据拿钱多少做决策，但在N人局中，当x小于(N-1)//2时，海盗还会为了活命做决策。现假设按从junior到senior排序时，一个海盗的编号为y：

• 若y<=2x，则海盗y一定能活下来，且y有机会根据自己编号的奇偶得到钱。
• 若y>2x，y有可能死亡。
  • 只有当(y-2x)为2的整数幂时，y的提案才可能成立。
  • 若z是小于(N-2x)的最大的2的整数幂，且(N-2x)不是2的整数幂，则2x+z<y<=N时，海盗y会死。
  • 若y为其他值均可在任意一次2的整数幂提案中投票，以争取存活机会。

下表是一个2金8人的例子，从下往上看是减员顺序，在当前轮次会投票的人加粗了，单纯为了活命而投票的额外加了🆘。7人时G的提案无法通过，因此G为了活命会在H提案时投票。6人时钱可以分给BDE中任意两人，8人时钱可以分给ACF中任意两人。

<– Junior	A	B	C	D	E	F	G	H
1个✅	2
2个✅	0	2
3个✅	1	0	1
4个✅	0	1	0	1
5个✅	1	0	1	0	0🆘
6个✅	0	1	0	1	0	0🆘
7个	1	0	1	0	0	0	0🆘
8个✅	1	0	1	0	0	0	0🆘	0🆘

[BACK to BLOG] [BACK to HOME]