Hacker News Reader

> Steven Landsburg has pointed out that the problem is a bit underdetermined, and the usual solution is far from unique. For example, "the first pirate gets all the coins and everyone else votes yes" is a subgame-perfect equilibrium which is just as good as the usual solution, because no pirate has an incentive to deviate unilaterally (one vote can't change the voting outcome). There are many other equilibria like that. The moral of the story is that games with more than two players seldom have unique solutions, unless your assumptions are very strong and explicit.

I don't follow. If pirate A assigns themself all the coins, the other pirates may as well vote against the plan - doing so risks nothing, and might result in them getting more than 0 coins if others happen to also vote against.

I don't follow either. In addition to what you say, the rules state that, all else being equal, pirates would prefer other pirates to die. Pirates would prefer A to die, so they would vote against this proposal.

Right, so you need a more restrictive equilibrium concept than subgame-perfect equilibrium. It's a good math exercise to try fleshing out exactly which concept is implied by your common sense reasoning (which I'm not arguing against!) Some folks have suggested trembling hand equilibria and other ideas, none of which are obvious from a naive reading of the problem.

Maybe it's more helpful to think about such problems in terms of "how would I write a program to solve all problems in this class?", rather than "how would I act using common sense in this particular problem?" That often makes things clearer.

> "...no pirate has an incentive to deviate unilaterally (one vote can't change the voting outcome)..."

I would strongly challenge that assumption as having any realism (even for perfectly rational agents and no communication): if an agent decided to vote, he could assume all other perfectly rational agents (another usual assumption) would also take the same decision (by symmetry), so he can safely vote yes. This symmetry could only be broken if the agents have access to randomness.

Right, so we need to figure out what kinds of reasoning by symmetry are allowed under perfect rationality (in all possible games, not just this one). For example, should a rational person cooperate in the Prisoner's Dilemma because the opponent will be forced to cooperate by symmetry? In that case, won't irrational people eat rational people for breakfast, thus devaluing the idea that rational behavior maximizes utility?

If you take the time to think it though, you might well reinvent superrationality, updateless decision theory and other fascinating things. In fact, you'll quickly get to questions that I have no idea how to solve!

Yes I don't think this assumption makes a lot of sense in general if you don't assume your perfectly rational players have access to randomness (I do think it's the best assumption if the players can't communicate or have any entropy).

In the case of Prisoner's Dilemma, if the cooperate/defect outcome had sufficiently large cooperation bonus for fixed other payoffs (large enough T>>R in wikipedia's notation), then with my assumptions it's clear that each prisoner should flip a coin to decide, and each one gets ~T/4 expected payoff.

But the most glaring problem is of course assuming every player is perfectly rational. Personally I'd only assume that if your players are all game theorists with enough of time and paper :) I probably wouldn't even assume myself as rational.

In conclusion, I believe equating maximin with optimal play/perfect rationality is misguided, but maximin is a good safe bet.

What do you mean, "in all possible games"? The assumptions that hold for this game don't hold for the Prisoner's Dilemma.

Like someone else said, you seem to be speaking in jargon. "Superrationality", "updateless decision theory", none of this matters in order to understand the Pirate Game. The rules of the game are very simple, maybe the pirates thing is throwing you off? That's just a theme for the puzzle (people aren't rational like this, and of course pirates aren't, and the whole situation is extremely artificial and unrealistic). The non-intuitive solution is derived from the rules as stated without any need for additional theory.

This is Hofstadter's SuperRationality. It's main contribution isnto highlight the arbitrary simplifying assumptions of traditional game theory

Ah thanks it's exactly what I was thinking. It clearly isn't a good model for games in real life, but yes it does show the assumptions of traditional game theory can be misleading. Optimal play can only be defined with relation to your knowledge of the precise inner workings of your opponents.

I still don't understand, you seem to be responding with jargon.

The point made was that your 'equilibrium' is not valid because a pirate voting that way decreases their expected return. I don't see how you need a different 'equilibrium concept' for your proposed solution, when the basic assumption of rationality excludes it.

Not trying to be mean, but your response seems obfuscatory.

If everyone votes "yes", one pirate deciding to vote "no" doesn't affect their expected return. Therefore everyone voting "yes" is a subgame-perfect equilibrium.

Ideas like Nash equilibria and subgame-perfect equilibria are the only known formalizations of rational behavior in multiplayer games. I'm not obfuscating, I just don't know any other kind of math that would work...

> If everyone votes "yes", one pirate deciding to vote "no" doesn't affect their expected return.

If everyone knows what everyone else is going to do, then neither option is better or worse, sure. But where did you get this perfect knowledge from? Certainly you couldn't deduce your situation.

And why is 'no' your default choice: this isn't a repeated game. You're trying to decide what to vote, you don't have a mind to change, at this stage. And neither does anyone else. Therefore, if everyone knows I can choose to vote either way, your situation is irrational.

You're objecting to a problem that isn't the one being considered.

It may well be that there is a compelling mathematical argument you're trying to evoke, but at the moment you're not actually putting it forward. You're name-dropping, but not explaining. Well, not in a way I can follow, anyway.

Man, I agree with you. This kind of reasoning is bizarre, how could you possibly know the strategies of the other players? And yet it's right. Read the first sentence of https://en.wikipedia.org/wiki/Nash_equilibrium, which is brilliant in its simplicity:

> In game theory, the Nash equilibrium is a solution concept of a non-cooperative game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

Many people have tried to define mathematically what "rational behavior" means when there are multiple players. Nash equilibrium is the one idea that stayed. It's the first chapter of every game theory textbook. Since the 1950s, literally all publications about non-cooperative games have been based on Nash equilibrium. To understand why, you'd have to look at the history of the field, or you could take my word for it. If it's any consolation, it was very unintuitive for me at first, too.

Oh don't get me wrong, my objection is not because I don't understand Nash Equilibria (my PhD was in evolutionary dynamics, so it's been a while, and I was never a game theoretician, but I'm not totally ignorant of the field). My problem is that the mathematical tools you are name checking don't apply in this case. Even your quote itself says 'changing ... strategy', and goes on:

"If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged..."

which is not the situation in this case.

Strategies for infinite games are not necessarily optimal if the game is finite, and vice versa.

I'm sorry, now I don't follow. If not subgame-perfect equilibrium, what do you think is the right solution concept for the pirate game? Maybe it doesn't have a name, but can you describe it (at least informally)?

Can you explain a little more how this subgame-perfect equilibrium should be reached? From the game's description it appears that, all other things equal, I as a pirate reject a proposed coin distribution if I could kill the proposer. Thus, if offered 0 coins, I would always choose to reject that plan.

Well, one pirate changing their vote to "no" wouldn't actually kill anyone. So it sounds like you want a utility function over outcomes (prefer outcomes where someone is killed) and another, separate utility function over actions (prefer voting to kill someone even if that won't actually kill them).

That's a pretty unusual setup, because game theory usually just gives you a utility function over outcomes and lets you derive strategic behavior from that, without fiddling with individual actions. Though I guess most people solving the problem have tried to merge the two utility functions somehow? That's probably the root of the disagreement in this thread...

You keep saying "change their vote to no". Perhaps it would be educational why you think they should default to "yes" in the first place when offered 0 coins. It really doesn't seem that the problem you see necessarily arises from this specific set of rules for this game. Offered 0 --> vote no; no would at worst be equal and at best be better than yes.

The point is that everyone voting yes is a possible equilibrium solution (along with the "normal" solution), so a priori there's no rule that tells you which one is the equilibrium the pirates would reach.

No, the point being made is there is no 'equilibrium' because the game is not repeated.

Equilibrium meaning 'if everyone votes this way, there is no benefit for any individual to vote differently' - that doesn't apply when the pirates are trying to determine what to vote for the one and only time they'll ever vote on this question, not knowing what anyone else will be voting.

The idea of Nash equilibrium isn't just for repeated games, in fact it was invented for one-shot games. (Now I understand why you keep mentioning "infinite games"...)

It isn't, but it requires knowledge of the other strategies: there is at least a 'starting' strategy. That isn't the case here.

Which is why you've been unable to express your disagreement with the puzzle without resorting to language of 'changing' votes, or assuming that you know what other people are going to vote. None of which are reasonable assumptions here.

Ok, I guess I need to understand how this is an equilibrium and read more carefully what the rules of this game are exactly. Because from reading it once I understood that pirates are supposed to decide on a proposed distribution. And according to my understanding, a pirate would never vote YES if offered 0. Therefore, I seem to not see how the situation we are discussing is a viable equilibrium. (I do see how once in this "state" unilateral change of votes means no advantage to any one player, but is this really interesting for this game, i.e. is it a viable outcome of it despite being stable once reached? Maybe I have it all wrong though.)

> I do see how once in this "state" unilateral change of votes means no advantage to any one player

Right, so it meets the definition of an equilibrium.

> but is this really interesting for this game, i.e. is it a viable outcome of it despite being stable once reached?

In "reality" no. But the Nash Equilibrium formalism gives us no way of determining which of the two possible equilibria (this one and the usual solution) will happen in practice. So you need some more powerful idea to solve that (see references to "superrationality" and "trembling hand" elsewhere in this thread), and none of those theories is mathematically complete.

Yep okay. So is what this then shows, really, that a Nash equilibrium is not so meaningful for this game?

It's meaningful, but it's insufficient to completely solve it.

> And according to my understanding, a pirate would never vote YES if offered 0.

A pirate will vote YES if offered 0 when the alternative is getting killed in one of the following turns. Pirates always prefer to live first, and only then they prefer to maximize their money.

what "following turns"?

edit: to clarify, the only pirate that would have to consider being killed is the one making the offer. thus yes, offering yourself 0 is possible and in fact seems to be a requirement for the (one of the) stable solutions. But if I'm not most senior, I would never accept 0.

The game has turns in theory: each split proposal is one turn. The most senior pirate proposes a split; if it's not accepted, he gets killed and the next pirate proposes a split. That's the next "turn", assuming the first split gets rejected.

Theoretically, a pirate could accept a seemingly inconvenient proposal if he evaluates that rejecting it would result in himself getting killed further down the line, when it's his own turn to propose a split.

You're right that this never happens in the 5-pirate game as stated (I'm not sure about the general N-pirate, C-coins game). The pirates who are offered 0 coins reject the split, but they don't get to alter the result anyway.

The solution is contained in the post. I can't find a problem with it. It was you who were suggesting this is a naive analysis.

Equilibria just seem to me to be the wrong tool for the job, you have to (as you have) invent a related infinite game with additional axioms and expectations before that kind of analysis kicks in.

Check your responses. If you can't describe what you're trying to say without mentioning anyone 'changing' their strategy, or assuming that a strategy is default, then you've got the wrong framework, I'd suggest (modulo my admitted lack of specific expertise).

This clip [1], from the UK game show "Golden Balls", is a very entertaining example of a two-player zero-sum game

EDIT: As explained in the replies, this is not actually a zero-sum game.

[1] https://www.youtube.com/watch?v=S0qjK3TWZE8

That's not a zero-sum game, though. The total money awarded to both players isn't the same in all outcomes. That's the whole reason why the game isn't purely adversarial and it makes sense to negotiate.

I remember seeing this clip in 2012, and back then I proposed a solution based on correlated equilibria which still seems pretty good to me:

"We have two minutes to talk, right? I'm going to ask you to flip a coin (visibly to both of us) at the last possible moment, the exact second where we must cease talking. If the coin comes up heads, I promise I'll cooperate, you can just go ahead and claim the whole prize. If the coin comes up tails, I promise I'll defect. Please cooperate in this case, because you have nothing to gain by defecting, and anyway the arrangement is fair, isn't it?"

The comments mention that the rules were changed to disallow out-of-band bargaining after this event, which is important because this is one of the core solutions to the Prisoner's Dilemma (which is what they're playing, and is not a zero-sum game). The solution in general is contract law.

The verbal agreement "If you do this and I do that then I will split the money 50/50 with you after the show" is a verbal contract which (due to the cameras recording the event) is nevertheless indisputable. You are giving them a task to accomplish in exchange for a promised financial reward. They have all rights to sue you in court if they did what you asked and you didn't pay them for it.

What's really interesting is that he promises to split 50/50. In theory a rational actor who could commit to these things absolutely would say, "Look, I am pre-committing to steal, and I will give you $100 after the game if you choose split." Then it is still rational for the other guy to choose "split" (getting $100) rather than "steal" (getting 0). However most people, in study after study, will be insulted by the disparity of only getting 1% of the winning, and the insult is magnified by the camera: it is public shame. So in some sense being insulted by unfairness introduces out-of-band costs that also tend to pull you to splitting the money, and splitting it more fairly.

Basically there are qualitative reputation costs at play, which is why it's not really a zero sum.

An anonymous, blind experiment would be more interesting, but less entertaining.

There's decision-theoretic reasons to be the sort of person who refuses unfair bargains that make you slightly better off. Specifically, people will give you much fairer bargains, because otherwise you might refuse them.

By the way, in some cultures the opposite happened (they viewed being given large sums as an obligation they could never repay and were displeased with them).

I think you have not read the rules carefully enough to appreciate the challenge of this game,

> Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.

If a pirate found themself in a situation where they thought their vote wouldn't change the outcome -- i.e. all other results would otherwise be equal -- they would vote to murder the proposer. In the situation you describe, every pirate would find themselves in that situation, and would thus vote for blood.

This is fascinating. I'm pretty sure the wikipedia page implicitly assumes that pirates are superrational (https://en.wikipedia.org/wiki/Superrationality).

A group of superrational players may choose an outcome which is not even a NE! For example, two superrational players playing the prisoner's dilemma game will choose to cooperate.

Conversely, Nash equilibria are no longer "stable" in the original sense that there is no incentive for any player to unilaterally deviate. The concept of "unilaterally deviating" doesn't even make sense, because a group of superrational players will all choose the same strategy. The superrationality allows them to cooperatively deviate.

To demonstrate, I consider the smallest case for which your equilibrium strategy differs from the wiki pages' strategy, that is n=3. Suppose there are 3 pirates, A, B and C. Suppose the first pirate proposes that he gets all the coins. Then the state where everyone votes yes is a Nash equilibrium because no one has an incentive to unilaterally. However I claim that a group of supperrational players will vote to kill A.

Here is the proof of my claim (caveat: I don't think this is actually a valid analysis - see next paragraph. however it's the same level of rigor as the wiki page and demonstrates how B and C can cooperate to kill A, "escaping" the NE of both voting Y). C will vote No because accepting the proposal is the worst possible outcome for him (he gets 0 gold and no one dies; note that it is not possible for C to die), so strategies where he votes No in this round dominate strategies where he votes Yes in this round. B knows that C is thinking this. Hence he will vote No.

Explanation of caveat: actually, the nonstrict dominance proof in the above paragraph suggests that C does not know how B will vote and the dominance is nonstrict because of this unknown. However, since B and C are superrational, there is no such thing as not knowing how someone would vote; C knows that B will vote No, so the dominance is strict. However this argument seems circular (even though, because of superrationality, I think it really isn't).

Unrelated point: If we ammend the rules of the pirate game to include another tiebreaker with lowest priority: that all pirates prefer to vote "no", then your situation is no longer even a Nash equilibrium (much less a subgame-perfect NE). Then how many NEs are there in the ammended game?

> In the end there's no possible setup that everyone will stick with.

Wouldn't Alice, Bob and Carol realize that then and agree to divide the cake evenly since it's the only solution that is fair to everybody?

That would be the Nash equilibrium across splitting multiple cakes over and over again.

For a single cake, offering a fair split is just as hard to predict success as any other split. It also assumes there are no other signals, which is why it's not very insightful to begin with.

>Another problem which puzzles me even more is dividing a cake among three people by majority vote.

Is there a name for this problem? I can only find the fair cake cutting problem, which has been solved for 3 people.

https://www.math.hmc.edu/~su/fairdivision/theory.html

Or more specifically, https://en.wikipedia.org/wiki/Envy-free_cake-cutting

On a tangential note, something that's always bothered me about write-ups of "envy-free" division is that they assume a couple of things I don't think are true:

- That someone cutting a cake always executes exactly the cut they planned.

- That once the cake has been divided, no one will experience envy because their piece is worth, to them, at least their "fair share" of the total.

Take the classic example of envy-free division of one cake among two people. The solution is simple enough that most people understand it instantly: person A divides the cake into two portions however they please, and person B then selects one of those portions, A receiving the other. Everyone will agree that this is intuitively fair. But it's certainly not fair for either of the two reasons I dispute -- A might still envy the portion of the cake that went to B, imagining a different world where the entire cake was theirs... or A might slip up with the knife and create one portion which is obviously better than the other portion, which B then chooses.

Rather, I think the benefits of envy-free division come from two other points:

- The parties involved agree beforehand that the process is fair. This requires them to be able to understand it, which is easy for the two-person division and quite difficult for more than two.

- Instead of assuming that division goes off without a hitch, we can observe that if you receive a portion you're unhappy with, it's because you messed up. The blame falls on you rather than someone else.

I think he's describing a different problem, since he mentions majority voting. If I was splitting a cake with 2 other people (A and B), A suggested fair division into thirds, and B suggested half for me and half for B, B's suggestion would clearly win the vote.

No, there's no name AFAIK. I learned it from Robin Hanson (well-known blogger and economics professor at GMU). It's different from envy-free cake cutting, which doesn't involve voting.

> 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.

There's a stable solution if you can offer a credible pre-commitment. Instead of a tentative 50/50 split between Alice and Bob, they pre-commit to either voting for a 50/50 split or voting for giving Carol the entire cake.

Yeah, if you reformulate the game to allow precommitment, it will have many Nash equilibria. But I think of it as a last resort, because it gives you too many solutions with no way to choose between them.

I heard research into the 3 person cake division is held back by years due to all the researchers getting diabetes and dying young.

True story.