Pirate Democracy

[mike-l]

Except he doesn't have to say anything. It's being deduced that it is more profitable for him to commit absolutely to not betraying. If we deduce that he would only lie, and always betray, then he will always receive 0 gold in the three pirate situation, yet if we can deduce that he will commit to not betraying, then there is an avenue for pirate 2 to make 998 gold and give 2 to pirate 1. 998 > 0 and 2 > 1. Surely, if possible, pirate 2 will commit (not say he will commit, but actually do so, so that we may deduce a desirable course of action about him committing) to anything he must to make this possible.

We can't deduce that, since there's no avenue to enforce that commitment. Surely he'd like there to be one, but the way the problem is set up, there's nothing stopping him from 'betraying' and just taking 1000 gold.

[WarDaft]

So you're saying that there is no such branch possible in his decision tree?

Code: Select all

   ....
    |
    |--------------------------------|
    |                                |
    V                                V
  Betray                        Never Betray
    |                                |
    V                                |----------------------|----.....
Get 0 Gold                           |                      |
                                     V                      V
                             Offer P1 2 Gold        Offer P1 3 Gold
                               Get 998 Gold           Get 997 Gold

We know that P2 would like such a branch. If there was a magical ritual to add such a branch, surely P2 would choose it to perform it. We know that P2 knows the entire betray branch simplifies to the above (we even assume this in the 4 pirate case!) So why cannot a perfectly logical being simply decide not to ever betray someone, without magical aid? It's not like they can do any worse than getting no gold by making such a decision, so they're certainly not missing out on anything.

[mike-l]

I'm saying there's no situation in which a rational agent whose priority is to make the most money will choose 998 gold over 1000 (with no further actions in the game to follow)

[WarDaft]

But would they not be willing to remove the choice if said removal was profitable? And if a magical ritual can create a branch of their choice tree without that choice, why can they not construct one, and then enter it willingly. If constraining your future choices is more beneficial now than it will be then, why would that stop you from constraining yourself now?

Do remember that perfectly logical beings, by definition, do not have anything that we might consider free will. Their decision to change their decision tree.... is in their decision tree... and can certainly be removed.

[Gwydion]

WarDaft, mike hits it on the head there - if there are no further actions, there is nothing to compel P2 to actually hold to his word. It's not really about the commitment to being honest, but the belief by other players that you are committed to being honest (whether you'll betray in the end or not).

Let's change the game, though: Now, all pirates write down their proposed divisions in sealed envelopes. They are opened one by one, starting with the highest-numbered pirate, and they vote. If it loses, that pirate is tossed off and the next envelope is opened. Now, P2 has an option to do better - he takes his paper out, writes "2 gold for P1, rest for P2", and shows it to P1 before sealing the envelope. Now, he is committed to his claim, and your solution works... until P3 finds out and offers P1 one more gold piece.

In fact, if P3 knows about P2's strategy in this situation, P2 will still never get anything - because P1 gets it all! Imagine that P3 values survival more than gold. For any x (where x is the amount P3 offers P1), P2 can write down x+1 and get P1 to cheat P3. This works all the way up to x=998, where P2 keeps 1 gold piece and still votes down P3 with P1's help. For x=999, however, P2 should not offer P1 all 1000 pieces because he gets nothing either way, and would rather see P3 die than not (all else being equal). So an equilibrium strategy in this game would be P3 offers P1 999 coins, ensuring his survival and keeping one for himself.

[WarDaft]

We could just consider that puzzle yes. It's effectively the same as what I was proposing I think (at least for this puzzle), and we can get the discussion back to what the pirates would do, rather than why.

The 3 pirate case still isn't that simple though... pirate 1 cannot demand 501 gold so easily! Consider: if pirate 1 demands 502 gold, that means pirate 2 has committed to paying pirate 1 501 gold, which means pirate 2 is left with... 499 gold! 500 gold would buy his vote, as opposed to 502 for pirate 1's vote!

This is rather why I was steering towards this interpretation... I think it has the potential to be more interesting. I haven't been able to concretely solve even the 4 pirate case, and I'm still not certain I have 3 down.

[Gwydion]

The 3 pirate case still isn't that simple though... pirate 1 cannot demand 501 gold so easily! Consider: if pirate 1 demands 502 gold, that means pirate 2 has committed to paying pirate 1 501 gold, which means pirate 2 is left with... 499 gold! 500 gold would buy his vote, as opposed to 502 for pirate 1's vote!

Actually, no. P2 will NEVER vote for P3's proposal. Assume the proposals are sealed in the envelopes at the same time, and are public knowledge (so there's no wondering about who moves first). Our logic works like this: If P3's proposal fails, P2's proposal necessarily passes (no matter how bad it is for P2, it's better than dying). It's usually assumed in puzzles like this that pirates are bloodthirsty, and if the gold is the same, would rather see a maximum of pirates die. As a result, there is no amount P3 can offer P2 that he can't take for himself, offering the same to P1. If P1 is getting the same amount from both proposals, he too will prefer to see P3 die (barring future repeated games). Thus, P3 offering P2 anything will not change his behavior. Thus, P3 should bribe the bejeezus out of P1 or else.

Actually, I've rethought my previous solution - If P3 offers P1 all 1000, P2 can just make the same proposal - P1 will vote down P3 to see him sink, then take the 1000 from P2's proposal. P3 is unable to survive this game, and P2 still hasn't helped himself. Good job breaking it, WarDaft

[WarDaft]

Yet it is not possible for both p1 and p2 to receive more than 500 gold each.

Hmm.... no matter what plan p2 chooses, p3 can always afford to pay one of them more than p2's plan would allocate. Aha, the problem is that they'll never finish deliberating if they all seal their envelopes at the same time.

Instead, let's make them seal them in order (2's, then 3's, etc) but give them an arbitrary amount of time to decide on each. That should prevent it from becoming degenerate. It at least ensure's p3's survival.

[Gwydion]

All right, now P2 writes (499 to P2, 501 to P1), and P3 pays the cheaper of the two for his vote - P2 gets half, P3 gets half, P1 is out of luck.

Now add in a fourth pirate - I'm not sure how this would work out except that it will clearly be in P4's favor. He only needs one other vote, which means that anyone P3 "ignores" can be bought cheaply - P3 would offer 334 to P1 and P2, keep 332 for himself, and then P4 would give P3 333 and keep 667. It doesn't matter what P2 writes, because P4 and P3 control the vote for themselves.

Is this result generalizable? What happens with n pirates?

[tomtom2357]

So, why can't P1 demand all of the coins in the 3-pirate problem? Also, to do an accurate analysis on this, you need utility values, so every coin is worth 1, and death is -x, where x is some positive integer, find x, and you find the optimal strategy.

[Gwydion]

We can speak of P1 making "demands", but in the end, P2 can always match P3's bid, so it's not a matter of making demands as much as P3/P2's willingness to play along. As discussed before, P3 can NEVER get P2's vote, and P1 will always vote for any strategy in which he gets strictly more from P3 than P2.

As to the utility values, I've always treated death as having a utility of negative infinity. As in, it doesn't matter how many coins you get, dying really really sucks (and you don't get to keep the coins). The general setup of preferences, as far as pirates go, looks like this: Coins have a positive utility of 1. Personally dying has a utility of negative infinity. Other pirates dying has a utility of 1/n where n is the number of pirates. This is based on the typical assumptions made in the problem statement: A pirate's first priority is always survival, regardless of coins received. Given that a pirate Pk survives, his second priority is to maximize the number of coins received. Lastly, given that the number of coins received is equal between two plans, Pk would always prefer more dead (non-Pk) pirates to fewer dead pirates. Since the pirates are well-ordered by some arbitrary rank (given), the numbers given should provide a unique utility value for every possible distinct outcome from Pk's perspective (meaning, if Pk gets x coins, Pk is indifferent to the distribution of the y-x other coins in the treasure chest provided the same number of corpses are generated).

[WarDaft]

Is this result generalizable? What happens with n pirates?

I had a lot of trouble building up very far until I just gave up and started working down assuming the first two controlled the vote.

If there are 100 pirates, pirate 99 assures that they receive gold by offering himself 9 gold, 87 other pirates 10 gold, and 11 pirates 11 gold. Pirate 100 can surely afford to buy 49 of these votes at a cost of 538 gold. The question is now was there anything pirate 98 could have done that would have prevented this exact scenario from working. The answer is actually yes, and we don't even need pirate 98's ideal case to prove it. Suppose pirate 98 decided to keep 100 gold for themselves, and give 60 other pirates 15 gold. The pirates that pirate 98 plans to give 15 gold to obviously cannot be bought by pirate 100 for 11 gold, which means that at least 11 pirates must be payed 16 gold to assure their votes, disproving that only the last two pirates have sway over the distribution of gold.

I am still not sure what the ideal strategy is however.

[TPressey]

Wardaft, you're almost right.

With 100 pirates, pirate 99 doesn't have to be the pirate receiving the lowest amount of gold in his scheme - pirate 100 needs to buy off 49 pirates, so 99 can receive the 49th lowest amount - basically he offers 48 pirates 0 coins, and ensures he is the lowest out of the remaining pirates.

In the 100 pirate case, this works out to pirate 99 offers himself 18 coins, 18 pirates get 19 coins, 32 pirates get 20 coins and 48 pirates get nothing. Pirate 100 will buy off 48 pirates for 1 coin and pirate 99 for 19 coins - he keeps 933 coins for himself.

As for pirate 98, he'll never be able to upset what's laid out above - it's pretty easy to check with the pigeon hole principal that there will always be at least 50 pirates that can be bought off for ~20 coins. (check the case where pirate 98 offers 50 pirates 20 coins each -- pirate 99 can buy off the 48 pirates who receive nothing for 19 coins and has 70 coins left over to buy off 2 other pirates). Pirate 98 would like 99 to offer him 0 coins so that pirate 100 offers him 1 - but he cannot force pirate 99 into this course of action.