www.wired.com/news/culture/0,1284,65317,00.html?tw=rss.TOP
The Southampton group, whose primary research area is software agents, sa id its strategy involved a series of moves allowing players to recognize each other and act cooperatively.
Prisoner's Dilemma is a game-theory problem for two players. As t ypically described, two accomplices are arrested and separated for inter rogation by the police, who give each the same choice: confess to author ities (defect) or remain silent (cooperate). If one defects and the othe r cooperates, the defector walks free and the cooperator gets 10 years i n jail.
Nick Jennings, a professor i n computer science at Southampton University and leader of the winning t eam along with his PhD student, Gopal Ramchurn. "People are very keen on it because they can see so many parallels in real life." Before Southampton came along, a strategy called Tit for Tat had a consis tent record of winning the game. Under that strategy, a player's first m ove is always to cooperate with other players. Afterward, the player ech oes whatever the other players do. The strategy is similar to the one nu clear powers adopted during the Cold War, each promising not to use its weaponry so long as the other side refrained from doing so as well.
The Iterated Prisoner's Dilemma is a version of the game in which the cho ice is repeated over and over again and in which the players can remembe r their previous moves, allowing them to evolve a cooperative strategy. The 2004 competition had 223 entries, with each player playing all the o ther players in a round robin setup. Because Axelrod's original competit ion was run twice, Kendall will run a second competition in April 2005, for which he hopes to attract even more entries. Teams could submit multiple strategies, or players, and the Southampton t eam submitted 60 programs. These, Jennings explained, were all slight va riations 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 Southampt on players recognized each other, they were designed to immediately assu me "master and slave" roles -- one would sacrifice itself so the other c ould 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-Southampto n player.
result is that Southampton had the top three performer s -- but also a load of utter failures at the bottom of the table who sa crificed themselves for the good of the team. Another twist to the game was the addition of noise, which allowed some m oves to be deliberately misrepresented. In the original game, the two pr isoners could not communicate. But Southampton's design lets the prisone rs do the equivalent of signaling to each other their intentions by tapp ing in Morse code on the prison wall. Kendall noted that there was nothing in the competition rules to preclude such a strategy, though he admitted that the ability to submit multiple players means it's difficult to tell whether this strategy would really beat Tit for Tat in the original version. But he believes it would be i mpossible to prevent collusion between entrants. "Ultimately," he said, "what's more important is the research." "What's interesting from our point of view," he said, "was to test some i deas we had about teamwork in general agent systems, and this detection of working together as a team is a quite fundamental problem. What was i nteresting was to see how many colluders you need in a population. It tu rns out we had far too many -- we would have won with around 20." Jennings is also interested in testing the strategy on an evolutionary va riant of the game in which each player plays only its neighbors on a gri d If your neighbors do better than you do, you adopt their strategy. "Our initial results tell us that ours is an evolutionarily stable strate gy -- if we start off with a reasonable number of our colluders in the s ystem, in the end everyone will be a colluder like ours," he said. The winners don't get much -- an unexpected $50 check and a small plaque. But, says Kendall, "Everybody in our field knows the name of Anatol Rap oport, who won the Axelrod competition. So if you can win the 20th-anniv ersary one, in our field there's a certain historical significance." End of story Send e-mail icon Have a comment on this article?
Terms & Conditions Note: You are reading this message either because you can not see our css files (served from Akamai for performance reasons), or because you do n ot have a standards-compliant browser.
|
http://csua.com/feed/