Game Theory Syllabus

Define a zero-sum game and give its payoff property.

A zero-sum game is one in which the sum of all players' payoffs is zero (constant) for every outcome; one player's gain exactly equals another's loss. For two players: $u_1 + u_2 = 0$, so $u_2 = -u_1$.

What is a non-zero-sum game?

A non-zero-sum game is one in which the total payoff to all players varies across outcomes, so it is not constant. Cooperation can make all players better or worse off simultaneously; gains and losses need not cancel.

What is the difference between simultaneous and sequential games?

In simultaneous games, players choose their actions at the same time (or without knowing others' choices), typically shown in normal form. In sequential games, players move in a defined order and later players observe earlier moves, typically shown in extensive form.

Define a Nash equilibrium.

A Nash equilibrium is a strategy profile in which no player can increase their payoff by unilaterally changing their own strategy, given the strategies of all other players. Each player's strategy is a best response to the others.

State the formal condition for a strategy profile $s^{*} = (s_i^{*}, s_{-i}^{*})$ to be a Nash equilibrium.

For every player $i$ and every alternative strategy $s_i$: $$u_i(s_i^{*}, s_{-i}^{*}) \geq u_i(s_i, s_{-i}^{*}).$$

What does Nash's existence theorem guarantee?

Every finite game (finitely many players, each with finitely many pure strategies) has at least one Nash equilibrium, possibly in mixed strategies.

What is a dominant strategy?

A dominant strategy is one that yields a payoff at least as good as any other strategy for a player, regardless of what the opponents do. A strictly dominant strategy is strictly better against every opponent profile.

State the condition for strategy $s_i$ to strictly dominate strategy $s_i'$ for player $i$.

For all opponent strategy profiles $s_{-i}$: $$u_i(s_i, s_{-i}) > u_i(s_i', s_{-i}).$$

What is iterated elimination of dominated strategies?

A solution procedure that repeatedly removes strictly dominated strategies for each player. Since a rational player never plays a dominated strategy, removing them can simplify the game and sometimes yield a unique predicted outcome.

In the Prisoner's Dilemma, what is the dominant strategy and the resulting equilibrium?

Defect is the strictly dominant strategy for each player, so the unique Nash equilibrium is (Defect, Defect) — even though (Cooperate, Cooperate) would give both higher payoffs, making it Pareto-inferior.

Define Pareto efficiency (Pareto optimality).

An outcome is Pareto efficient if no player can be made better off without making at least one other player worse off. No alternative outcome Pareto-dominates it.

When does outcome A Pareto-dominate outcome B?

Outcome A Pareto-dominates B if every player is at least as well off under A as under B, and at least one player is strictly better off under A.

Why is a Nash equilibrium not necessarily Pareto efficient?

Because players optimize individually, not collectively. The Prisoner's Dilemma shows the Nash equilibrium (Defect, Defect) is Pareto-dominated by (Cooperate, Cooperate); rational self-interest can lead to collectively suboptimal outcomes.

What is a mixed strategy Nash equilibrium?

A Nash equilibrium in which at least one player randomizes over pure strategies according to a probability distribution, and each player's mixing probabilities make opponents indifferent among the strategies they randomize over.

State the indifference principle used to find a mixed strategy equilibrium.

In a mixed strategy equilibrium, each player chooses probabilities so that every opponent is indifferent among the pure strategies in their support — i.e., all such strategies yield equal expected payoff. A player randomizes only if all supported actions give equal expected payoff.

In a $2\times 2$ game, how do you compute the opponent's mixing probability $p$ using indifference?

Set the player's expected payoff from each of their pure strategies equal as a function of the opponent's probability $p$ and solve for $p$. For example, if action A gives $u_A(p)$ and action B gives $u_B(p)$, solve $u_A(p) = u_B(p)$ for $p$.

How is the expected payoff of a mixed strategy computed?

It is the probability-weighted sum of payoffs over outcomes: $$E[u_i] = \sum_{s} \Pr(s)\, u_i(s),$$ where $\Pr(s)$ is the product of the players' independent strategy probabilities for profile $s$.

What is a Bayesian game (game of incomplete information)?

A Bayesian game is one in which players have private information (their "type") that others do not fully know. Players hold probabilistic beliefs about others' types, and payoffs depend on the combination of actions and types.

What are the key components of a Bayesian game?

Players, actions, a set of types for each player, a common prior probability distribution over types (from Nature's move), belief systems, and payoff functions that depend on actions and types.

Define a Bayesian Nash equilibrium.

A Bayesian Nash equilibrium is a strategy profile (a mapping from each player's type to an action) in which every type of every player maximizes their expected payoff given their beliefs about others' types and the others' strategies. No type can gain by deviating.

What is the role of Nature in a Bayesian game?

Nature is a non-strategic player that makes an initial random move assigning types to players according to the common prior distribution, thereby modeling the uncertainty/incomplete information in the game.

What is a repeated game?

A repeated game is one in which the same stage game (base game) is played multiple times by the same players, allowing strategies to depend on the history of past play and enabling reputation, punishment, and cooperation.

Distinguish finitely repeated from infinitely repeated games.

A finitely repeated game has a known, fixed number of rounds; an infinitely repeated (or indefinitely repeated) game continues indefinitely, often with future payoffs discounted. Cooperation is more sustainable in infinitely repeated games.

State the Folk Theorem for infinitely repeated games.

The Folk Theorem states that in an infinitely repeated game with sufficiently patient players (discount factor close to 1), any feasible payoff profile in which each player receives at least their minimax (individually rational) payoff can be sustained as a subgame-perfect Nash equilibrium.

How is a discounted total payoff computed in an infinitely repeated game?

With per-period payoff $u_t$ and discount factor $\delta \in (0,1)$: $$U = \sum_{t=0}^{\infty} \delta^{t} u_t.$$ A constant payoff $u$ each period sums to $\frac{u}{1-\delta}$.

Why does backward induction cause cooperation to unravel in the finitely repeated Prisoner's Dilemma?

In the last round, defection is dominant; anticipating this, players defect in the second-to-last round, and so on by backward induction. This unravels cooperation, making defection in every round the unique subgame-perfect equilibrium.

What is a subgame-perfect Nash equilibrium?

A subgame-perfect Nash equilibrium is a strategy profile that constitutes a Nash equilibrium in every subgame of the extensive-form game. It is typically found by backward induction and rules out non-credible threats.

What is evolutionary game theory, and how does it differ from classical game theory?

Evolutionary game theory applies game theory to populations of interacting individuals whose strategies evolve over time via natural selection or imitation. It replaces the assumption of full rationality with population dynamics, where successful strategies increase in frequency.

Define an Evolutionarily Stable Strategy (ESS).

An ESS is a strategy that, if adopted by a whole population, cannot be invaded by any rare alternative (mutant) strategy. Once common, it resists displacement because it earns a higher payoff against the population than any mutant does.

State the mathematical conditions for a strategy $x$ to be an ESS against a mutant $y$.

$x$ is an ESS if for all $y \neq x$, either (1) $u(x,x) > u(y,x)$, or (2) $u(x,x) = u(y,x)$ and $u(x,y) > u(y,y)$. The first is the strict Nash condition; the second is the stability condition when payoffs against the incumbent tie.