The \Pirate game" is a popular mathematical puzzle, the problem aimed at demonstration of backward induction. It is also a shining example of non-cooperative behaviour of rational agents in mathematical game theory. A linearly ordered crew votes for the captain's sharing o er. The captain needs the approval by a given fraction of the crew called quorum at the minimal cost. In this paper, we present the comprehensive quorum analysis on strategies and payo s for the \Pirate game" problem, for any crew size and any quorum.
The \Pirate game" (also known as the \Puzzle for pirates") is a well-known widely-used mathematical puzzle, which often stirs up disputes3. The rst appearing of the problem in scienti c literature seems to be in the book by E. Moulin [6] as an example; we found no earlier publications of this problem. The \Pirate game" is the following4:
There are ve rational pirates (in strict order of seniority A, B, C, D and E) who found 100 gold coins. They must decide how to distribute them. The pirate world's rules of distribution say that the most senior pirate rst proposes a plan of distribution. The pirates, including the proposer, then vote on whether to accept this distribution. If the majority accepts the plan, the coins are dispersed and the game ends. In case of a tie vote, the proposer has the casting vote. If the majority rejects the plan, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again. The process repeats until a plan is accepted or if there is one pirate left.
Pirates base their decisions on four factors. First of all, each pirate wants to survive. Second, given survival, each pirate wants to maximize the number of gold coins he receives. Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal. And nally, the pirates do not trust each other, and will neither make nor honor any promises between pirates apart from a proposed distribution plan that gives a whole number of gold coins to each pirate.
Using backward induction, one can nd the nal solution: A: 98 coins; B: 0 coins; C: 1 coin; D: 0 coins; E: 1 coin.
In [6], there is no restriction on the number of pirates (N ) and the general solution is the following:
For N = 2p + 1 and N = 2p + 2, the most senior pirate gets (100 p) coins. One coin gets each of p pirates whose numbers have the same parity as the number of the most senior pirate.
Obviously, this solution works while the number of coins is more than half of the number of pirates (N > 2M ). An extension of the \Pirate game" to the case of a larger number of pirates is presented in [7] by I. Stewart.
In popular scienti c literature, there are also a few other extensions; for example, when the needed quorum is greater than 0:55 or \six pirates and a single coin"6.
A similar to the \Pirate game" problem is considered in [4], but there the junior crew member makes an o er to be approved by everybody (Q = 1) or everybody except at most one. Also, there are several approve-sharing problems with envious and/or greedy same-rank pirates, where also the share must be approved by every crew member (e.g, [2]).
Work [3] analyses the \Pirate Game" by a game-theoretic solution concept of \subgame perfect strong Nash equilibrium," as the subgame version of the strong Nash equilibrium. In particular, the thesis provides an analysis of the general form of the \Pirate Game", by determining the maximum number of coins that the most senior pirate could guarantee.
Paper [5] develops a quantum model for the voting system in the \Pirate game".
Most of the discussed problem variations (with rare exceptions) are based on quorum Q = 0:5, i.e., the proposition to be accepted needs at least 50% of votes. However, it is still an open question, how the quorum size a ects on payo s and strategies. This paper aims at making the comprehensive quorum analysis (with 0 Q 1) of the \Pirate Game". Various generalizations of this game will be the subject of our future work.
The paper is organized as follows. Section 2 describes the formal problem. Section 3 provides the quorum analysis with subsections of di erent solutions: small quorums (0 Q 0:5), the ranges 0:5 < Q 0:6, 0:6 < Q 0:625 5 https://en.wikibooks.org/wiki/Puzzles/Logic puzzles/Gold Coins 6 http://www.mytechinterviews.com/6-pirates- ght-for-1-gold-coin and 0:625 < Q 2=3, and high quorums 2=3 < Q 1. Section 4 provides possible applications of the problem. Finally, section 5 gives the conclusion and nal remarks. 2
We consider the problem of sharing with voting in the form presented in [6] with some generalization. The context of pirates is convenient, because no trust, neither cooperative behaviour, between the players are suggested.
The problem is as follows. A crew of N pirates is linearly ordered by seniority. The senior pirate is called the captain. The captain o ers to share a number M of coins; we assume that this number is su ciently large. The crew votes for or against the o er; if the number of the votes for the o er is at least QN , where 0 Q 1 is called the quorum, the o er is accepted. Otherwise, the captain is expelled from the crew and does not take part in the subsequent voting. The new captain o ers a new sharing.
Let the junior member of the crew have number one; the higher the number, the higher the position in the hierarchy. Crew members vote rationally and in their interests, payments are discrete and are multiples of one coin. A member of the crew who is o ered a payout of all M coins votes for the share.
The number of M coins is su ciently large in the following sense: if the sums o ered to the members of the crew do not depend on M , then the captain gets more than anyone of the crew, after paying the o ered sum to every member.
In a situation of indi erence, that is, if a crew member is o ered the same share that he expects to receive from the new captain, he can vote either for, or against the o er. The captain, therefore, needs to assume that all such crew members may vote against the o er. 3
In this paper, we solve the problem for all values 0 Q 1. Besides the payo functions for any crew size N and any quorum Q, we would like to emphasize the following results: { In a general case, the captain has some freedom in deciding who is o ered some money and who is not. This is not the case for Q = 0:5. { The quorum span [0; 1) is separated into intervals, the payo for a given N is the same within the interval; also, the asymptotic average individual payo grows piecewise-linearly with respect to Q and may jump at intervals' ends. { The span [0; 2=3) is divided into just ve intervals, while the rest consists of in nitely many intervals that condense near 1.
Note that the rules of the voting can be di erent: instead of \at least" Q, it can be \more than" Q. This is also the case when the captain does not vote. However, one problem is equivalent to the other replacing Q by Q + with su ciently small ; in fact, it is su cient to choose < 1=N .
Below we consider the following cases: 0 Q 0:5 and Q = 0:5 + , which are di erent. Then we show, that this pattern is valid for 0:5 < Q 0:6, while a similar pattern holds for 0:6 < Q 0:625. After that, we consider the case Q = 2=3 and show that it is applicable also for 0:625 < Q 2=3. Finally, we consider completely di erent case 2=3 Q 1. 3.1
Q
0:5 The classical problem for Q = 0:5 has the well-known solution presented in [6] that allows the captain to keep the most of the sum for himself. It is proved by induction. The payo (to every crew member except the captain) is either one coin or nothing depending on the parity of the member's rank.
Indeed, for N = 2 the captain can keep everything for himself, being himself one half of the team. For N = 3, he needs one more vote, so he o ers one coin to the junior member, who otherwise would get nothing.
So, the payout scheme is
C (01)(01) : : : (01)(0) for | {z }
n 1 times C (01)(01) : : : (01) | n t{imzes }
N = 2n; for
N = 2n + 1;
Here the payo s of the crew members are shown from the senior (left) to the junior (right), with the captain (who takes the rest) denoted by C. Parentheses are used for visual grouping only.
The captain can use the same payout scheme for quorums less than 0:5: C (0?)(0?) : : : (0?)(0) for | {z } n 1 times
N = 2n; C (0?)(0?) : : : (0?) | n t{imzes } for
N = 2n + 1;
(
For lower values, i.e., 0 < Q 1=3, the captain o ers nothing to every crew member for any N 1=Q, because his own vote is enough. Then he o ers nothing to number 2 and has at least two members to choose from for one more vote. For the next N , these junior members are not reliable, but number 3 would agree for one coin. After that, the parity pattern continues. Let us illustrate this
C0???; C0?000; C0?0???; C0?0?000;
C0?0?0???;
So, the pattern is as follows: for N = 2n, n > 2, several juniors get nothing, as well as every crew member with even number; other can hope for one coin. For N = 2n + 1, n 2, the same junior members and those with odd numbers may hope for one coin, other are o ered nothing.
The number of these junior members, denote it by J , is the minimal J that satis es the condition J > 1=Q 2, because J + 2 is the rst N when the captain needs one more vote besides his own. So, in the general case the pattern is the same, only N J + 2 (i.e., N > Q 1 2):
C (01?)(01?) : : : (01?) 10 for N = 3n; | {z }
n 1 times C (01?)(01?) : : : (01?) 0?1 for N = 3n + 1; | {z }
n 1 times C (01?)(01?) : : : (01?) 010? for N = 3n + 2: | {z }
n 1 times C (0?)(0?) : : : (0?)(0) ? : : :? | {z } | {Jz }
l 1 times C (0?)(0?) : : : (0?) 0 : : : 0 | l ti{mz es } | {Jz } for
N
J = 2l; l for
N
J = 2l + 1; l 1; 1;
The special case Q = 0 is trivial: the captain takes everything for any crew size N . 3.2
Let us consider the case when the captain needs the approval of more than one half of the crew (Q = 0:5 + ); alternatively, this is the case when the captain does not have a vote.
The distribution of payments by players depends on the remainder of dividing
N by 3. Players are divided into three types: deprived, who are o ered nothing;
privileged, who are o ered one coin; and the others. The captain chooses the
necessary amount from this third category and o ers them two coins; others are
o ered nothing. This third category is marked by the question mark.
(
The base of induction is checked directly: for N = 2, the junior member of the crew takes everything; here we use the assumption that if a member is o ered everything, he votes for the o er. Therefore, for N = 3, the captain simply o ers the second member one coin, which gives the case N = 3n for n = 1.
With N = 4, the captain o ers one coin to the youngest, but he needs another vote, which can only be number 2, who would be o ered one coin by the next captain. Therefore, to guarantee his vote, the captain o ers him two coins. Formally, the captain selects one member from the third category, which has a single member; this is N = 3n + 1 for n = 1.
With N = 5, the captain o ers one coin to number 3, which would be o ered nothing by the next captain; one more vote is needed. Number 2 wants to become a captain and get everything, so he is not o ered anything, and there remains a choice of two crew members (1 and 2). Number 2 would be o ered two coins by the new captain and may not agree to two; therefore, it is more reliable to o er two coins to the youngest (he falls into the third category). So, we have the case N = 3n + 2 for n = 1.
The induction step is now obvious. Every one o ered nothing on the previous step are o ered one; this gives the captain n votes. Nothing is o ered to those who could hope for two coins, because they may refuse even the o er of two. There remain at least n 1 crew members, who would be o ered one coin on the previous step. Among them, the captain needs to choose enough people to get the quorum and o er them two coins.
Thus, the series of (?10) transforms to (0?1) (the cyclic shift to the right), the same is true for the series (0?1) and the series (10?). The series (01?) becomes (1?0) (the left shift). Then the payout at N = 3n becomes, taking into account the zero payout to number 2,
C0 (1?0)(1?0) : : : (1?0)?1; | {z }
n 1 times which, after rearranging the parentheses, gives a payout for N = 3n + 1.
The transition to N = 3n + 2 is considered in the same way. Now let us consider the transition from N = 3n + 2 to N = 3(n + 1). Similarly, we get a series
C0 (1?0)(1?0) : : : (1?0) 1?10 = C (01?)(01?) : : : (01?) 10;
| n 1 {tzimes } | n t{imzes } which coincides with the formula for N = 3(n + 1).
The minimum payout follows from the fact that no member of the crew can reduce the payout without guaranteeing his vote.
The proof is complete.
The payo pattern for Q = 0:5 + is valid up to some , because there are more people from the third category, to choose from to make up the quorum. Let us show that this pattern is preserved up to Q = 0:6.
The captain, as we have already established, has n votes of those who would be o ered nothing by the next captain, his own vote, and has at least n 1 people to choose the necessary number and o er them two coins. So, the captain can to get 2n votes out of not more than 3n + 2.
Moreover, if N is not divisible by 3, then the number of people to choose from is n + 1, so the captain can get up to 2n + 1 votes.
Thus, the captain can get exactly 2=3 of votes at N = 3n, or 2n + 1 3n + 1 for N = 3n + 1;
for N = 3n + 2: 2n + 1 3n + 2 The rst of these expressions decreases in n and exceeds 2=3 for all n 0, while the second one increases and is equal to 3=5 at n = 1 (so for larger n it is even more).
Due to this equality, it is impossible to use the same pattern for higher Q; let us construct the pattern for this case. 3.3
For Q = 0:6 + up to Q = 0:625 we have the following rst steps:
N = 3 : This easily checked by induction. This pattern cannot be used for Q > 0:625 because for N = 5 (emphasized by italic font) the captain would lack a zero. For this case, the pattern would depend on divisibility on four. 3.4
The Case 0:625 < Q
2=3 Consider the situation when the proposal of the captain is accepted if at least two-thirds of the crew (including the captain) vote for it (Q = 2=3). The payout scheme depends on divisibility by 4. Players are divided into four types: those, who are o ered nothing; those, who are o ered one coin, two coins, and the rest: each of the rest may be o ered three coins, or nothing, depending on the captain's arbitrary choice. This category is marked by question marks: n 1 {tzimes n 1 {tzimes
n 1 {tzimes The induction base is constructed in the same way as in the previous case: for N = 2 the captain gives everything to the youngest, providing 100%, and for N = 3 he gives one coin to number 2, getting exactly two thirds (payout is C10). With N = 4, the captain also receives three quarters (payout is C021). However, with N = 5, two votes are now not su cient: the third vote is needed. So, the captain must o er three coins to someone who would be o ered two by the next captain: the payout is C0132 = C01?2). Finally, with N = 6, the captain also needs three votes, and he can o er nothing to the one who would be given three coins by the next captain: C01203 = C0120?.
By induction, the captain o ers one coin to those who would receive nothing (at least n people) and two coins to everyone, who would be o ered one (also at least n people). Also, there are at least n 1 people who would be o ered two coins: the captain chooses the necessary number of people to get the quorum and o ers them three coins each, to guarantee their votes. It is easy to check that this algorithm indeed produce the payout scheme for 4n + 1 from 4n, 4n + 2 from 4n + 1, 4n + 3 from 4n + 2, and 4(n + 1) from 4n + 3.
So, we can use this pattern also for Q < 2=3, only fewer people need to be chosen to secure the quorum. The lower bound for this pattern is Q = 0:625 because for this value a better scheme is available. Moreover, with N = 5, that is, with N = 4n + 1 with n = 1, the captain is forced to provide the votes of all subordinates, except one (which is number 2, who will not be satis ed with any payment). Since in the previous step two coins would be paid, it is not possible to manage with a smaller amount. Finally, let us consider the quorum Q > 2=3.
To solve the problem, we need to strengthen the loyalty assumption: now, if the captain gives everything to one subordinate, then the rest of the crew in a position of indi erence are loyal. This is necessary, because already in the case of 3 members the captain needs to o er everything to the junior, while the third member (number 2) gets nothing but still votes for the captain. Otherwise, the captain cannot win.
Under this assumption and for Q = 1, the best captain can do is to survive by o ering everything to the junior crew member; let us study the case Q < 1.
Firstly, as N grows, the captain gives everything to the youngest, until N reaches N1 = d1=(1 Q)e; after that one member can be o ered nothing, and this would be the junior. The remaining members (let us call them aristocrats, their number is A = d(1 Q) 1e 2) get one coin, and the rest is taken by the captain.
On the next step, nothing is o ered to number 2, who now wishes to become the captain. The aristocrats get two coins, and the junior gets one.
Next, we have an increasing series of 0, 1, 2, . . . , i 1, then i + 1, . . . , i + 1, and nally i, (for i 1), until N = d(1 Q) 1e 2 + i + 1 exceeds the value N2 =
1 1 Q
1 1 Q 1 : At the same time, the captain gets the opportunity to o er nothing to two people, then three, and so on, to be selected among the aristocrats, who receive i + 1 coins.
The number of aristocrats is constant and equal to A. When A + 1 pirates can be o ered nothing, the captain o ers them (and number 2) nothing and they know that. So, at the next step, they can not hope for anything and, therefore, would agree to one coin. The captain gets the opportunity to o er nothing to those who desire more than others, and so on. At the same time, payments to aristocrats grow and they can be \repressed" again.
Let consider the case Q = 2=3 + rst. At the beginning up to N = 3, the captain has to give everything to the junior. Then the payment has the form Next, one more member can be o ered nothing, but not both aristocrats. They have hopes and, therefore, it is impossible to rely on their loyalty. Choosing any aristocrat and giving him nothing, we continue: Then three men can be o ered nothing: number 2 and both aristocrats; we get
C012345006 C0123450110 Here italic font means that all zeros are used, meaning that the captain has no choice.
At the next step, one more pirate can be o ered nothing. They are those who want more and some of those who want three coins (the captain has a choice): This scheme is easily checked by induction, provided that the number of those who can be o ered nothing, is high enough. The base of induction has been obtained above.
Note that the payout does not exceed three coins, exactly as for the case Q > 0:625, provided that the number of crew members is high enough. However, for a small crew, this payo can be as large as six coins, and for very small everything is o ered to the junior.
Also note that for large N the fraction of those who are o ered zero are asymptotically 1=4, though the amount of zeros is asymptotically 1=3. Therefore, the pattern possesses some stability for large N : the captain has some resources to control the growth of the individual payo , provided that the crew is large enough.
The pattern remains valid for positive up to some threshold value; then it is replaced by a similar pattern. The threshold value is 0:7: this can be checked by considering the patterns in italics. There the captain has enough zeros, in particular at N = 10, where he needs exactly 7 votes: higher Q would demand 8, so the pattern would be destroyed.
is constructed similarly, the rst steps (up to C (0123) : : : (0123)(000112332);
| }
This pattern is valid up to some nite , and so on. For Q = 0:7 + , the payo is limited by the same value 3 as for Q = 0:7 (with the di erent tail), but for higher quorums, it is not so. However, the pattern is constructed for any Q in the same way. Let us consider, as another example, the scheme for Q = 0:9.
First, everything is o ered to the junior, up to N = 10. Starting with 10 people, the captain can o er the junior nothing and one coin to other members of the crew (called aristocrats), so the payout is 1 : : : 10.
Then number 2 is o ered nothing, and up to N = 89 (or i = 79), we have
The group of eight people who expect 10 coins is o ered nothing, as well as the leader (underlined in the scheme) of the group with growing demands (he expects 11) and number 2 until another group (marked in the scheme by the word \new") of 12 : : : [10] grows up.
By then it will be possible to exclude one more person, which would be the leader of the new group. The pattern depends on divisibility by 11, with a repeating group of growing demands from 0 to 10 and a tail that depends on the remainder of the division by 11. The maximum payout can be kept no higher than 10 coins, provided that the number of the crew is su ciently high, although for a small crew it is much higher.
The maximal payo is asymptotically (1 Q) 1. The number of people who can be o ered nothing is (1 Q)N , and to N 1 crew members (with the captain excluded) this can be applied (1 Q) 1 times (to those, who desire more than others). So, after getting nothing, the desire of a crew member will grow up to this value.
It is convenient to imagine the growth of the crew by adding new captains. Then the ex-captain becomes number 2 and wishes to become the captain again, so he is not happy with any o er and thus is o ered nothing. He joins the group of b(1 Q) 1c + 1 crew members with increasing demands: 012 : : : . The leader of this group, who wants too much, is o ered nothing and joins the next such group. So, the length of such groups remains constant. The leader of the rightmost group, who are o ered nothing, joins the new growing group; after two steps, this ex-leader gets one coin and the new ex-leader joins him with 0 to form the 01 sequence, then one more comes and they form 012 sequence, and so on. The rest of the crew (members of low rank, who are also the oldest) form some pattern, including sequences of members who want the same amount. Among them are the aristocrats and the junior. The captain o ers nothing to the group leaders, who want too much, and either to some constant-size groups in the low-rank part, including aristocrats, who want too much each, or to some shorter group plus the junior. Note that by the time the new group is ready, its leader can join the set of those who can be o ered nothing. 4
Similar problems appear in volunteer computing [1]. Assume that owners of computers join to solve a computationally intense problem; the e ective power of their devices is di erent, not only because of di erent hardware but also because of di erent fraction of power granted to the project. The owner of the most powerful device, i.e., the one who contributes the most, distributes some sort of credits for the work. Of course, if a signi cant part of the participants is not happy with this distribution, they may expel the leader (or launch another project with fewer members). The quorum may be di erent depending on the agreement between the members and psychological description of their behaviour (if many colleagues approve the o er you do not like, perhaps you would obey).
One could assume that the leader would distribute the credits \fairly", but this is not the case: the payo pattern is highly uneven, and individual payo depends very weakly on the personal contribution. 5
In this paper, we present the comprehensive quorum analysis in the \Pirate
game" problem. We discover six intervals of quorum value with the di erent
strategies patterns; they are:
{ 0 < Q 1=3: the payo depends on divisibility on 2 and is given by (
The main conclusions of the study are: the captain with enough money to share is always able to make an o er to satisfy enough crew members and to keep most coins for himself; the maximal individual payo does not depend on the crew size if this size is su ciently large; and in a general case, the captain has some freedom in choosing those who are o ered something and those who are not.