Google Case Study

Toward Adaptive Cooperative Behavior

Elpida S. Tzafestas Institute of Communication and Computer Systems Electrical and Computer Engineering Department National Technical University of Athens Zographou Campus Athens 15773, GREECE brensham@softlab.ece.ntua.gr

Abstract

We analyze the Iterated Prisoner’s Dilemma and the performance of GRADUAL, the best behavior found so far. This behavior has the undesirable property of permanent memory, which would be detrimental for stability. As a solution to the permanent memory problem, we propose an adaptive tit-for-tat behavior that uses a self-regulated estimate of the opponent’s friendliness. On a second level, we demonstrate that an additional self-regulation loop, parallel to the first, is necessary to ensure performance comparable to GRADUAL’s. A number of theoretical conclusions are drawn, the most prominent being that the actual cooperative potential of the behavior is the by-product of the double self-regulation loop and that the second regulation loop concerns the parameters that define the temporal dynamics of behavior. Our results trigger a discussion on stability as well as on the nature of the cooperation problem itself.

Usual experiments with IPD strategies are either tournaments or ecological experiments. In tournaments, each strategy plays against all others and scores are summed in the end. In ecological experiments, populations of IPD strategies play in tournaments and successive generations retain the best strategies in proportions analogous to their score sums. The first notable behavior for the IPD designed and studied by Axelrod (Axelrod & Hamilton 1981, Axelrod 1984) is the Tit For Tat behavior (TFT, in short) : Start by cooperating, From there on return the opponent’s previous move. This behavior has achieved the highest scores in early tournaments and has been found to be fairly stable in ecological settings. TFT demonstrates three important properties, shared by most high scoring behaviors in...