Saturday, June 30, 2012

tit for tat


Nice Guys Finish First (BBC Horizon television series) is a 1986 documentary by Richard Dawkins which discusses selfishness and cooperation, arguing that evolution often favors co-operative behaviour, and focusing especially on the tit for tat strategy of the prisoner's dilemma game. The film is approximately 45 minutes long and was produced by Jeremy Taylor.

The twelfth chapter in Dawkins' book The Selfish Gene (added in the second edition, 1989) is also named Nice Guys Finish First and explores similar material.

This strategy is dependent on four conditions, which have allowed it to become the most successful strategy for the iterated prisoner's dilemma:[1]
  1. Unless provoked, the agent will always cooperate
  2. If provoked, the agent will retaliate
  3. The agent is quick to forgive
  4. The agent must have a good chance of competing against the opponent more than once.
In the last condition, the definition of "good chance" depends on the payoff matrix of the prisoner's dilemma. The important thing is that the competition continues long enough for repeated punishment and forgiveness to generate a long-term payoff higher than the possible loss from cooperating initially.

A fifth condition applies to make the competition meaningful: if an agent knows that the next play will be the last, it should naturally defect for a higher score. Similarly if it knows that the next two plays will be the last, it should defect twice, and so on. Therefore the number of competitions must not be known in advance to the agents.

Generally, in game theory, effectiveness of a strategy is measured under the assumption that each player cares only about him or herself. (Thus, the game-theory measure of effectiveness is impractical in many real life situations where players do have a vested interest in, or an altruistic compassion towards, other players.) Furthermore, game-theory effectiveness is usually measured under the assumption of perfect communication, where it is assumed that a player never misinterprets the intention of other players. By this game-theory definition of effectiveness tit for tat was superior to a variety of alternative strategies, winning in several annual automated tournaments against (generally far more complex) strategies created by teams of computer scientists, economists, and psychologists. Some game theorists informally believe the strategy to be optimal, although no proof is presented.

In some competitions tit for tat was not the most effective strategy, even under the game-theory definition of effectiveness. However, tit for tat would have been the most effective strategy if the average performance of each competing team were compared. The team which recently won over a pure tit for tat team outperformed it with some of their algorithms because they submitted multiple algorithms which would recognize each other and assume a master and slave relationship (one algorithm would "sacrifice" itself and obtain a very poor result for the other algorithm to be able to outperform tit for tat on an individual basis, but not as a pair or group). This "group" victory illustrates one of the important limitations of the Prisoner's Dilemma in representing social reality, namely, that it does not include any natural equivalent for friendship or alliances. The advantage of tit for tat thus pertains only to a Hobbesian world of so-called rational solutions (with perfect communication), not to a world in which humans are inherently social.






However, that this winning solution does not work effectively against groups of agents running tit for tat illustrates the strengths of tit for tat when employed in a team (that the team does better overall, and all the agents on the team do well individually, when every agent cooperates).


Proving that a new approach can secure victory in a classic strategy game, a team from England's Southampton University has won the 20th-anniversary Iterated Prisoner's Dilemma competition, toppling the long-term winner from its throne. The Southampton group, whose primary research area is software agents, said its strategy involved a series of moves allowing players to recognize each other and act cooperatively.
The Prisoner's Dilemma is a game-theory problem for two players. As typically described, two accomplices are arrested and separated for interrogation by the police, who give each the same choice: confess to authorities (defect) or remain silent (cooperate). If one defects and the other cooperates, the defector walks free and the cooperator gets 10 years in jail. If both cooperate, both get six months. If both defect, both get six years. Neither suspect knows the other's choice. "The Prisoner's Dilemma is this canonical problem of how to get cooperation to emerge from selfish agents," said Nick Jennings, a professor in computer science at Southampton University and leader of the winning team along with his Ph.D. 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 consistent record of winning the game. Under that strategy, a player's first move is always to cooperate with other players. Afterward, the player echoes whatever the other players do.

The strategy is similar to the one nuclear 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 20th-anniversary competition was the brainchild of Graham Kendall, a lecturer in the University of Nottingham's School of Computer Science and Information Technology and a researcher in game theory, and was based on the original 1984 competition run by a University of Michigan political scientist, Robert Axelrod.

The Iterated Prisoner's Dilemma is a version of the game in which the choice is repeated over and over again and in which the players can remember their previous moves, allowing them to evolve a cooperative strategy. The 2004 competition had 223 entries, with each player playing all the other players in a round robin setup. Because Axelrod's original competition 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 team submitted 60 programs. These, 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. Another twist to the game was the addition of noise, which allowed some moves to be deliberately misrepresented. In the original game, the two prisoners could not communicate. But Southampton's design lets the prisoners do the equivalent of signaling to each other their intentions by tapping 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 impossible to prevent collusion between entrants.

"Ultimately," he said, "what's more important is the research." In Jennings' case, the real interest is agents. "What's interesting from our point of view," he said, "was to test some ideas we had about teamwork in general agent systems, and this detection of working together as a team is a quite fundamental problem. What was interesting was to see how many colluders you need in a population. It turns out we had far too many -- we would have won with around 20." 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. 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 Rapoport, who won the Axelrod competition. So if you can win the 20th-anniversary one, in our field there's a certain historical significance."

No comments:

Post a Comment