=Paper=
{{Paper
|id=Vol-2792/paper2
|storemode=property
|title=Quorum Analysis for the Pirate Game Problem
|pdfUrl=https://ceur-ws.org/Vol-2792/paper2.pdf
|volume=Vol-2792
|authors=Ilya Chernov,Evgeny Ivashko
}}
==Quorum Analysis for the Pirate Game Problem==
https://ceur-ws.org/Vol-2792/paper2.pdf
Quorum Analysis
for the “Pirate Game” Problem?
Ilya Chernov1 and Evgeny Ivashko1,2
1
Institute of Applied Mathematical Research, Karelian Research Center of the
Russian Academy of Sciences, Petrozavodsk, Russia
2
Petrozavodsk State University
{chernov,ivashko}@krc.karelia.ru
http://mathem.krc.karelia.ru/
Abstract. The “Pirate game” is a popular mathematical puzzle, the
problem aimed at demonstration of backward induction. It is also a shin-
ing example of non-cooperative behaviour of rational agents in mathe-
matical game theory. A linearly ordered crew votes for the captain’s
sharing offer. 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 payoffs for the “Pirate
game” problem, for any crew size and any quorum.
Keywords: Pirate Game · Puzzle for Pirates · Quorum Analysis · Non-
Cooperative Game Theory
1 Introduction and Related Work
The “Pirate game” (also known as the “Puzzle for pirates”) is a well-known
widely-used mathematical puzzle, which often stirs up disputes3 . The first ap-
pearing of the problem in scientific literature seems to be in the book by E. Mou-
lin [6] as an example; we found no earlier publications of this problem. The
“Pirate game” is the following4 :
There are five 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
first 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.
?
Supported by Russian Foundation for Basic Research, project 18-07-00628
3
http://www.mytechinterviews.com/5-pirates-fight-for-100-gold-coins
4
Cited from https://en.wikipedia.org/wiki/Pirate game
Copyright © 2020 for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
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 finally, 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 find the final 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 scientific 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 offer 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 affects on payoffs 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 different 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-fight-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
final remarks.
2 The Problem
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 offers to share a number M
of coins; we assume that this number is sufficiently large. The crew votes for or
against the offer; if the number of the votes for the offer is at least QN , where
0 ≤ Q ≤ 1 is called the quorum, the offer is accepted. Otherwise, the captain
is expelled from the crew and does not take part in the subsequent voting. The
new captain offers 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 offered a payout of all M coins votes for the share.
The number of M coins is sufficiently large in the following sense: if the sums
offered to the members of the crew do not depend on M , then the captain gets
more than anyone of the crew, after paying the offered sum to every member.
In a situation of indifference, that is, if a crew member is offered the same
share that he expects to receive from the new captain, he can vote either for,
or against the offer. The captain, therefore, needs to assume that all such crew
members may vote against the offer.
3 The Quorum Analysis
In this paper, we solve the problem for all values 0 ≤ Q ≤ 1. Besides the payoff
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 offered
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 payoff for a given N is
the same within the interval; also, the asymptotic average individual payoff
grows piecewise-linearly with respect to Q and may jump at intervals’ ends.
– The span [0, 2/3) is divided into just five intervals, while the rest consists of
infinitely many intervals that condense near 1.
Note that the rules of the voting can be different: 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
sufficiently small δ; in fact, it is sufficient to choose δ < 1/N .
Below we consider the following cases: 0 ≤ Q ≤ 0.5 and Q = 0.5 + δ, which
are different. 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 different case 2/3 ≤ Q ≤ 1.
3.1 Small Quorums: 0 ≤ 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 payoff (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 offers one coin
to the junior member, who otherwise would get nothing.
So, the payout scheme is
C (01)(01) . . . (01)(0) for N = 2n,
| {z }
n−1 times
C (01)(01) . . . (01) for N = 2n + 1,
| {z }
n times
Here the payoffs 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 N = 2n, (1)
| {z }
n−1 times
C (0?)(0?) . . . (0?) for N = 2n + 1, (2)
| {z }
n times
arbitrarily choosing the necessary number of people from the group marked with
question marks. For Q = 0.5 all these members are offered one coin, so question
marks can be replaced by ones. The mark 0 (or 1) means the offer, the question
mark means that this member might be chosen for a one-coin offer, but the
captain needs fewer members than the total amount of this category (or exactly
this number). However, this scheme is optimal for Q > 1/3.
For lower values, i.e., 0 < Q ≤ 1/3, the captain offers nothing to every
crew member for any N ≤ 1/Q, because his own vote is enough. Then he offers
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
for Q = 0.25, starting from N = 5:
C0???, 1 to choose,
C0?000, 1 to choose
C0?0???, 1 to choose,
C0?0?000, 1 to choose,
C0?0?0???, 2 to choose.
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 offered nothing.
The number of these junior members, denote it by J, is the minimal J that
satisfies the condition J > 1/Q − 2, because J + 2 is the first 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 (0?)(0?) . . . (0?)(0) |? .{z . .?} for N − J = 2l, l ≥ 1, (3)
| {z }
J
l−1 times
. . 0} for N − J = 2l + 1, l ≥ 1,
C (0?)(0?) . . . (0?) 0| .{z (4)
| {z }
J
l times
The special case Q = 0 is trivial: the captain takes everything for any crew
size N .
3.2 The Range 0.5 < Q ≤ 0.6
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 offered nothing;
privileged, who are offered one coin; and the others. The captain chooses the
necessary amount from this third category and offers them two coins; others are
offered nothing. This third category is marked by the question mark.
C (01?)(01?) . . . (01?) 10 for N = 3n, (5)
| {z }
n−1 times
C (01?)(01?) . . . (01?) 0?1 for N = 3n + 1, (6)
| {z }
n−1 times
C (01?)(01?) . . . (01?) 010? for N = 3n + 2. (7)
| {z }
n−1 times
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 offered
everything, he votes for the offer. Therefore, for N = 3, the captain simply offers
the second member one coin, which gives the case N = 3n for n = 1.
With N = 4, the captain offers one coin to the youngest, but he needs
another vote, which can only be number 2, who would be offered one coin by the
next captain. Therefore, to guarantee his vote, the captain offers 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 offers one coin to number 3, which would be offered
nothing by the next captain; one more vote is needed. Number 2 wants to become
a captain and get everything, so he is not offered anything, and there remains a
choice of two crew members (1 and 2). Number 2 would be offered two coins by
the new captain and may not agree to two; therefore, it is more reliable to offer
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 offered nothing on the previous
step are offered one; this gives the captain n votes. Nothing is offered to those
who could hope for two coins, because they may refuse even the offer of two.
There remain at least n − 1 crew members, who would be offered one coin on
the previous step. Among them, the captain needs to choose enough people to
get the quorum and offer 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,
| {z } | {z }
n−1 times n times
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 payoff 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 offered nothing by the next captain, his own vote, and has at least n − 1
people to choose the necessary number and offer 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 2n + 1
for N = 3n + 1, for N = 3n + 2.
3n + 1 3n + 2
The first 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 The range 0.6 < Q ≤ 0.625
For Q = 0.6 + δ up to Q = 0.625 we have the following first steps:
N =3: C10
N =4: C021
N =5: C0132
N =6: C(012)03
N =7: C(012)310
After that we have the pattern:
C (01?)(01?) . . . (01?) 00?1 for N = 3n + 2, n ≥ 2 (8)
| {z }
n−1 times
C (01?)(01?) . . . (01?) 0110? for N = 3n, n ≥ 3 (9)
| {z }
n−2 times
C (01?)(01?) . . . (01?)?10 for N = 3n + 1, n ≥ 3. (10)
| {z }
n−1 times
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 offered nothing; those, who are offered one coin, two coins, and the
rest: each of the rest may be offered three coins, or nothing, depending on the
captain’s arbitrary choice. This category is marked by question marks:
C (012?)(012?) . . . (012?)(021) for N = 4n, (11)
| {z }
n−1 times
C (012?)(012?) . . . (012?)(01?2) for N = 4n + 1, (12)
| {z }
n−1 times
C (012?)(012?) . . . (012?)(0120?) for N = 4n + 2, (13)
| {z }
n−1 times
C (012?)(012?) . . . (012?)(10) for N = 4n + 3. (14)
| {z }
n times
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 sufficient: the third vote is needed. So, the
captain must offer three coins to someone who would be offered two by the next
captain: the payout is C0132 = C01?2). Finally, with N = 6, the captain also
needs three votes, and he can offer nothing to the one who would be given three
coins by the next captain: C01203 = C0120?.
By induction, the captain offers one coin to those who would receive nothing
(at least n people) and two coins to everyone, who would be offered one (also at
least n people). Also, there are at least n − 1 people who would be offered two
coins: the captain chooses the necessary number of people to get the quorum
and offers 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 satisfied with any
payment). Since in the previous step two coins would be paid, it is not possible
to manage with a smaller amount.
3.5 The High Quorum: 2/3 < Q ≤ 1
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 indifference are loyal. This is necessary, because already in the case
of 3 members the captain needs to offer 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 offering 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 N̄1 = d1/(1 − Q)e; after that one member can be offered nothing, and
this would be the junior. The remaining members (let us call them aristocrats,
their number is A = d(1 − Q)−1 e − 2) get one coin, and the rest is taken by the
captain.
On the next step, nothing is offered 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 finally i, (for i ≥ 1), until N = d(1 − Q)−1 e − 2 + i + 1 exceeds the value
1 1
N̄2 = −1 .
1−Q 1−Q
At the same time, the captain gets the opportunity to offer 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 offered nothing, the captain offers 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 offer 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 + δ first. At the beginning up to N = 3, the
captain has to give everything to the junior. Then the payment has the form
N =4: C110
N =5: C0221
N =6: C01332
Next, one more member can be offered 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:
N =7: C012443
N =8: C0123554
N =9: C01234665
Then three men can be offered nothing: number 2 and both aristocrats; we get
N = 10 : C012345006
N = 11 : C0123450110
N = 12 : C01234001221
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 offered nothing. They are those who
want more and some of those who want three coins (the captain has a choice):
N = 13 : C012300112332
Continuing further, we get
N = 14 : C0123011223003
N = 15 : C01230122330110
N = 16 : C012301233001221
N = 17 : C0123012300112332
N = 18 : C01230123011223003
This can be written as a pattern:
C (0123) . . . (0123)(00112332), N = 4n + 1, n ≥ 3;
| {z }
n−2
C (0123) . . . (0123)(011223003), N = 4n + 2, n ≥ 3;
| {z }
n−2
C (0123) . . . (0123)(0122330110), N = 4n + 3, n ≥ 3;
| {z }
n−2
C (0123) . . . (0123)(3001221), N = 4n, n ≥ 4;
| {z }
n−2
This scheme is easily checked by induction, provided that the number of those
who can be offered 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 payoff can be as large as six coins, and for very small
everything is offered to the junior.
Also note that for large N the fraction of those who are offered 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 payoff, 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.
The pattern for Q = 0.7 + δ is constructed similarly, the first steps (up to
N = 9) are the same. Then:
N = 10 : C012345776
N = 11 : C0123456007
N = 12 : C01234560110
N = 13 : C012345001221
After that, for N ≥ 14, we have the pattern:
C (0123) . . . (0123)(000112332), N = 4n + 2, n ≥ 3;
| {z }
n−2
C (0123) . . . (0123)(0111223003), N = 4n + 3, n ≥ 3;
| {z }
n−2
C (0123) . . . (0123)(01222330110), N = 4n, n ≥ 4;
| {z }
n−3
C (0123) . . . (0123)(33001221), N = 4n + 1, n ≥ 4;
| {z }
n−2
This pattern is valid up to some finite δ, and so on. For Q = 0.7 + δ, the
payoff is limited by the same value 3 as for Q = 0.7 (with the different 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 offered to the junior, up to N = 10. Starting with 10
people, the captain can offer the junior nothing and one coin to other members
of the crew (called aristocrats), so the payout is 1 . . . 10.
Then number 2 is offered nothing, and up to N = 89 (or i = 79), we have
C 012 . . . (i − 1) (i + 1) . . . (i + 1) i.
| {z }| {z }
i 8
Starting with N = 90, 9 people can be offered nothing: number 2 and eight
aristocrats:
C 012 . . . [79] 0| .{z
. . 0}[80]
| {z }
80 8
C 012 . . . [73] 0| .{z
. . 0} 1| .{z
. . 1} 0
| {z }
74 7 8
C 012 . . . [66] 0| .{z
. . 0} 1| .{z
. . 1} 2| .{z
. . 2} 1
| {z }
67 8 7 8
...
C 012 . . . [17] 0| .{z
. . 0} . . . 7| .{z
. . 7} 8| .{z
. . 8} 9| .{z
. . 9} 8
| {z }
18 8 8 7 8
C 012 . . . [10] 0| .{z
. . 0} . . . 8| .{z
. . 8} 9| .{z
. . 9} [10] . . . [10] 9
| {z } | {z }
11 8 8 7 8
Here and below we use brackets to isolate two-digit numbers, so [10] is one
payment of ten coins, not two payments of 0 and 1 coin.
Next, one more can be offered nothing:
C 012 . . . [10] 0 1 . . . 1 . . . 9 . . . 9 [10] . . . [10] 0 . . . 0[10]
| {z } | {z } | {z } | {z } | {z }
11 8 8 7 8
C 012 . . . [10] 01 |2 .{z
. . 2} . . . [10] . . . [10] 0| .{z
. . 0} 1| .{z
. . 1} 0
| {z } | {z }
11 8 8 7 8
new
z}| {
C 012 . . . [10] 0123 |3 .{z
. . 3} . . . [10] . . . [10] 0| .{z
. . 0} 1| .{z
. . 1} 2| .{z
. . 2} 1
| {z } | {z }
11 7 8 8 7 8
...
new
z }| {
C 012 . . . [10] 012 . . . [10] [10] . . . [10] 0| .{z
. . 0} . . . 7| .{z
. . 7} 8| .{z
. . 8} 9| .{z
. . 9}[10]
| {z } | {z } | {z }
11 11 7 8 8 7 8
new
z}|{
C 012 . . . [10] 012 . . . [10] | 0 {z. . . 0} 1| .{z
. . 1} . . . 8| .{z
. . 8} 9| .{z
. . 9} [10] . . . [10] 0
| {z } | {z } | {z }
11 11 8 8 8 7 8
The group of eight people who expect 10 coins is offered 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 sufficiently high, although
for a small crew it is much higher.
The maximal payoff is asymptotically (1 − Q)−1 . The number of people who
can be offered 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 offer and thus is offered nothing. He joins the group
of b(1 − Q)−1 c + 1 crew members with increasing demands: 012 . . . . The leader
of this group, who wants too much, is offered nothing and joins the next such
group. So, the length of such groups remains constant. The leader of the right-
most group, who are offered 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 offers 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 offered nothing.
4 Applications
Similar problems appear in volunteer computing [1]. Assume that owners of
computers join to solve a computationally intense problem; the effective power
of their devices is different, not only because of different hardware but also
because of different 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 significant 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 different depending on the
agreement between the members and psychological description of their behaviour
(if many colleagues approve the offer 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 payoff pattern is highly uneven, and individual payoff
depends very weakly on the personal contribution.
5 Conclusion
In this paper, we present the comprehensive quorum analysis in the “Pirate
game” problem. We discover six intervals of quorum value with the different
strategies patterns; they are:
– 0 < Q ≤ 1/3: the payoff depends on divisibility on 2 and is given by (3)–(4);
– 1/3 < Q ≤ 0.5: the payoff depends on divisibility on 2 and is given by
(1)–(2);
– 0.5 < Q ≤ 0.6: the payoff depends on divisibility on 3 and is given by (5)–(7);
– 0.6 < Q ≤ 0.625: the payoff depends on divisibility on 3 and is given by
(8)–(10);
– 0.625 < Q ≤ 0.66(6): the payoff depends on divisibility on 4 and is given by
(11)–(14);
– 0.66(6) < Q < 1: this interval is divided into subintervals in which the
patterns are constructed as it is described in subsection 3.5.
The main conclusions of the study are: the captain with enough money to
share is always able to make an offer to satisfy enough crew members and to
keep most coins for himself; the maximal individual payoff does not depend on
the crew size if this size is sufficiently large; and in a general case, the captain
has some freedom in choosing those who are offered something and those who
are not.
References
1. Anderson, D.P., Fedak, G.: The computational and storage potential of volunteer
computing. In: Turner, SJ and Lee, BS and Cai, W (ed.) Sixth IEEE International
symposium on cluster computing and the GRID: spanning the world and beyond.
pp. 73+. IEEE Comp Soc TCSC; Oracle; HP; IBM; Intel; Sun; Platform; PTC
(2006), 6th IEEE International Symposium on Cluster Computing and the Grid
(CCGRID 2006), Singapore, May 16–19, 2006
2. Brams, S., Taylor, A.: An envy-free cake division protocol. The American Mathe-
matical Monthly 102(1), 9–18 (1995)
3. Chi Changye: A game-theoretic analysis of the pirate game. Bachelor Thesis, Na-
tional University of Singapore (2019)
4. Coram, B.: Second best theories and the implications for institutional design. In:
Goodin, R. (ed.) The theory of Institutional Design, pp. 90–102. Cambridge Uni-
versity Press (1996)
5. Fontes, D.F.P.: Quantum Pirates. A Quantum Game-Theory Approach to The Pi-
rate Game. Master’s thesis, Tecnico Lisboa (2014)
6. Moulin, H.: Game theory for social sciences. University Press, New York (1986)
7. Stewart, I.: A puzzle for pirates. Scientific American 5, 98–99 (1999)