10 November 2004—Within a certain obsessive breed of computer scientists, the geek equivalent of the World Series is a little known tournament called the Iterated Prisoner's Dilemma Competition.

Academics from around the globe struggle to devise the best strategy for tackling one of the fundamental problems in game theory, Prisoner's Dilemma, and then build artificially intelligent software "robots" to play their strategies in a competitive round-robin tournament. As it turns out, real-world situations from live auctions to nuclear standoffs can bear striking resemblance to this very simple game, and so it was no small matter when this year the longstanding champion of Iterated Prisoner's Dilemma had to settle for silver.

A team of robots submitted by computer scientists from Southampton University, in England, used conspiracy and collusion to sweep this year's competition stealing the crown from the 20-year reigning incumbent, a simple strategy called Tit for Tat.

The Prisoner's Dilemma is a game theory problem in which two competing players must decide between cooperation and betrayal. In its classic form, two accomplices in a crime are arrested and then interrogated separately by the police. Each accomplice must choose either to confess to the crime (defection) or remain silent (cooperation). Depending on his choice, and the choice of the other player, different payoffs will be given. If one player defects and the other cooperates, the defector walks free, while the cooperator gets five years in jail. If both defect and confess, both get four years. But if the players both cooperate and remain silent, they each get only two years.

In the actual Prisoner's Dilemma competition, held in June at a conference in Portland, Ore., the various outcomes are given different point values, so that a score may be tallied after a series of rounds are played. Each player is aware of how his opponent behaved in previous rounds, and may adapt his strategy accordingly. During the course of the tournament, each robot will play every other robot, even those submitted by the same research team.

"The Prisoner's Dilemma encapsulates the essence of how cooperation can emerge when you have self-interested behavior," said Nick Jennings, a computer science professor at Southampton University and member of the winning team. "It's very, very simple, and yet very powerful."

The winning strategy, Tit for Tat, worked like this: a player began by cooperating each round, until his opponent defected. After this point, the player echoed his opponent's last move, defecting after the other player had betrayed him, and cooperating when his opponent began to cooperate again.

The Southampton University researchers, who entered a team of 60 software robots, or agents, into the competition, found that an even better strategy was to submit a group of robots that behaved in the tournament either as masters or slaves. A robot's particular role was encoded in its pattern of opening moves, allowing any other robot that knew what to listen for to recognize its opponent as another Southampton player. When a Southampton "master" was pitted against a Southampton "slave", the slave would sacrifice itself, cooperating every round to allow the master to defect repeatedly and rack up a huge score. In the end, the individual master robots scored more points than the robots playing Tit for Tat.

"It was almost like a cult," said Graham Kendall, a professor at the University of Nottingham, in England, who organized the 20th-anniversary competition, referring to the culture the Southampton entries created. "There were superagents who exploited all their friends."

While technically this strategy violates the spirit of the Prisoner's Dilemma, which assumes that the two prisoners cannot communicate with one another, the Southampton system is not without its uses. In reality, collusion between competitors is generally impossible to prevent, and a whole field of research has sprung up to study how intelligent agents can use what's called coding theory to communicate covertly, and how such collusion can in turn be prevented. For example, the U.S. Federal Communications Commission's radio spectrum auctions have historically been plagued by cases of bidders colluding by coding hidden signals in their bids, and so the FCC has brought in researchers to advise it on how to modify the rules of its auctions to try to mitigate collusion.

"How agents can collude and how you can stop that collusion—now that's an interesting area of research," said Southampton's Jennings, who likened the discipline to an arms race between bidders and auctioneers.

A second round of the Iterated Prisoner's Dilemma competition will be held in April of 2005 at the IEEE Symposium on Computational Intelligence and Games hosted by the University of Essex, in England. Armchair game theorists may submit an entry by visiting http://www.prisoners-dilemma.com.