Hacker News Reader

Comment by forrestthewoods | Hacker News Reader

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 I don't really understand it. Neither do journalists it seems. Can someone explain?

View on HN

Actually, the original paper is this one: 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_...

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.

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.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com