dominated strategy

In game theory, dominated strategies are options available to players which may be safely discarded as a result of being strictly inferior to other options. In particular, this may allow a large payoff matrix to be reduced to one which can be tackled without appeal to advanced techniques such as linear programming (or fixed point theorems from topology); see, for instance, the analysis of 2×2 payoff matrices in the saddle point writeup.

As an example, consider the zero-sum strategic form game with payoff matrix given by

-2   3   -1
3   -4   5
1   4    2

In this game, each player has three options. However, Player 1 (choosing from the rows) would be ill-advised to ever play strategy 1 when strategy 3 is available since, regardless of Player 2’s choice, the payoff is higher for strategy 3 than strategy 1. Meanwhile, Player 2’s third option (column 3) always offers a larger payoff to Player 1 than column 1, so Player 2 should always prefer their first option. Discarding inferior options, the payoff matrix becomes

3   -4
1   4

and we may proceed as for a 2×2 payoff matrix.

We formalise this result as follows:

Definition: For a payoff matrix A = (a_ij), the ith row dominates the kth row if a_ij ≥ a_kj ∀ j ∈ {1, . . . , n}
The dominance is strict if a_ij > a_kj ∀ j ∈ {1, . . . , n}.

DefinitionFor a payoff matrix A = (a_ij), the jth column dominates the kth column if a_ij ≤ a_ik ∀ i ∈ {1, . . . ,m}
The dominance is strict if a_ij < a_ik ∀ i ∈ {1, . . . ,m}.

If the payoff matrix A' is obtained from A by removal of dominated rows and columns, then the value of A' is the value of A, and there is an optimal strategy on A' that remains optimal on A. If all the removed rows and columns were strictly dominated, then the set of optimal strategies is unchanged from A.

Note that after removal of a row or column, a previously undominated row or column may become dominated and thus can itself be removed. Consider, for instance, a slight alteration to the payoff matrix above:

-2   3   4
3   -4   5
1   4    2

Player 1's strategy 3 no longer dominates strategy 1, since if Player 2 opts for their third strategy, Player 1 is better rewarded by strategy 1. However, this situation will never arise, since strategy 3 is strictly dominated for Player 2 by their first strategy. So we reduce the payoff matrix:

-2   3
3   -4
1   4

Now it is clear that strategy 3 dominates strategy 1 for Player 1, so we discard the first row:

3   -4
1   4

Hence we have arrived at the same game as before- the change made corresponded to an option that was never going to be taken.

Dominated Strategies in the Prisoner's dilemma

Similar analysis can be applied to general sum games, but to equate optimal or rational behaviour with dominant strategies requires acceptance of a particular viewpoint. This is illustrated by the Prisoner's dilemma, a bimatrix game which we consider with the following payoffs:

                                         Defect       Co-operate
                                    +--------------+--------------+
                                    |              |              |
                     Defect         |   1  , 1     |   4  ,  0    |
                                    |              |              |
                                    +--------------+--------------+
                                    |              |              |
                     Co-operate     |   0  , 4     |   3 ,  3     |
                                    |              |              |
                                    +--------------+--------------+

We can analyse the game from the perspective of Player 1 (the row player). In the absence of knowledge of Player 2’s strategy, it is clear that Player 1 should defect, since row 1 dominates row 2 as follows. Supposing Player 2 defects, then Player 1 is better served by also defecting- both are found guilty of the crime, but Player 1 doesn’t incur the penalty for failing to confess. Meanwhile, should Player 2 have co-operated, Player 1 can secure his freedom (and hence the greatest payoff) by defecting. The situation is exactly the same for Player 2, who must also defect (this is reflected in the payoff matrix by column 1 dominating column 2). Thus we arrive at the scenario of mutual defection, with a payoff to each of 1 (which may be interpreted as years of freedom over the next 5 years, say).

Yet there is a sense in which this behaviour is irrational. Even if motivated entirely by self interest, the prisoners prefer the outcome of mutual co-operation to mutual defection (a payoff of 3 each, instead of 1 each). This outcome also corresponds to the greater good, the sum of payoffs being greater for mutual co-operation (6) than for exploiting the other prisoner to secure your freedom (4). The problem is that neither may deviate from the defection strategy alone, for to do so simply gets them an extra year in jail whilst their partner dodges a sentence. To secure the benefits of co-operation, the prisoners require some binding arrangement: honour codes like the mafia omerta or an external authority such as the state to enforce co-operation. Otherwise a prisoner, acting in accordance with self-interest, maximises their personal gain at the cost of the group: by promising to co-operate to secure the other participant’s co-operation, then defecting anyway to collect the higher payoff.

To describe mutual defection as the rational strategy, therefore, is to take the non-cooperative view of games. In this interpretation, players are either unable to negotiate with each other, or simply unable to trust the promises of the others enough to risk being short-changed by a deceptive partner. Each is therefore best served by a strategy which avoids the potential for exploitation, at a probable cost of being able to co-operate for mutual gain. Such a model of rationality in non-cooperative games is captured by the Nash equilibrium.

Part of A survey of game theory- see project homenode for details and links to the print version.