| |
|
Axelrod's Tournament: Introduction |
[top] |
The Prisoners' Dilemma (PD) game gets its name from
the scenario where two people are arrested for some crime and are questioned
separately. Each is given the opportunity to either cooperate with his/her
accomplice and not give any information to the police, or defect against
his/her partner by ratting to the police in exchange for some kind of
immunity.
A game is constructed to mimic this situation by
providing payoffs to the players based on how they both respond. A typical
payoff is to give 3 points to each if they both cooperate (police have no
case against the criminals and can only get them for a very light crime). If
one cooperates, and the other defects, the defector gets 5 points, while
his suckered partner receives none. If both players defect, they each only
receive 1 point (police get them for a moderate crime, but not as severe
as if only one person had taken the blame.)
The total payoff to both players is
greatest for mutual cooperation (6 pts), while a cooperate-defect play
results in 5 pts, and mutual defection only hands out 2 pts. So, clearly,
it is best for the collective system if all players cooperate, but here is
the interesting paradox. Each player individually is better off by
defecting in any given situation. If your partner cooperates, you can get
3 points by cooperating back, but you can get 5 by defecting. Similarly,
if your partner defects, you get nothing if you cooperate, but you can
still salvage 1 point by defecting back.
The extension of the PD game to permit repeated PD game play between players
is known as the Iterated Prisoner's Dilemma (IPD) game. In 1979
Robert Axelrod (University of Michigan) hosted a tournament to see what kinds
of strategies would perform best over the long haul in the IPD game. Various
game theorists were solicited for IPD strategies in the form of computer
algorithms, and the submitted strategies were then pitted against each other
in repeated round-robin PD game play. The strategy that received the highest
total payoff from this repeated PD game play was declared the winner of the
tournament. |
|
| Software Description |
[top] |
This demonstration software ("demo") features a library of
commonly used types of agents (strategies) for playing the IPD game as well as a wide variety
of other iterated two-person games. The demo allows a user to host his or her
own tournament by selecting the number and types of agents
present in the tournament player pool, the payoffs that the agents receive as
a result of their game play moves, and the total number of iterations in the
tournament. The demo then runs the tournament and presents the user with
detailed results from the tournament.
Available Features:
- User-Friendly Interface. The Graphical User Interface (GUI) allows
the user to configure the tournament in a point-and-click environment. Current configuration
settings can be saved (as a binary file) by clicking on either the "Save Configuration" or the
"Save Configuration As" options in the File menu. The saved configuration settings can then be
uploaded and used at a later time by clicking on the "Load Configuration" File menu option.
- Library of 16 Agent Types.
The user specifies the population of agents to be entered into the tournament
by clicking on the menu tab marked "Agent."
This brings up, on the left, a library of 16 available agent types. These agent types
possess a wide range of "traits" to let the user
create a tournament with a very unique personality. The library includes
various agent types that are responsive to the play of rivals and others (such as
"Always Cooperate" and "Random") that are not. The agent types also differ
along various other dimensions: e.g., nice (initial cooperation) or mean
(initial defection), forgiving or vengeful, and so forth. When the user
clicks on one of the 16 listed agent types, a screen on the right is activated.
This screen provides a verbal description of the strategy for this agent type. It also contains
a "Count" box within which the user can
set the integer number of agents of this type to be entered into the tournament.
In addition, it allows the user to associate with this agent type either the
default payoff matrix or a user-customized payoff matrix (see below).
- Customizable Payoff Matrix. The user can specify and
save a variety of customized payoff matrices by clicking on the main screen
button marked "Payoffs." This action opens a payoff matrix screen in which the user can adjust the
payoffs corresponding to each of the four possible combinations of
actions in any particular game play: CC, CD, DC, DD.
For example, increasing the payoff for temptation DC (defecting against a
cooperative rival) or sucker CD (cooperating against a defecting rival)
could lead to higher rewards for agents that fall into alternative
cooperate-defect cycles than for agents that attain mutual cooperation. Also,
changing the payoffs allows the user to experiment with other forms of two-player
games such as Chicken or Stag Hunt.
- Type-Specific Payoff Matrix.
As noted above, as part of the process of agent specification the user can assign a
specific user-customized payoff matrix to a specific type of agent.
For example, the user can test an environment in which one type of agent is more
highly rewarded for cooperation than other types of agents.
- Variable Number of Iterations. The user can specify the integer number (between 1 and 100)
of iterated game plays between matched agent pairings by clicking on the main screen button marked "Options."
This action opens an options screen that includes an entry box marked "Tournament Iterations."
- Pseudo-Random Number Seed Setting and Capture. The user can specify the seed value for the pseudo-random number generator by clicking on the main screen button marked "Options." This action opens an options screen that permits the user to set the seed value. If no random seed is specified, the system default is to use the system clock. The seed value used for each tournament run can be saved in a binary file (together with all other configuration settings) by clicking on either the "Save Configuration" or
the "Save Configuration As" File menu option.
- Variable Speed. The user can control the speed of execution and output display for
each tournament by clicking on the main screen button marked "Options." This action opens an
options screen providing a slide control. Using the slider control to set a faster (slower) game speed
results in more (less) work being performed between each pause for display so that the user
sees fewer (more) intermediate results and the tournament takes less (more) time to run.
- Tournament Rules. Let the total number of agents that
the user has entered into the tournament be denoted by N, and let the number
of iterations the user has specified for the tournament be denoted by I.
When the user then hits the "Start" button, the following
tournament effectively takes place:
- In the first iteration i, a round-robin is conducted in which each distinct
agent pairing is matched for one play of the game. Since there are N[N-1]/2 distinct
agent pairings, this means there are N[N-1]/2 matches in the first iteration and each
individual agent engages in [N-1] game plays.
- This round-robin is repeated for I successive iterations. The end of the Ith iteration
marks the end of the tournament.
- At the conclusion of the tournament, the total number of matches TM (i.e., the total number
of games that have been played between distinct agent pairings) is I x N[N-1]/2.
From the perspective of each of the N individual agents, I x [N-1] is the total number of
games that this agent has participated in. Since two agents
participate in each match, adding up all the game plays from the viewpoint
of individual agents gives N x I x [N-1] = 2 x TM.
- As the demo is running, the "matches" reported in run-time mode
in the lower left of the main demo screen is a counter keeping
track of the number of matches completed so far.
- Graphed Output.
During the execution of the tournament, the user can view the results of the
tournament by clicking on the menu tab labeled "Graph." This brings up a run-time graph
that plots the current cumulated payoff attained by
each agent and each type of agent in each successive iteration. This lets
the user see easily that certain agent types are performing better than
others in the tournament. The user can choose to make
certain agent types invisible by clicking "none" under the agent type's identifier.
The user can also choose to graphically depict either the average performance of an agent type (by
clicking "Show") or the performance of all agents of this type (by clicking "Expand").
- Agent Statistics. After a tournament is completed, the user can
view the final results of the tournament by clicking on the menu tab labeled "Agent Stats."
These results include: Agent type; Agent count; Games played, i.e. the
total number of game plays (TG) engaged in by all agents of a specified type;
Result frequency, i.e. the frequency of play-pairs (CC,CD,DC,DD) for
all agents of a specified type; Total payoff (TP) attained by all agents
of a specified type; Average payoff (AP) attained by agents of a specified type,
calculated as AP = TP/TG.
- Game Records Table. Clicking on the button marked "Game Log" on the
main demo screen at the conclusion of a tournament gives the user access to a complete
game-by-game record of the tournament. This Game Log can be saved to a CVS file that
can be opened by either a text editor or most spreadsheet applications (such as Excel) without
need to copy/paste or import data. The top of the saved Game Log includes a listing
of the number of iterations, the random seed, and the roster of agent types included
in the tournament (including a record of the payoff matrix associated with each agent type).
The Game Log is the only saved file that is user readable.
If you have tried the software and have suggestions about
features that you think would be nice, or if you want to report a bug,
please email me:
chrisdcook@gmail.com. |
|
| Software Downloads
|
[top]
|
| Demo Installation Package |
InstWinIPD_1_2_1.zip |
Includes the setup files necessary to install this demo on your computer. |
| .Net Framework Redistributable |
Microsoft.com |
The .Net framework must be installed on your computer to run this demo. It can be acquired via Windows Update on your computer or at this website. For installation directions or to see if you already have it, see the installation notes. |
| Installation Notes |
WinIPD Install Notes.html |
Provides information for installing the demo, determining if you have the .Net Framework, and installing it if you do not. |
|
|
| Source Code and Implementation
Info |
[top]
|
IMPLEMENTATION: I wrote this demo as a
windows application in C# using Microsoft's Visual Studio .Net.
If you want the source code, the following installer will copy all
the necessary files to your machine:
WinIPD_source_1_2.zip.
ALGORITHM AND INNER WORKINGS: The application is divided into two
projects, a library file that contains the data for the agent types and
payoff matrices, and a windows application that runs the tournament and
interacts with the user.
Each specific agent type in the tournament derives from a base agent class
that contains basic attributes and methods common to all agents, such as
payoff matrix, accumulated payoffs, etc. Each specific agent type augments
the base-class attributes and methods with type-specific
attributes and method implementations, such as history and strategy
algorithms. The Windows application contains code that drives the tournament.
After the user starts the tournament, an array of agents is created as well
as a schedule that lists every matchup that needs to take place in the
tournament. A timer is enabled and, on each tick, a number of matchups are
randomly selected from the schedule and executed. The matched agents are
informed regarding whom they are playing. They then make their moves, the
resulting payoffs are recorded and cumulated, the stats are updated, and the
players add the results to their own personal histories. When all the
matchups listed in the schedule are complete, the timer is disabled and the
final agent stats are displayed. |
|
| Copyright Information
|
[top]
|
This demo is licensed as open source freeware under the
GNU Public License,
Copyright Chris Cook, 2006. Anybody who is interested is allowed to view,
modify, and/or improve upon the code used to produce this demo, but any
software generated using all or part of this code must be released as open
source freeware as well. To view the software license in its entirety,
go here.
|
|
| Feedback |
[top]
|
| You may contact me at
chrisdcook@gmail.com.
I would greatly appreciate your comments and suggestions.
|
