1
$\begingroup$

I recently encountered the Pirate's Game and I found the solution for the malevolent pirates where the strict majority is needed for the highest ranking pirate's survival. Rules:

We have $P$ pirates and $G$ gold coins which are indivisible. The pirates are ranked in order of seniority from $1$ to the $P$. Based on the pirates' tradition, all of the coins are given to the most senior pirate to be distributed. The plan devised will be put forth, whereupon all pirates would vote. If the plan gets more than half of the votes, it will be enacted, otherwise the most senior pirate will be killed and the second most senior officer takes on and the process starts over. Let's note that all pirates are rational, greedy (maximizing the number of golds they get), bloodthirsty (wanting to kill other pirates), and want to stay alive (their livelihood has the highest priority for them).

My challenges:

  1. How can the general formula be calculated? I believe it has some similarities with the case that the proposer can't vote but in that case we are calculating for $ \lfloor(n-1)/2\rfloor$ there but here it's $\lfloor n/2 \rfloor$.

  2. What difference does the malevolence make? If it was not bloodthirsty (a pirate never can be benevolent), how would have the problem changed and what would have been the choice for equivalent cases for each pirate? What I mean is if the pirate was neutral and he was offered two dividing strategies, would he just choose randomly?

$\endgroup$
2
  • $\begingroup$ See also here: Pirates and gold coins. $\endgroup$ Mar 7 at 13:55
  • $\begingroup$ @JaapScherphuis dear sir ; I saw this thread but the problem I had was the fact that It checked for the case where even half was enough. what bothers me is the case where you strictly need more than half of the votes. how would that be solved? $\endgroup$
    – itspaspas
    Mar 7 at 14:03

1 Answer 1

1
$\begingroup$

I find the base problem surprisingly complex:

Special case 1: 2 pirates
Whatever the leader proposes, nr2 votes against , the leader gets killed and nr2 happily leaves with all the gold.
Special case 2: 3 pirates
Due to case 1, the number 2 pirate does not want to become the leader since that gets him killed, thus the leader can assign all gold to himself
Otherwise: Assuming he has the gold, the leader will offer 1 gold to all pirates the next leader would ignore, and occasionally 2 to a pirate that would get 1

This does not completely work

Special case 3: with 6 pirates, it is unclear which pirate gets 2 the next round, but you need the loyalty of 1 of them; to be certain of their loyalty 3 should (probably) be paid.
A listing up to P=13:
{?,?} nr2 always votes against; leader gets killed
{G,0,0} nr2 supports leader or both will get killed -- so leader can take all gold
{G-2,0,1,1}
{G-3,0,1,(2),(2)} (1 times 2, leader's choice)
{G-6,0,1,2,(3),(3)} (1 times 3)
{G-6,0,1,2,3,0,0}
{G-5,0,1,2,0,0,1,1}
{G-5,0,1,(2),0,1,1,(2),(2)} (1 times 2)
{G-8,0,1,2,0,1,2,2,0,0}
{G-6,0,1,(2),0,1,(2),0,0,1,1} (1 times 2)
{G-8,0,1,(2),0,1,(2),0,1,1,(2),(2)} (2 times 2)
{G-9,0,1,(2),0,1,(2),0,1,(2),(2),0,0} (3 times 2)

Special category: What if a leader does not have enough gold?

Normally that would mean getting killed, but with a small shortage this does not necessarily happen:

With 5 pirates and 1 gold the second in command would also get killed the next round - so will support the leader even with 0 gold offered! Thus the leader can offer the single gold to nr 4 or 5.

With 5 pirates and 2 gold the second in command would get no gold (or get killed) the next round - so will support the leader even with 1 gold offered! Thus the leader can offer 1 gold to nr2 and nr3.

Similar things can happen with larger numbers

Addition

Assuming pirates can be counted on to use probability the solution becomes a bit cleaner:

If there is plenty of gold:

Number 2 wants to be captain desperately and only supports the captain for a large sum; thus is a lost cause and gets nothing.
Number 3 does not want to become nr2 for above reason; will support the captain for 1 gold.
The lower ranks are greedy they know they can get at least 1 on average and with their gambling habits understand probabilities; enough of them need to be paid at least 2.

If gold is scarce:

The lower ranks know they get less than 1 on average if the captain dies; enough of them need to be paid for their vote but 1 is enough.
The higher ranks will form blocks, they will give free support if the captain getting killed will also get them killed.
The first block will be 2 pirates (with 1 free vote from nr2).
The next block will be 4 additional pirates (with 3 free votes from nr2..nr4). etc.

The transition:

odd P and P-2 gold
In this case your number 2 will get no gold if the captain dies.
The captain ,nr2 and nr3 can all get 1 gold and be happy while 1 lower rank need to be paid 2 to be happy. This is the minority of them, allowing the switch to the scarce gold scenario!
odd P and P-1 gold
In this case your number 2 will get 1 gold if the captain dies The captain and nr3 can both get 1 gold and be happy, while nr2 and the lower ranks need to be paid 2 to be happy. This is the minority of them, allowing the switch to the scarce gold scenario!

example: 8 Gold

P
2 captain gets killed
3 8@0 @: gets paid 0 but supports
4 6011
5 501?? ?: 1 gets paid 2
6 301??? ?: 2 get paid 2
7 301???? ?: 2 get paid 2
8 101????? ?: 3 get paid 2
9 1?1?????? ?: 3 get paid 2; the minority!
10 30#0###### #: 5 get paid 1
11 30(5/9) (5/9): 5 of last 9 get paid 1
12 20(6/10)
13 20(6/11) 14 10(7/12)
15 10(7/13)
16 00(8/14)
17 0(8/16)
18 captain gets killed
19 0@(8/17) @: gets paid 0 but supports
20 captain gets killed
21 captain gets killed
22 captain gets killed
23 0@@@(8/19) @: gets paid 0 but supports

$\endgroup$
4
  • $\begingroup$ thank you for your answer! there was one point though that had me thinking about it. for the cases of 5 and 6 pirates, you said that the leader will choose to whom he gives the 2 and 3 coins. is that insinuating that the problem is showing a probabilistic nature? can't we say he could give 2 coins once to one and the next time the 2 coins to the other one , respectively for 5 and 6 pirates cases? $\endgroup$
    – itspaspas
    Mar 7 at 21:12
  • $\begingroup$ for P5: yes 1 vote is needed from a pirate that gets 1 gold on his death, 1 such pirate will get bribed at random. for P6: sort of: 1 vote is needed from a pirate that gets potentially gets 2 gold on his death, it is unspecified in the problem if a certain 1 or a certain 2 is preferred over a potential 2 + a kill. Considering the devious nature of pirates, and to highlight the special situation, I assumed the leader could only guarantee survival by offering 3. If pirates think probabilistically, 2 would be enough. $\endgroup$
    – Retudin
    Mar 8 at 7:31
  • $\begingroup$ PS: I just read the linked question; it seems my "Similar things can happen" at the end is a huge can of worms (similar to the 'little gold available'-reasoning there) that deserves much more attention. $\endgroup$
    – Retudin
    Mar 8 at 7:35
  • $\begingroup$ can any closed form formula be achieved for this question? I assume a recurrence must be solved for this purpose but I cannot surely do this. what I calculated was $P$ and $2^G-1+2^k$ for $k$ being any natural number but as said, I highly doubt its accuracy. $\endgroup$
    – itspaspas
    Mar 9 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.