Another Pirates and Gold coins (with announcements)

Question

Once again we have group of pirates, 6 this time, and they want to split 300 gold coins.

They split gold according to familiar rules but with a twist. Oldest pirate propose split and if he gets majority of votes (including his own), his proposal is implemented. Otherwise he is killed and next oldest pirate is making his proposal under same rules. All pirates are intelligent, greedy, bloodthirsty and cautious.

The "twist" in rules (making this significantly different problem from classic) is that, before oldest pirate P6 make his proposal, each pirate (starting with youngest, in order P1,P2..P6) will announce what they will propose if they get chance to propose - and they must honor that proposal or they will get killed.

What will P6 announce/propose, and how many coins he will get?

Some bonus questions:
b) if there are 7 pirates, what is their expected gain? [harder and more interesting than 6 pirates]
c) formula C(P,G) for expected coins oldest pirate P will get out of G gold (or his full proposal)

Clarification of rules:

• "majority" means pirate P need V > P/2 votes. For example, with 4 pirates he needs 3 votes (his own and two more)
• pirates' priority for optimal result: survive, greedy, bloodthirsty
• "intelligent" means that they can assume all pirates are able to find optimal solution
• "greedy" means that pirates will propose and vote in such way that they maximize their expected gold gain and still survive, so they will vote NO if they expect more gold from next proposal
• "bloodthirsty" means pirates will also vote NO if they expect same gold from next proposal
• "cautious" means that any younger pirates is aware of (unlikely) possibility that he will be one to propose first (if pirates older than him suddenly disappear after he makes an announcement)
• cautious rule means that if a younger pirate has choice of several optimal proposal to announce (they yield equal expected gold assuming oldest pirate propose first), he will choose one that is optimal for him even in case that he gets to propose first

This is different from classic pirates puzzle in several ways:

• very significant difference due to announcements
• significant difference since pirates need "majority" of votes
• 6 pirates in this problem are noticeably more complex than 5 (unlike classic)

I created this problem based on some incorrect solutions that were posted related to my previous pirate problem. Those were incorrect because rules of that previous problem did not allow them, and only way where those could affect solution would be to make different problem. Eventually I decided to try to create such "different" problem - resulting in this problem with announcements.

Some hints:

- this may look similar to classic puzzle with "majority" rule, but it is (arguably) significantly harder
- order of announcements ensure that older pirates can tailor their proposal/announcement based on younger pirates announcements
- unlike all classic or semi-classic versions, here solution can not be easily done by induction from youngest pirate (quite the opposite)
- for example, the classic P5 proposal is same regardless if at start there was 5 or 6 pirates, but here it is not
- for the primary problem (with 6 pirates) "expected values" or probability in general should not play a major role ... but it may for the bonus problem
- the "cautious" rule should make pirate choices more specific, especially for the bonus problem
- after I posted this problem, I found a similar one here. It also has a form of announcement but differs in other two significant elements (no "majority" rule, and only 5 pirates), so it is easier and with a different solution compared to this one - but can be used as a hint

Some hints for bonus problems:

- "7 pirates" is noticeably harder than 6 pirates, and "expected value" does play a crucial role (while the "cautious" rule is not crucial yet)
- there is a twist for optimal P3 proposal in "7 pirate" version
- I still did not solve the "formula" bonus or, to be more precise, I did not prove yet my expected solution formula

Answer 1

(Edit 2: Turns out, I was confused. The original answer is incorrect, the oldest pirate will instead

give any of the three possible splits $(0,0,1,1,100,198)$, $(0,0,1,2,100,197)$ and $(0,0,2,1,100,197)$ with a probability of $\frac{1}{3}$.

I will give the reasoning for that at the end.)

---

Unless I made a mistake (I got quite confused working this out), the oldest pirate will propose to give a split of

(0,0,1,1,100,198), that is, nothing to pirates 1 and 2, one coin each to pirates 3 and 4, 100 coins to pirate 5 and the remaining 198 to herself.

This time, the reasoning is a bit more complex than just working backwards: Let's call a proposal of a single pirate $P_i$ stable if it would get approved in the case that every offer so far would be rejected. To get things started, we may first observe that $P_3$'s proposal (what ever it may be) is always stable (as $P_2$'s is certainly not, so that $P_3$ is always guaranteed two votes). From there, it is not hard to see that the proposals of all older pirates will be stable as well (each successive pirate can just buy off the cheapest few votes from the previous offer, which clearly gives them a stable proposal). (Edit: This assumption is actually not warranted. We may at this point only conclude that $P_6$'s offer will be stable, nothing else. Nonetheless, the statement is correct, which I will show at the end.)

As such, we can already conclude that the greediest option for pirate 6 will be to increase the three cheapest offers of pirate 5 by 1 and give the rest to herself.

What will pirate 5 propose in order to gain the most from this knowledge? Well, to get paid at all, she would like to maximize her value while still guaranteeing to belong among the three cheapest options of her own proposal. The optimal way this will pan out is for her to buy two votes for 100 and 101 coins each (this is clearly always possible - just take the two lowest bids from prop 4) and pocket the remaining 99 coins.

From this, we can now conclude that pirate 6 will definitely offer a split of $(0,0,1,1,100,198)$, with 198 coins for herself, 100 for $P_5$ and one each for the two pirates that were promised nothing under $P_5$. It remains to figure out who these pirates will be.

As a direct consequence, pirate 4 can stand to gain at most 1 coin from the final offer. How can they achieve at least that? In order for them to come (shared) last in the penultimate proposal, they would like to guarantee to not belong to the pirates that $P_5$ can buy off with at most 101 coins, i.e. they would like to pay themselves at least 101. Is this possible, while still fulfilling the demands of a stable offer? Not in general! For her offer to be stable, $P_4$ needs to improve upon two of $P_3$'s bids. With only 199 coins to spare, this will be impossible if (and only if) the proposal of $P_3$ will give each pirate at most 103 coins. At first glance, this looks as though $P_4$ cannot guarantee to get paid. But in fact, it is counter to $P_3$'s interest, to space her offers so tightly! Indeed, if she does so, $P_4$ could get a stable proposal by paying both of the youngest pirates 150 coins each (say). In that case, both of these pirates will end up with the single coins from $P_6$ in the end. Therefore, if there is any other way that $P_3$ can guarantee to be paid in the end (we will see that there is), she will make a proposal that allows $P_4$ to give a stable offering while paying herself (at least) 101 coins.

In order for $P_3$ to receive any money in the end, she would need to land among the pirates that get offered nothing from $P_5$, which is only guaranteed if her offer by $P_4$ is at least 101. Can she force this to happen? In order to do so, $P_3$ needs to craft her proposal in such a way that the only stable offering of $P_4$ that gives the latter at least 101 coins, also gives that amoung to $P_3$. And this, finally, is easily seen to be possible, by proposing a split of (say) $(0,200,100)$ in order.

So, to recap the order of events:

• The first two offers are irrelevant, as the third will always be stable.
• The third pirate will propose a split of $(0,200,100)$ (or anything that gives herself at least 100 coins while still being among the definite two cheapest options).
• The fourth pirate will then give a split of $(1,97,101,101)$ (or anything that pays her and $P_3$ at least 101 while still improving upon the other cheap offer from $P_3$).
• The fifth pirate will propose $(100,101,0,0,99)$ (up to a swap of the first two).
• And, finally, the sixth and last pirate will propose the split of $(0,0,1,1,100,198)$.

I have not thought much about the bonus question yet. Seems quite tricky ...

---

To finish the proof, it still remains to see why the offers of both $P_5$ and $P_4$ will necessarily be stable. Luckily, this is not too hard: If $P_5$ would propose an unstable offer, the greediest option from $P_6$ would be to pay nothing to $P_5$ and secure the other two votes by buying off the cheapest vote(s) from the last stable offer (depending on the stability of the fourth one). As such, $P_5$ is guaranteed to go empty handed unless they give a stable offering.

Now, if the fourth offer is also stable, the above solution kicks in. But otherwise, $P_5$ can still go with the $99,100,101$ split by paying 100 coins to $P_4$ and 101 to the least paid pirate on the third list. This possibility would then leave $P_4$ with nothing in the end, so that they too will instead choose to give a stable offer and thus follow the solution above.

---

---

So, where did this solution go wrong? In the simple assumption that P5's only option for maximizing her payout while still coming among the three cheapest would be a split of 99,100,101. Instead, she may just as well propose 0,1,99,100,100, whenever this also gives a stable solution. In fact, it is very much in P4's and P3's interest that such a split is possible, for that increases their expected payout by half a coin each. Hence, if at all possible, P4 will propose a stable split that gives herself 101 coins and still allows P5 to make a stable offer with the 0,1,99,100,100 option. Similarly as in the mistaken answer, this may only fail if P3 pays each pirate at most 103 coins. But, this is (as above) not in P3's interest, for P4 may then go with a split that guarantees P3 to get nothing in the end. Therefore, P3 will again strive to make an offer such that P4's only option for a stable offer while paying herself $\geq 101$ coins also gives P3 at least that much. There are (again) various possibilities of achieving this - the example in the original answer (up to P5) works just fine here.

Thus, the only measurable difference comes from P5 having three equally viable splits, which each give a different final proposal from P6.

Answer 2

Answer above from Tim is practically correct for primary problem ( with 6 pirates), and he even caught "surplus +1" issue that I missed initially.

It is correct logic and I marked it as an answer, but since it still misses few things I will post them here for completeness: final solution for primary "6 pirates" problem and exact solution for harder "formula" problem.

---

"6 pirates" question

Reasoning logic is nicely described in Tim's answer so there is no need to repeat it here, although I will repeat important findings that continue to be valid for 7+ pirates:

• pirates younger than P3 have NO influence on result
• P3 and P4 pirates CAN influence result by offering themselves >100g, thus ensuring that P5 offer them zero/low gold, thus ensuring P6 offer them at least 1g
• P5 pirate is most interesting one : he can ensure that he gets fairly large amount of gold, by proposing for himself 3rd smallest amount - and since P6 need 3 additional votes, he must include his amount in final proposal. And largest possible 3rd smallest amount is 99g, eg ( 101,100,0,0,99 ) - zeros are for P3/4 that offered themselves >100g
• but there is "surplus" twist there: what P5 minimally need is two pirates with larger amount than him, so even (100,100,0,0,99) would do ... meaning there is surplus +1g that can go to any of P1..P4. So equally valid P5 proposals are: (101,100,0,0,99), (100,101,0,0,99), (100,100,1,0,99) and (100,100,0,1,99) with equal 1/4 chance
• responses to those proposals by P6 are, respectively: (0,0,1,1,100,198), (0,0,1,1,100,198), (0,0,2,1,100,197) and (0,0,1,2,100,297) with same 1/4 chance
• so answer to "what will P6 propose" is : P6 will propose 0g to P1/2 and 100g to P5. To P3/P4 he proposes 1g in half cases (when he gets 198g) and 1g/2g or 2g/1g otherwise (when he gets 197g)
• thus answer to "expected gold value for P6" is 1/4*(198+198+197+197)= 197.5g

---

Formula question

If only approximate value was needed, that this would be relatively simple formula C(P,G) , using integer math where % is moduo:

C(P,G) ~ G-2G/(P+P%2)-P/2+1

But actual correct formula is somewhat more complicated :

• it must also solve expected value for ALL younger pirates
• it must account for "surplus" variations

Formula is based on same logic that was used for "6 pirates", only generalized regarding total "P" pirates count:

• pirates younger than P-3 have NO influence on result
• #(P-3) and #(P-2) pirates CAN influence result by ensuring that #(P-1) offer them zero/low gold, thus ensuring #P offer them at least 1g
• #(P-1) second oldest pirate is most interesting one : he can ensure that he gets fairly large amount of gold.
• if V is number of votes needed by oldest, then second oldest will propose so he gets (V-1)th smallest amount. That way oldest can not ignore him in his offer
• if N is number of votes needed by second oldest, it turns out that being "(V-1) smallest" is always same as being "Nth largest". So optimal strategy for 2nd oldest is to split gold by N and fix by +/-1 so that he is smallest of those N values (while still being as large as possible, to satisfy "greedy")

Optimal proposal by second oldest pirate is key element of solution. From above we see that he must split gold to N semi-equal values Z. If Z=G/N (integer quotient) and M=G%N (remainder) then he can offer something like:

• Z+1,Z+1,Z,...,Z,0,0,Z-1
• 2nd oldest pirate (P-1) offers "Z-1" gold to himself and zeros to (P-2) and (P-3) since they will ensure in their offers for themselves at least Z+1 gold
• with N of those "~Z" values, 2nd oldest ensure his is smallest with "Z-1", so oldest pirate will be forced to offer him Z gold (one more gold)
• to younger pirates (1..P-4) he offers either "Z" or "Z+1" (or 0g, see below). There will be (M+1) of those "Z+1"
• special case is when M==N-1, since then 2nd oldest can offer (Z+1,Z+1...,Z+1,0,0,Z)
• note that while pirate (P-2) ensure his low/0g offer from second oldest (P-1) in standard way (by offering largest value to himself), pirate (P-3) must use same "Nth smallest" logic as (P-1) to ensure large offer from (P-2) pirate, which in turn ensure low/0g offer from second oldest (P-1).

But there is twist to above logic for second oldest (except in special case) : we actually have "surplus" of S=M+1 "+1s" that do not need to be given as "+1". They can be actually distributed in ANY way, among ALL pirates younger than 2nd oldest ( including those with 0g in proposal above ). If (Z,Z,Z,..Z,0,0,Z-1) is "baseline" with S "surplus" then if for example S=3, following are examples of valid proposals with equal expected gain for 2nd oldest :

• Z+1,Z+1,Z,..Z+1,0,0,Z-1
• Z,Z+1,Z,..Z,1,1,Z-1
• Z+3,Z,Z,..Z,0,0,Z-1
• Z,Z,Z,..Z,2,1,Z-1
• Z,Z,Z+1,..Z,0,2,Z-1
• ... and all other combinations with (1,1,1) or (2,1) or (3)

What is average "surplus" gold that any of X pirates can expect, if proposing pirate has S surplus total and choose randomly among all possible options?

That is interesting small problem in itself, but it turns out it is simple S/X ( I will skip proving this, but it is not hard ). And in this case where proposing pirate is second oldest, X=P-2 (he can distribute surplus to any other pirate except himself).

So, what is average expected gold for those (P-2) youngest pirates from proposal of oldest pirate? Without "surplus", those that got 0g from second oldest would get 1g from oldest. With "surplus", they will get 1+S/(P-2) gold on average.

But we have two groups of pirates who can get "low offer" (0g without surplus, <=S with surplus) by second oldest:

• (P-2) and (P-3) get guaranteed low offer, so their "expected gold value" after oldest offer is 1+S/(P-2)
• younger pirates 1st..(P-4)th get either "Z" or "0" (plus eventual surplus) - where order of those "Z"/"0" is random and there are K=V-4 of those "0"s ( where "V" are votes needed by oldest, and K>=0 ). So those younger pirates will get low offer from second oldest with chance K/(P-4)= (V-4)/(P-4) , and their "expected gold value" is (V-4)/(P-4)*(1+S/(P-2))

Second oldest will be offered (Z-1)+1 by oldest, and since Z= [G/N] (integer division), "expected gold value" by second oldest is [G/N]. And oldest "expected value" is total gold G minus expected values of all other pirates, or EV(P)= G - EV_2nd_oldest - 2xEV_older - (P-4)xEV_younger = G-[G/N]-(1+S/(P-2))*(V-2)

So formulas in normal cases for "expected gold value" of all pirates are:

- EV_younger =EV(pirates 1..P-4)= (V-4)/(P-4)*(1+S/(P-2))
- EV_older =EV(pirates P-2 and P-2)= 1+S/(P-2)
- EV 2nd_oldest =EV(P-1)= [G/N]
- EV_oldest =EV(P)= G-[G/N]-(1+S/(P-2))*(V-2)

But, as it was mentioned above, there is one special case when there is no "surplus", when M==N-1 and second oldest proposal looks like (Z+1,Z+1,...Z+1,0,0,Z). For that special case, expected values are same as in above formulas with S=0, but 2nd oldest now expect one more (Z+1 instead of Z), and accordingly oldest expect one less.

And formulas for special case, when there is no surplus, are :

- EV_younger =EV(pirates 1..P-4)= (V-4)/(P-4)
- EV_older =EV(pirates P-2 and P-2)= 1
- EV 2nd_oldest =EV(P-1)= [G/N]+1
- EV_oldest =EV(P)= G-[G/N]-V+1

Derived values (N,V,S) that both above groups of formulas depend on, in addition to actual parameters (P,G), were already explained above :

- V= int[P/2]+1 ( number of votes needed by oldest )
- N= int[(P+1)/2] ( number of votes needed by second oldest )
- S=G%N+1 ( surplus, where % is MOD function )
- special case is when G%N==N-1 ( then S=0 )

Note that only one set of formulas from above is applicable at a time, as explained above. So, depending on specific P and G, either "normal" or "special" case formulas are used.

Above formulas work under condition 6 <= P < 2*G :

- formula for K=V-4 is only valid if P>=6, otherwise it should be K=0
- it is fairly easy to cover P>=4 with change K=max(0,V-4), and changing number of older pirates with guaranteed low/0g by 2nd oldest from fixed 2 to IF(P>5,2,1)
- but P<=3 remain special cases that can not be covered with these formulas
- formulas also cover only situation when there is enough gold to share, which in general is when P<2*G
- it is not so easy to cover low gold cases. I suspect they would exhibit same 2^z survival pattern as in classic solution, but I did not solve those

What will oldest pirate actually propose was not in bonus question, but neither was EV for all other pirates, so we can try to answer that one too. Proposal of oldest pirate is based on second oldest (P-1) random distribution, which include himself and two groups : two older pirates (P-2) and (P-3) with guaranteed "~0", and younger pirates 1..(P-4) which get (N-1)x "~Z" and (V-4)x "~0" [ put in square brackets below, where "Z" and "0" can be in any order ], with "~" denoting that any of those pirates can get increase in [0,S]g range, but with total surplus in sum always being S.

Proposals by 2nd oldest and oldest, with surplus "~" and any order inside []:
- [~Z,~Z,~Z,~Z,~0,~0], ~0,~0, Z-1     : proposal by 2nd oldest,~= up to +S  
- ( 0, 0, 0, 0,~1,~1), ~1,~1, Z  , R  : proposal by oldest

Example proposals by 2nd oldest, followed by proposal from oldest, if S=3:
-  Z,  1,  Z,  0, Z, Z, 2, 0, Z-1     
-  0,  2,  0,  1, 0, 0, 3, 1, Z  , R  : R get -3 due to S

-  0,Z+1,  Z,Z+1, 0, Z, 0, 1, Z-1     
-  1,  0,  0,  0, 1, 0, 1, 2, Z  , R  : R gets -1 due to S


-  0,Z+1,Z+1,Z+1, 0, Z, 0, 0, Z-1     
-  1,  0,  0,  0, 1, 0, 1, 1, Z  , R  : R gets -0 due to S
 1

Oldest will propose "0g" to any of the younger pirates with "~Z", and will propose +1g to any pirate with "~0g" from 2nd oldest proposal, denoted by "~1g" in oldest proposal. Normal brackets around younger pirates in oldest proposal denote that "~1" and "0" can be in any order, where that order is determined not by him but by 2nd oldest pirate ( whose proposal use square brackets for that reason ). That "~1" is randomly in range [1,S+1], but increases above 1g cannot be larger than S in total ( and can be lower in total, even zero if all surplus by 2nd oldest goes to pirates with "~Z" )

So oldest will propose :

( 0, 0, 0, 0,~1,~1), ~1,~1, Z , R : proposal by oldest with any order inside ( brackets )

- "0" gold to (N-1) younger pirate, and "~1" gold to (V-4) younger pirates, in any order
- "~1" gold to pirates (P-2) and (P-3)
- "Z" gold to second oldest (P-1) pirate
- "R" gold, as remainder of initial G gold, to himself
- in "special cases" there is no surplus "~" and 2nd oldest get "Z+1" gold

---

8 pirates with 302g question

I will not answer here that particular question, nor simpler "7 pirates" one, since their final solution is also covered by general formula explanation.

But they are interesting to solve manually and see/check if there is really no way for younger pirates to "bomb" logic that was explained in formula solution.

And "8 pirates with 302 gold" is also very interesting to solve manually since that is lowest number of pirates where 0g offers appear for younger pirates, in addition to "surplus". If I had my final solution when I initially posted this question (which obviously I did not), I would have chosen to ask only for "(8p,302g)" as primary problem and "formula C(P,G)" as bonus one.