Computer Science Colloquium, 2006-2007

Dana S. Nau
University of Maryland

June 27
, 2007

Title: Accident or Intention: That Is the Question (in the Noisy Iterated Prisoner's Dilemma)

Abstract:
The Prisoner's Dilemma is a well known non-zero-sum game in which two players can cooperate with or betray the other player in order to maximize his/her own payoff.  In its Iterative form (IPD) the game is played repeatedly, giving the players the opportunity to punish or give incentive leading to the possibility of cooperation (see http://en.wikipedia.org/wiki/Prisoner's_dilemma and http://www.prisoners-delemma.com).

The Noisy IPD is a modified version of the famous Iterated Prisoner's Dilemma (IPD) that includes the possibility of accidents or miscommunications. The noise causes standard IPD strategies, such as Tit-for-Tat, to do quite badly.

In this talk, Dr. Nau will describe the DBS algorithm, which builds a model of the the other player's strategy by observing the player's behavior during the game.  DBS uses the model to detect whether anomalies in the other player's behavior represent noise or deliberate changes of strategy; it updates the model whenever it deduces that the other player's strategy has changed; and it uses a dynamic-programming lookahead algorithm to decide what moves it should make.

In the Noisy IPD track of the 2005 Iterated Prisoner's Dilemma competition, DBS placed third out of 165 contestants.  Only two programs did better, and both
used a highly controversial "master-and-slaves" strategy in which a large number of "slave" programs conspired to feed points to their "master" program.

 


Benny Pinkas