A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Screwy Pirates」.

Screwy pirates #

Problem #

Five pirates looted a chest full of 100 gold coins. Being a bunch of democratic pirates, they agree on the following method to divide the loot: The most senior pirate will propose a distribution of the coins. All pirates, including the most senior pirate, will then vote. If at least 50% of the pirates (3 pirates in this case) accept the proposal, the gold is divided as proposed. If not, the most senior pirate will be fed to shark and the process starts over with the next most senior pirate. The process is repeated until a plan is approved. You can assume that all pirates are perfectly rational: they want to stay alive first and to get as much gold as possible second. Finally, being blood-thirsty pirates, they want to have fewer pirates on the boat if given a choice between otherwise equal outcomes. How will the gold coins be divided in the end?

Solution #

假设序号大的海盗级别更高. 考虑 $2$ 个人的情况, 因为只需要一票, 可以按照 $(0, 100)$ 进行分配; 考虑 $3$ 个人的情况, 按照 $(0, 0, 100)$ 分配只能得到一票, 如果按照 $(1, 0, 99)$ 分配则可以得到 $1$ 号海盗的一票. 这是因为如果 $1$ 号海盗不接受这个提案, 问题回归到 $2$ 个人的情况, 他将什么也得不到; 考虑 $4$ 个人的情况, 为了凑齐两票, 按照 $(0, 1, 0, 98)$ 分配, 与 $3$ 个人的情况相比, $2$ 号海盗会接受这个提案; 回到原问题, $5$ 号海盗给出 $(1, 0, 1, 0, 98)$ 的提案即可. 用归纳法不难证明, 在 $n$ 不超过 99 的情况下, 最优的分配是 $1 , 3, …, 2n-1$ 号海盗各分到一枚金币, $n$ 号海盗分到剩余的金币.