8 ms·

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 t

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 you make very strong and explicit assumptions. Another problem which puzzles me even more is dividing a cake among three people by majority vote. Let's say Alice and Bob make an agreement where each of them gets half of the cake and Carol is left out. But that's unstable, because Carol can offer Bob a different agreement where Bob gets 60%, Carol gets 40%, and Alice is left out. Since Bob gets 10% more than before, he has an incentive to switch. But that's unstable as well, because now Alice can make a similar offer to Carol, etc. In the end there's no possible setup that everyone will stick with. As far as I know, this problem is still mostly open (though a few advances have been made). To sum up, the idea of "perfectly rational" decision-making is surprisingly difficult to nail down. It's been definitively solved only for the case of two-player zero-sum games. When the game is not zero-sum, you get complications like bargaining and equilibrium selection, and when you have more than two players, you get an explosion of complexity without any clear-cut answers.

J-dawg 11y ago
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 https://www.youtube.com/watch?v=S0qjK3TWZE8
- cousin_it 11y ago
  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?"
- drostie 11y ago
  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.
  - bduerst 11y ago
    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.
  - ThrustVectoring 11y ago
    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.
  - StavrosK 11y ago
    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).
HerpDerpLerp 11y ago
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.
lmm 11y ago
> 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.
- the_af 11y ago
  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.
- cousin_it 11y ago
  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.
  - darkmighty 11y ago
    > "...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.
deleted 11y ago
[deleted]
- the_af 11y ago
  You have to remember this is merely a logic puzzle devised to have a non-intuitive solution. The pirates thing is merely a pasted-on theme. If it helps, consider these are robots who must follow a set of predetermined rules.
  - clort 11y ago
    Arrr matey, it certainly would help because a) not once have I seen an 'Arrr matey' in the comments b) the article didn't mention walking the plank at all c) I don't think that we can count on lower level pirates to be competent at complex logic
h2077545 11y ago
> 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.
- deleted 11y ago
  [deleted]
jessedhillon 11y ago
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.
gregschlom 11y ago
> 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?
- bduerst 11y ago
  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.
Kapow 11y ago
>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.
- thaumasiotes 11y ago
  https://www.math.hmc.edu/~su/fairdivision/theory.html https://www.math.hmc.edu/~su/fairdivision/theory.html Or more specifically, https://en.wikipedia.org/wiki/Envy-free_cake-cutting 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.
  - Kapow 11y ago
    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.
ThrustVectoring 11y ago
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.
- cousin_it 11y ago
  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.
zodiac 11y ago
This is fascinating. I'm pretty sure the wikipedia page implicitly assumes that pirates are superrational (https://en.wikipedia.org/wiki/Superrationality 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?

J-dawg 11y ago

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 https://www.youtube.com/watch?v=S0qjK3TWZE8

cousin_it 11y ago
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?"
drostie 11y ago
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.
- bduerst 11y ago
  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.
- ThrustVectoring 11y ago
  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.
- StavrosK 11y ago
  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).

HerpDerpLerp 11y ago

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.

lmm 11y ago

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

the_af 11y ago
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.
cousin_it 11y ago
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.
- darkmighty 11y ago
  > "...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.

deleted 11y ago

[deleted]

the_af 11y ago
You have to remember this is merely a logic puzzle devised to have a non-intuitive solution. The pirates thing is merely a pasted-on theme. If it helps, consider these are robots who must follow a set of predetermined rules.
- clort 11y ago
  Arrr matey, it certainly would help because a) not once have I seen an 'Arrr matey' in the comments b) the article didn't mention walking the plank at all c) I don't think that we can count on lower level pirates to be competent at complex logic

h2077545 11y ago

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

deleted 11y ago
[deleted]

jessedhillon 11y ago

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.

gregschlom 11y ago

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

bduerst 11y ago
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.

Kapow 11y ago

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

thaumasiotes 11y ago
https://www.math.hmc.edu/~su/fairdivision/theory.html https://www.math.hmc.edu/~su/fairdivision/theory.html Or more specifically, https://en.wikipedia.org/wiki/Envy-free_cake-cutting 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.
- Kapow 11y ago
  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.

ThrustVectoring 11y ago

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.

cousin_it 11y ago
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.

zodiac 11y ago

This is fascinating. I'm pretty sure the wikipedia page implicitly assumes that pirates are superrational (https://en.wikipedia.org/wiki/Superrationality 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?