Lecture
Prisoner's dilemma (English: Prisoner's dilemma, the name «bandit's dilemma» is used less often) — a fundamental problem in game theory, according to which rational players will not always cooperate with each other, even if it is in their interest. It is assumed that a player (the «prisoner») maximizes his own payoff, without caring about the benefit of others.
The essence of the problem was formulated by Merrill Flood[en] and Melvin Dresher[en] in 1950. The dilemma was named by the mathematician Albert Tucker.
In the prisoner's dilemma, betrayal strictly dominates cooperation, so the only possible equilibrium is betrayal by both participants. Simply put, whatever the other player's behavior, each player wins more by betraying. Since betraying is more advantageous than cooperating in any situation, all rational players will choose betrayal.
Behaving rationally individually, the participants together arrive at an irrational decision: if both betray, they will receive in total a smaller payoff than if they had cooperated (the only equilibrium in this game does not lead to a Pareto-optimal solution). This is precisely the dilemma.
In the iterated prisoner's dilemma, the game takes place periodically, and each player can «punish» the other for prior non-cooperation. In such a game, cooperation can become an equilibrium, and the incentive to betray can be outweighed by the threat of punishment (as the number of iterations grows, the Nash equilibrium tends toward the Pareto optimum).
In all judicial systems, the punishment for banditry (committing crimes as part of an organized group) is much harsher than for the same crimes committed alone (hence the name «bandit's dilemma»).
The classic formulation of the prisoner's dilemma is as follows:
Two criminals — A and B — were caught at roughly the same time for similar crimes. There is reason to believe that they acted in collusion, and the police, having isolated them from each other, offer them the same deal: if one testifies against the other, and the latter remains silent, then the first is released for assisting the investigation, while the second receives the maximum prison term (10 years). If both remain silent, their act falls under a lighter charge, and each of them is sentenced to six months in prison. If both testify against each other, they receive the minimum term (2 years each). Each prisoner chooses whether to remain silent or testify against the other. However, neither of them knows exactly what the other will do. What will happen?
The game can be represented as the following table:
| Prisoner B remains silent | Prisoner B testifies | |
| Prisoner A remains silent | Both get six months. | A gets 10 years, B is released |
| Prisoner A testifies | A is released, B gets 10 years in prison |
Both get 2 years in prison |
| The «prisoner's dilemma» in normal form. |
The dilemma arises if we assume that both care only about minimizing their own prison term.
Let us imagine the reasoning of one of the prisoners. If the partner remains silent, it is better to betray him and go free (otherwise — six months in prison). If the partner testifies, it is also better to testify against him, in order to get 2 years (otherwise — 10 years) in prison. The strategy of «testifying» strictly dominates the strategy of «remaining silent». Similarly, the other prisoner arrives at the same conclusion.
From the point of view of the group (these two prisoners), it is best to cooperate with each other, remain silent, and get six months each, since this reduces the total term of imprisonment. Any other decision would be less advantageous. This vividly demonstrates that in a non-zero-sum game, the Pareto optimum can be the opposite of the Nash equilibrium.
| Cooperate | Betray | |
| Cooperate | C, C | c, D |
| Betray | D, c | d, d |
| Canonical payoff matrix of the «prisoner's dilemma» |
The game scheme can be developed further by abstracting away from the prisoner subtext. The generalized form of the game is often used in experimental economics. The following rules give a typical implementation of the game:
These rules were established by Douglas Hofstadter and form the canonical description of the typical prisoner's dilemma.
Hofstadter suggested that people find it easier to understand tasks such as the prisoner's dilemma when it is presented as a separate game or trading process. One example is the «closed bag exchange»:
Two people meet and exchange closed bags, understanding that one contains money and the other contains goods. Each player can honor the deal and put in the bag what was agreed, or deceive the partner by giving an empty bag.
In this game, cheating will always be the decision with the maximum short-term material gain.
In some TV game shows, a similar principle is used to determine the winners of a round or the final. An example of the dilemma was demonstrated in 2012 in the British game show The Bank Job in the final of each season: the two players who reached the final had to decide how to dispose of the winnings. Half of the total jackpot at stake lay in cases marked CASH, and the other half in cases containing newspaper scraps marked TRASH (each player had one case of each type). Each player had to take one of their own cases and give it to the other. If both players gave CASH cases, they split the winnings equally. If one gave a TRASH case, he took the entire bank of the game. If both gave TRASH — both were left without money, and the winnings went to the players who had been eliminated at earlier stages of the final.
The examples with prisoners, a card game, and an exchange of closed bags may seem contrived, but in reality there are many examples of interactions among people and animals that have the same payoff matrix. That is why the prisoner's dilemma is of interest to the social sciences, such as economics, political science and sociology, as well as to branches of biology — ethology and evolutionary biology. Many natural processes have been generalized into models in which living creatures participate in endless games of the prisoner's dilemma type. Such broad applicability gives this game considerable importance.
In political realism, for example, the dilemma scenario is often used to illustrate the problem of two states involved in an arms race. Both states will claim that they have two options: either increase military spending or reduce armaments. In doing so, the postulates of the prisoner's dilemma are obviously satisfied (D > C > d > c) :
From side A's point of view, if side B does not arm, then for A the choice is between D and C — it is better to arm. If B arms, then for A the choice is between d and c — again, it is more advantageous to arm. Thus, whatever B chooses, it is more advantageous for side A to arm. The situation for side B is entirely analogous, and as a result both sides will strive for military expansion.
William Poundstone, in his book about the prisoner's dilemma, describes a situation in New Zealand where newspaper boxes are left unlocked. A newspaper can be taken without paying for it, but few people do so, because most people recognize the harm that would result if everyone stole newspapers. Since the prisoner's dilemma in its pure form is simultaneous for all players (no one can influence the decisions of the others), this common line of reasoning is called «magical thinking». As an explanation for the absence of petty theft, magical thinking also explains voluntary voting in elections (when a non-voter is considered a free rider). Alternatively, this behavior can be explained by the expectation of future actions (and need not be linked to «magical thinking»). Modeling future actions requires adding a dimension of time, which is done in the iterated dilemma.
The theoretical conclusion of the dilemma is one of the reasons why plea bargaining is prohibited in many countries. Often the dilemma scenario is repeated very precisely: it is in the interest of both suspects to confess and testify against the other suspect, even if both are innocent. Perhaps the worst case is when only one is guilty, in which case the innocent person is unlikely to confess to anything, while the guilty one will do so and give testimony against the innocent one.
Many real-life dilemmas involve multiple players. Although metaphorical, Hardin's «tragedy of the commons» can be viewed as a generalization of the dilemma for multiple players. Each resident of the community chooses whether to graze livestock on the common pasture and gain a benefit by depleting its resources, or to limit their own income. The collective outcome of universal (or frequent) maximal use of the pasture is low income (leading to the destruction of the community). However, this game is not formal, since it can be broken down into a sequence of classic 2-player games.
In his 1984 book «The Evolution of Cooperation», Robert Axelrod explored an extension of the dilemma scenario, which he called the iterated prisoner's dilemma (IPD). In it, participants make a choice again and again and remember previous outcomes. Axelrod invited academic colleagues from around the world to develop computer strategies to compete in an IPD tournament. The programs entered differed in algorithmic complexity, initial hostility, capacity for forgiveness, and so on.
Axelrod discovered that when the game was repeated for a long time among many players, each with different strategies, «greedy» strategies performed poorly in the long run, whereas more «altruistic» strategies performed better, from the standpoint of self-interest. He used this to demonstrate a possible mechanism for the evolution of altruistic behavior out of mechanisms that are initially purely selfish, through natural selection.
The best deterministic strategy turned out to be «Tit for Tat», developed and entered into the tournament by Anatol Rapoport. It was the simplest of all the participating programs, consisting of just 4 lines of code in the BASIC language. The strategy is simple: cooperate on the first iteration of the game, after which the player does the same thing the opponent did on the previous move. A slightly better performer is the «Tit for Tat with forgiveness» strategy. When the opponent defects, on the next move the player sometimes, regardless of the previous move, cooperates with a small probability (1—5%). This allows a random way out of the cycle of mutual defection. It works best when misunderstanding is introduced into the game — when one player's decision is communicated to the other with an error.
Analyzing the strategies that achieved the best results, Axelrod named several conditions necessary for a strategy to achieve a high score:
Thus, Axelrod arrived at the utopian-sounding conclusion that selfish individuals, for the sake of their own selfish good, will tend to be nice, forgiving, and non-envious.
Let us consider the arms race model again. It was concluded that the only rational strategy is to arm, even if both countries would rather spend GDP on butter than on guns . Interestingly, attempts to demonstrate that the dilemma's conclusion works in practice (by analyzing «high» and «low» military spending between periods, based on IPD assumptions) often show that such behavior does not occur (for example, Greek and Turkish military spending does not change in accordance with the «tit for tat» strategy, but most likely follows domestic politics). This may be an example of rational behavior differing between single-move and multi-move games.
If in a single-move game the strategy of defecting dominates in any case, then in a multi-move game the optimal strategy depends on the behavior of the other participants. For example, if everyone in a population deceives everyone else, and one person behaves according to the «tit for tat» principle, he ends up at a slight disadvantage due to the loss on the first move. In such a population, the optimal strategy is to always defect. If, however, the number of those professing the «tit for tat» principle is greater, then the outcome depends on their share of society.
The optimal strategy can be determined in two ways:
Although the «tit for tat» strategy was considered the most successful simple strategy, a team from the University of Southampton led by Professor Nicholas Jennings presented a new strategy for the 20th anniversary of the IPD Championship. This strategy proved more successful than «tit for tat». It was based on interaction between programs in order to obtain the maximum score for one of them. The university entered 60 programs in the championship, which recognized each other by a sequence of actions during the first 5—10 moves. Having recognized another, one program would always cooperate while the other would defect, which gave the defector the maximum score. If a program understood that its opponent was not from Southampton, it would then defect against it the whole time, in order to minimize the opponent's result. As a result , this strategy took the first three places in the competition, as well as several places in a row below that.
Although this evolutionarily stable strategy proved more effective in the competition, this was achieved due to the fact that in this particular competition a team could participate with several agents. If a player can control only one agent, «tit for tat» turns out to be the best. It also complies with the rule prohibiting communication between players. The fact that the Southampton programs performed a «ritual dance» in the first 10 moves in order to recognize each other only confirms how important communication is in shifting the balance of the game.
If the IPD is played exactly N times (some known constant N), there is another interesting fact. The Nash equilibrium is to always defect. We prove this by induction: if both cooperate, on the last move it is advantageous to defect, since the opponent will then have no opportunity to retaliate. Therefore, both will defect against each other on the last move. Since the opponent will defect on the last move in any case, any player will want to defect on the second-to-last move, and so on. For cooperation to remain advantageous, the future must be uncertain for both players. One solution is to make the number N random and calculate results based on the average payoff per move.
The prisoner's dilemma is fundamental to some theories about human interaction and trust. From the assumption of the dilemma model that a transaction between two people requires trust, trusting behavior in populations can be modeled using a multi-player iterated version of the game. This has inspired many scientists for years. In 1975, Grofman and Pool estimated the number of works devoted to this topic at around 2,000.
If players can assess the likelihood of betrayal by other players, their behavior is influenced by experience. Simple statistics show that inexperienced players usually behave excessively well or badly. If they continue to act this way all the time, they will lose because of their excessive aggressiveness or excessive kindness. As they gain more experience, they assess the probability of betrayal more realistically and achieve better results. Early rounds have a stronger effect on inexperienced players than later ones do on experienced players. This is an example of why early experience has such an influence on the young, and why they are particularly vulnerable to unmotivated aggression, sometimes becoming the same way themselves.
The likelihood of betrayal in a population can be reduced through cooperation in early games, allowing trust to be built . Consequently, self-sacrifice can, in some situations, boost the group's morale. If the group is small, positive behavior is more likely to be reciprocated, which encourages individuals toward further cooperation. This is related to yet another dilemma, namely that kindness without cause is indulgence, which can worsen moral qualities.
These processes are the main field of interest for reciprocal altruism, group selection, kin selection, and ethics.
Religious beliefs significantly increase the degree of cooperation between players. In studies conducted, even an implicit mention of religious words in a preliminary task before the game led to a significant increase in prosocial behavior .
Comments