Rationalizability

In game theory , rationalizability is a solution concept that generalizes the Nash equilibrium . Rationalizability is based on the iterated elimination of those strategies that are never the best answers . Strategies that survive the process of elimination are called rationalizable . Underlying assumptions about the behavior of the players are knowledge of the game structure and the common knowledge of rationality . The concept of rationalization was first formulated independently by Bernheim (1984) and Pearce (1984) and used by Aumann (1987) and by Brandenburger and Dekel (1987).

Research and the main results

Bernheim (1984) and Pearce (1984) investigated the question of which restrictions are imposed on individual expectations of players' behavior solely through the demand for rationality. They investigate which strategies can be rationalized when the players have a common knowledge of the structure of the game and the fact that all players are rational. The restrictions on the behavior of the players are that all behavior must be consistent with this shared knowledge. The key findings in relation to rationalizable strategies are:

1. A strategy can be rationalized when it is the best answer in relation to another rationalizable strategy. It follows:
2. Every strategy that is part of the Nash equilibrium can therefore be rationalized.

Important definitions

The following terms are closely related to the definition of rationalizability.

Expectation

For player i, his expectation with regard to the players' choice of strategy is a probability distribution , where the strategy set for any player is j and the set of probability distributions is above . In this definition, player i expects all players to behave independently of one another ( independent mixing ). ${\displaystyle \textstyle \sigma _{-i}}$ ${\displaystyle \textstyle \sigma _{-i}\in \prod _{j\not =i}\sum \nolimits _{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle \textstyle \sum \nolimits _{j}}$ ${\displaystyle S_{j}}$

Rational player

A rational player only plays strategy when there is a possible expectation as to the strategy choice of the other players for whom the best answer is. The assumption that player i behaves rationally does not say anything about whether the strategy choice of his teammate j is also rational. (After all, an irrational teammate can play anything.) ${\displaystyle \textstyle \sigma _{i}}$ ${\displaystyle \textstyle \sigma _{-i}}$ ${\displaystyle \textstyle \sigma _{i}}$

Best answer

A player i strategy is called a best answer to if for all . ${\displaystyle \textstyle \sigma _{i}\in \sum \nolimits _{i}}$ ${\displaystyle \textstyle \sigma _{-i}}$ ${\displaystyle \textstyle u_{i}(\sigma _{i},\sigma _{-i})\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})}$ ${\displaystyle \textstyle \sigma _{i}^{'}\in \sum \nolimits _{i}}$

Under common knowledge of rationality is understood that:

1. all players are considered completely rational; and
2. general rationality is so-called "shared knowledge" where everyone knows that everyone knows that everyone is rational

act ... That means that the expectation must also be rational. ${\displaystyle \textstyle \sigma _{-i}}$

Note that the players' choice of strategy can differ in the presence and absence of rationality as shared knowledge.

example

The following example is taken from the article by Bernheim (1984).

		Player 2
		${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle b_{3}}$	${\displaystyle b_{4}}$
Player 1	${\displaystyle a_{1}}$	0, 7	2, 5	7, 0	0, 1
	${\displaystyle a_{2}}$	5, 2	3, 3	5, 2	0, 1
	${\displaystyle a_{3}}$	7, 0	2, 5	0, 7	0, 1
	${\displaystyle a_{4}}$	0, 0	0, - 2	0, 0	10, -1

In the presence of rationality as shared knowledge

In this case, player 2 will never choose the strategy because it is not the best answer for any strategy of player 1. But then it is never advantageous for player 1 to play, since this strategy is only profitable in relation to for 1. Strategies and therefore cannot be rationalized. Looking at the remaining strategies, then it should be noted that they are rationalized: while strategies , , , form a cycle of best answers, presents and represents mutually a best answer. ${\displaystyle b_{4}}$ ${\displaystyle a_{4}}$ ${\displaystyle b_{4}}$ ${\displaystyle b_{4}}$ ${\displaystyle a_{4}}$ ${\displaystyle a_{1}}$ ${\displaystyle b_{3}}$ ${\displaystyle a_{3}}$ ${\displaystyle b_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle b_{2}}$

In the absence of common knowledge of rationality

Player 1 has to expect that player 2 will play, in this case the best answer is rational. ${\displaystyle b_{4}}$ ${\displaystyle a_{4}}$

Rationalizability and rationalizable strategy

Rationalizability is defined by a recursion in which strategies that are never the best answer are iteratively eliminated. If the game can be rationalized, the recursion ends in a non-empty set of strategies which represent the best answers to at least one other strategy in this set.

A normal form game is given ; mathematically, rationalizability is defined by the following recursion:

Set . For each and every , ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{i}^{0}}}\equiv \sum \nolimits _{i}}$ ${\displaystyle i}$ ${\displaystyle n\geq 1}$

${\displaystyle \textstyle {\widetilde {\sum \nolimits _{i}^{n}}}={\Bigl \lbrace }\sigma _{i}\in {\widetilde {\sum \nolimits _{i}^{n-1}}}|\exists \sigma _{-i}\in \prod _{j\not =i}\operatorname {conv} (\textstyle {\widetilde {\sum \nolimits _{j}^{n-1}}})}$so that for everyone . ${\displaystyle u_{i}(\sigma _{i},\sigma _{-i})\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})}$ ${\displaystyle \sigma _{i}^{'}\in \textstyle {\widetilde {\sum \nolimits _{i}^{n-1}}}{\Bigr \rbrace }}$

The rationalizable strategies for players are: ${\displaystyle i}$

${\displaystyle R_{i}=\bigcap \nolimits _{n=0}^{\infty }{\widetilde {\sum \nolimits _{i}^{n}}}}$.

Verbally means the amount of surviving strategies after the -th round for all players, and the amount of surviving strategies that represent the best answer to a particular strategy in . The strategies that survive the iterated elimination of the strategies that are never best answer are called a player's rationalizable strategies. ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{-i}^{n-1}}}}$ ${\displaystyle (n-1)}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{i}^{n}}}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{-i}^{n-1}}}}$

Note that the convex hull of is used in the definition of rationalizability . The reason is that player i is unsure which strategies player j will play. It can e.g. B. be that the mixture is not part of , although and are elements of . However, the mix must also be considered. ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{j}^{n-1}}}}$ ${\displaystyle \textstyle \sigma _{j}\in {\widetilde {\sum \nolimits _{j}^{n-1}}}}$ ${\displaystyle \textstyle ({\tfrac {1}{2}}\sigma _{j}^{'},{\tfrac {1}{2}}\sigma _{j}^{''})}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{j}^{n-1}}}}$ ${\displaystyle \textstyle \sigma _{j}^{'}}$ ${\displaystyle \textstyle \sigma _{j}^{''}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{j}^{n-1}}}}$

Bernheim (1984) and Pearce (1984) show that the set of rationalizable strategies is not empty and keeps at least one pure strategy for every i. ${\displaystyle R_{i}}$

example

Given a game in pure strategies:

		Player 2
		${\displaystyle L}$	${\displaystyle R}$
Player 1	${\displaystyle O}$	4, 2	0, 3
	${\displaystyle M}$	1, 1	1, 0
	${\displaystyle U}$	3, 0	2, 2

Status quo

For player 1 applies and for player 2 applies . ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{1}^{0}}}=\sum \nolimits _{1}=\{O,M,U\}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{2}^{0}}}=\sum \nolimits _{2}=\{L.R\}}$

1 round

Strategy O is the best answer to L, U is the best answer to R, L is the best answer to M, R is the best answer to O and U. In summary: Strategies O and U survive for player 1 and L and R for player 2, because they each represent the best answer to at least 1 opposing strategy. In other words: Strategy M is eliminated this round because it is never the best answer. Mathematically: for player 1 and for player 2. ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{1}^{1}}}=\{O,U\}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{2}^{1}}}=\{L,R\}}$

2nd round

L is only the best answer to M but M did not survive the first round. Strategy L is eliminated this round because it is never the best answer to the strategies that survived in the last round. It then applies to player 1 and player 2. ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{1}^{2}}}=\{O,U\}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{2}^{2}}}=\{R\}}$

3rd round

O is only the best answer to L but L did not survive the second round. Strategy O is eliminated this round because it is never the best answer to the strategies that survived the last round. It then applies to player 1 and player 2. ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{1}^{3}}}=\{U\}}$ ${\displaystyle \textstyle {\widetilde {\sum \nolimits _{2}^{3}}}=\{R\}}$

The recursion ends at this point because U and R are mutually best answers.

Iterated elimination of strictly dominated strategies and rationalizability

Iterated elimination of strictly dominated strategies and rationalization in a two-player game

theorem

Rationalizability and iterated elimination of strictly dominated strategies are equivalent in a two-player game.

The starting point of the iterated elimination of strictly dominated strategies (IESDS) is the consideration that rational players never play a dominated strategy , while the starting point of rationalizability is the complementary question: What kind of strategies can a rational player play? ´

A strictly dominated strategy cannot be rationalized; that is, it is never a best answer, no matter what strategies one expects of one's opponents: if is strictly dominated by in relation to , then a strictly better answer than to any in . In summary: A necessary condition for the rationalization of a strategy is that it survives the IESDS process. ${\displaystyle \sigma _{i}^{'}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle \textstyle \sum \nolimits _{-i}}$ ${\displaystyle \sigma _{i}^{'}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle \sigma _{-i}}$ ${\displaystyle \textstyle \sum \nolimits _{-i}}$

Bernheim (1984) and Pearce (1984) show that for games with two players all strategies that remain after IESDS can be rationalized. This is the sufficient condition for the rationalization of a strategy.

example

Consider the example from Bernheim (1984). Here, the sufficient condition is confirmed: the rationalisable strategies , , , , , survive the IESDS because they are not dominated. Strategy is strictly dominated by the mixed strategy (1/3 , 1/3 , 1/3 ). After being eliminated is strictly dominated by . ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle a_{3}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle b_{3}}$ ${\displaystyle b_{4}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle a_{3}}$ ${\displaystyle b_{4}}$ ${\displaystyle a_{4}}$ ${\displaystyle a_{2}}$

Necessary condition is also confirmed: the strategy to survive the IESDS are , , , , , , they are actually rationalized. ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle a_{3}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle b_{3}}$

Using this example, the equivalence between iterated elimination of strictly dominated strategies and rationalizability in a two-person game can be observed.

Iterated elimination of the strictly dominated strategies and (correlated) rationalization in multi-player games

As shown, there is an equivalence between IESDS and rationalization in a two-player game. However, the equivalence between “being strictly dominated” and “never being the best answer” does not have to be valid in multi-person games. So: IESDS and rationalization do not have to be equivalent in multi-person games. The reason lies in the expectation (belief) of the behavior of the other players: if the players expect the others to behave independently (independent mixing), then the equivalence does not apply. Note that independent mixing is already assumed in the definition of the expectation . ${\displaystyle \textstyle \sigma _{-i}\in \prod _{j\not =i}\sum \nolimits _{j}}$

Only in games where the expectation of a correlation of the strategies is made possible (see correlated strategy ) does the equivalence apply again. In this case the definition of expectation needs to be modified: where all possible probability distributions are over . ${\displaystyle \textstyle \sigma _{-i}\in \Delta S_{-i}}$ ${\displaystyle \textstyle \Delta S_{-i}}$ ${\displaystyle S_{-i}}$

example

The following example is taken from Asu Ozdalar's game theory script at MIT. It shows that IESDS are not equivalent in three-person games where no correlated strategy is allowed. In this example, the payouts are the same for all players. Game 1 chooses A or B, Player 2 chooses C or D, and Player 3 chooses for . ${\displaystyle M_{i}}$ ${\displaystyle i=1,2,3,4}$

	C.	D.
A.	8th	0
B.	0	0
${\displaystyle M_{1}}$

	C.	D.
A.	4th	0
B.	0	4th
${\displaystyle M_{2}}$

	C.	D.
A.	0	0
B.	0	8th
${\displaystyle M_{3}}$

	C.	D.
A.	3	3
B.	3	3
${\displaystyle M_{4}}$

It can be observed that there is never the best answer to the strategies of player 1 and player 2: ${\displaystyle M_{2}}$

Let the probability that player 1 choose A be p and the probability that player 2 choose C be q. It is also assumed that p and q are independent of one another. Player 3's payoff , if he plays, is then . ${\displaystyle u_{3}}$ ${\displaystyle M_{2}}$ ${\displaystyle u_{3}(M_{2},p,q)\ =4pq+4(1-p)(1-q)\ =8pq+4-4p-4q}$

If there were a best answer to a particular p and q, then three inequalities should hold: ${\displaystyle M_{2}}$

${\displaystyle 8pq+4-4p-4q\geq u_{3}(M_{1},p,q)=8pq}$ (1)

${\displaystyle 8pq+4-4p-4q\geq u_{3}(M_{3},p,q)=8+8pq-8p-8q}$ (2)

${\displaystyle 8pq+4-4p-4q\geq u_{3}(M_{4},p,q)=3}$ (3)

The following applies from the first two inequalities: and . It follows: . ${\displaystyle p+q\geq 1}$ ${\displaystyle p+q\leq 1}$ ${\displaystyle p+q\ =1}$

If you insert into the third inequality, you get . ${\displaystyle p+q\ =1}$ ${\displaystyle pq\geq 3/8}$

After substituting q with p, we get . ${\displaystyle p^{2}-p+3/8\leq 0}$

After the transformation one obtains and it is clear that the inequality can never hold, thus the best answer is never, no matter what value p takes. ${\displaystyle (p-1/2)^{2}+(3/8-1/4)\leq 0}$ ${\displaystyle M_{2}}$

On the other hand, it is clear that this is not a dominated strategy. ${\displaystyle M_{2}}$

Rationalizability and Nash equilibrium

Nash equilibrium is a rationalizable equilibrium. Only the best answers are played in equilibrium. Non-rational strategies are not the best answers.

However, rationalizable strategy combination does not have to be a Nash equilibrium. The Nash equilibrium requires as a consistency condition that the expectations of the players are actually fulfilled ex post . In other words: in Nash equilibrium, the strategy of player i is optimally given his expectations about player j and for player j it is actually optimal to behave according to the expectations of player i if he himself correctly expects player i to adopt the strategy will choose. A Nash equilibrium is based on a combination of mutually consistent expectations. In a game outcome that results from the choice of rationalizable strategies and that is not a Nash equilibrium, at least one player has false expectations. Rationalizability alone is not a sufficient condition for generating Nash equilibria, because it does not require any probability assessments by the players as common knowledge and thus no consistency of expectations. ${\displaystyle s_{i}}$ ${\displaystyle s_{i}}$

example

Consider the following game battle of the sexes :

		Player 2
		B.	F.
Player 1	F.	0, 0	2, 1
	B.	1, 2	0, 0

There are two pure strategy Nash equilibria in the game. Strategies F and B are rationalizable because F is the best answer to F and B is the best answer to B. Rationalizability allows the prediction that the game will end with (F, B) and that both players will get the payout 0. (F, B) can come about because player 1 thinks player two is playing F and 2 thinks player 1 is playing F. Both predictions make sense because they can be justified by rational predictions about the behavior of the other player - and yet both players will miss each other. This is because the players' likelihood estimate is not shared knowledge.

Rationalizability, Subjective Correlated Equilibrium, and Correlated Equilibrium

Brandenburger and Dekel (1987) have shown in their work that every rationalizable combination of strategies is equivalent to a subjective correlated equilibrium in a two-person game. A subjective correlated equilibrium is a correlated equilibrium in which the ex ante probability estimates of the players do not have to match. An analogous equivalence applies to multi-player games; But it then makes a difference whether the players believe that all other players have to choose their strategies independently of one another or can correlate their choices with one another.

According to Aumann (1987), a game-theoretic analysis that allows players to make different prior probability estimates shows a conceptual inconsistency. He advocates assuming that the players have common prior not only through the moves of nature, but also through the behavior of all players. If one accepts this strict common prior assumption, then only the rationalizable strategies remain those which result in a Nash equilibrium in correlated strategies (see equilibrium in correlated strategies ).

discussion

Rationalizability as a technology is only of limited use to discriminate against plausible solutions, since only a few strategies can often be excluded. It gives a very poor prognosis; it hardly distinguishes between the rationalizable results. In the game of battle of the sexes , all combinations of strategies are conceivable as a result of the choice of rationalizable strategies while there are only two Nash equilibria; the demand for the rationality of expectations does not impose any restrictions on the choice of strategy.

See also

• Game theory
• Solution concept
• Dominant strategy
• Nash equilibrium
• Common Knowledge
• Equilibrium in Correlated Strategies

literature

• Holler / Illing: Introduction to Game Theory , 6th edition, Springer, Berlin 2006
• Gernot Sieg: Game Theory , 3rd edition, Oldenbourg, Munich 2010
• Harald Wiese: Decision and Game Theory , Springer, Berlin 2002
• Robert Gibbons: A Primer in Game Theory , First Edition, Financial Times, Harlow 1992
• Fudenberg, Drew and Jean Tirole: Game Theory , MIT Press, Cambridge, 1993
• Bernheim, D. (1984) Rationalizable Strategic Behavior. Econometrica 52: 1007-1028.
• Pearce, D. (1984) Rationalizable Strategic Behavior and the Problem of Perfection. Econometrica 52: 1029-1050

Web links

• Jim Ratliff's Graduate-Level Course in Game Theory at the University of Arizona
• Game theory script by Prof. Dr. Ana B. Ania at the Ludwig Maximilians University of Munich (PDF; 185 kB)
• Game theory script from Asu Ozdaglar to MIT (PDF; 116 kB)

Individual evidence

1. ↑ Holler / Illing: Introduction to Game Theory, 6th edition, Springer, Berlin 2006, pp. 95–96
2. ↑ ^{a b} Holler / Illing: Introduction to Game Theory, 6th edition, Springer, Berlin 2006, page 97
3. ^ Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, pp. 49-50
4. ^ ^{A b} Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, p. 49
5. ^ Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, pp. 51-52
6. ^ ^{A b} Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, pp. 48-49
7. ↑ ^{a b} Static games with complete information: (PDF; 185 kB) Game theory script by Prof. Dr. Ana B. Ania at the Ludwig Maximilians University in Munich, page 9
8. ↑ Rationalizability and Strict Dominance  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. (PDF; 116 kB) - Asu Ozdaglar's game theory script at MIT  
9. ↑ Holler / Illing: Introduction to Game Theory, 6th edition, Springer, Berlin 2006, page 95
10. ↑ Holler / Illing: Introduction to Game Theory, 6th edition, Springer, Berlin 2006, page 96
11. ↑ ^{a b} Holler / Illing: Introduction to Game Theory, 6th edition, Springer, Berlin 2006, page 98