RandomThinker comments on Paper: Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent - Less Wrong

27 Post author: mapnoterritory 02 June 2012 08:50PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (19)

You are viewing a single comment's thread.

Comment author: RandomThinker 25 June 2012 03:46:29PM *  0 points [-]

I find the article very interesting, but have trouble following the math. Maybe someone here better at math can help. I do have some understanding of linear algebra, and I've tried to check it with a spreadsheet:

  1. At the very beginning, their closed form solution for V, the stationary vector, seems to allow V's that have negative numbers for the state probabilities. That can't be describing a real game. E.g. if you set p = (0.9, 0.7, 0.2, 0.1) and q = (0.5, 0.5, 0.5, 0.5), you get V = (0.08, -0.08, 0.1, -0.1). [p here is set to the Force-Opponent-Score-Equal-to-2 values, q is a random strategy, and V is calculated by 3x3 determinants of portions of M' as described in the paper]

I don't know how to convert that into a V with no negative numbers. Some of the co-efficients are positive and some negative, so you can't just scale it. Their formula for s_y correctly returns 2, but it's unclear if that corresponds to a real world equilibrium.

  1. Their formula for payoffs sx and sy require division by D(p,q,1). D(p,q,1) can be 0, e.g. for the classic tit-for-tat strategies matched head to head, p = (1,0,1,0) and q = (1,1,0,0). I don't know if that ruins the conclusion or not. If you match their Extort-3 strategy against tit-for-tat, again you get a 0 denominator.

Are these fatal problems? Not sure yet. Their overall conclusion meets with my intuition. They're just saying that if one player only tries to maximize his own score, while the other player is strategic (in terms of denying the first player a higher score), then the second player is going to win in the long term. Except they call the first player "evolutionary," and the second player "sentient."

And two, there's no point being too "smart" (looking back too many moves) when your opponent is "dumb" (looking back only 1 move).

You could say both of these things about the current bargaining position of the US political parties right now.

Comment author: snarles 02 July 2012 06:52:57PM *  1 point [-]

v cannot have negative entries. It appears that are you are forgetting the signs in the formula for the adjugate.

v is guaranteed to exist and be a valid probability vector as long as M is an irreducible Markov matrix (that is, any state can eventually be reached from any other state). An equivalent and intuitively easier way to calculate v is by repeatedly squaring M: when you do this, all rows of M^k converge to v. This is a consequence of the fact that v is an equilibrium state, i.e., the probability distribution you end up with if you let the Markov chain run forever (from any starting state).

Comment author: RandomThinker 06 July 2012 11:14:03PM 0 points [-]

You're right snarles. Thanks for spotting my error. I forgot the signs in the formula for adjugate.

What about the problem of the zero determinant in the denominator? Is that fatal? What's the real world interpretation?