Nash Equilibrium

A strategy profile $\sigma^* = (\sigma_1^*, \ldots, \sigma_n^*)$ is a Nash equilibrium of a normal-form game $(N, S, u)$ if no player can strictly improve their expected payoff by unilateral deviation:

$u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(\sigma_i, \sigma_{-i}^*) \quad \forall \sigma_i \in \Delta(S_i), \; \forall i \in N$

Notation: $\sigma_{-i}^*$ denotes the strategies of all players except $i$. A strict Nash equilibrium requires strict inequality for all $\sigma_i \neq \sigma_i^*$.

A strategy profile $\sigma$ is an $\varepsilon$-Nash equilibrium if no player can improve their payoff by more than $\varepsilon$:

$u_i(\sigma_i, \sigma_{-i}) \leq u_i(\sigma_i^*, \sigma_{-i}) + \varepsilon \quad \forall \sigma_i \in \Delta(S_i), \; \forall i$

This relaxation is important computationally. While exact Nash equilibria are hard to compute, approximate equilibria may be tractable.

The support of a mixed strategy $\sigma_i$ is the set of pure strategies played with positive probability: $\text{supp}(\sigma_i) = \{s_i \in S_i : \sigma_i(s_i) > 0\}$.

At a Nash equilibrium, every pure strategy in the support of $\sigma_i^*$ yields the same expected payoff (player $i$ is indifferent among them). Any pure strategy outside the support yields equal or lower expected payoff.

A complexity class containing problems whose solutions are guaranteed to exist by parity arguments on directed graphs. The canonical PPAD-complete problem is finding the end of a path in a directed graph where vertices have in-degree and out-degree at most 1, given one endpoint.

In extensive-form games (games with sequential moves), a strategy profile is subgame perfect if it induces a Nash equilibrium in every subgame. This eliminates Nash equilibria that rely on non-credible threats. Found by backward induction in finite games of perfect information.

A Nash equilibrium $\sigma^*$ is trembling-hand perfect if it is the limit of a sequence of totally mixed strategy profiles $\sigma^{(k)}$ (every strategy played with positive probability) that are best responses to each other. This eliminates equilibria that rely on the assumption that opponents never make mistakes.

A correlated equilibrium is a probability distribution $p$ over strategy profiles such that, if a mediator samples $s \sim p$ and privately tells each player their component $s_i$, no player wants to deviate. Formally, for each player $i$ and each $s_i$ with $p(s_i) > 0$:

$\sum_{s_{-i}} p(s_{-i} | s_i) \, u_i(s_i, s_{-i}) \geq \sum_{s_{-i}} p(s_{-i} | s_i) \, u_i(s_i', s_{-i}) \quad \forall s_i' \in S_i$

Every Nash equilibrium is a correlated equilibrium (with product distribution), but correlated equilibria can achieve higher total payoffs. A correlated equilibrium can be computed in polynomial time via a linear program, unlike Nash equilibria.

For a game with a social welfare function $W(s) = \sum_i u_i(s)$, the price of anarchy is:

$\text{PoA} = \frac{\max_{s \in S} W(s)}{\min_{\sigma^* \in \text{NE}} W(\sigma^*)}$

It measures how much social welfare is lost in the worst Nash equilibrium compared to the social optimum. $\text{PoA} = 1$ means all equilibria are socially optimal. Large PoA means selfish behavior can be very costly.