The Prisoner's Dilemma: a summary, and new advances
bosker.wordpress.com
bosker.wordpress.com
>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_...
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?
I suspect that if you caught on to this, the best strategy would in fact be to impersonate the Southampton players, mimicking the ten-move dance, and then perpetually defect, assuring the best strategy against either the "always defect" or "always cooperate" players.
Another interesting strategy mentioned by a commenter on the post is win-stay lose-shift, which reportedly outperforms GTFT: http://abel.math.harvard.edu/archive/153_fall_04/Additional_...
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.
The metaphor with the elephant and the goldfish had absolutely nothing to offer either, it was just a rehash of the previous sentence.
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."
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.
2. You would have to define "exploit that," especially with the understanding that this is game theory and probabilistic strategies are certainly encouraged. So for example, you might imagine a genius who can consistently outthink you, knows your entire history and how you like to play Rock-Paper-Scissors and immediately as you throw down Rock, simply is able to guess that this is what you're likely to do, and throws Paper.
You can beat this guy. Or, more precisely, you can equal him. It's very simple: before the day has begun, roll a six-sided die and memorize the sequence. As long as they are not exploiting certain "tells" (as a Japanese robot did in the news a week or two ago) -- as long as they are just making a deduction based upon the sort of person you are, they cannot produce a net win against you and you're safe. Indeed, the Nash equilibrium for RPS is not terribly interesting, it's to choose each of the options with probability 1/3rd -- I don't really have much reason to believe that this changes dramatically in iterated RPS.
2. Well, I was thinking that a strategy would be a mapping from game history to a probability distribution over possible moves. Should this be considered in some other way?
Sure, you can just play according to the Nash equilibrium and you can't be exploited, but probably a more interesting case is when both players try to outsmart the other player and not just aim for a draw.
The metaphor didn't really have anything to offer, before the preceding paragraph made it clear that the strategy is first-order Markov (it did state very plainly that you only remember the last position).
I don't understand the consequence. It seems to me that you aren't forcing the opponent to commit to a first-order Markov strategy themselves, you just make it easier on them to do that, because they don't need any more moves in the past.
Of course, you're doing this to simplify your own life, and because (I guess) first-order strategies work just as well as higher-order ones. Their conclusion seems to verify this, because they state that you really don't need (since you can't do any better than first-order) higher-order strategies, since you can model the opponent effectively with just the last move (which is the exact model the opponent is using).
Taking more moves into account, you would either just be trying to predict randomness (since that's the whole difference, if the opponent only remembers one move), or you would be "decompressing" their strategy into thousands of moves (since you can express a thousand moves of tit-for-tat with just "my move is the opponent's last move").
Literally, knowing any states further than the last gives you exactly zero extra information. Thus, it's useless.
Think of "the consequence" here in a purely security-theory way. In some sense that's what we're doing, securing ourselves from exploitation.
Press and Dyson are expressing the radical idea that "if I protect myself from some stupid attackers, I protect myself from all smarter ones." How does this work? It works precisely because there is a threshold above which "smarter doesn't matter" -- a smarter attacker has the exact same payoffs as a stupid attacker playing a different strategy. In that sense there are no higher-order strategies for exploiting a sufficiently stupid strategy: sure you can program a smarter attack, but it cannot do better than a different, stupid attack.
So if I intentionally choose my strategy to be stupid and show that, for all of your stupid strategies, the expected payoff is the same -- then for all of your smart strategies, the expected payoff is also the same!
It's not quite "trying to predict randomness", it's "if I dumb myself down I can also assume, without loss of generality, that my adversaries are dumb."
Unless I'm confused again, it seems to me that there's just no advantage to them remembering more moves, since they know everything you're going to do from that last one. It's not that your strategy being stupid actively forces them to be stupid, they're not losing anything by being cleverer, they just don't gain anything because they already have it all.
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)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.
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.
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.
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.
"A more powerful variation would be to offer the same deal but without looking at the balls at the beginning, stating that you will pick one at random. The other player is then forced to split or risk walking away with nothing."
http://www.schneier.com/blog/archives/2012/04/amazing_round_...
I've seen people immediately regret doing it when they see that their opponent shared. They seem more upset about it than the loser and tend to cite an expectation that the other person would steal as their reason for stealing, even though this makes no logical sense. It was a fascinating but horrible ending to sixty minutes of otherwise tedious viewing.
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 ...".