University of Southampton team wins Prisoner's Dilemma competition
07 October 2004
A solution that allows computer agents to collude, rather than compete with each other, has won this year's recreation of Axelrod's classic Iterated Prisoner's Dilemma competition.
The winning solution was devised by a team from the University of Southampton's School of Electronics and Computer Science (ECS) which met the competition's 20th anniversary challenge to resolve the original dilemma in a noisy environment where moves could be misinterpreted.
Professor Nick Jennings, a member of the ECS winning team said: 'We developed ways of looking at the Prisoner's Dilemma in a more realistic environment and we devised a way for computer agents to recognise and collude with one another despite the noise. Our solution beats the standard tit-for-tat strategy.'
The Iterated Prisoner's Dilemma has been of interest to the world of computer science since the publication of Robert Axelrod's seminal book in the 1980s. It presents a simple game between two prisoners, in which their combined choices to co-operate or defect, determines whether they are imprisoned or walk free. Both players make a choice and then their decisions are revealed and both receive scores.
Up to this year, the most common strategy applied to the dilemma was tit-for-tat which consistently outperformed every strategy entered in the original competition. It starts out by co-operating, and then punishes any strategy that defects by defecting on the next move.
The solution devised by ECS uses coding theory to enable agents to recognise one another and to transmit messages reliably over noisy communication channels. No outside communication is allowed so the agents have to recognise one another by playing a specific sequence of moves at the start of each game.
Dr Alex Rogers, another ECS team member said: "A key question in future computing systems is how the different agents within the system should interact and co-operate. Working on simple models such as the Prisoner's Dilemma gives a fundamental understanding of how to tackle these problems."
Notes for editors
Further information about The Prisoner's Dilemma competition can be found at http://www.prisoners-dilemma.com.
The members of the Southampton team were Professor Nick Jennings, Dr Alex Rogers, Gopal Ramchurn, Raj Dash and Krishnen Vytelingum.
ECS houses IAM, Intelligence, Agents, Multimedia Group which is a world leader in the key technologies of agent-based computing. Further details can be found at www.iam.ecs.soton.ac.uk.
The University of Southampton is a leading UK teaching and research institution with a global reputation for leading-edge research and scholarship. The University has over 19,200 students and over 4,800 staff. Its annual turnover is in the region of £250 million.