Rationalizability

Rationalizability
A solution concept in game theory
Relationships
Superset of	Nash equilibrium
Significance
Proposed by	D. Bernheim and D. Pearce
Example	Matching pennies

In game theory, rationalizability is a solution concept. The general idea is to provide the weakest constraints on players while still requiring that players are rational and this rationality is common knowledge among the players. It is more permissive than Nash equilibrium. Both require that players respond optimally to some belief about their opponents' actions, but Nash equilibrium requires that these beliefs be correct while rationalizability does not. Rationalizability was first defined, independently, by Bernheim (1984) and Pearce (1984).

Definition

Given a normal-form game, the rationalizable set of actions can be computed as follows: Start with the full action set for each player. Next, remove all actions which are never a best reply to any belief about the opponents' actions -- the motivation for this step is that no rational player could choose such actions. Next, 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. Continue the process until no further actions are 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.

Constraints on beliefs

*Coordination game*
	A	B
a	1, 1	0, 0
b	0, 0	1, 1

Consider a simple coordination game (the payoff matrix is to the right). The row player can play a if she can reasonably believe that the column player could play A, since a is a best response to A. She 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. He can believe that she will play a if it is reasonable for him to believe that she could play a, etc.

*Prisoner's Dilemma*
	C	D
c	2, 2	0, 3
d	3, 0	1, 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.

	L	R
t	3, -	0, -
m	0, -	3, -
b	1, -	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.^[1] 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 every Nash equilibrium is a rationalizable equilibrium; however, the inverse is not true. Some rationalizable equilibria are not Nash equilibria. This makes the rationalizability concept a generalization of Nash equilibrium concept.

*Matching pennies*
	H	T
h	1, -1	-1, 1
t	-1, 1	1, -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 the 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.

Footnotes

↑ Gibbons, Robert (1992). A Primer in Game Theory. pp. 32–33.

References

Bernheim, D. (1984) Rationalizable Strategic Behavior. Econometrica 52: 1007-1028.
Fudenberg, Drew and Jean Tirole (1993) Game Theory. Cambridge: MIT Press.
Pearce, D. (1984) Rationalizable Strategic Behavior and the Problem of Perfection. Econometrica 52: 1029-1050.
Ratcliff, J. (1992–1997) lecture notes on game theory, §2.2: "Iterated Dominance and Rationalizability"

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 12/10/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.