Game

Definition(game). A game is a formal representation of a situation in which a number of individuals interact in a setting of strategic interdependence.

• Strategic Interdependence. It means that each individual’s welfare depends not only on her own actions but also on the actions of the other individuals.

4 elements of game.

• The players. Who is involved?
• The rules. Who moves when? What do they know when they move?What can they do?
• The outcomes. For each possible set of actions by the players, what is the outcome of the game?
• The payoffs. What are the players’ preferences (i.e., utility functions) over the possible outcomes?

The Extensive Form

Definition (extensive form). The extensive form captures who moves when, what actions each player can take, what players know when they move, what the outcome is as a function of the actions taken by the players, and the players’ payoffs from each possible outcome.

Graphic Form

Definition (game tree). Like an actual tree, it has a unique connected path of branches from the initial node (also called the root) to each point in the tree.

Definition (information set). An information set is a subset of a particular player’s decision nodes. The interpretation is that when play has reached one of the decision nodes in the information set and it is that player’s turn to move, she does not know which of these nodes she is actually at.

• Partition of decision nodes (mutually exclusive and exhaustive).
• No information set contains both a node and its predecessor.

Natural restriction. At every node within a given information set, a player must have the same set of possible actions.

Definition (perfect recall). Loosely speaking, perfect recall means that a player does not forget what she once knew, including her own actions.

Definition (game of perfect information). A game is one of perfect information if each information set contains a single decision node.

Definition (common knowledge). It is a basic postulate of game theory that all players know the structure of the game, know that their rivals know it, know that their rivals know that they know it, and so on. In theoretical parlance, we say that the structure of the game is common knowledge.

Mathematical form

Formally, a game in extensive form is specified by the collection

$${\mathrm{\Gamma }}_E=\{\mathcal{X},\mathcal{A},I,p(\cdot ),\alpha (\cdot ),\mathcal{H},H(\cdot ),\iota (\cdot ),\rho (\cdot ),u\}.$$

The Normal Form

Definition (strategy). Let ${\mathcal{H}}_i$ denote the collection of player i's information sets, $\mathcal{A}$ the set of possible actions in the game, and $C(H)\subset \mathcal{A}$ the set of actions possible at information set $H$. A strategy for player $i$ is a function $s_i:{\mathcal{H}}_i\to \mathcal{A}$ such that $s_i(H)\in C(H)$ for all $H\in {\mathcal{H}}_i$.

Definition (Normal form representation). ${\mathrm{\Gamma }}_N=[I,\{S_i\},\{u_i(\cdot )\}]$

• Strategy Profile. $s=(s_1,s_2,\dots ,s_I)=(s_i,s_{-i})$, $s\in S,s_i\in S_i$.
• Payoff Function: $u_i(s)$.

Randomized Choices

Definition (pure strategy). A deterministic choice $s_i(H)$ at each of player i's information set $H\in {\mathcal{H}}_i$. Definition (Mixed Strategy). Given player i's (finite) pure strategy set $S_i$, a mixed strategy for player i , ${\sigma }_i:S_i\to [0,1]$, assigns to each pure strategy $s_i\in S_i$ a probability ${\sigma }_i(s_i)\ge 0$ that it will be played, where $\sum _{s_i\in S_i}{\sigma }_i(s_i)=1$.

• Expected utility: von-Neumann-Morgenstern type.
  • $\sigma =({\sigma }_i,{\sigma }_{-i})$
  • $u_i(\sigma )=E_{\sigma }[u_i(s)]=\sum _{s\in S}[{\sigma }_1(s_1){\sigma }_2(s_2)\cdots {\sigma }_I(s_I)]u_i(s)$

Dominant and Dominated Strategies

Definition (Strictly Dominant Strategy). A strategy $s_i\in S_i$ is a strictly dominant strategy for player i in game ${\mathrm{\Gamma }}_N=[I,S_i,u_i(\cdot )]$ if for all $s_i^{\prime }\ne s_i$, we have

$$u_i(s_i,s_{-i})>u_i(s_i^{\prime },s_{-i})$$

for all $s_{-i}\in S_{-i}$.

Definition (Strictly Dominated). A strategy $s_i\in S_i$ is strictly dominated for player i in game ${\mathrm{\Gamma }}_N=[I,S_i,u_i(\cdot )]$ if there exists another strategy $s_i^{\prime }\in S_i$ such that for all $s_{-i}\in S_{-i}$

$$u_i(s_i^{\prime },s_{-i})>u_i(s_i,s_{-i})$$

In this case, we say that strategy $s_i^{\prime }$ strictly dominates strategy $s_i$.

Def (weakly dominated). A strategy $s_i\in S_i$ is weakly dominated for player i in game ${\mathrm{\Gamma }}_N=[I,S_i,u_i(\cdot )]$ if there exists another strategy $s_i^{\prime }\in S_i$ such that for all $s_{-i}\in S_{-i}$

$$u_i(s_i^{\prime },s_{-i})\ge u_i(s_i,s_{-i})$$

with strict inequality for some $s_{-i}$. In this case, we say that strategy $s_i^{\prime }$ weakly dominates strategy $s_i$.

Def (weakly dominant strategy). A strategy is a weakly dominant strategy for player i in game ${\mathrm{\Gamma }}_N=[I,S_i,u_i(\cdot )]$ if it weakly dominates every other strategy in $S_i$.

Nash Equilibrium

Def (Best Response). In game ${\mathrm{\Gamma }}_N=[I,\{S_i\},\{u_i(\cdot )\}]$, strategy $s_i$ is a Best Response for player i to his rivals' strategies $s_{-i}$ if

$$u_i(s_i,s_{-i})\ge u_i(s_i^{\prime },s_{-i})$$

for all $s_i^{\prime }\in S_i$.

Def (Nash Equilibrium). A strategy profile $s=(s_1,\cdots ,s_I)$ constitutes a Nash Equilibrium of game ${\mathrm{\Gamma }}_N=[I,\{S_i\},\{u_i(\cdot )\}]$ if for every $i=1,\dots ,I$,

$$u_i(s_i,s_{-i})\ge u_i(s_i^{\prime },s_{-i})$$

for all $s_i^{\prime }\in S_i$.

Mixed Strategy Nash Equilibrium

Definition (Mixed Strategy Nash Equilibrium). A mixed strategy profile $\sigma =({\sigma }_1,\cdots ,{\sigma }_I)$ constitutes a Nash equilibrium of game ${\mathrm{\Gamma }}_N=[I,\{\mathrm{\Delta }(S_i)\},u_i(\cdot )]$ if for every $i=1,\dots ,I$,

$$u_i({\sigma }_i,{\sigma }_{-i})\ge u_i({\sigma }_i^{\prime },{\sigma }_{-i})$$

for all ${\sigma }_i^{\prime }\in \mathrm{\Delta }(S_i)$.

Proposition 8.D.1. Let $S_i^{+}\in S_i$ denote the set of pure strategies that player $i$ plays with positive probability in mixed strategy profile $\sigma =({\sigma }_1,\dots ,{\sigma }_I)$. Strategy profile $\sigma =({\sigma }_1,\dots ,{\sigma }_I)$ constitutes a Nash equilibrium of game ${\mathrm{\Gamma }}_N=[I,\{\mathrm{\Delta }(S_i)\},u_i(\cdot )]$ if and only if for all $i=1,\dots ,I$,

1. $$u_i(s_i,{\sigma }_{-i})=u_i(s_i^{\prime },{\sigma }_{-i})\text{ for all }{s}_i,s_i^{\prime }\in S_i^{+};$$
2. $$u_i(s_i,{\sigma }_{-i})\ge u_i(s_i^{\prime },{\sigma }_{-i})\text{ for all }{s}_i\in S_i^{+}\text{ and all }{s}_i^{\prime }\notin S_i^{+}.$$

Existence of Nash Equilibrium

Proposition 8.D.2. Every game ${\mathrm{\Gamma }}_N=[I,\{\mathrm{\Delta }(S_i)\},u_i(\cdot )]$ in which the sets $S_1,\dots ,S_I$ have a finite number of elements has a mixed strategy Nash Equilibrium.

Proposition 8.D.3. A Nash Equilibrium exists in game ${\mathrm{\Gamma }}_N=[I,\{\mathrm{\Delta }(S_i)\},u_i(\cdot )]$ if for all $i=1,\dots ,I$,

1. $S_i$ is a nonempty, convex and compact subset of some Euclidean space ${\mathbb{R}}^M$.
2. $u_i(s_1,\dots ,s_I)$ is continuous in $(s_1,\dots ,s_I)$ and quasiconcave in $s_i$.

Prop.8.D.2 and 8.D.3 are sufficient conditions, not necessary.