Game Theory and Mechanism Design

This builds on Decision Analysis: Multi-Attribute Utility and Decision Networks, 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 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.

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^{\prime }$ for a player if its outcome is better than $s^{\prime }$ 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.

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,

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:one;(1-p):two]$, $O$'s two pure responses give payoffs linear in $p$; $O$ picks the smaller, and $E$ chooses $p$ where the two lines cross.

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:one;5/12: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.

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,

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=\frac{1}{3}$. The mixed equilibrium is $(p=\frac{2}{3},q=\frac{1}{3})$: 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=\frac{2}{3}$, 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.

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?¹ 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{\$}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.

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+ϵ$ 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

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.

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.

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.² 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.³ 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.

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.⁴

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.⁵ 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.⁶ 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.