Shue ([info]sojo) wrote in [info]mathematics,
@ 2004-10-14 20:03:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Current mood: crazy

game theorists unite (untie?)
In my daily browsing of /. I came across a story that shocked me at first. Wired News is running a story about the 20th-anniversary running of an Axelrod style Iterated Prisoner's Dilemma competition.
Apparently Tit-For-Tat was toppled this year by some strategies from the University of Southampton. Which..well is a little surprising, since TFT is a pretty good strategy. What was really amazing at first was that their "strategy" is an ESS (Evolutionarily Stable Strategy).

Maybe I'm just losing touch with my inner game theorist, but it did surprise me, at least until I read how it happened.

Basically, what happened is that they submitted 60 strategies which would all recognize each other and upon doing so, immediately assume "master and slave" roles with each other, and then just sabatoge anyone else.

Surprise turned to disgust. Maybe I'm just a purist who thinks that the whole point of the Prisoner's Dilemma thought game is that the prisoners aren't allowed to communicate, and this is essentially the same as them "tapping in Morse code on the prison wall."

Game theory is an excellent field of mathematics, and was one of the most enjoyable courses I took as an undergraduate. I'm led to ask the community now, have you ever participated in an IPD tournament? What was the idea of your strategy? (And how did you do?)

I ran a similar tournament a couple years ago, for the game of Chicken. (Picture two cars driving at each other. Both swerve, little gained for each. If you swerve, and your opponent doesn't then you lose a bit, your opponent gains a bit. If nobody swerves, both lose a lot.)

A lot of fun, and these things lead to some pretty interesting strategies.




(Post a new comment)


[info]bigbob007
2004-10-15 12:13 am UTC (link)
Could you really say the Southampton team won?

I would contest that each of the individual entries was not "the Southampton team," but rather the collection of the 60 entries was. So, how the 60 entries did on an overall scale should measure how successful they were.

The article said that the top three spots were Southampton, but the majority of the Southampton entries were at the bottom. That would make me not consider them the winners.

Besides that, their solution has no bearing on the original problem. You can't get 60 inmates / countries to cooperate like that, you can only control yourself. Isn't that the premise of the game? If the 60 inmates new that 57 of them were going to horribly lose, and 3 would win, would they cooperate?

(Reply to this)(Thread)


[info]bigbob007
2004-10-15 12:14 am UTC (link)
Keep in mind (1) I have no relevant background. I'm an undergrad, am not especially interested in game theory, and hadn't heard of this problem before now and (2) I only read it in brief.

(Reply to this)(Parent)


[info]kvschwartz
2004-10-15 12:32 am UTC (link)
I would say they didn't quite cheat, but that next year the rules should be set in place to prevent this. Obviously a strong team can produce someone to defeat any individual, especially if the team is a large percentage of the total players. If it had been 60 on the team out of 10 million players, they would not have faired well at all.

(Reply to this)


[info]jp7010
2004-10-15 12:38 am UTC (link)
I can't wait for next semester, for my indepedent study in game theory, so I can learn what the hell you're talking about! Hehe, just kidding..
but I'm tempted to agree, the point of the prisoner's dilemma IS that neither prisoner has any idea what the other is going to do! At least, this is as far as I know, with my preliminary study[reading the first chapters in a pair of game theory books].

(Reply to this)


[info]landofnowhere
2004-10-15 01:00 am UTC (link)
It's been known for a while that there are strategies out there that can beat Tit for Tat. TFT just gets all the publicity because it's so simple and it makes a really good story.

(Reply to this)(Thread)


[info]sojo
2004-10-15 02:22 am UTC (link)
Well, yes and no, right? In any given tournament, it is very easy to produce something that will beat TFT. Part of the challenge is to come up with something that will be an Evolutionarily Stable Strategy. TFT gets so much hype, I'd say, for a couple reasons. It was those 4 lines of code that won Axelrod's first couple tournaments. And because -no matter- the tournament, TFT is pretty much going to do well. You can change the payoffs (as long as it isn't by so much that you are no longer within the bounds for Prisoner's Dilemma), and you can enter a different variety of strategies (which is, perhaps one of the largest determiners of the outcome of a tournament), but TFT is still going to whollop much of the competition.

The question I wonder about right now...well if you took just ONE of the strategies that the Southampton crew entered, would That be an ESS? I doubt it. I don't remember the theorem, but there was something about an ESS having to be something akin to TFT. I'd have to run to the other room for the books, so far...

(Reply to this)(Parent)


[info]malaya_zemlya
2004-10-15 02:38 am UTC (link)
They should evenly divide the points for all stategies in the team among all the team members. That, and make sure that

sucker payoff + cheater payoff < 2 * cooperator payoff

This will make collusion unprofitable.

(Reply to this)


[info]sunavatar
2004-10-15 02:40 pm UTC (link)
MATHMAN ICON.

More to the point, I agree with you that the collusion sort of misses the point of Prisoners' Dilemma, but I guess it wasn't per se against the rules. Just stupid.

(Reply to this)


[info]scattergather
2004-10-17 12:13 am UTC (link)
If the rules are there and they don't preclude it, it's not cheating. Let's face it, if you develop a strategy and it beats tit-for-tat in a competeition where such strategies are excluded, you'll know about it without having to submit it in such a competition; you'll have run the trials yourself. The Southampton strategy is an interesting attack which has opened up a new game-theoretic problem, which clearly has analogues (albeit not readily imaginable ones against such overwhelming numbers) in reality. I consider that a result.

(Reply to this)


Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…