---
title: Game Theory and Mechanism Design
module: Uncertainty
moduleNumber: 4
lessonNumber: 10
order: 410
summary: >
  When outcomes depend on other rational agents, single-agent utility maximization
  no longer suffices. Game theory studies decisions among agents — normal-form games,
  dominant strategies, Nash and maximin equilibria, and repeated games — and mechanism
  design runs the logic backwards, engineering rules (auctions, VCG) so that
  self-interested play produces a good collective outcome. Algorithmic game theory then
  asks whether equilibria can be computed, what selfishness costs society, and how the
  mechanisms deployed at internet scale actually behave.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 17 — Making Complex Decisions; §17.5 Decisions with Multiple Agents: Game Theory"
  - book: AIMA
    ref: "§17.6 Mechanism Design"
---

This builds on [Decision Analysis: Multi-Attribute Utility and Decision Networks](/artificial-intelligence/uncertainty/decision-networks-and-game-theory),
which completed single-agent decision theory — utility over many attributes, decision
networks, and the value of information. All of it assumed a world indifferent to the
agent. Here, outcomes are shaped by _other_ rational agents whose choices depend on
the agent's own, and rational action has to be redefined for that setting.

## Game theory: decisions among agents

Everything so far assumed the world is indifferent to the agent. Now suppose the
outcomes depend on _other_ agents whose decisions are in turn shaped by yours.
[Adversarial search](/artificial-intelligence/search/adversarial-search) handled
one slice of this — turn-taking games of perfect information, solved by minimax.
**Game theory** covers the rest: simultaneous moves and partial observability
(game theorists say _imperfect information_). It serves two purposes. _Agent design_:
compute the best strategy and expected return against rational opponents. _Mechanism
design_: engineer the rules so that selfish play yields a good collective outcome —
the topic of the final section.

### Normal-form games

A **single-move game** — all players choose simultaneously, or at least without
seeing each other's choice — is defined by three parts. **Players** (agents making
decisions), **actions** each player can take, and a **payoff function** giving each
player's utility for every combination of actions. For a single-move game the payoff
function is a matrix, the **normal form** (or **strategic form**).

Consider the **prisoner's dilemma**. Alice and Bob are arrested; each may _testify_
against the other or _refuse_. If both refuse they get one year each; if both
testify, five years each; if one testifies while the other refuses, the testifier
goes free (0 years) and the other serves ten. Utility falls with prison time.

$$
% caption: Prisoner's dilemma payoff matrix; entries are (A, B) utilities in years
% of prison, negated so higher is better. testify strictly dominates refuse for
% both, forcing the (testify, testify) equilibrium at (-5, -5) even though
% (refuse, refuse) at (-1, -1) is better for both.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % header cells
  \node[anchor=center] at (2.4,3.05) {Alice: testify};
  \node[anchor=center] at (4.6,3.05) {Alice: refuse};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,1.9) {Bob:\,testify};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,0.5) {Bob:\,refuse};
  % grid
  \draw[black] (1.3,-0.2) rectangle (5.7,2.6);
  \draw[black] (3.5,-0.2) -- (3.5,2.6);
  \draw[black] (1.3,1.2) -- (5.7,1.2);
  % payoffs
  \node at (2.4,1.9) {A = -5, B = -5};
  \node at (4.6,1.9) {A = -10, B = 0};
  \node at (2.4,0.5) {A = 0, B = -10};
  \node[acc] at (4.6,0.5) {A = -1, B = -1};
  % highlight dominant-strategy equilibrium
  \draw[red, thick] (1.35,1.25) rectangle (3.45,2.55);
  \node[red, anchor=north, font=\scriptsize] at (2.4,-0.35) {equilibrium (both testify)};
\end{tikzpicture}
$$

Each player adopts and executes a **strategy** — game theory's word for a policy. A
**pure strategy** is deterministic (for a single move, just one action); a **mixed
strategy** randomizes, written $[p{:}\, a;\; (1{-}p){:}\, b]$ for "play $a$ with
probability $p$, else $b$." A **strategy profile** assigns a strategy to each player,
and given the profile the **outcome** is a utility for each. A **solution** is a
profile in which every player is playing rationally — and defining "rational" when
each agent controls only part of the outcome is the central problem.

### Dominant strategies and Nash equilibrium

Alice reasons: "If Bob testifies, I get $-5$ by testifying versus $-10$ by refusing —
testify is better. If Bob refuses, I get $0$ versus $-1$ — testify is better again.
So I testify regardless." Strategy $s$ **strongly dominates** $s'$ for a player if
its outcome is better than $s'$ for _every_ choice of the others (weakly if at least
as good everywhere, strictly better somewhere). _testify_ is a **dominant strategy**;
it is irrational to play a dominated strategy or to skip a dominant one. Bob reasons
identically, so both testify and both get $-5$: a **dominant strategy equilibrium**.

An **equilibrium** in general is a profile from which no player can gain by switching
unilaterally, given that the others hold fixed — a local optimum in strategy space.
John Nash proved that _every game has at least one equilibrium_, now called a **Nash
equilibrium**. A dominant strategy equilibrium is always a Nash equilibrium, but many
games have Nash equilibria without any dominant strategy.

The _dilemma_ is that the equilibrium is bad for everyone: $(testify, testify)$ at
$(-5, -5)$ is Pareto-dominated by $(refuse, refuse)$ at $(-1, -1)$, which both
prefer. An outcome is **Pareto optimal** if no other outcome is preferred by all
players, and **Pareto dominated** if some outcome is preferred by all. Yet each
player contemplating _refuse_ sees that switching to _testify_ improves their own
result, so the good outcome is unreachable by rational unilateral play. This
tension recurs throughout the field.

Games can have several Nash equilibria and no dominant strategy. Acme makes game
consoles and must pick Blu-ray or DVD; Best makes software and must pick a format;
both profit if they agree and lose if they clash.

$$
% caption: A coordination game with two pure-strategy Nash equilibria, (bluray,
% bluray) and (dvd, dvd). Neither player has a dominant strategy; if they aim for
% different equilibria both lose, so they must coordinate — the Pareto-optimal
% (bluray, bluray) is the natural focal point.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=center] at (2.4,2.9) {Acme: blu-ray};
  \node[anchor=center] at (4.6,2.9) {Acme: dvd};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,1.85) {Best:\,blu-ray};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,0.5) {Best: dvd};
  \draw[black] (1.3,-0.1) rectangle (5.7,2.5);
  \draw[black] (3.5,-0.1) -- (3.5,2.5);
  \draw[black] (1.3,1.2) -- (5.7,1.2);
  \node[acc] at (2.4,1.8) {A = +9, B = +9};
  \node at (4.6,1.8) {A = -4, B = -1};
  \node at (2.4,0.5) {A = -3, B = -1};
  \node at (4.6,0.5) {A = +5, B = +5};
  \draw[acc, thick] (1.35,1.25) rectangle (3.45,2.45);
  \draw[black, thick] (3.55,-0.05) rectangle (5.65,1.15);
\end{tikzpicture}
$$

Both $(bluray, bluray)$ and $(dvd, dvd)$ are Nash — no unilateral switch helps — but
aiming for different ones is disastrous. Restricting "solution" to the unique
Pareto-optimal Nash equilibrium picks $(bluray, bluray)$; when there is no unique
one, players must **communicate** to coordinate, which is why such **coordination
games** motivate communication in the same way multiagent planning does.

### Mixed strategies and the maximin equilibrium

Some games have _no_ pure-strategy Nash equilibrium. In two-finger Morra, players $O$
and $E$ each show one or two fingers; if the total is odd, $O$ collects, if even, $E$
collects. For any pure profile, whoever is losing wants to switch, so no pure profile
is stable and we need mixed strategies. Which mixed strategy? Von Neumann's answer,
for two-player **zero-sum games** (payoffs sum to zero), is the **maximin** technique.

Pick $E$ as the maximizer with payoff $U_E(e, o)$. Imagine forcing $E$ to reveal her
strategy first, then $O$ best-responds: this is a turn-taking game solvable by
minimax, with value $U_{E,O}$, and since revealing first can only hurt, the true
value satisfies $U \ge U_{E,O}$. Reverse the order — $O$ reveals first — and by the
same argument $U \le U_{O,E}$. Together,

$$
U_{E,O} \;\le\; U \;\le\; U_{O,E}.
$$

Once the first player has fixed a mixed strategy, the second may
as well play a _pure_ strategy, because the expected payoff of any mix is a linear
combination of the pure-action payoffs and can never beat the better pure action. So
if $E$ commits to $[p{:}\, \mathit{one};\; (1{-}p){:}\, \mathit{two}]$, $O$'s two pure
responses give payoffs linear in $p$; $O$ picks the smaller, and $E$ chooses $p$ where
the two lines cross.

$$
% caption: Solving Morra for the even player. With $E$ committed to a mixed strategy
% $[p{:}\text{ one}; (1-p){:}\text{ two}]$, $O$'s two pure responses give payoffs
% linear in $p$ (lines one and two); $O$ minimizes, so $E$ receives the lower
% envelope (heavy) and maximizes it at the crossing $p = 7/12$, where $U = -1/12$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,-2.0) -- (0,2.4) node[above, black] {U};
  \draw[->, black] (0,0) -- (5.0,0) node[right, black] {p};
  \node[anchor=north east, black] at (0,0) {0};
  \node[anchor=north, black] at (4.2,0) {1};
  \draw[black, dashed] (4.2,-2.0) -- (4.2,2.2);
  % O plays one: payoff 5p - 3  (from p=0: -3 to p=1: +2)
  \draw[acc, thick] (0,-1.6) -- (4.2,1.05);
  \node[acc, anchor=west] at (2.7,0.7) {one};
  % O plays two: payoff 4 - 7p  (from p=0: +2.13 to p=1: -1.6)
  \draw[red, thick] (0,1.05) -- (4.2,-1.6);
  \node[red, anchor=east] at (1.3,0.75) {two};
  % lower envelope (heavy) up to crossing then along the other
  \draw[black, very thick] (0,-1.6) -- (2.45,0.0) -- (4.2,-1.6);
  % crossing point p = 7/12
  \fill[black] (2.45,0.0) circle (2.4pt);
  \node[anchor=south west, font=\scriptsize] at (2.45,0.05) {p = 7/12};
\end{tikzpicture}
$$

For Morra the crossing gives $p = 7/12$ and value $-1/12$; solving for $O$ gives
$q = 7/12$ and the same value, so $U = -1/12$ exactly. The strategy
$[7/12{:}\, \mathit{one};\; 5/12{:}\, \mathit{two}]$ is the **maximin equilibrium**,
and it is a Nash equilibrium. Von Neumann's theorem: _every two-player zero-sum game
has a maximin equilibrium in mixed strategies_, and every Nash equilibrium of such a
game is a maximin for both players. The maximin strategy gives two guarantees — no
strategy does better against a well-playing opponent, and it keeps its value _even
if revealed to the opponent_. Finding it reduces to **linear programming**: after
removing dominated pure strategies (possibly repeatedly), the optimal mixed strategy
is the highest intersection of the remaining constraints, solvable in polynomial time.
Non-zero-sum games are harder — enumerate candidate supports, then check each with a
system of equations and inequalities, linear for two players but nonlinear (and hard)
for three or more.

### Worked example: a mixed Nash equilibrium by indifference

The maximin computation above solved a _zero-sum_ game. For a general-sum game the
same lower-envelope picture no longer applies, because the two players are not
dividing a fixed pie, but a mixed Nash equilibrium is found by a closely related
idea — the **indifference principle**. Return to the console coordination game and
strip it to its essentials: two players, Acme and Best, each choose _blu-ray_ (B)
or _dvd_ (D), and both do best when they match.

$$
% caption: A 2x2 coordination game used for the mixed-equilibrium computation.
% Rows are Acme's action, columns Best's; each cell lists (Acme payoff, Best
% payoff). Both pure profiles on the diagonal are Nash equilibria; a third,
% mixed, equilibrium is computed in the text.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=center] at (2.4,2.9) {Best: B};
  \node[anchor=center] at (4.6,2.9) {Best: D};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,1.85) {Acme: B};
  \node[rotate=90, font=\scriptsize, anchor=center] at (0.75,0.5) {Acme: D};
  \draw[black] (1.3,-0.1) rectangle (5.7,2.5);
  \draw[black] (3.5,-0.1) -- (3.5,2.5);
  \draw[black] (1.3,1.2) -- (5.7,1.2);
  \node[acc] at (2.4,1.8) {2, 1};
  \node at (4.6,1.8) {0, 0};
  \node at (2.4,0.5) {0, 0};
  \node[acc] at (4.6,0.5) {1, 2};
\end{tikzpicture}
$$

Both pure profiles $(B, B)$ and $(D, D)$ are Nash: from either, a unilateral switch
drops the switcher from a positive payoff to $0$. The interesting equilibrium is the
mixed one. Let Acme play $B$ with probability $p$ and Best play $B$ with probability
$q$. The equilibrium condition is that _each player is indifferent among the actions
it mixes_ — if one action paid more, the player would shift all its probability
there, and the profile would not be stable.

Best's indifference condition determines Acme's $p$, so compute it first. Best's expected payoff
from playing $B$ is $p \cdot 1 + (1-p)\cdot 0 = p$ (Best gets $1$ only when Acme also
plays $B$). Best's expected payoff from $D$ is $p \cdot 0 + (1-p)\cdot 2 = 2(1-p)$.
Setting them equal,

$$
p \;=\; 2(1 - p) \quad\Longrightarrow\quad 3p = 2 \quad\Longrightarrow\quad p = \tfrac{2}{3}.
$$

By the symmetric computation for Acme's indifference — Acme's payoff from $B$ is
$q \cdot 2 = 2q$, from $D$ is $(1-q)\cdot 1$ — we get $2q = 1 - q$, so $q = \tfrac13$.
The mixed equilibrium is $\big(p = \tfrac23,\; q = \tfrac13\big)$: Acme leans toward
its favourite (B) two-thirds of the time, Best leans toward _its_ favourite (D)
two-thirds of the time, and each is exactly indifferent given the other's mix. Its
value is poor — plugging back, Acme's expected payoff is $2q = \tfrac23$, well under
the $2$ or $1$ of a coordinated pure equilibrium — which is why mixed equilibria in
coordination games are a warning, not a plan: they are what rational play collapses
to when the players cannot agree which pure equilibrium to aim for.

$$
% caption: The indifference computation. Best's payoff to playing B (line B) and to
% playing D (line D) are both linear in Acme's probability p; they cross where Best
% is indifferent, at p = 2/3, which fixes Acme's equilibrium mix. Acme's own
% indifference fixes q = 1/3 by the same construction.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (5.2,0) node[right, black] {p};
  \draw[->, black] (0,0) -- (0,2.7) node[above, black] {Best payof\/f};
  \node[anchor=north east, black] at (0,0) {0};
  \node[anchor=north, black] at (4.2,0) {1};
  \node[anchor=east, black] at (0,2.1) {2};
  \draw[black, dashed] (4.2,0) -- (4.2,2.5);
  % Best plays B: payoff p  (0 at p=0, 1 at p=1 -> height 1.05)
  \draw[acc, thick] (0,0) -- (4.2,1.05);
  \node[acc, anchor=south east] at (4.15,1.0) {play B};
  % Best plays D: payoff 2(1-p) (2.1 at p=0, 0 at p=1)
  \draw[red, thick] (0,2.1) -- (4.2,0);
  \node[red, anchor=south west] at (0.2,1.9) {play D};
  % crossing at p = 2/3 -> x = 2.8, payoff = 0.7
  \fill[black] (2.8,0.7) circle (2.4pt);
  \draw[black, dashed] (2.8,0) -- (2.8,0.7);
  \node[anchor=north, font=\scriptsize] at (2.8,-0.05) {p = 2/3};
\end{tikzpicture}
$$

This support-enumeration method generalizes: to find every equilibrium of a two-player
game, guess which actions each player mixes over (the **support**), write the
indifference equations that make each player indifferent across its support, solve the
linear system, and discard any solution with a negative probability or a profitable
deviation to an action outside the support. It is finite but exponential in the number
of actions — a hint of the complexity result the beyond-the-book section returns to.

### Repeated games

The prisoner's dilemma changes character when it **repeats** and players carry the
history forward; payoffs add over time as in an MDP. If Alice and Bob know they play
_exactly_ 100 rounds, backward induction ruins cooperation: the 100th round has no
future, so both testify; then the 99th has no live future either, and so on down —
$(testify, testify)$ every round, 500 years each.

Change the rules and cooperation revives. If after each round there is a 99% chance
of meeting again, no round is known to be last, and cooperative equilibria exist. Under
**perpetual punishment** — refuse until the other ever testifies, then testify forever —
the future payoff while both cooperate is $\sum_{t=0}^{\infty} 0.99^t \cdot (-1) = -100$,
whereas defecting once nets $0$ now but $\sum_{t=1}^{\infty} 0.99^t \cdot (-5) = -495$
after, so no one deviates. The gentler **tit-for-tat** starts by refusing, then echoes
the opponent's previous move; despite its simplicity it performs well in practice. Changing
the _agents_ rather than the rules works too: finite-state machines with fewer states
than rounds cannot run the backward induction and so may settle into the cooperative
$(refuse, refuse)$ outcome — a case where limited computational power, or being
_believed_ to be limited, is an advantage.

## Mechanism design

Game theory asks: given a game, what is a rational strategy? **Mechanism design** —
sometimes _inverse game theory_ — runs it backward: given that agents pick rational
strategies, what game should we design so that each agent pursuing its own interest
maximizes some _global_ utility?[^aima-md] A market's invisible hand is supposed to
do this automatically; the examples below show it takes deliberate design.
Formally, a **mechanism** is a language of allowable
strategies, a distinguished agent (the **center**) that collects strategy reports, and
an outcome rule, known to all, that maps reports to payoffs.

### Auctions

An **auction** sells goods to a pool of bidders; each bidder $i$ has a value $v_i$ for
the item (a **private value**, as with a broken laser pointer worth $\text{\textdollar}14.83$ to one
collector and nearly nothing to others, or a **common value** like drilling rights
worth the same to all but uncertain). Bidder $i$ bids $b_i$; the highest bid wins, but
the price paid is part of the mechanism's design. An auction is **efficient** if the
goods go to whoever values them most. Two design goals — maximize the seller's revenue,
maximize global utility — overlap, since an efficient auction gives the item to the
highest-valuer.

$$
% caption: Three auction mechanisms compared on the winner's payment and the bidders'
% dominant strategy. The English (ascending-bid) and Vickrey (sealed second-price)
% auctions have a simple truthful dominant strategy; the first-price sealed-bid
% auction does not, forcing bidders to model each other.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[anchor=center, font=\footnotesize] at (2.0,3.5) {English};
  \node[anchor=center, font=\footnotesize] at (5.4,3.5) {First-price sealed};
  \node[anchor=center, font=\footnotesize] at (8.8,3.5) {Vickrey (2nd-price)};
  \draw[black] (0.5,-0.6) -- (0.5,3.0);
  \draw[black] (3.9,-0.6) -- (3.9,3.0);
  \draw[black] (7.3,-0.6) -- (7.3,3.0);
  % row labels
  \node[anchor=west, black] at (-1.9,2.4) {rule:};
  \node[anchor=west, black] at (-1.9,1.3) {winner pays:};
  \node[anchor=west, black] at (-1.9,0.1) {dominant strategy:};
  % English
  \node[anchor=center, align=center] at (2.0,2.4) {bid rises openly\\until one left};
  \node[anchor=center] at (2.0,1.3) {bo + d};
  \node[acc, anchor=center, align=center] at (2.0,0.1) {bid up to vi\\(truthful)};
  % First-price
  \node[anchor=center, align=center] at (5.4,2.4) {one secret bid,\\highest wins};
  \node[anchor=center] at (5.4,1.3) {own bid bi};
  \node[red, anchor=center, align=center] at (5.4,0.1) {shade below vi;\\model rivals};
  % Vickrey
  \node[anchor=center, align=center] at (8.8,2.4) {one secret bid,\\highest wins};
  \node[anchor=center] at (8.8,1.3) {second bid bo};
  \node[acc, anchor=center, align=center] at (8.8,0.1) {bid exactly vi\\(truthful)};
\end{tikzpicture}
$$

The best-known mechanism is the **ascending-bid** or **English auction**: the center
raises the asking price until one bidder remains, who pays their last bid. The dominant
strategy is simple — keep bidding while the price is below $v_i$ — so the winner pays
about $b_o + d$, the runner-up's value $b_o$ plus the increment $d$. It is usually
efficient and revenue-maximizing, but it has drawbacks: an obviously advantaged bidder
scares off competitors, who see they cannot win, and it needs high communication (open
outcry or secure lines for many rounds).

The **sealed-bid auction** cuts communication: each bidder submits one secret bid. But
now there is no simple dominant strategy — you should bid $b_o + \epsilon$ where $b_o$
is your estimate of the highest rival bid if that is below $v_i$, so you must model the
others. Also the highest-$v_i$ bidder may lose, which hurts efficiency but reduces the
advantaged-bidder bias.

The **sealed-bid second-price**, or **Vickrey**, **auction** addresses this: the winner pays
the _second_-highest bid $b_o$, not their own. The utility to bidder $i$ is

$$
u_i = \begin{cases} v_i - b_o & \text{if } b_i > b_o \\ 0 & \text{otherwise,} \end{cases}
$$

and now bidding $b_i = v_i$ is a dominant strategy: when $v_i - b_o > 0$ any winning bid
is optimal and $v_i$ wins; when $v_i - b_o < 0$ any losing bid is optimal and $v_i$
loses. The mechanism is **truth-revealing** with no need to model rivals — one reason
Vickrey-style auctions run billions of times a day in online advertising. Its expected
revenue equals the English auction's, an instance of the **revenue equivalence theorem**:
under mild conditions any auction with risk-neutral bidders whose private values are
drawn from a known distribution yields the same expected revenue, so mechanisms compete
on _other_ qualities.

A mechanism where every agent has a **dominant strategy** is **strategy-proof**; if that
strategy is to reveal $v_i$ truthfully it is **truth-revealing** (or **incentive
compatible**). The **revelation principle** states that any mechanism can be transformed
into an equivalent truth-revealing one, so restricting attention to truthful mechanisms
costs no generality. The other design goal is discouraging **collusion**: in Germany's 1999 spectrum
auction, a "10% minimum raise" rule let one firm's odd opening bid of 18.18M signal
"let's split at 20M and not bid the price up," which the rival read and accepted — a
tacit cartel a sealed-bid first-price auction (no signalling through bids) would have
blocked.

### The tragedy of the commons

Auctions allocate scarce goods. A dual problem is a shared resource that everyone can
exploit for free. Each of 100 countries chooses to reduce pollution at a private cost of
$-10$, or to keep polluting for a private benefit of $-5$ that also imposes $-1$ on
_every_ other country. Polluting dominates: whatever the others do, a country is $5$
better off polluting. So all pollute and each ends at $-5 - 99 = -104$, whereas universal
reduction gives each $-10$. This is the **tragedy of the commons**: an unpriced shared
resource is over-exploited, dragging total utility below what cooperation would reach —
the prisoner's dilemma at scale.

$$
% caption: The tragedy of the commons for 100 countries. Continue-to-pollute strictly
% dominates reduce, so every rational country pollutes and lands at -104; the
% cooperative all-reduce outcome (-10) is far better for everyone but unreachable
% without changing the mechanism to price the externality.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,4.1);
  \node[anchor=south west, black, font=\scriptsize] at (0.1,3.7) {utility per country};
  \draw[black] (-0.12,0) -- (0.12,0);
  % axis ticks
  \node[anchor=east, black] at (-0.1,3.0) {-10};
  \node[anchor=east, black] at (-0.1,0.4) {-104};
  \draw[black, dashed] (0,3.0) -- (5.6,3.0);
  \draw[black, dashed] (0,0.4) -- (5.6,0.4);
  % bars
  \fill[acc!18, draw=acc] (1.0,0) rectangle (2.2,3.0);
  \node[acc, anchor=north, align=center, font=\scriptsize] at (1.6,2.9) {all reduce\\(cooperate)};
  \fill[red!14, draw=red] (3.8,0) rectangle (5.0,0.4);
  \node[red, anchor=south, align=center, font=\scriptsize] at (4.4,0.5) {all pollute\\(dominant, equilibrium)};
\end{tikzpicture}
$$

The remedy is to change the mechanism so that agents pay for the commons — more
generally, to make every **externality** (an effect on global utility not felt in the
agent's own transaction) explicit. Set the prices right and each agent, maximizing its
_local_ payoff, is effectively forced to maximize global utility: a carbon tax is one
such mechanism.

### VCG and strategy-proof allocation

Pricing externalities correctly is the hard part. The **Vickrey-Clarke-Groves (VCG)**
mechanism does it for allocating common goods — say, free wireless transceivers to the
neighborhoods that value them most. Ask each council its value and they will all inflate;
VCG makes truthful reporting a dominant strategy by charging each agent a tax equal to the
loss its presence imposes on everyone else.

> **Algorithm (VCG allocation).** Each agent $i$ reports a value $b_i$. The center picks
> the allocation $A$ maximizing total reported utility $B = \sum_i b_i(A)$, where $b_i(A)$
> is $i$'s reported value if $i$ wins under $A$ and $0$ otherwise. It then computes, for
> each $i$, the others' welfare under $A$, $B_{-i} = \sum_{j \ne i} b_j(A)$, and the best
> welfare achievable _without_ $i$ in the game, $W_{-i}$. Agent $i$ pays the tax
> $W_{-i} - B_{-i}$.

Concretely, a winner pays the highest reported value among the losers it displaced. VCG
is truth-revealing: $i$'s payoff is $v_i(A) - (W_{-i} - B_{-i})$, which since the center
maximizes $\sum_j b_j(A) = b_i(A) + \sum_{j \ne i} b_j(A)$ can be rewritten as
$v_i(A) + \sum_{j \ne i} b_j(A) - W_{-i}$. Because $i$ cannot affect $W_{-i}$ (it depends
only on the others), the only way $i$ steers the center toward what $i$ actually wants is
to report the truth, $b_i = v_i$. Every winner pays less than its value and every loser
values the goods below the tax, so everyone is content: the rules alone steer
self-interested agents to an efficient outcome.

## Algorithmic game theory

AIMA presents game theory and mechanism design as they stood in the classical
economics tradition: Nash's existence theorem, von Neumann's minimax, the VCG
mechanism. Three questions those results leave open became the subject of
**algorithmic game theory**, the field surveyed in the collection edited by Nisan,
Roughgarden, Tardos, and Vazirani.[^agt-nisan] Each takes a theorem the lesson
stated and asks the computational or quantitative follow-up an algorithm designer
must answer.

### Is a Nash equilibrium computable?

Nash proved that _an_ equilibrium always exists, but existence is not an algorithm.
The support-enumeration method used above runs in time exponential in the number of
actions, and for decades no polynomial method was known even for two players. The
resolution is negative and precise. Computing a Nash equilibrium is complete for the
complexity class **PPAD** (Polynomial Parity Arguments on Directed graphs), a class
Papadimitriou introduced in 1994 to capture problems, like Nash, whose _solution is
guaranteed to exist_ by a non-constructive argument. Daskalakis, Goldberg, and
Papadimitriou proved the general case PPAD-complete, and Chen and Deng extended it to
the two-player case.[^agt-ppad] PPAD sits between P and NP; a polynomial-time
algorithm for any PPAD-complete problem would settle all of them at once, and none is
known.

$$
% caption: The complexity of computing a Nash equilibrium. Zero-sum two-player games
% reduce to linear programming and are solvable in polynomial time (von Neumann). The
% general case is PPAD-complete: existence is guaranteed but no polynomial algorithm
% is known, placing it between P and the harder NP-complete problems.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  band/.style={draw, minimum width=62mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[band, draw=acc, text=acc] (p) at (0,2.4) {zero-sum 2-player = linear programming\\polynomial time};
  \node[band] (ppad) at (0,0.9) {general Nash = PPAD-complete\\exists always, no poly algorithm known};
  \node[band, draw=red, text=red] (np) at (0,-0.6) {(harder still: NP-complete search)};
  \draw[->, thick] (p) -- (ppad) node[midway, right=2mm, font=\scriptsize, text=black] {drop zero-sum};
  \draw[->, thick, black] (ppad) -- (np);
\end{tikzpicture}
$$

In practice, _finding_ equilibria is a
genuine obstacle, which pushes applied work toward games with structure (zero-sum,
succinctly represented, or with few players) where equilibrium computation is tractable.

### How much does selfishness cost? The price of anarchy

VCG shows a mechanism can steer selfish agents to a globally good outcome. But most
real systems — road networks, the internet, markets — run with no such mechanism, and
the natural question is how far selfish equilibrium play falls short of the social
optimum. Koutsoupias and Papadimitriou made this quantitative with the **price of
anarchy**: the ratio between the social cost of the worst Nash equilibrium and the
cost of the centrally-optimal outcome.[^agt-poa]

$$
% caption: The price of anarchy is the ratio (worst equilibrium cost) / (optimal
% cost). A ratio of 1 means selfish play is already optimal; a large ratio means
% uncoordinated agents pay a heavy toll. For nonatomic selfish routing with linear
% delays the ratio is exactly 4/3.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,3.4) node[above, black, font=\scriptsize] {social cost};
  \draw[black] (-0.12,0) -- (0.12,0);
  \node[anchor=east, black] at (-0.1,1.4) {opt};
  \node[anchor=east, black] at (-0.1,2.6) {worst eq};
  \draw[black, dashed] (0,1.4) -- (5.6,1.4);
  \draw[black, dashed] (0,2.6) -- (5.6,2.6);
  \fill[acc!18, draw=acc] (1.0,0) rectangle (2.2,1.4);
  \node[acc, anchor=north, font=\scriptsize] at (1.6,1.35) {optimum};
  \fill[red!14, draw=red] (3.6,0) rectangle (4.8,2.6);
  \node[red, anchor=south, font=\scriptsize] at (4.2,2.65) {worst Nash};
  \draw[<->, black] (5.2,1.4) -- (5.2,2.6);
  \node[anchor=west, black, font=\scriptsize] at (5.3,2.0) {ratio};
\end{tikzpicture}
$$

The best-known result is for **selfish routing**. Drivers each choose the route that
minimizes their own travel time; the resulting equilibrium (a **Wardrop
equilibrium**) need not minimize total travel time. Roughgarden and Tardos proved that
when edge delays are linear in congestion, the price of anarchy is exactly $4/3$ — a
selfish population wastes at most a third more time than an optimal routing would, no
matter how complex the network.[^agt-routing] The same analysis explains **Braess's
paradox**, in which _adding_ a road can make everyone's commute longer, because the
new road shifts the selfish equilibrium to a worse point. The price of anarchy turned
mechanism design's promise into a measurable quantity: a bound on how much a system
loses by _not_ having a good mechanism.

### Auctions at internet scale: the generalized second-price auction

The Vickrey auction of the lesson is truthful but was, until recently, rare in
practice. What actually clears billions of transactions a day is the auction for
**sponsored search** — the ranked ad slots beside a search result. Google and Yahoo!
settled on the **generalized second-price (GSP)** auction: bidders submit per-click
bids, slots are assigned in bid order, and each winner pays the next-highest bid down.
GSP looks like a multi-slot Vickrey auction, but Edelman, Ostrovsky, and Schwarz
showed it is _not_ truthful — with multiple slots, a bidder can gain by shading its
bid, so GSP lacks the dominant-strategy property VCG guarantees.[^agt-gsp] They
analyzed its equilibria instead, showing that a particular "locally envy-free"
equilibrium of GSP yields the same outcome and revenue as the truthful VCG mechanism.
The episode is a caution the classical theory does not deliver on its own: the
theoretically clean mechanism (VCG) is not always the one the market adopts, and
analyzing the messy mechanism it _does_ adopt is where much applied mechanism design
now lives.

The common thread: classical game theory established _what_ rational
agents do at equilibrium; algorithmic game theory asks _whether we can compute it_,
_what it costs society_, and _how the mechanisms deployed at scale actually behave_ —
the questions that matter once game theory meets computer systems.

[^aima-md]: **Russell & Norvig**, §16.6 — The Value of Information (VPI, its nonnegativity and order-independence, and the myopic information-gathering agent); §17.5 — Game Theory (normal form, dominant strategies, Nash and maximin equilibria, repeated games); §17.6 — Mechanism Design (auctions, the revenue equivalence and revelation principles, the tragedy of the commons, and VCG).
[^agt-nisan]: **Nisan, Roughgarden, Tardos, and Vazirani** (eds.), _Algorithmic Game Theory_ (Cambridge University Press, 2007) — the founding survey of the field, covering equilibrium computation, the price of anarchy, and mechanism design from a computational standpoint.
[^agt-ppad]: **Papadimitriou** (1994), "On the complexity of the parity argument and other inefficient proofs of existence", _J. Computer and System Sciences_, introduced the class PPAD. **Daskalakis, Goldberg, and Papadimitriou** (2009), "The complexity of computing a Nash equilibrium", _SIAM J. Computing_ (conf. version STOC 2006), proved general Nash PPAD-complete; **Chen and Deng** (2006), "Settling the complexity of two-player Nash equilibria", FOCS, extended it to two players.
[^agt-poa]: **Koutsoupias and Papadimitriou** (1999), "Worst-case equilibria", STACS, introduced the ratio later named the price of anarchy by Papadimitriou (2001).
[^agt-routing]: **Roughgarden and Tardos** (2002), "How bad is selfish routing?", _J. ACM_, proved the price of anarchy for nonatomic selfish routing with linear latencies is exactly 4/3, independent of the network; the analysis also formalizes Braess's paradox (Braess, 1968).
[^agt-gsp]: **Edelman, Ostrovsky, and Schwarz** (2007), "Internet advertising and the generalized second-price auction: selling billions of dollars worth of keywords", _American Economic Review_, showed GSP is not truthful for multiple slots and characterized its locally envy-free equilibrium, which matches the VCG outcome; **Varian** (2007), "Position auctions", _Int. J. Industrial Organization_, gave a concurrent analysis.