Extra Games

Games of Incomplete Information

Incomplete information: eg. unknown costs / preferences.

Rationalizability Problem: to consider a player's beliefs about other players' preferences, his beliefs about their beliefs about his preferences, and so on.

Harsanyi's Approach:

• a player's preferences: determined by the realization of a random variable (r.v.)
• actual realization is only observed by the player.
• all observe ex ante prob. distribution.

Bayesian game: Incomplete information $\to$ Imperfect information.

• Nature makes the first move, choosing realizations of the r.v. (player's type), and each player observe's the realization of only his own r.v.

General Formulation of a Bayesian Game

Definition (Bayesian Game). $[I,\{S_i\},\{u_i(\cdot )\},\mathrm{\Theta },F(\cdot )]$.

• $I$ players.
• ${\theta }_i\in {\mathrm{\Theta }}_i$ : player i's type, a r.v. choosing by nature that is observed only by player i . $\mathrm{\Theta }={\mathrm{\Theta }}_1\times \cdots \times {\mathrm{\Theta }}_I$.
• $F({\theta }_1,\dots ,{\theta }_I)$: joint p.d.f. of the ${\theta }_i$'s. common knowledge.
• $s_i({\theta }_i)$: a pure strategy for player i (decision rule) that gives the player's strategy choice for each realization of his type ${\theta }_i$.
• $u_i(s_i,s_{-i},{\theta }_i)$: payoff function for player i.

The related game with imperfect information by Harsany's Approach: $[I,\{{\phi }_i\},\{{\tilde{u}}_i(\cdot )\}]$

• ${\phi }_i$ : player i's pure strategy set. all possible functions: ${\mathrm{\Theta }}_i\to S_i$
• Player i's expected payoff given a profile of pure strategies for the I players $(s_1,\dots ,s_I)$

$${\tilde{u}}_i(s_1,s_{-i})=E_{\theta }[u_i(s_i,s_{-i},{\theta }_i)]$$

Bayesian Nash Equilibrium

Definition (Bayesian Nash Equilibrium). A (pure strategy) Bayesian Nash Equilibrium for the Bayesian game $[I,\{S_i\},\{u_i(\cdot )\},\mathrm{\Theta },F(\cdot )]$ is a profile of decision rules $(s_1(\cdot ),\dots ,s_I(\cdot ))$ that constitutes a Nash Equilibrium of game ${\mathrm{\Gamma }}_N=[I,\{{\phi }_I\},\{{\tilde{u}}_i(\cdot )\}]$.

• That is, for every $i=1,\dots ,I$$${\tilde{u}}_i(s_i,s_{-i})\ge {\tilde{u}}_i(s_i^{\prime },s_{-i})$$for all $s_i^{\prime }(\cdot )\in {\phi }_i$, where ${\tilde{u}}_i(s_i,s_{-i})=E_{\theta }[u_i(s_i,s_{-i},{\theta }_i)].$

Proposition. A profile of decision rules $(s_1(\cdot ),\dots ,s_I(\cdot ))$ is a Bayesian Nash Equilibrium in Bayesian game $[I,\{S_i\},\{u_i(\cdot )\},\mathrm{\Theta },F(\cdot )]$ if and only if, for all i and all ${\overline{\theta }}_i\in {\mathrm{\Theta }}_i$ occurring with positive probability

$$E_{{\theta }_{-i}}[u_i(s_i({\overline{\theta }}_i),s_{-i}({\overline{\theta }}_{-i}),{\overline{\theta }}_i)|{\overline{\theta }}_i]\ge E_{{\theta }_{-i}}[u_i(s_i^{\prime }({\overline{\theta }}_i),s_{-i}({\overline{\theta }}_{-i}),{\overline{\theta }}_i)|{\overline{\theta }}_i]$$

for all $s_i^{\prime }\in S_i$, where the expectation is taken over realization of the other players' random variables conditional on player i's realization of his signal ${\overline{\theta }}_i$.

Sequential Rationality

An important new issue in dynamic games: the credibility of a player's strategy.

Definition (Principle of Sequential Rationality). A player's strategy should specify optimal actions at every point in the game tree.

Backward induction

Definition (Backward induction). (1) determine first for optimal behavior at the "end" of the game; (2) then determine what optimal behavior is earlier in the game given the anticipation of this later behavior.

Definition (Finite Games of Perfect Information). Games in which every information set contains a single decision node and there is a finite number of such nodes.

Prop (Zermelo's Theorem). Every Finite Game of Perfect Information ${\mathrm{\Gamma }}_E$ has a pure strategy N.E. that can be derived through backward induction. Moreover, if no player has the same payoffs at any two terminal nodes, then there is a unique N.E. that can be derived in this manner.

Subgame Perfect Nash Equilibria

Definition (Subgame). A subgame of an extensive form game ${\mathrm{\Gamma }}_E$ is a subset of the game having the following properties:

• It begins with an information set containing a single decision node, contains all the decision nodes that are successors (both immediate and later) of this node, and contains only these nodes.
• If decision node x is in the subgame, then every $x^{\prime }\in H(x)$ is also, where H(x) is the information set that contains decision node x.(That is, there are no "broken" information sets.)

Definition (Subgame Perfect Nash Equilibria, SPNE). A profile of strategies $\sigma =({\sigma }_1,\dots ,{\sigma }_I)$ in an I-player extensive form game ${\mathrm{\Gamma }}_E$ is a Subgame Perfect Nash Equilibrium if it induces a Nash equilibrium in every subgame of ${\mathrm{\Gamma }}_E$, i.e., the moves specied in $\sigma$ for information sets within the subgame constitute a Nash equilibrium when this subgame is considered in isolation.

Every SPNE is a N.E., but not every N.E. is subgame perfect.

Proposition. Every finite game of perfect information ${\mathrm{\Gamma }}_E$ has a pure strategy SPNE. Moreover, if no player has the same payoffs at any two terminal nodes, then there is a unique SPNE.

SPNE: Multiple Equilibria

Multiple SPNE: Behavior earlier in the game could depend on which equilibrium resulted after entry.

SPNE: Nested Subgames

Definition (nested subgame). A game with imperfect information may in general have many subgames, with one subgame nested within another, and that larger subgame nested within a still larger one, and so on.

Proposition. Consider an $I$-player extensive form game ${\mathrm{\Gamma }}_E$ involving successive play of T simultaneous-move games, ${\mathrm{\Gamma }}_N^t=[I;\{\mathrm{\Delta }(S_i^t)\},\{u_i^t)\}]$ for $i=1,\dots ,T$, with the players observing the pure strategies played in each game immediately after its play is concluded. Assume that each player's payoff is equal to the sum of her payoffs in the plays of the $T$ games. If there is a unique Nash equilibrium in each game ${\mathrm{\Gamma }}_N^t$, say ${\sigma }^t=({\sigma }_1^t,\dots ,{\sigma }_I^t)$, then there is a unique SPNE of ${\mathrm{\Gamma }}_E$ and it consists of each player $i$ playing strategy ${\sigma }_i^t$ in each game ${\mathrm{\Gamma }}_N^t$ regardless of what has happened previously.