NECSI Resources

 International Conference on Complex Systems (ICCS2007)

A CAS for Finding the Best Strategy for Prisoner’s Dilema

Mirsad Hadzikadic
UNC Charlotte

Min Sun
Department of Computer Science, UNC Charlotte

     Full text: PDF
     Last modified: September 13, 2007

Abstract
A CAS for Finding the Best Strategy for Prisoner’s Dilema
Mirsad Hadzikadic and Min Sun
College of Computing and Informatics
UNC Charlotte

Prisoner’s Dilemma (PD) is a typical type of non-zero-sum game in game theory. Since first raised by Merrill Flood and Melvin Dresher in 1950’s, a lot of research has been done in this area, especially after Robert Axelrod introduced the concept of the iterated prisoners dilemma in his book “The Evolution of Cooperation” in 1984. In this project, we have explored a complex adaptive system (CAS) designed for finding the “best” strategy for playing PD. The winning strategy depends on the starting conditions. After running the system for a while, an interesting pattern emerges. First, there is an initial consolidation of starting strategies. Second, one (and the same) strategy emerges as the favorite one in the middle of the run. In the end, however, either Tit-for-Tat or “History-Matters” wins the “minds” of the agents. Both of those strategies are of the “cooperate” flavor.

The simple representation mechanism we deployed used only five genes to implement all previously reported strategies, in addition to many new ones. The agents randomly adopted strategies and then played each other until a winning strategy emerged as the “consensus” strategy in the society of agents. Some agents were given the ability to record outcomes of a randomly selected number of previous matches. Consequently, the society included agents with both differing and similar strategies (e.g., identical strategies with parameters like “depth of memory” slightly modified) that allowed various strategies to be tested against each other, including themselves.

The results have shown that
1. The “first-principles” based knowledge representation allowed us to produce and test “all possible” (within the representational framework) strategies.
2. A “consensus” (cooperate) strategy emerges after a long run, even though it is not always exactly the same one.
3. All winning strategies have a similar pattern during the run.
4. All strategies contribute to the “winning” strategy (context dependency).

The future work will include evaluation of aggregated strategies hoping to demonstrate the “wisdom of the crowds” phenomenon.







Maintained by NECSI Webmaster Copyright © 2000-2007 New England Complex Systems Institute. All rights reserved.