Iterated prisoner's dilemma contains evolutionary opponent dominating strategies | Hacker News Reader

Iterated prisoner's dilemma contains evolutionary opponent dominating strategies

pnas.org

95 pointsryanmolden26 comments

So, I understand the argument that having more memory than your opponent is marginalized, and I then understand why, if you have a good memory-one strategy, you may as well just play oblivious (directly marginalizing the opponent's memory).

Appendix A: """The importance of this result is that the player with the shortest memory in effect sets the rules of the game. A player with a good memory-one strategy can force the game to be played, effectively, as memory-one. She cannot be undone by another player’s longer-memory strategy."""

However, I'm having a hard time understanding how a memory-one strategy actually can be good, given that if your opponent has a theory of mind you apparently want to be paying enough attention to notice and dial down your extortion factor.

Discussion: """However, if she imputes to Y a theory of mind about herself, then she should remain engaged and watch for evidence of Y’s refusing the ultimatum (e.g., lack of evolution favorable to both)."""

How does one actually "remain engaged and watch for evidence" without having access to at least as much memory as their opponent's theory? It would seem that the "should" in this paragraph undermines the "can" in the previous one due to a conflict over "good".

Yes, they would appear to contradict each other.

What's happening here, I believe, is that neither of the players are actually playing a memory-one game. They extract a result for memory-one games and try to apply it to reason about a memory-N game, which I believe might be an error.

The "evolutionary" strategy used by Y is in fact a way for Y to base their decision on the outcome of many previous games. X is similarly using a long-term strategy. In the end, the players end up in a meta-game that is similar to the original one.

Note how this meta-game only works if both players agree to it -- if X is "out to lunch", as they put it, or if Y was simply playing a memory-one strategy without evolutionary adaption, the meta-game does not exist.

The title holds - they show how to use a local optimum to exploit a hill-climbing evolutionary player. However this can not be used to beat a true memory-one player, and I think the assumption that Y would require a "theory of mind" to counter this strategy is unfounded.

Could we say that this famous episode of Golden Balls demonstrates a simple application the idea?

Quote: "You're about to walk away with my money because you're an idiot."

http://www.youtube.com/watch?v=S0qjK3TWZE8

That's well known if you ever took evolutionary biology course, or game theory course.

Even popular books like Richard Dawkins' "The Selfish Gene" talk in some detail about it, and this 25 hour video course is also a must see for pretty much everyone:

http://youtu.be/NNnIGh9g6fA

This is really what I signed on to add. This paper really adds nothing to what is already known in various other fields. Perhaps its new to the authors' field however? I'm not a Computer Scientist so I'm not sure.

(Full Disclosure: {Applied Games in Economics} \in {What I do})

I'm really interested in this, but I have an extremely shallow knowledge of applied game theory. Can you point out some papers or textbooks you'd recommend on this subject? Particularly about the design of strategies that will dominate evolutionary strategies.

In all reality, one of the best places to start is Wikipedia. The sources quoted in the game theory articles are fantastic.

Also, "Game Theory" by Fudenberg and Tirole of you're mathy, or Gibbons if you're wanting a fairly awesome introduction: http://www.amazon.com/Game-Theory-Applied-Economists-ebook/d...

There are also a lot of blogs on algorithmic (computational) game theory if that is of interest to you.

Pretty amazing for a gentleman of 88 (Freeman Dyson). What an amazing life he has led.

http://en.wikipedia.org/wiki/Freeman_Dyson

Really, do people still embed PDFs in HTML frames? :)

Direct Link: http://www.pnas.org/content/early/2012/05/16/1206569109.full...

Moodle? :).

:) I was more worried about my inability to fully understand this paper (which is worth re-reading many times), than complaining about it being embedded in an HTML frame.

"This fact is important. We derive strategies for X assuming that both players have memory of only a single previous move, and the above theorem shows that this involves no loss of generality. Longer memory will not give Y any advantage."

Makes me think of parsers and lookahead-tokens.

I arrived at some related results in game theory in 2005. If I understand this new paper correctly, section 1.4 in this pdf is similar but less formal:

http://www.math.nyu.edu/~neylon/files/game_thy1.pdf

The best strategy appears to be the most sane. A great metaphor for life as well:

http://www.gmilburn.ca/2010/02/24/triumph-of-the-golden-rule...

I'm actually working on a research paper at the moment which shows how this case is overstated. The IPD merely shows that given a situation in which neither party has any advantage over the other the best choice for maximizing outcomes is cooperation. In this sense the prisoner's dilemma "begs the question" or assumes the answer it then provides. There is no "moral symmetry" in this game, merely a set of preconditions (poorly representative of the "real world") which make this cooperative outcome inevitable.

Here is a great show which talks about the ideal strategy a bit: http://www.radiolab.org/2010/dec/14/

I always love to enrage board game geeks by purposedly going out of Nash equilibrium after first giving them impression that I won't.

Good strategy for infrequent players that one is.

My quick reaction is to be confused about why X being unaffected by Y's longer memory would that Y is unaffected as well. In the zero-sum case, this would be obvious, but the whole point is that we're not in a zero-sum game.

I don't understand why so many people like the prisoner's dilemma.

Sure, it's a standart problem in game theory, but it's "uninteresting" to say the least

For example, it has a limited Nash Equilibrium http://en.wikipedia.org/wiki/Nash_Equilibrium

It also is rarely applicable to "real situations" like Economy, populations, etc.

Sure, the wikipedia page has various examples, but in real situations it's usually something else, as there are more details

What game would you recommend instead?

Depends on the situation

There is:

Stag Hunt http://en.wikipedia.org/wiki/Stag_hunt

http://en.wikipedia.org/wiki/Volunteer%27s_dilemma is also interesting

http://en.wikipedia.org/wiki/Nash_bargaining_game

Volunteer's Dilemma and the Nash Bargaining Game have more complex equilbiria, so they're not quite as good if you're looking for an introduction to game theory. Stag Hunt is basically a game about whether the players know they are in such a game and can communicate about it, so it's not the best for learning about games themselves. Prisoner's Dilemma really stands out among the basic games.

But really, Prisoner's Dilemma is uniquely fascinating in iterated form [0]. Iterated Stag Hunt would be boring, and Iterated Volunteer's Dilemma would be crazy, but Iterated Prisoner's Dilemma is a very deep game which seems to have things to say about Biology, Politics, and Computer Science all together.

[0] http://en.wikipedia.org/wiki/Repeated_game

True

I don't deny the learning importance of the PD. But it would be more interesting if other types of games were explained as well.

Otherwise it's just PD and it gets boring.

About the Iterated PD yes, it's very interesting! Especially evolving competing strategies in it.

I agree. Why not stag hunt?

The prisoner's dilemma is very useful as a beginner/layman introduction to the game theory mindset. It has a similar role arithmetic has in preparing you to calculus/differential eqs.

Reply on news.ycombinator.com