Monday, October 18, 2004

Rumors of Tit-for-Tat's Death Greatly Exaggerated

In a 20-year-anniversary recreation of Robert Axelrod’s famous repeated Prisoners’ Dilemma tournament, the famous tit-for-tat strategy lost its throne to what may become known as the Southampton gambit:
Teams could submit multiple strategies, or players, and the Southampton team submitted 60 programs. These, [computer science professor Nick] Jennings explained, were all slight variations on a theme and were designed to execute a known series of five to 10 moves by which they could recognize each other. Once two Southampton players recognized each other, they were designed to immediately assume "master and slave" roles -- one would sacrifice itself so the other could win repeatedly.

If the program recognized that another player was not a Southampton entry, it would immediately defect to act as a spoiler for the non-Southampton player. The result is that Southampton had the top three performers -- but also a load of utter failures at the bottom of the table who sacrificed themselves for the good of the team.
Now, the Southampton team’s approach is undoubtedly clever. They took advantage of a loophole in the tournament design that allowed them to submit as many “ringers” as they needed to give a leg up to the others. But does this result prove anything significant about the evolution of strategies?

I suspect not. In a real evolutionary setting, losing strategies would get periodically weeded from the population. As the tournament results show, the Southampton approach yielded a handful of winners and a boatload of losers. Natural selection would tend to knock out the losers, leaving the winners without their guaranteed slaves.

The article does not make it clear whether the Southampton strategies’ master-and-slave roles are pre-specified (i.e., when strategy A and strategy B meet and recognize each other, A will automatically be the master and B the slave) or randomized (i.e., when A and B meet and recognize each other, either A or B might be the master). If roles are pre-specified, then the master strategies’ success is crucially dependent on the existence of slaves. Without slaves in the population, the masters would die out as well. If the roles are randomized, then the tournament-winning Southampton strategies must have been the “lucky” ones that became the masters in a disproportionately large number of meetings with others in the Southampton group. In future plays of the tournament, they could end up at the bottom.

Jennings recognizes the importance of the selection process:
Jennings is also interested in testing the strategy on an evolutionary variant of the game in which each player plays only its neighbors on a grid. If your neighbors do better than you do, you adopt their strategy.

"Our initial results tell us that ours is an evolutionarily stable strategy -- if we start off with a reasonable number of our colluders in the system, in the end everyone will be a colluder like ours," he said.
I’m skeptical, but perhaps Jennings is correct given the particular evolutionary structure he supposes (a grid in which one only plays neighbors, and losers adopt winners’ strategies). I strongly doubt, however, that the Southampton strategies could survive a version of the Axelrod tournament in which losing strategies are removed and surviving strategies participate again in the next round of the tournament.

In addition, the Southampton approach would probably be vulnerable to mutation. Consider a Southampton program, which is supposed to defect immediately upon meeting and detecting a non-Southampton program. If the non-Southampton program is a tit-for-tat player, the Southampton program could do better by cooperating instead. Suppose a mutant-Southampton program emerged, which duplicated the standard Southampton program except that it played tit-for-tat against non-Southampton-programs. This program would benefit from its interaction with Southampton programs (unless it was a pre-specified slave, in which case it would do badly even if unmutated), and it would do better in its interactions with the rest of the population – especially if tit-for-tatters were common enough in the population to begin with. The mutant strategy would therefore tend to reproduce more successfully, and the standard Southampton strategies would lose the benefits of sabotage.

In short, tit-for-tat ain’t dead yet.

2 comments:

Anonymous said...

One way to get around the need for pre-programmed masters and slaves without relying purely on luck to get some high scorers would be to add an encoding of the current scores into the handshake at the beginning. The program instance with the lower score could then sacrifice itself for the version with the higher. If they are tied when they meet, then a random selection would be appropriate. (And if both have above some threshold score, perhaps they should cooperate.)

This variation would still, as you mention, fair poorly in a contest where poor performers die out. I wonder, though, how it would do in a contest where performers reproduce at a rate dependant on their scores in the previous round (with sufficiently poor performers reproducing 0 times). Under what conditions would the instances which sacrifice themselves give that generation's winners enough of a boost to replace the population?

It's still probably not stable if mutations are introduced. Playing tit-for-tat with non Southampton variants would probably still give an advantage compared to the standard programs. If they also started lying about their scores during the handshake (as seems likely), it would actually turn into tit-for-tat over time.

Anonymous said...

I agree that the results are not particularly meaningful, due to the artificiality of being able to submit ringers at no cost. Long discussion on my personal blog herePatri Friedman