Game theory and the Prisoner's Dilemma The Prisoner's dilemma is an old game theory problem invented in 1950 by A.W. Tucker. Two burglars, Bob and Al, are captured near the scene of a burglary and are interogated separately by the police. Each has to choose whether or not to confess and implicate the other. - If neither man confesses, then both will serve one year on a charge of carrying a concealed weapon. - If each confesses and implicates the other, both will go to prison for 10 years. - If one burglar confesses and implicates the other, and the other burglar does not confess, the one who has collaborated with the police will go free, while the other burglar will go to prison for 20 years on the maximum charge. What should Bob do to minimize his time in jail? If Al cooperates and keeps quiet, Bob should defect and confess, setting him free. If Al defects and confesses, he should also defect and confess, avoiding the maximum charge of 20 years. Does this mean it is wise to always defect? Not necessarily. In social or business interactions, we remember the previous strategies of our "partners" and adopt our own strategy accordingly. The game is played over many rounds. This is called the iterated Prisoner's Dilemma. The Tournament Robert Axelrod had the idea to run a computer tournament for the Prisoner's Dilemma. He asked a few people to provide strategies for computer programs playing against each other. There were 14 entries, one program for example used stochastical models (Markov processes) to predict the behavior of its opponent. There also was one programm with totally random output. Tit for Tat Tit for Tat is said to be - nice: because it cooperates on the first move - reciprocal: because it retaliates a defection with its own defection - forgiving: because it goes back to cooperation if the opponent cooperates Genetic Algorithms In the 1970's John Holland and others developed a software technique which mimicks evolutionary processes. Evolving "Tit for Tat" by computer simulation Axelrod tried if the Tit for Tat strategy would appear when running a genetic algorithm. There is much more to it, but I better stop short now. Most of it out of http://www-personal.umich.edu/~axe/research/Evolving.pdf
