4 ms·

This is roughly the 5th article on a "Revolution in Game Theory" that I've seen and not a single one of them has successfully described what the so called revol

This is roughly the 5th article on a "Revolution in Game Theory" that I've seen and not a single one of them has successfully described what the so called revolutionary strategy is. Here is a direct link to a PDF of a paper defining the Zero Determinant Strategy. http://arxiv.org/pdf/1208.2666v1.pdf http://arxiv.org/pdf/1208.2666v1.pdf I don't really understand it. Neither do journalists it seems. Can someone explain?

chewxy 14y ago
I dunno, I think this sentence in the 2nd paragraph is quite clear: 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.
kkwok 14y ago
At a high level the strategy is pretty intuitive. It's why cognition is important. if you're opponent purely optimizes for choosing the best option for each individual decision, or even for the game, you can take advantage of them. If you face someone who understands how you're trying to manipulate them then it turns into a whole different situation.
jorleif 14y ago
Actually, the original paper is this one: http://www.pnas.org/content/early/2012/05/16/1206569109.full.pdf+html http://www.pnas.org/content/early/2012/05/16/1206569109.full... Here is an description of the result and its implications http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_strategies_in.html http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_...
- DennisP 14y ago
  Wow. Not long ago I was trying to test whether an idea for a certain kind of online interaction would work out the way I hoped. I built a simulation with agents that evolved their strategies, trying to optimize their own outcomes. Maybe that's not such a good test after all.
  - AnIrishDuck 14y ago
    I don't believe this outcome is optimal from an evolutionary standpoint. It requires the other player to know what your strategy is and accept the ultimatum (I will do x% better than you). The other player still has the option to reject the ultimatum, screwing over both parties. 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.
    - DennisP 14y ago
      What I'm thinking is, it appears that players with a theory of mind may not actually use the optimal evolutionary strategy. Since humans have a theory of mind, my simulation may be a poor predictor of what my users would actually do.
- edghf 14y ago
  I found the second link you posted when I went looking for clarification. The takeaway for me was that zero-determinant strategies do tend to win games, in that the end score of someone playing a ZD strategy is usually higher than that of someone playing a different strategy, but that both scores in such games tend to be low. Against a basic tit-for-tat player, the ZD player will win by a very small margin but the game will largely consist of mutual defections. Basic tit-for-tat, as the author points out, is never a 'winning' strategy--it always either ties or loses. Its strength isn't that it wins, but rather that it limits its losses. That characteristic of tit-for-tat is as effective against a ZD strategy as it is against any other strategy.
peterderivaz 14y ago
As far as I understand, the basic idea is to cooperate with a probability that depends on whether your opponent cooperated in the previous round. (Actually there are 4 probabilities because the strategy also depends on whether you cooperated in the last round.) 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.

chewxy 14y ago

I dunno, I think this sentence in the 2nd paragraph is quite clear: 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.

kkwok 14y ago

At a high level the strategy is pretty intuitive. It's why cognition is important. if you're opponent purely optimizes for choosing the best option for each individual decision, or even for the game, you can take advantage of them. If you face someone who understands how you're trying to manipulate them then it turns into a whole different situation.

jorleif 14y ago

Actually, the original paper is this one: http://www.pnas.org/content/early/2012/05/16/1206569109.full.pdf+html http://www.pnas.org/content/early/2012/05/16/1206569109.full... Here is an description of the result and its implications http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_strategies_in.html http://golem.ph.utexas.edu/category/2012/07/zerodeterminant_...

DennisP 14y ago
Wow. Not long ago I was trying to test whether an idea for a certain kind of online interaction would work out the way I hoped. I built a simulation with agents that evolved their strategies, trying to optimize their own outcomes. Maybe that's not such a good test after all.
- AnIrishDuck 14y ago
  I don't believe this outcome is optimal from an evolutionary standpoint. It requires the other player to know what your strategy is and accept the ultimatum (I will do x% better than you). The other player still has the option to reject the ultimatum, screwing over both parties. 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.
  - DennisP 14y ago
    What I'm thinking is, it appears that players with a theory of mind may not actually use the optimal evolutionary strategy. Since humans have a theory of mind, my simulation may be a poor predictor of what my users would actually do.
edghf 14y ago
I found the second link you posted when I went looking for clarification. The takeaway for me was that zero-determinant strategies do tend to win games, in that the end score of someone playing a ZD strategy is usually higher than that of someone playing a different strategy, but that both scores in such games tend to be low. Against a basic tit-for-tat player, the ZD player will win by a very small margin but the game will largely consist of mutual defections. Basic tit-for-tat, as the author points out, is never a 'winning' strategy--it always either ties or loses. Its strength isn't that it wins, but rather that it limits its losses. That characteristic of tit-for-tat is as effective against a ZD strategy as it is against any other strategy.

peterderivaz 14y ago

As far as I understand, the basic idea is to cooperate with a probability that depends on whether your opponent cooperated in the previous round. (Actually there are 4 probabilities because the strategy also depends on whether you cooperated in the last round.) 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.