Rationalizable strategy

Last updated
Rationalizability
A solution concept in game theory
Relationship
Subset of Dominant strategy equilibrium
Superset of Nash equilibrium
Significance
Proposed byD. Bernheim and D. Pearce
Example Matching pennies

Rationalizability is a solution concept in game theory. It is the most permissive possible solution concept that still requires both players to be at least somewhat rational and know the other players are also rational, i.e. that they do not play dominated strategies. A strategy is rationalizable if there exists some possible set of beliefs both players could have about each other's actions, that would still result in the strategy being played.

Contents

Rationalizability is a broader concept than a Nash equilibrium. Both require players to respond optimally to some belief about their opponents' actions, but Nash equilibrium requires these beliefs to be correct, while rationalizability does not. Rationalizability was first defined, independently, by Bernheim (1984) and Pearce (1984).

Definition

Starting with a normal-form game, the rationalizable set of actions can be computed as follows:

  1. Start with the full action set for each player.
  2. Remove all dominated strategies, i.e. strategies that "never make sense" (are never a best reply to any belief about the opponents' actions). The motivation for this step is no rational player would ever choose such actions.
  3. Remove all actions which are never a best reply to any belief about the opponents' remaining actions—this second step is justified because each player knows that the other players are rational.
  4. Continue the process until no further actions can be eliminated.

In a game with finitely many actions, this process always terminates and leaves a non-empty set of actions for each player. These are the rationalizable actions.

Iterated elimination of strictly dominated strategies (IESDS)

The iterated elimination (or deletion, or removal) of dominated strategies (also denominated as IESDS, or IDSDS, or IRSDS) is one common technique for solving games that involves iteratively removing dominated strategies. In the first step, at most one dominated strategy is removed from the strategy space of each of the players since no rational player would ever play these strategies. This results in a new, smaller game. Some strategies—that were not dominated before—may be dominated in the smaller game. The first step is repeated, creating a new even smaller game, and so on. The process stops when no dominated strategy is found for any player. This process is valid since it is assumed that rationality among players is common knowledge, that is, each player knows that the rest of the players are rational, and each player knows that the rest of the players know that he knows that the rest of the players are rational, and so on ad infinitum (see Aumann, 1976).

There are two versions of this process. One version involves only eliminating strictly dominated strategies. If, after completing this process, there is only one strategy for each player remaining, that strategy set is the unique Nash equilibrium. [1] Moreover, iterated elimination of strictly dominated strategies is path independent. That is, if at any point in the process there are multiple strictly dominated strategies, then it doesn't matter for the end result which strategies we remove first. [2]

Strict Dominance Deletion Step-by-Step Example:

Figure 0.png

Figure 1 IDSDS.png Figure 2 IDSDS.png Figure 3 IDSDS v2.png Figure 4 IDSDS v2.png

  1. C is strictly dominated by A for Player 1. Therefore, Player 1 will never play strategy C. Player 2 knows this. (see IESDS Figure 1)
  2. Of the remaining strategies (see IESDS Figure 2), Z is strictly dominated by Y and X for Player 2. Therefore, Player 2 will never play strategy Z. Player 1 knows this.
  3. Of the remaining strategies (see IESDS Figure 3), B is strictly dominated by A for Player 1. Therefore, Player 1 will never play B. Player 2 knows this.
  4. Of the remaining strategies (see IESDS Figure 4), Y is strictly dominated by X for Player 2. Therefore, Player 2 will never play Y. Player 1 knows this.
  5. Only one rationalizable strategy is left {A,X} which results in a payoff of (10,4). This is the single Nash Equilibrium for this game.

Another version involves eliminating both strictly and weakly dominated strategies. If, at the end of the process, there is a single strategy for each player, this strategy set is also a Nash equilibrium. However, unlike the first process, elimination of weakly dominated strategies may eliminate some Nash equilibria. As a result, the Nash equilibrium found by eliminating weakly dominated strategies may not be the only Nash equilibrium. (In some games, if we remove weakly dominated strategies in a different order, we may end up with a different Nash equilibrium.)

Weak Dominance Deletion Step-by-Step Example:

Figure 5 IDSDS.png

  1. O is strictly dominated by N for Player 1. Therefore, Player 1 will never play strategy O. Player 2 knows this. (see IESDS Figure 5)
  2. U is weakly dominated by T for Player 2. If Player 2 chooses T, then the final equilibrium is (N,T)

Figure 6 IDSDS.png

  1. O is strictly dominated by N for Player 1. Therefore, Player 1 will never play strategy O. Player 2 knows this. (see IESDS Figure 6)
  2. T is weakly dominated by U for Player 2. If Player 2 chooses U, then the final equilibrium is (N,U)

In any case, if by iterated elimination of dominated strategies there is only one strategy left for each player, the game is called a dominance-solvable game.

Iterated elimination by mixed strategy

There are instances when there is no pure strategy that dominates another pure strategy, but a mixture of two or more pure strategies can dominate another strategy. This is called Strictly Dominant Mixed Strategies. Some authors allow for elimination of strategies dominated by a mixed strategy in this way.

Iterated elimination by mixed strategy example.png

Example 1:

In this scenario, for player 1, there is no pure strategy that dominates another pure strategy. Let’s define the probability of player 1 playing up as p, and let p = ½. We can set a mixed strategy where player 1 plays up and down with probabilities (½,½). When player 2 plays left, then the payoff for player 1 playing the mixed strategy of up and down is 1, when player 2 plays right, the payoff for player 1 playing the mixed strategy is 0.5. Thus regardless of whether player 2 chooses left or right, player 1 gets more from playing this mixed strategy between up and down than if the player were to play the middle strategy. In this case, we should eliminate the middle strategy for player 1 since it's been dominated by the mixed strategy of playing up and down with probability (½,½).


Example 2:

We can demonstrate the same methods on a more complex game and solve for the rational strategies. In this scenario, the blue coloring represents the dominating numbers in the particular strategy.

Mixed Stragety Domination.png







Step-by-step solving:

For Player 2, X is dominated by the mixed strategy ½Y and ½Z.

The expected payoff for playing strategy ½Y + ½Z must be greater than the expected payoff for playing pure strategy X, assigning ½ and ½ as tester values. The argument for mixed strategy dominance can be made if there is at least one mixed strategy that allows for dominance.

Testing with ½ and ½ gets the following:

Expected average payoff of ½ Strategy Y: ½(4+0+4) = 4

Expected average payoff of ½ Strategy Z: ½(0+5+5) = 5

Expected average payoff of pure strategy X: (1+1+3) = 5


Set up the inequality to determine whether the mixed strategy will dominate the pure strategy based on expected payoffs.

u½Y + u½Z ⩼ uX

4 + 5 > 5

Mixed strategy ½Y and ½Z will dominate pure strategy X for Player 2, and thus X can be eliminated from the rationalizable strategies for P2.

For Player 1, U is dominated by the pure strategy D.

For player 2, Y is dominated by the pure strategy Z.

This leaves M dominating D for Player 1.

The only rationalizable strategy for Players 1 and 2 is then (M,Z) or (3,5).

Constraints on beliefs

Coordination game
AB
a1, 10, 0
b0, 01, 1

Consider a simple coordination game (the payoff matrix is to the right). The row player can play a if he can reasonably believe that the column player could play A, since a is a best response to A. He can reasonably believe that the column player can play A if it is reasonable for the column player to believe that the row player could play a. She can believe that he will play a if it is reasonable for her to believe that he could play a, etc.

Prisoner's Dilemma
CD
c2, 20, 3
d3, 01, 1

This provides an infinite chain of consistent beliefs that result in the players playing (a, A). This makes (a, A) a rationalizable pair of actions. A similar process can be repeated for (b, B).

As an example where not all strategies are rationalizable, consider a prisoner's dilemma pictured to the left. Row player would never play c, since c is not a best response to any strategy by the column player. For this reason, c is not rationalizable.

LR
t3, -0, -
m0, -3, -
b1, -1, -

Conversely, for two-player games, the set of all rationalizable strategies can be found by iterated elimination of strictly dominated strategies. For this method to hold however, one also needs to consider strict domination by mixed strategies. Consider the game on the right with payoffs of the column player omitted for simplicity. Notice that "b" is not strictly dominated by either "t" or "m" in the pure strategy sense, but it is still dominated by a strategy that would mix "t" and "m" with probability of each equal to 1/2. This is due to the fact that given any belief about the action of the column player, the mixed strategy will always yield higher expected payoff. [3] This implies that "b" is not rationalizable.

Moreover, "b" is not a best response to either "L" or "R" or any mix of the two. This is because an action that is not rationalizable can never be a best response to any opponent's strategy (pure or mixed). This would imply another version of the previous method of finding rationalizable strategies as those that survive the iterated elimination of strategies that are never a best response (in pure or mixed sense).

In games with more than two players, however, there may be strategies that are not strictly dominated, but which can never be the best response. By the iterated elimination of all such strategies one can find the rationalizable strategies for a multiplayer game.

Rationalizability and Nash equilibria

It can be easily proved that a Nash equilibrium is a rationalizable equilibrium; however, the converse is not true. Some rationalizable equilibria are not Nash equilibria. This makes the rationalizability concept a generalization of Nash equilibrium concept.

Matching pennies
HT
h1, -1-1, 1
t-1, 11, -1

As an example, consider the game matching pennies pictured to the right. In this game the only Nash equilibrium is row playing h and t with equal probability and column playing H and T with equal probability. However, all pure strategies in this game are rationalizable.

Consider the following reasoning: row can play h if it is reasonable for her to believe that column will play H. Column can play H if its reasonable for him to believe that row will play t. Row can play t if it is reasonable for her to believe that column will play T. Column can play T if it is reasonable for him to believe that row will play h (beginning the cycle again). This provides an infinite set of consistent beliefs that results in row playing h. A similar argument can be given for row playing t, and for column playing either H or T.

See also

Footnotes

  1. ↑ Joel., Watson,. Strategy : an introduction to game theory (Second ed.). New York. ISBN   9780393929348.
  2. ↑ Gilboa, I.; Kalai, E.; Zemel, E. (1990). "On the order of eliminating dominated strategies" (PDF). Operations Research Letters. 9 (2): 85–89. doi:10.1016/0167-6377(90)90046-8.
  3. ↑ Gibbons, Robert (1992). A Primer in Game Theory. pp. 32–33.

Related Research Articles

An evolutionarily stable strategy (ESS) is a strategy that is impermeable when adopted by a population in adaptation to a specific environment, that is to say it cannot be displaced by an alternative strategy which may be novel or initially rare. Introduced by John Maynard Smith and George R. Price in 1972/3, it is an important concept in behavioural ecology, evolutionary psychology, mathematical game theory and economics, with applications in other fields such as anthropology, philosophy and political science.

In game theory, the Nash equilibrium is the most commonly-used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy. The idea of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to his model of competition in an oligopoly.

The game of chicken, also known as the hawk-dove game or snowdrift game, is a model of conflict for two players in game theory. The principle of the game is that while the ideal outcome is for one player to yield, individuals try to avoid it out of pride, not wanting to look like "chickens." Each player taunts the other to increase the risk of shame in yielding. However, when one player yields, the conflict is avoided, and the game essentially ends.

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

A coordination game is a type of simultaneous game found in game theory. It describes the situation where a player will earn a higher payoff when they select the same course of action as another player. The game is not one of pure conflict, which results in multiple pure strategy Nash equilibria in which players choose matching strategies. Figure 1 shows a 2-player example.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round, but after an additional switch the potential payoff will be higher. Therefore, although at each round a player has an incentive to take the pot, it would be better for them to wait. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

In game theory, a player's strategy is any of the options which they choose in a setting where the optimal outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship. A player's strategy will determine the action which the player will take at any stage of the game. In studying game theory, economists enlist a more rational lens in analyzing decisions rather than the psychological or sociological perspectives taken when analyzing relationships between decisions of two or more parties in different disciplines.

<span class="mw-page-title-main">Solution concept</span> Formal rule for predicting how a game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

In game theory, a Bayesian game is a strategic decision-making model which assumes players have incomplete information. Players hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed, for the first time in game theory, for the specification of the solutions to games with incomplete information.

In game theory, normal form is a description of a game. Unlike extensive form, normal-form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations. The normal-form representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, for each player.

In game theory, a dominant strategy is a strategy that is better than any other strategy for one player, no matter how that player's opponent will play. Some very simple games can be solved using dominance. The opposite, intransitivity, occurs in games where one strategy may be better or worse than another strategy for one player, depending on how the player's opponents may play.

In game theory, "guess 2/3 of the average" is a game that explores how a player’s strategic reasoning process takes into account the mental process of others in the game.

In game theory, trembling hand perfect equilibrium is a type of refinement of a Nash equilibrium that was first proposed by Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973. The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them so as to make every other player also indifferent.

Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. A Nash equilibrium is considered payoff dominant if it is Pareto superior to all other Nash equilibria in the game.1 When faced with a choice among equilibria, all players would agree on the payoff dominant equilibrium since it offers to each player at least as much payoff as the other Nash equilibria. Conversely, a Nash equilibrium is considered risk dominant if it has the largest basin of attraction. This implies that the more uncertainty players have about the actions of the other player(s), the more likely they will choose the strategy corresponding to it.

In game theory, the traveler's dilemma is a non-zero-sum game in which each player proposes a payoff. The lower of the two proposals wins; the lowball player receives the lowball payoff plus a small bonus, and the highball player receives the same lowball payoff, minus a small penalty. Surprisingly, the Nash equilibrium is for both players to aggressively lowball. The traveler's dilemma is notable in that naive play appears to outperform the Nash equilibrium; this apparent paradox also appears in the centipede game and the finitely-iterated prisoner's dilemma.

<span class="mw-page-title-main">Simultaneous game</span>

In game theory, a simultaneous game or static game is a game where each player chooses their action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taking turns. In other words, both players normally act at the same time in a simultaneous game. Even if the players do not act at the same time, both players are uninformed of each other's move while making their decisions. Normal form representations are usually used for simultaneous games. Given a continuous game, players will have different information sets if the game is simultaneous than if it is sequential because they have less information to act on at each step in the game. For example, in a two player continuous game that is sequential, the second player can act in response to the action taken by the first player. However, this is not possible in a simultaneous game where both players act at the same time.

In game theory a max-dominated strategy is a strategy which is not a best response to any strategy profile of the other players. This is an extension to the notion of strictly dominated strategies, which are max-dominated as well.

In game theory, a bimatrix game is a simultaneous game for two players in which each player has a finite number of possible actions. The name comes from the fact that the normal form of such a game can be described by two matrices - matrix describing the payoffs of player 1 and matrix describing the payoffs of player 2.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.