15 ms·
The pirate game
- ryandvm 11y agoThis puzzle should be called "The VC game". Real pirates were actually far more egalitarian. http://www.newyorker.com/magazine/2007/07/09/the-pirates-code http://www.newyorker.com/magazine/2007/07/09/the-pirates-cod...
- kbutler 11y agoI initially thought the parent was being unfair to the VCs, but then considered policies that exclude other investors, like preferred shares and buyouts that fall just short of any payout to common shareholders, and so forth, and realized it's pretty accurate.
- jerf 11y agoHumans in general actively punish perceived unfairness. Put simply, that's because real life is iterated and this puzzle is explicitly a one-off game. Give those real pirates a guaranteed one-off game and they would be far less egalitarian.
- Fuzzwah 11y agoJust on the off chance that anyone else reading this new yorker article clicked on the link to the Buccaneers.pdf file and also found that it 404'd: Archive.org have a mirror: http://web.archive.org/web/20081218012123/http://history.byu.edu/fac/miller/251/Buccaneers.pdf http://web.archive.org/web/20081218012123/http://history.byu...
- oilywater 11y agoI remember reading about this game on a private music torrent tracker what.cd and was working on the solution for a couple of hours. I believe there was a whole thread dedicated to these kinds of problems. Quite an entertaining problem, skip the result and try it out yourself, the sense of accomplishment is fulfilling, especially if your mood is shaky.
- afro88 11y agoThere's a Korean gameshow called "The Genius" which plays on these kinds of games. It's more socially oriented but the contestants and the "narrator" go through the mathematics and strategies a bit. Highly recommended.
- aninhumer 11y agoI second that recommendation. The usual format is that they play a game each episode, and the winner and another player of their choice are guaranteed to go to the next round. The loser of the main game then plays a one-on-one game with another player of their choice, and the loser of that game is eliminated. This creates an interesting metagame surrounding the main games. One thing that makes it work particularly well is that the participants all seem to be relatively pleasant people. There were alliances and sudden-but-inevitable betrayal, but no one was ever unpleasant about it. I'm not sure if it's a cultural thing, or that they're all notionally "geniuses" (talented in some field) rather than random people or celebrities, but that atmosphere really made a good premise into an excellent show.
- vacri 11y agoIf the pirates were that strictly rational and interested in their own survival, they wouldn't be pirates. They'd have a nice, safe job, free from threat of death or injury.
- jere 11y agoI don't think many jobs during the Golden Age of Piracy would be considered safe and free from threat of death or injury.
- mikeash 11y agoI don't normally go for pop culture quotes here, but this one seems rather appropriate: Oh, get a job? Just get a job? Why don't I strap on my job helmet and squeeze down into a job cannon and fire off into job land, where jobs grow on little jobbies?!
- vacri 11y agoYeah, and while you're doing that, why not have a chat to the pirates so bloodthirsty to kill each other, but with such a code of honour that they're satisfied with the booty split which has 98% of the money going to only 20% of the crew. Why are you so disturbed about the ridiculousness of my comment, yet quite happy to take the ridiculousness of the situation's premise?
- mfoy_ 11y agoIf you were ever curious what the phrase "couldn't see the forest for the trees" meant... here's an example.
- andyraskin 11y agoI was asked to solve this puzzle once during a project management interview. The solution here says "work backwards," but I found that "work recursively" was a more helpful (and instructive) way to think about it.
- kbutler 11y agoApplying the maximization of benefit logic, "work backwards" is very meaningful to a very large population of readers, "work recursively" is somewhat more meaningful to a very small population.
- seivan 11y agoThey could have explained it differently instead of going backwards. I tried to explain the backwards part to my mum and she didn't quite grok it. Then I explained it from perspective of A, B, C and so on. When A is in charge this affects.... When B is in charge this affects... Maybe that's recursively? solve(pirates) {..... solve(mutatedPirates) }
- tamana 11y agoThe are very similar. Recursion is expressing a problem in terms of a smaller case of the same problem. Working backwards/induction is building up from a base case.
- andyraskin 11y agoRecursion is exactly the same (as induction) because it also requires specifying what to do in a base case. I guess I think recursion is a more instructive term than "working backwards" because it speaks to a rigorous programmatic approach.
- hisham_hm 11y agoWikipedia is not written for programmers only.
- coldcode 11y ago
- archibaldJ 11y agoReminded me of the game theory course by Stanford on Coursera. It was in the exercise on [backward induction](https://en.wikipedia.org/wiki/Backward_induction https://en.wikipedia.org/wiki/Backward_induction), if I remember correctly.
- drelihan 11y agoI was asked this question in an interview 10+ years ago. I thought it was a really good question to promote logical discussions. Lots of branches and extensions you can add to see how people think. Really fun.
- cousin_it 11y agoSteven 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 agoThis 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 agoThat'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?"
- personjerry 11y agoIsn't this our current economic status? The rich (A) become and stay rich by scoring votes with key voters (C and E). These key voters are kept in line by intimidation, because they know they could end up worse (like B and D).
- h2077545 11y agoIn addition B, C, D and E are usually the same people divided by A.
- stygiansonic 11y agoThis is an interesting way to think about it, i.e. getting thrown overboard == ruling class overthrown in revolution.
- talmand 11y agoLet's see if my logic works. It seems some motivations and negotiations are left out of the proposed solution. If I were C I would have voted no on A's proposal and try to make a deal with D and E. The idea is that knowing if A were thrown overboard then B might be more apt to provide a more beneficial coin sharing program in an effort to save his life. After all, he just watched the previous guy get tossed overboard and die. The most I could lose would be 1 coin if B decided to try A's method on D and E and they went along with it. The key is that I would have already negotiated a deal with D and E, if A or B doesn't share the wealth fairly then we vote to toss them. Once I'm in charge, I'll share the coins equally as possible.
- sokoloff 11y agoThat fails because one of the explicit stipulations in the problem is: "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." I read that as "an actual proposal, by the leader" not as a "theoretical future proposal, iff that negotiator becomes the leader" and I believe that's the intended reading. Thus, D and E cannot trust that you'll hold your word to give them 33 coins each provided you get to be in charge.
- talmand 11y agoIf that were true then the whole thing falls apart as soon as the first proposal is made. They all have to trust that A will follow through with the proposal, of which they apparently do not. But yes, I glossed over that part apparently.
- the_af 11y agoThey do trust A (the first proposal). If all of them accept A's proposal, they are all committed to honoring it. What they cannot trust is any hypothetical proposals made by a pirate whose turn is not to make the current proposal. "I have the turn and I propose we split this way": trusted. "I don't have the turn yet, but when it's my turn, I promise I'll propose this / kill him / won't kill you": not trusted.
- dsego 11y agoIf you like this type of puzzle, I can recommend the book: “How Would You Move Mount Fuji?: Microsoft's Cult of the Puzzle”.
- mcv 11y agoIt's a nice demonstration of how the lack of trust ultimate screws everybody except the leader.
- pierrebai 11y agoA tantalizing idea I've been trying to spell out properly that goes against the usual reasoning behind similar problem is that of putting into question the correctness of causality in hypotheticals. Each such problem I've read about assumes that we can assume causality while reasoning about hypothetical, but strangely, if we let go of that assumptions, then we can arrive at different answers which hinge on otherwise surprising behaviour. I relate this idea to the fact that in logical reasoning, all true statements are, once proved, held to be simultaneously true. That is, given if A then B, with A being true, we don't hold B to be true 'after' A, but to have been always true, given A. In the pirate problem, limiting ourselves to three pirates to shorten my explanation, we end up with the split being: 99 to C, 0 to D, 1 to E. This is because we assume that if only D and E were left, D would keep 100 to himself. Now given that distribution (99,0,1), D should now change his hypothetical proposal to (0,98,2). If we assume that C is not a 'non-causality' believer, but both D and E to be, then E would vote no to (99,0,1) and D would do the (0,98,2) split. You may argue that D could then do a (0,100,0) split, but that's not how a non-causality believer MUST act, because he knows that to get to that point, he must know thet E can logically know that he will do this split. This can be justified by arguing that when a pirates survives, he will enter such gold-splitting game later on. But my argument is subtler than this and doesn't require it. It basically become this: all such pirates, posited to be perfectly logical, are interchangeable. Thus they must all reason in the same fashion. Thus, my argument is that true pure logical minds see that the true way to maximize their gold profit is to hold a world view that maximize their profit, even if causality is discarded. Thus both D and E know that tehy can maximize their profit by discarding their belief in causality. That is how D ends up proposing (0,98,2) and E accepts it. Of course, I ended up there by assuming C was not a believer, but given my argument, C must also be ready to throw causality out of the window, otherwise he will end up dead. I believe my argument ends up splitting (49,51,0), but I'm not sure. Once causality is throw out, it's hard to tell, but intuitively, with three pirates, those voting must be given almost equal gold and the remaining pirates must not have a majority.
- cousin_it 11y agoThat's not completely right, but close enough to be dangerous. Indeed, quite a few researchers around LessWrong, MIRI, FHI etc. agree that the right way to formalize decision-making should use the timeless view that you advocate. Decisions and precommitments are provable consequences of an agent's source code, agents with the same source code can use that fact to coordinate, and so on. I've done a lot of work on this, so feel free to ask :-)
- Pxtl 11y agoShouldn't it be E: 2 in the solution? If pirates, all things being equal, prefer violence to peace (which is implied) then E getting 1 from A is less preferable than killing A and B and getting 1 from C. Or is it that E knows that B will be offering next, and B will offer him 0, so it makes sense for him to accept A's offer of 1?
- vog 11y ago> Or is it that E knows that B will be offering next, and B will offer him 0, so it makes sense for him to accept A's offer of 1? Yes. That's why it is sufficient to offer E: 1.
- mrfusion 11y agoThis kind of reminds me of the surprise execution paradox. https://en.m.wikipedia.org/wiki/Unexpected_hanging_paradox https://en.m.wikipedia.org/wiki/Unexpected_hanging_paradox
- asift 11y agoI love game theory, but I hate that the focus outside of academia is almost always on simplistic single period games. These games can result in some interesting conclusions and teach some valuable concepts, but they are terrible at representing how people behave in the real world. Anyone interested in a more complex and realistic examination of the economics of pirating should consider Peter Leeson's book, The Invisible Hook: The Hidden Economics of Pirates. I would also recommend Leeson's Anarchy Unbound: Why Self-Governance Works Better Than You Think for some interesting applications of game theory in more realistic historical contexts.
- pavel_lishin 11y agoIt's not meant to teach you about people or pirates; it's a simplified tool used to teach concepts and methods of thinking. Much like a two-body system is useful for explaining gravity, even though there's virtually no place in the real world where that particular example would be useful.
- asift 11y agoI get that, which is why I said it's useful for teaching, but I disagree with your notion that game theory is incapable of being anything other than an educational tool. When models utilize more realistic assumptions, they can be incredibly powerful tools for understanding past behavior and predicting future behavior. Historical evaluation is particularly powerful when game theory is utilized with the analytical narrative form of analysis.
- smaddox 11y agoNot sure I agree with your last statement. Our solar system can be modelled quite accurately and usefully as several overlapping 2-body systems. The interplanetary interactions are very small perturbations.
- efnx 11y agoThese outcomes assume you can live rich (having ~98 coins) in the same space as poor pirates without them stabbing you and taking your coins! Real pirates would distribute more evenly for fear of death after distribution.
- aakilfernandes 11y agoI really hate questions like this. Since they mistake rationality for computer-like adherence to a set of rules. —————————————————————— Imagine a 100 rounds of ultimatum games. In each round, Alice proposes a split of $1 and Bob can either accept or reject. If Bob rejects, the $1 is burned in a fire. How much money will each end up with? Lets work backwards, as we do in the pirate game. In ROUND100, Alice knows Bob will take whatever non-zero offer she makes. She can offer him 1 cent and Bob will agree. In ROUND99, Alice knows that Bob can will accept whatever non-zero offer she makes in ROUND100, so she can make whatever non-zero offer she wants this round without fear of repercussion. She offers him 1 cent and knows he will agree. Continuing to work backwards, we find that in all 100 rounds, Alice takes 99 cents and offers Bob 1 cent. Alice ends up with $99 and Bob ends up with $1. —————————————————————— This is obviously (and experimentally proven) not what would happen in real life. In experimental outcomes, Bob rejects offers that are too low to broadcast that he is “irrational”. As a result, Bob is able to negotiate a much higher outcome (around 40%). So who is more rational? The "rational" Bob who gets $1, or the “irrational” Bob who gets $40?
- robzyb 11y agoI really love questions like this. The insight obtained from from comparing the computer-like rationality to what would happen in the real world is truly fascinating to me. Also, your example of Bob negotiating fits in very well with the theoretical computer-like rationality. Alice's offer of 1c is equivalent to an offer of 0c nominal in the hypothetical case. The real-life 40% is more a commentary of utility of money as opposed to decision making. I think that you're conflating concepts.
- aakilfernandes 11y agoI should rephrase. I hate it from an interview-question point of view. I like it from an insight point of view.
- resu_nimda 11y agoWhat are some such insights to be gained from the pirate example? What did we learn? How a set of "rational" computers might play out this scenario? How do we apply that to our decision making? These questions might seem obtuse or questioning the value of game theory, but I'm just having a hard time understanding what to take from it. The real-life 40% is more a commentary of utility of money as opposed to decision making. Only real-life humans make decisions though. If there is no implied utility of money then Bob might as well reject all offers. And it does seem that the only important question is "what would real humans do?" We can set up a simulation that strictly adheres to a simple set of rules and watch how it plays out, but what is that telling us?
- quickpost 11y agoThis game reminds me of some employee stock option negotiations I've been on the lessor end of...
- logfromblammo 11y agoNow that you have that down, allow the pirates to secretly bribe each other out of their own savings before the vote. If multiple votes occur, previous bribes are added to a pirate's savings. If a pirate is thrown overboard, his remaining personal savings are looted and added to the pool of coins to be divided. The personal savings of each pirate are secret from all the other pirates, but all pirates always have more in savings than the next pirate in order of decreasing seniority. According to the pirate's code, a bribe is a binding contract, but only to the extent that breaching the terms of the contract results in returning the amount of the bribe after the breach occurs. Otherwise, the bribed pirate is thrown overboard. A pirate may therefore spend the bribe money before reneging, if reneging will still yield enough money to pay back the bribe afterward. Pirate P[x] has savings s[x], and s[x] > s[x+1]. The degenerate case where n=1 is easy to deduce. P[1] proposes {pool}, votes yes, and wins. The case where n=2 is also easy. P[1] proposes {pool, 0}, votes yes, and wins. When n=3, it gets more complicated. P[1] needs one more vote to win. If P[2] is able to propose a split, he will be proposing {0, pool + s[1], 0}. So the cost of P[2]'s vote is at least pool + s[1] + 1, which is normally impossible to achieve for P[1]. But since P[2] does not know how much s[1] is, other than that it is more than s[2], P[1] might be able to risk it. But since P[1] doesn't know s[2], bluffing a lower amount for s[1] is risky, as if the bluff amount is lower than s[2] + 1, then P[2] will immediately know to vote no. The cost of P[3]'s vote is at least 1. P[1] and P[2] will therefore be bidding competitively for P[3]'s vote. P[1] has the choice of offering value to P[3] publicly in the proposal, or secretly as a bribe. Either way, P[1] is likely to propose 0 for P[2]. So if P[1] proposes { pool, 0, 0 }, and bribes P[3] to vote yes with s[1], P[2] might try bribing P[3] with any amount from 1 to s[2] to vote no, with no effect. The net effect is { +pool -s[1], 0, +s[1] }. Remember also that any bribe P[1] pays to P[2] could be added to a bribe from P[2] to P[3]. If P[1] bribes 1 to P[2] to vote yes, and s[1]-1 to P[3] to vote yes, and P[2] bribes s[2]+1 to P[3] to vote no, then if P[2] and P[3] both vote no, P[1] is thrown overboard for losing the vote, and P[2] is thrown overboard for reneging on a bribe and not having the coin to pay it back, so P[3] gets everything. If P[3] suspects that P[1] may have bribed P[2] to vote yes, and knows that P[2] bribed him to vote no--which would be useless unless P[2] himself intended to vote no--then P[3] may vote no on the possibility of getting pool + s[1] + s[2], which would otherwise be impossible for him. So knowing this, P[1] may be confident that any bribe to P[2] to vote yes would not reasonably be re-bribed to P[3] to vote no. So P[1] could bribe 1 to P[2] to vote yes, tell P[3] that he had bribed P[2], tell P[2] that he had told P[3], and then propose {pool - 1, 0, 1}. It would be useless for P[2] to bribe P[3] unless he intended to reneg, he can't add P[1]'s bribe to his own, and he knows that s[1] - 1 >= s[2]. With the 1 from the pool, he could not match such a theoretical bribe anyway. So the net effect is now { +pool -2, 1, 1 }. I'm not exactly sure if that is a stable solution or not. I think maybe that P[3] might be able to get more by bribing P[1] to vote no, or P[2] to vote yes.
- deleted 11y ago[deleted]
- ALee 11y agoWell now I have to choose a new interview question.
- blobbers 11y agoThe results of the pirate game seem a lot like the stock allocation at my company. A billion dollar acquisition and Pirate A figuring out how to distribute the coins... guess where they end up! Note to self: don't get thrown overboard.
- pratyushag 11y agoI think this is a great game and a portrayal of reality where a small number of people get most of the wealth, a 50% number are middle class with enough to be just okay (or at 1) and with a still a very large number who can barely have a comfortable life (say $4k/month household income).