5 ms·
The Prisoner's Dilemma: a summary, and new advances
- losethos 14y agoI'm bored. I could sit in a cell and talk to God. What's yer point. God says... C:\Text\Words\AUGUST.TXT wledge admit of any thing transitory. "What will ye say then, O ye gainsayers? Are these things false?" "No," they say; "What then? Is it false, that every nature already formed, or matter capable of form, is not, but from Him Who is supremely good, because He is supremely?" "Neither do we deny this," say they. "What then? do you deny this, that there is a certain sublime creature, with so chaste a love cleaving unto the true and truly eternal God, that although not coeternal with Him, yet is it God says... Afterwards downfall lacking finding inserted damages imagination structure rocket_science Increase eternally dragging scanning vision personated so_he_sess checked Tanzania provest protest nine-and-twentieth thirtieth toilsome please Do forms inappropriately brides Know Babylonian blotted calling honest GIVE enforced do_I_have_to burnest replied 03/19/01 deliberates sweetnesses shower poems evidence Will high_five hungering flee called refuge glories careth forests considers assurance affairs space slumin whereat teacheth correction favourites etext99 check Surely allow crazy Predicament hot perused You_fix_it contritions when- divine well-spring Whatever comment Spirit modestly USA preserved companion g withering encumbrances enduring chastenest reasonable 100 staggered fellows heresy carelessly thrustedst Earth help well-pleased stories denied incorruption you_owe_me cloyed which company unrulily cheap majesty attained country Israel heeded marrying hindereth fishes stones custom perfected committed thanksgivings raise devilish filename came unreasoning strings hang_in_there login a_flag_on_that_play incredibly happier burial sweetness heat last ascended contemptible loose refreshment ---- Through prayer, I have killed over 100 cops over the years. Is that what you're getting at?
- scotty79 14y agoI played against extotionist strategy and I guess I got lucky because I'm leading (my score - 1) : (his score - 1) = 2:1 and won't change into 1:3 as advertised because from this step I will always defect. 25. You defected (1 points) and I defected (1 points) 24. You defected (1 points) and I defected (1 points) 23. You defected (1 points) and I defected (1 points) 22. You defected (1 points) and I defected (1 points) 21. You defected (1 points) and I defected (1 points) 20. You defected (1 points) and I defected (1 points) 19. You defected (1 points) and I defected (1 points) 18. You defected (1 points) and I defected (1 points) 17. You defected (1 points) and I defected (1 points) 16. You defected (1 points) and I defected (1 points) 15. You defected (1 points) and I defected (1 points) 14. You defected (1 points) and I defected (1 points) 13. You defected (1 points) and I defected (1 points) 12. You defected (1 points) and I defected (1 points) 11. You cooperated (0 points) and I defected (5 points) 10. You defected (1 points) and I defected (1 points) 9. You defected (5 points) and I cooperated (0 points) 8. You cooperated (3 points) and I cooperated (3 points) 7. You defected (5 points) and I cooperated (0 points) 6. You cooperated (0 points) and I defected (5 points) 5. You defected (1 points) and I defected (1 points) 4. You defected (5 points) and I cooperated (0 points) 3. You cooperated (3 points) and I cooperated (3 points) 2. You defected (5 points) and I cooperated (0 points) 1. You cooperated (3 points) and I cooperated (3 points)
- nopassrecover 14y agoI found I could get better than 2:1 against extortionist fairly easily by mixing up my strategy as well.
- gjm11 14y ago> won't change into 1:3 as advertised because from this step I will always defect. From the description of the extortionist strategy in the demo: "The only way you can avoid being taken advantage of is to resign yourself to the meagre rewards of mutual defection, and to defect on every turn." So: yes, indeed you can do that, but then your long-run score will be rotten because it will look like a vast succession of (D,D) plays, 1 point each. If you let the Extortionist extort you, you will get substantially more points.
- scotty79 14y ago"The only way you can avoid being taken advantage of is to resign yourself to the meagre rewards of mutual defection, and to defect on every turn. If you do anything else then I will take advantage of your cooperation and I will do three times better than you, in the sense that – on average over the long run – (my score minus 1) will be thrice (your score minus 1)." I was refering to that. I did something else than dfecting all the time and got better result than 1:3 but that's ok since 1:3 is average over all strategies.
- deleted 14y ago[deleted]
- nopassrecover 14y agoThis is actually a really good article, including easily missed gems like the demos that the author put together (e.g. http://s3.boskent.com/prisoners-dilemma/fixed.html http://s3.boskent.com/prisoners-dilemma/fixed.html and http://s3.boskent.com/prisoners-dilemma/titfer.html http://s3.boskent.com/prisoners-dilemma/titfer.html)
- Toenex 14y agoThanks, very enjoyable read.
- andyjohnson0 14y agoIt's good to see Freeman Dyson still producing new insights in his late eighties. A great mind.
- macavity23 14y agoWatch the embedded video, it's a great illustration of the article. :-)
- deleted 14y ago[deleted]
- CaptainDecisive 14y agoThe parable about the elephant and the goldfish was wonderful. I imagined, when the time is right, telling it to my little boys as I tucked them in to bed at night. And then imagined one of them coming in to my bedroom later that night and beginning with "Papa, why did the elephant ...".
- StavrosK 14y agoDid anyone else find that article meandering? The description of the game, in particular, struck me as especially pompous wiring. The metaphor with the elephant and the goldfish had absolutely nothing to offer either, it was just a rehash of the previous sentence.
- drostie 14y agoThe metaphor might have been a little over-the-top but I support this sort of creativity in blog posts, if only because it can ripen into something much more aesthetically pleasing. There are places where it goes way too far -- Gödel, Escher, Bach comes to mind -- but this is only a couple paragraphs. In this case it does have something to "offer": it offers the insight that the only value that looking at past states can offer is a sort of "strategy tomography" to tell you what the other person's conditional probabilities actually are, but that once you know this, your strategy is first-order Markov, just because their strategy is first-order Markov. (This term, nth-order Markov, just means "depends only on the last n game states.") It's true, however, that this leads to a very interesting consequence which is not discussed in this context, something quite convoluted: "I will commit to a first-order Markov strategy in order to prevent my opponent from using a higher-order Markov strategy, so that my own analysis of their strategy simplifies." It is a curious statement that your own ignorance forces someone else to be ignorant, which you can then exploit. This is proven in appendix A of their paper. To state the conclusion in their words, "In iterated play of a fixed game, one might have thought that a player Y with longer memory of past outcomes has the advantage over a more forgetful player X. For example, one might have thought that player Y could devise an intricate strategy that uses X’s last 1,000 plays as input data in a decision algorithm, and that can then beat X’s strategy, conditioned on only the last one iteration. However, that is not the case when the same game (same allowed moves and same payoff matrices) is indefinitely repeated. In fact, for any strategy of the longer-memory player Y, X’s score is exactly the same as if Y had played a certain shorter-memory strategy (roughly, the marginalization of Y’s long-memory strategy), disregarding any history in excess of that shared with X."
- sisu 14y ago> It's true, however, that this leads to a very interesting consequence which is not discussed in this context, something quite convoluted: "I will commit to a first-order Markov strategy in order to prevent my opponent from using a higher-order Markov strategy, so that my own analysis of their strategy simplifies." It is a curious statement that your own ignorance forces someone else to be ignorant, which you can then exploit. This is only true if you know the strategy of the enemy beforehand, though. For instance if you play rock-paper-scissors and decide your move only based on the previous move your enemy can easily exploit that after playing for a while. It is true that the enemy doesn't have to remember more than one move after he learns your strategy but he needs to remember many moves to learn it.
- biot 14y agoIf I were playing Split or Steal, my strategy would be exactly this: tell the other player that I'm going to choose "steal" and if they choose "split", I'll give them half of the winnings. We would shake on it on national television which forms a nice contract: an offer, consideration for both parties, and acceptance. The beauty of this is that if they're not an idiot they'll choose "split" and we each walk away with half. However, if they are an idiot and they also chose "steal" then nobody gets anything and I can sue them for violation of the contract in the amount of the 50% I would have won. Sadly, I suspect everyone would then copy that strategy and much like everyone choosing the letters R, S, T, L, N, and E in Wheel of Fortune, it would quickly become a formula and would ruin the suspense the show hopes to create.
- redslazer 14y agoHere is the video of this happening on the tv show. http://www.youtube.com/watch?v=S0qjK3TWZE8 http://www.youtube.com/watch?v=S0qjK3TWZE8 . It worth a watch, I recommend it.
- mmcnickle 14y agoThere's a twist in this example though. He says he's going to steal (but split after the show) and convinces the other guy to split. At the last minute he changes to split so that the split is governed by the rules of the game.
- alexfoo 14y agoI deeply wanted "the other guy" to steal leaving that guy with nothing.
- mmcnickle 14y agoI think that's why the guy proposing the deal ended up splitting. If the other guy did steal to spite him, the fact he split would show that he was acting in good faith and would increase the chance of a split after the show.
- jere 14y agoThe most interesting story on IPD (especially from a hacker perspective) wasn't mentioned: >Although tit for tat is considered to be the most robust basic strategy, a team from Southampton University in England (led by Professor Nicholas Jennings [1] and consisting of Rajdeep Dash, Sarvapali Ramchurn, Alex Rogers, Perukrishnen Vytelingum) introduced a new strategy at the 20th-anniversary iterated prisoners' dilemma competition, which proved to be more successful than tit for tat. This strategy relied on cooperation between programs to achieve the highest number of points for a single program. The University submitted 60 programs to the competition, which were designed to recognize each other through a series of five to ten moves at the start. Once this recognition was made, one program would always cooperate and the other would always defect, assuring the maximum number of points for the defector. If the program realized that it was playing a non-Southampton player, it would continuously defect in an attempt to minimize the score of the competing program. As a result,[8] this strategy ended up taking the top three positions in the competition, as well as a number of positions towards the bottom. >This strategy takes advantage of the fact that multiple entries were allowed in this particular competition and that the performance of a team was measured by that of the highest-scoring player (meaning that the use of self-sacrificing players was a form of minmaxing). In a competition where one has control of only a single player, tit for tat is certainly a better strategy. Because of this new rule, this competition also has little theoretical significance when analysing single agent strategies as compared to Axelrod's seminal tournament. However, it provided the framework for analysing how to achieve cooperative strategies in multi-agent frameworks, especially in the presence of noise. In fact, long before this new-rules tournament was played, Richard Dawkins in his book The Selfish Gene pointed out the possibility of such strategies winning if multiple entries were allowed, but he remarked that most probably Axelrod would not have allowed them if they had been submitted. It also relies on circumventing rules about the prisoners' dilemma in that there is no communication allowed between the two players. When the Southampton programs engage in an opening "ten move dance" to recognize one another, this only reinforces just how valuable communication can be in shifting the balance of the game. http://en.wikipedia.org/wiki/Prisoners_dilemma#Strategy_for_the_iterated_prisoners.27_dilemma http://en.wikipedia.org/wiki/Prisoners_dilemma#Strategy_for_... By the way, if you haven't read The Selfish Gene, do yourself a favor and read it now. It discusses IPD and coins the word "meme"... what more could you possibly want?
- gwern 14y agoThe Hofstadter essays: http://www.gwern.net/docs/1985-hofstadter http://www.gwern.net/docs/1985-hofstadter
- mistercow 14y agoI feel bad for game theorists. Any time an article talks about their field, the first paragraph has to be a frantic explanation of what the field is and why it's interesting, in terms a five-year-old could understand, and then the article always ends up just being about the prisoner's dilemma. It would be as if every article about physics started out "How stuff moves is a really neat thing to study..." and then invariably ended up talking about the parabolic trajectories of projectiles.
- zmj 14y agoResults and strategy summary of an iterated Prisoner's Dilemma tournament from last year: http://lesswrong.com/lw/7f2/prisoners_dilemma_tournament_results/ http://lesswrong.com/lw/7f2/prisoners_dilemma_tournament_res...
- Xcelerate 14y agoFor the split or steal game (with the golden balls), here is what I what do. I would not open either ball, and I would tell the other contestant to pick one at random. Then, he MUST choose split for his own ball if he wants any chance of winning money. If my ball happened to say "steal" after opening, then I would split what I won with him. I think this would guarantee both of us winning unless he was willing to take the chance of winning nothing.
- cgag 14y agoYou could just tell him you're going to choose steal: http://www.youtube.com/watch?v=S0qjK3TWZE8 http://www.youtube.com/watch?v=S0qjK3TWZE8
- Xcelerate 14y agoI saw that video. That's what made me think of my idea. But mine removes the possibility that I might be holding out on "split" and I think has a better chance of guaranteeing we both split the money.
- pak 14y agoHe also has to be willing to trust that you will actually split what you win after stealing the whole pot. Otherwise, he will worry that you could dupe him and walk away with everything, and then choose to steal.