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.