Algorithmic Game Theory

Motivation

A network of resistors solves an optimization problem. Nobody tells the electrons what to do; each one moves under a purely local rule, and the current distribution that emerges minimizes energy dissipation over all distributions satisfying Kirchhoff's node law. Add a wire and the network can only become easier to traverse. This is the encouraging case, and Chapter 4 of Frank Kelly and Elena Yudovina's Stochastic Networks (Cambridge University Press, 2014) opens with it.

Road traffic is the discouraging case. Drivers also follow a local rule — take the fastest route — and the pattern that emerges is again characterized by an optimization problem, but not the one anyone wants solved. Braess's paradox is the sharp form of the discrepancy: in a small road network carrying six cars per unit time, every route takes 83 time units at equilibrium; open an extra road, and at the new equilibrium every route takes 92. Building road capacity made everyone slower. The difference from the electrical case is that a driver's choice imposes a delay on everyone else sharing the road and the driver does not pay for it, and correcting that — pricing the externality — is how a decentralized rule can be made to produce good global behaviour. That idea recurs in Chapters 7 and 8 of the book as the basis of Internet congestion control.

Setting

The network is a set $\mathcal{J}$ of $J$ directed links. A route $r$ is a subset of links, and $\mathcal{R}$ is the set of $R$ routes under consideration — not necessarily all physically possible ones. The link-route incidence matrix $A$ has $A_{jr}=1$ when $j \in r$ and $A_{jr}=0$ otherwise. Writing $x_r$ for the flow on route $r$, the flow on link $j$ is

$$y_j=\sum_{r}A_{jr}x_r, \qquad\text{that is } y = Ax.$$

Each link has a delay function $D_j(y_j)$, continuous and increasing in the flow on that link, and the delay along a route is the sum of the delays of its links, $\sum_j D_j(y_j)A_{jr}$. Drivers care only about getting from origin to destination: $\mathcal{S}$ is the set of source–destination pairs, each route $r$ serves exactly one of them, written $s(r)$, and the flow requirement between pair $\sigma$ is $f_\sigma$.

A routing pattern is stable when no driver has an incentive to switch. Definition 4.2 makes this precise: a Wardrop equilibrium is a feasible vector of route flows $x$ such that

$$x_r>0 \;\Longrightarrow\; \sum_{j}D_j(y_j)A_{jr}=\min_{r'\in s(r)}\sum_{j}D_j(y_j)A_{jr'}, \qquad y = Ax .$$

Every route actually carrying traffic is a shortest route, in delay, for the traffic it carries.

Formalization targets

Goal — Theorem 4.3, a Wardrop equilibrium exists

$$\exists\, x \ge 0 \ \text{ with } Hx=f \ \text{ such that } x \text{ is a Wardrop equilibrium.}$$

The goal asserts existence only, for an arbitrary network, arbitrary route set and arbitrary continuous increasing delay functions. It fixes no uniqueness claim, because the equilibrium flows need not be unique even though the link loads are, and no efficiency claim, because Braess's paradox is precisely the statement that the equilibrium is not efficient.

Supporting levels

Kirchhoff's node law as the equations satisfied by the expected reward in the random-walk game of section 4.1; the two Braess networks of Figures 4.4a and 4.4b, with their equilibrium delays $83$ and $92$; convexity of $\int_0^{y}D(u)\,du$ for increasing $D$; the optimization characterization that makes the goal reachable — a minimizer of $\sum_j\int_0^{y_j}D_j(u)\,du$ over the feasible flows is a Wardrop equilibrium; and the exact externality decomposition of the queueing network of section 4.3.1.

Significance

The result itself. Theorem 4.3 is what makes the Wardrop equilibrium a usable object: a traffic model that could fail to have an equilibrium would be describing nothing. Its proof does more than establish existence — it identifies the equilibrium as the solution of a specific convex program, minimizing $\sum_j\int_0^{y_j}D_j(u)\,du$. That function is not the total delay $\sum_j y_jD_j(y_j)$, and the gap between the two is exactly Braess's paradox: selfish routing optimizes the wrong objective. Once the two objectives are written side by side, the fix is readable off them, and it is the fix used in practice — a toll on link $j$ equal to $y_jD_j'(y_j)$, the marginal delay a driver imposes on everyone else, makes the selfish objective coincide with the social one. Section 4.3 then carries the same accounting into queueing and loss networks, where the derivative of the mean cost splits into a term for the delay a customer suffers and a term for the knock-on cost it inflicts.

Formalizing it. Nothing here is open; Wardrop stated the principle in 1952 and Beckmann, McGuire and Winsten gave the optimization formulation in 1956. What the mission produces is a machine-checked model of selfish routing — incidence matrix, link flows, delay functions, the equilibrium condition — and a formal record of Braess's paradox as a concrete pair of networks rather than a story. Mathlib has no traffic or congestion-game theory.

Difficulty

Existence is not a fixed-point argument in the obvious variable: the best-response map of the routing game is not continuous, since a small change in flows can flip which route is shortest and move all the traffic. The book's route is to replace the equilibrium condition by the stationarity conditions of a convex program on a compact feasible set, where existence is routine and the content is the translation. The translation is where the care is needed, and it is stated here as a separate milestone: the first-order conditions say the Lagrange multiplier $\lambda_{s(r)}$ equals the route delay on routes carrying traffic and is a lower bound on the others, which is Definition 4.2 restated.

The subtlety worth naming in advance is that "increasing" is doing real work in two different places. It makes $\int_0^{y}D(u)\,du$ convex, which is what makes the program tractable; and it is what makes each $D_j(y_j)$ interpretable as a price. Neither convexity of $D_j$ itself nor strict monotonicity is needed, and assuming them would be assuming more than the book does.

Formalization scope

Links, routes and source–destination pairs are indexed by finite types. The incidence matrix is real-valued with entries constrained to be $0$ or $1$, matching the book's definition in this chapter (unlike Chapter 3, which allows general non-negative integers). The map from routes to source–destination pairs is given as a function $s$ rather than as the matrix $H$, which is exactly the book's statement that each column of $H$ sums to $1$.

Delay functions are total functions $\mathbb{R}\to\mathbb{R}$, continuous and monotone. This excludes the vertical asymptote that Figure 4.5 permits — a link with a finite capacity at which delay blows up — and that restriction is recorded here rather than left implicit. The equilibrium condition is stated as the inequality "$\text{delay on } r \le \text{delay on } r'$ for every $r'$ serving the same pair", which is Definition 4.2 with the minimum written out; the two are equivalent because $r$ itself serves $s(r)$, and the inequality form avoids having to produce a minimum over a possibly empty set.

The goal is not vacuous: the feasibility hypotheses ($f_\sigma\ge0$, and each source–destination pair served by at least one route) are exactly what makes the feasible set non-empty, and without them the existence claim would be false rather than trivial.

Contributions welcome beyond the listed items: uniqueness of the equilibrium link loads $y$; the marginal-cost toll that aligns the selfish and social optima; Rayleigh monotonicity (Exercise 4.3, that effective resistance does not decrease when a resistance is increased); the price of anarchy for affine delays; and Theorem 4.6 on the derivatives of the loss-network rate of return with respect to offered traffic and capacity.

Selected references

• Frank Kelly and Elena Yudovina, Stochastic Networks, Cambridge University Press, 2014, Chapter 4 (pp. 85–107); Definition 4.2, Theorem 4.3, sections 4.1–4.3. DOI 10.1017/cbo9781139565363
• J. G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers 1 (1952), 325–362. DOI 10.1680/ipeds.1952.11259
• M. Beckmann, C. B. McGuire and C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, 1956.
• D. Braess, Über ein Paradoxon aus der Verkehrsplanung, Unternehmensforschung 12 (1968), 258–268. DOI 10.1007/BF01918335
• Peter Doyle and J. Laurie Snell, Random Walks and Electric Networks, Mathematical Association of America, 1984. arXiv:math/0001057
• R. G. Gallager, A minimum delay routing algorithm using distributed computation, IEEE Transactions on Communications 25 (1977), 73–85. DOI 10.1109/TCOM.1977.1093711

Motivation

Equilibrium concepts are static; play is dynamic. The bridge between the two is regret minimization: simple adaptive rules that, against arbitrary — even adversarial — opponents, perform nearly as well as the best fixed alternative in hindsight. The subject begins with Hannan (1957) and Blackwell (1956), whose consistency theorems predate most of computational learning theory; the modern multiplicative-weights style bounds are due to Littlestone–Warmuth (1994) and Freund–Schapire (1997); the reduction from external to swap regret, and with it the algorithmic route to correlated equilibria, is Blum–Mansour (2005), following Foster–Vohra (1997) and Hart–Mas-Colell (2000). Chapter 4 of Nisan–Roughgarden–Tardos–Vazirani (eds.), Algorithmic Game Theory (Cambridge, 2007), written by Blum and Mansour, is the source text of this mission.

The punchline of the chapter, and of this mission, is that a computationally trivial form of rationality — each player privately running a no-swap-regret algorithm — drives the empirical play of any finite game into an approximate correlated equilibrium (Aumann, 1974). No coordination, no knowledge of the game, no fixed-point computation: the equilibrium concept that Chapter 1 of the series defines through a correlating device is reached by decentralized learning.

Setting

The online model (§4.2): there are $N$ actions. At each time $t$ an online algorithm selects a distribution $p^t$ over actions, as a function of the loss vectors observed so far; then the adversary reveals a loss vector $\ell^t \in [0,1]^N$ and the algorithm suffers $\sum_i p^t_i \ell^t_i$. Cumulatively, $L_H^T = \sum_{t \le T} \sum_i p^t_i \ell^t_i$ and $L_k^T = \sum_{t \le T} \ell^t_k$ for a fixed action $k$. The external regret of $H$ is $L_H^T - \min_k L_k^T$. A modification rule $F : \{1,\dots,N\} \to \{1,\dots,N\}$ rewires the algorithm's play, giving the modified loss $L_{H,F}^T = \sum_t \sum_i p^t_i\, \ell^t_{F(i)}$; the swap regret is $L_H^T - \min_F L_{H,F}^T$ over all $N^N$ rules.

A finite game (the vocabulary of Mission I of this series, in loss form): players $\iota$, finite action sets $S_i$, cost functions $c_i : \prod_j S_j \to \mathbb{R}$. A joint distribution $Q$ on action vectors is an $\varepsilon$-correlated equilibrium (Definition 4.11) if for every player $i$ and every switching rule $F : S_i \to S_i$,

$$\mathbb{E}_{s \sim Q}\big[c_i(s)\big] \;\le\; \mathbb{E}_{s \sim Q}\big[c_i(F(s_i), s_{-i})\big] + \varepsilon.$$

Formalization targets

Goal (capstone) — Corollary 4.16, explicit form

$$\forall N, T\ \exists H:\quad \text{swap regret of } H \text{ on every } [0,1]\text{-loss sequence} \;\le\; 2N\sqrt{T \ln N}.$$

An online algorithm with vanishing per-round swap regret, with the constant the chapter's own route produces.

Theorem 4.6 — Polynomial Weights

$$L_{PW}^T \;\le\; L_k^T + \eta\, Q_k^T + \frac{\ln N}{\eta}, \qquad Q_k^T = \sum_{t\le T} (\ell^t_k)^2, \quad 0 < \eta \le \tfrac12.$$

Theorem 4.9 — external regret in constant-sum games

A player with external regret $R$ over $T$ rounds has average loss at most $v_i + R/T$, where $v_i$ is the game value — no-regret play guarantees the minimax value against any opponent.

Theorem 4.15 — external-to-swap reduction

Any algorithm with external regret $\le R$ on all $[0,1]$-loss sequences yields one with swap regret $\le N R$.

Theorem 4.12 — swap regret bounds distance from correlated equilibrium

If every player's swap regret over $T$ steps of mixed play is at most $R$, the empirical joint distribution is an $(R/T)$-correlated equilibrium.

Theorem 4.3 — deterministic algorithms fail

Every deterministic algorithm has a $\{0,1\}$-loss sequence forcing loss $T$ while some action loses at most $\lfloor T/N \rfloor$: randomization is necessary, not a convenience.

Significance

Correlated equilibrium is the equilibrium concept with a defensible dynamic foundation: Nash equilibria are PPAD-hard to find, but the capstone plus Theorem 4.12 exhibit polynomial-time decentralized dynamics whose empirical play is an $\varepsilon$-correlated equilibrium after $T = O(N^2 \ln N / \varepsilon^2)$ rounds. Later missions in this series lean on this machinery: the price-of-anarchy chapters bound the cost of no-regret play (not just of exact equilibria), and the routing-game chapter uses precisely the convergence result formalized here.

Formalizing it produces the platform's first online-learning library: the adversarial protocol, regret in both external and swap forms, the multiplicative-weights analysis, and correlated equilibria. The regret vocabulary is directly reusable for the bandit-flavored missions already on the platform. All results are classical, with textbook proofs; the work requested is machine-checked proof, not new mathematics.

Difficulty

The Polynomial Weights bound is a potential-function argument: the total weight $W^t$ falls geometrically with the algorithm's loss and is bounded below by the weight of action $k$; the formal work is inequalities for $\ln(1-x)$ on $[0, 1/2]$ and careful bookkeeping of the recursion. The reduction (Theorem 4.15) is the structurally interesting step: the master algorithm runs $N$ copies of the external-regret procedure, feeds copy $i$ the true losses scaled by the master's own probability $p^t_i$, and — the crux — plays the stationary distribution $p^t = p^t Q^t$ of the column-stochastic matrix assembled from the copies' outputs. Existence of that fixed point is exactly the existence of a stationary distribution of a finite Markov chain, available on this platform as the goal of Markov Chains and Mixing Times I — or provable directly. Theorem 4.12 is an averaging argument, deliberately easy; Theorem 4.3 is an adversary construction; Theorem 4.9 combines the regret bound with the security level the minimax theorem of Mission I supplies, through the opponent's empirical mixture. The capstone is the composition of 4.6 (tuned at $\eta = \min\{\sqrt{\ln N / T}, 1/2\}$) with 4.15, plus the arithmetic that turns $N \cdot 2\sqrt{T \ln N}$ into the stated bound.

Formalization scope

An online algorithm is a deterministic function from the observed history (the list of past loss vectors) to the mixed action played next — the standard formal reading of the full-information model; randomization lives in the mixed action, and losses are expected losses. Boundedness of losses ($[0,1]$) is a hypothesis on theorems, never part of a definition. The Polynomial Weights algorithm is defined concretely by its weight recursion, and its learning rate carries the hypothesis $0 < \eta \le 1/2$: the book writes only $\eta \le 1/2$, but at $\eta = 0$ the bound's $\ln N / \eta$ term degenerates and the claim is false, so positivity is explicit. Action sets are Fin (n+1), keeping them nonempty. The number of steps $T$ is a known parameter (the book's convention; guess-and-double is out of scope). Correlated equilibria use the switching-rule form of Definition 4.11, over the game vocabulary (IsLottery, IsMixedProfile, profileProb) published with Mission I of this series. In Theorem 4.12 the empirical distribution is the average of product distributions of the played profiles, $T \ge 1$ is required (at $T = 0$ there is no empirical distribution), and costs are not assumed bounded — the averaging is scale-free.

Trivializing readings are ruled out: the existential algorithms in Theorem 4.15 and the capstone are quantified before the loss sequence and the modification rule, so a witness must work uniformly against every adversary — nothing may be chosen with hindsight.

Selected references

• A. Blum, Y. Mansour, From external to internal regret, JMLR 8 (2007), 1307–1324. Link
• N. Littlestone, M. K. Warmuth, The weighted majority algorithm, Information and Computation 108 (1994), 212–261. DOI
• D. P. Foster, R. V. Vohra, Calibrated learning and correlated equilibrium, Games and Economic Behavior 21 (1997), 40–55. DOI
• S. Hart, A. Mas-Colell, A simple adaptive procedure leading to correlated equilibrium, Econometrica 68 (2000), 1127–1150. DOI
• N. Nisan, T. Roughgarden, É. Tardos, V. V. Vazirani (eds.), Algorithmic Game Theory, Cambridge University Press, 2007, Chapter 4. DOI

Motivation

When a decision rule is announced in advance, people may change the features on which the rule acts. A lender, for example, may offer loans with different probabilities to applicants with different reported characteristics. An applicant then weighs the greater chance of receiving a loan against the cost of changing those characteristics. The decision maker must account for this response when choosing the rule. Tsirtsis and coauthors study this problem with a finite feature set and a policy that specifies the probability of a positive decision at each value.

If moving to a better-outcome feature costs more and moving to a worse-outcome feature costs nothing, the paper shows that at least one optimal policy can be chosen to respect the ordering of outcomes. Section 5 asks what remains of that conclusion when change costs are general. Its three-value example answers the question sharply: an optimal policy exists, but no optimal policy respects outcome monotonicity. The example isolates the role played by the cost assumption in the earlier result. Source, §§4–5

Setting

There are $m$ feature values $x_1,\ldots,x_m$. An individual initially has value $x_i$ with probability $p(x_i)=P(x_i)$. At feature value $x_j$, the probability of a positive underlying outcome is $q(x_j)=P(y=1\mid x_j)$. A decision policy $\pi$ assigns a positive-decision probability $\pi(x_j)\in[0,1]$ to each value. The decision maker incurs a cost $\gamma\in(0,1)$ for a positive decision. This is the paper's base model: the individual benefit is $b(x)=\pi(x)$, and the outcome probability $P(y\mid x)$ does not change when an individual changes features. Source, §2, p. 3, equations (1)–(3)

An individual at $x_i$ may move to $x_j$, paying change cost $c(x_i,x_j)$. Their best response maximizes $\pi(x_j)-c(x_i,x_j)$ over all destinations. If several destinations tie, the paper selects one with the highest outcome probability $q(x_j)$. The resulting population distribution depends on $\pi$. The decision maker's strategic utility is the expected outcome surplus under that response:

$$u_{p,q,\gamma,c}(\pi)=\sum_{i=1}^{m}p(x_i) \bigl(q(\operatorname{br}_{c,q,\pi}(x_i))-\gamma\bigr) \pi(\operatorname{br}_{c,q,\pi}(x_i)).$$

This sum is equation (7) regrouped by each individual's initial value. An optimal policy maximizes it over every policy in $[0,1]^m$. The paper assumes a positive cost for moving to a distinct feature whose outcome is at least as good as the starting feature; its Section 5 matrix meets that assumption. Source, §3, pp. 4–5, equations (5) and (7)

The example has $m=3$, $\gamma=0.1$, $p=(0.1,0.4,0.5)$, and $q=(1,0.7,0.4)$. Rows of the following matrix are starting features and columns are destinations:

$$c=\begin{pmatrix} 0&0.2&0.3\\ 0.3&0&0.7\\ 1.2&1.1&0 \end{pmatrix}.$$

Moving from $x_1$ to the lower-outcome $x_2$ costs $0.2$. That violates the zero-cost requirement for such moves in the paper's outcome monotonic cost definition. A policy is called outcome monotonic here when a larger positive-decision probability implies a larger outcome probability: $\pi(x_i)<\pi(x_j)\Rightarrow q(x_i)<q(x_j)$. Source, §§2, 4–5, pp. 3, 6, 9

Formalization targets

The printed optimal family

For every admissible policy $\pi$ with $\pi(x_1)=1$, $\pi(x_2)\leq0.7$, and $\pi(x_3)=1$, the paper states that $\pi$ is optimal and that individuals initially at $x_2$ move to $x_1$:

$$\forall\pi\in[0,1]^3, \quad\bigl(\pi(x_1)=1\land\pi(x_2)\leq0.7\land\pi(x_3)=1\bigr) \Longrightarrow \bigl(\pi\text{ is optimal}\land\operatorname{br}_{c,q,\pi}(x_2)=x_1\bigr).$$

The endpoint $\pi(x_2)=0.7$ matters: the move from $x_2$ to $x_1$ ties with staying in benefit less cost, and the paper's outcome tie rule chooses $x_1$. Source, §5, p. 9

Goal: no outcome monotonic optimum

The principal target formalizes the Section 5 heading in this fixed instance:

$$\exists\pi\in[0,1]^3:\pi\text{ is optimal}, \qquad \forall\pi\in[0,1]^3:\pi\text{ is optimal}\Longrightarrow \neg\operatorname{OMPolicy}(q,\pi).$$

The existence clause rules out an empty optimal set. This formulation follows the heading's assertion that an outcome-monotonic optimum may fail to exist, while the printed family supplies concrete optima. Source, §5, p. 9

Significance

The result gives an explicit boundary for the earlier outcome-monotonic-policy guarantee. With the Section 5 costs, favoring the lowest-outcome value $x_3$ as much as the highest-outcome value $x_1$ can be optimal, because the response to a published policy changes where population mass receives decisions. Thus a search restricted to outcome-monotonic policies can miss every optimum in a general-cost instance. The milestone on the printed family records a full interval of optimal policies, including its tie endpoint. Source, §§4–5, pp. 6, 9

The paper proves its example informally; this mission asks for a machine-checked account of the fixed instance and the universal quantifiers behind “every” and “no.” The development also yields reusable definitions for finite strategic policies, the outcome-aware best response, and utility. The other missions in this series treat the additive-cost theorem and a stochastic-optimum example separately. No theorem in this mission is presented as an open research problem.

Difficulty

Checking that one displayed policy has high utility is insufficient to establish optimality over every policy in $[0,1]^3$. The best response changes at equality thresholds, so utility is piecewise defined and may jump when the tie rule changes the destination. The closed bound $\pi(x_2)\leq0.7$ makes one such threshold part of the statement. A finite numerical grid misses both arbitrary real policies and the exact tie behavior. The negative goal also requires excluding outcome monotonicity for every maximizer, rather than exhibiting one nonmonotonic maximizer.

Formalization scope

The features are Fin 3 in the example, with Lean indices $0,1,2$ representing $x_1,x_2,x_3$. The general model uses Fin m with a nonempty finite feature set. Probabilities, costs, and utility are real numbers; the example's decimals are exact rational reals. Policies range over all real-valued functions with each coordinate in $[0,1]$, and optimality uses IsMaxOn on precisely that set. The best response is constructed from the maximizers of $\pi(x_j)-c(x_i,x_j)$ and then the largest $q(x_j)$. If tied destinations also have equal $q$, the least index is chosen; the example has distinct outcome probabilities, so this final convention never affects its claims.

Equation (1) prints strict outcome and policy comparisons as a biconditional, although the paper's later policy class permits equal policy values at distinct outcomes. This mission uses its one-way implication from a strict policy comparison to a strict outcome comparison. Failure of this weaker condition is a stronger counterexample than failure of the printed biconditional. The cost definition applies its printed pair and triple comparisons only to distinct values and records $c(x_i,x_i)=0$, as required for free staying. The example's constants satisfy the paper's standing positive-upward-cost assumption. These readings are disclosed so the formal claim has a consistent, nonvacuous model.

A complete proof needs finite argmax reasoning, exact rational inequalities, a case analysis over real policy regions, and the semantics of IsMaxOn. The finite best-response and utility definitions can be reused for other strategic-decision instances. Contributions may establish the printed family, its transport claim, bounds for all admissible policies, or the final exclusion of monotonic maximizers. Policies are never restricted to a grid, and the best response is computed from the model data rather than supplied as a free variable. The paper's algorithms, complexity claims, empirical studies, and changes to $P(y\mid x)$ are outside this mission.

Selected references

• S. Tsirtsis, B. Tabibian, M. Khajehnejad, A. Singla, B. Schölkopf, and M. Gomez-Rodriguez, Optimal Decision Making Under Strategic Behavior, Management Science, 2024. arXiv:1905.09239v5, the source version used here.