(classic problem)
Definition: Two prisoners are questioned separately about a crime they committed. Each may give evidence against the other or may say nothing. If both say nothing, they get a minor reprimand and go free because of lack of evidence. If one gives evidence and the other says nothing, the first goes free and the second is severely punished. If both give evidence, both are severely punished. The overall (globally) best strategy is for both to say nothing. However not knowing (or trusting) what the other will do, each prisoner's (locally) best strategy is to give evidence, which is the worst possible outcome.
In general, a situation where local optimization leads to the worst possible outcome globally.
See also global optimum, optimization problem.
Note: This problem is in the area of game theory.
Author: PEB
A thorough treatment from Principia Cybernetica including links to a web-based game and related entries and definitions.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 11 September 2006.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "prisoner's dilemma", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 11 September 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/prisonersDilemma.html