The Emerging Revolution in Game Theory
technologyreview.com
technologyreview.com
Here is a direct link to a PDF of a paper defining the Zero Determinant Strategy. http://arxiv.org/pdf/1208.2666v1.pdf I don't really understand it. Neither do journalists it seems. Can someone explain?
Here is an description of the result and its implications http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_...
Maybe that's not such a good test after all.
In other words, for this strategy to work it needs "pragmatic" other players that are (a) intelligent enough to know what the other player is doing and (b) willing to accept the unequal outcome. This strategy isn't symmetric: if you turned two of these bots against each other the total outcome would be much worse than if two TFT bots played each other.
Thus it stands to reason that TFT or some small variant is still the evolutionary winner.
Such games can be described by a Markov process defined by the four probabilities that char- acterize each of the two player’s strategies [9] (because this is an infinitely repeated game, the probability to engage in the first move–which is unconditional–does not play a role here). Each Markov process has a stationary state given by the left eigenvector of the Markov matrix, which in this case describes the equilibrium of the process.
...
If we assume that two opponents play a sufficiently large number of games, their payoff approaches the payoff of the Markov stationary state [1,9]. We can use this mean expected payoff as the payoff to be used in the payoff matrix E that will determine the ESS.
TLDR: keep varying your strategy until you win in the long term, using your mean expected payoff as a payoff matrix in each subsequent state.
For example, you might say that you will cooperate with prob 75% if I cooperated, or 25% otherwise.
By choosing the probabilities carefully this can turn the game into one where the more I choose to cooperate, then the better I do - but you will always outperform me (unless I choose to always defect when we both end up equally lost).
Feels similar to only proposing win-lose business deals. You will never "lose" but will soon run out of people willing to deal.
Each prisoner dilemma round has four possible outcomes: CC, CD, DC and DD (C=Cooperate,D=Defect). We study probabilistic strategies which depend only on the previous round, so for instance, P(player 1 plays C at round i+1|CD was played at round i)=0.3. From the paper:
Such games can be described by a Markov process defined by the four probabilities that characterize each of the two player’s strategies [9] (because this is an infinitely repeated game, the probability to engage in the first move–which is unconditional–does not play a role here). Each Markov process has a stationary state given by the left eigenvector of the Markov matrix, which in this case describes the equilibrium of the process. The expected payoff is given by the dot product of the stationary state and the payoff vector of the strategy. But while the stationary state is the same for either player, the payoff vector–given by the score received for each of the four possible plays CC, CD, DC, and DD–is different for the two players for the asymmetric plays CD and DC. Because the expected payoff is a linear function of the payoffs, it is possible for one strategy to enforce the payoff of the opponent by a judiciously chosen set of probabilities that makes the linear combination of determinants vanish (hence the name ZD strategies). Note that this enforcement is asymmetric because of the asymmetry in the payoff vectors introduced earlier: while the ZD player can choose the opponent’s payoff to depend only on their own probabilities, the payoff to the ZD player depends on both the ZD player’s as well as the opponent’s probabilities. This is the mathematical surprise: the expected payoff is usually a very complicated function of six probabilities (and four payoff values, for the four possible plays). When playing against the ZD strategy, the payoff that the opponent reaps is defined by the payoffs and only two remaining probabilities that characterize the ZD strategies.
Huh? That isn't correct is it? Snitching is best because it gives the highest payout regardless of what the other person does (snitching strictly dominates not snitching).
If the other does not snitch and you do, you go free. If the other person does snitch, you should as well, because it gives you 3 months instead of 6.
Guess I need to go back and do some more reading on the subject. This reminds me, I've been meaning to read The Evolution of Cooperation[1] forever, and haven't found time yet. sigh
Personally I think it is somehow ahead of these academic researches in some sense.
If you'd join a tournament with only random players then your optimal strategy, actually doesn't matter because you're going to randomly win/lose (because your opponents always play random) and on average, end up in the middle rank, just like everybody else.
If there are other non-random players, then you can aim for the middle rank by playing random (and one of the other non-random players will do better than the other, and you will do worse than that one and better than the other). Or you can try to beat the non-random players (while still doing near 50/50 odds on the random ones).
So if you play random, and there is more than one non-random player, you will lose.
Also, check out some of the strategies. There's a couple of really well-performing ones that are incredibly clever, but not all that hard to understand.
One goes like this:
It's based on trying to predict the opponent's strategy and playing against that. But what if the opponent expects that and plays you against that? A-ha but what if you play against your opponent trying to play you?
You'd think that this reasoning can go on forever, but since there are only three moves in RPS, and they circularly defeat eachother, you only need to consider these three steps as the next one brings you to the move of square one.
The algorithm then basically keeps a running score of these three different depths of pre-emptive strategy, and picks the one that works best based on historical moves "what would have won" (and runs random while collecting data).
This algo did extremely well in the first couple of tournaments held many years ago. I don't know what the most popular strategy is currently though.
http://www.academicearth.org/courses/game-theory/ (you don't need an account)
http://www.schneier.com/blog/archives/2012/04/amazing_round_...
The relevant vid link within:
In a single game, the proposition of the dilemma still holds true. The best solution is if both don't talk.
In an iterative game, then things change.. but that's pretty obvious. So not sure what is so revoluationary about this paper.
This comment below the article made me smile. I kind of feel inclined to agree, even though it is of course too simplistic a view.
(see @jorleif's post here for the links)
"This just seems to be an extension of the folk theorem to the family of probabilistic strategies. 1. Any level payoff level can be supported in equilbrium (Press & Dyson), 2. None of those equilbria survive evolutionary refinements (this paper). Interesting stuff, but not quite revolutionary as it is suggested. "
The reference I was making was a famous line from the Simpsons where Bart's strategy of "good old rock, nothing beats that" is adapted to by Lisa who picks paper. Yeah I misquoted, season 4 was a long time ago :)
http://www.youtube.com/watch?v=NMxzU6hxrNA
No it probably wasn't the most intelligent or informed comment I could have made. Sometimes the not most intelligent comments can be useful. Maybe this one wasn't one of those but, /shrug I would probably make it again.