This appendix collects the mathematical prerequisites, stated for reference rather than developed from scratch.
Sets, functions, correspondences
A correspondence \(F : X \rightrightarrows Y\) assigns to each \(x \in X\) a subset \(F(x) \subseteq Y\) (e.g., best-response sets). \(F\) has a closed graph if \(x^k \to x\), \(y^k \to y\), \(y^k \in F(x^k)\) imply \(y \in F(x)\). A set \(K \subseteq \R^m\) is compact iff it is closed and bounded (Heine–Borel), and convex if it contains the segment between any two of its points. The simplex \(\Delta(A) = \{ p \in \R^{|A|}_{\ge 0} : \sum_a p_a = 1 \}\)—the home of mixed strategies—is compact and convex.
Optimization facts
Weierstrass: a continuous function on a nonempty compact set attains a maximum.
First-order condition: at an interior maximum of a differentiable function, the gradient vanishes; with concavity, the FOC is also sufficient.
Berge’s maximum theorem: if \(u(x, \theta)\) is continuous and the constraint set \(C(\theta)\) is a continuous, compact-valued correspondence, then the value function is continuous and the maximizer correspondence is upper hemicontinuous with closed graph—the workhorse behind continuity of best responses.
Envelope theorem: the derivative of a value function with respect to a parameter equals the partial derivative of the objective at the optimum; integral form (Milgrom–Segal) underlies Lemma [lem:envelope].
Jensen’s inequality: for concave \(u\), \(\E[u(W)] \le u(\E[W])\)—the definition of risk aversion.
Probability
Finite probability spaces suffice for most of this book. Key tools: expectation and its linearity; conditional probability and Bayes’ rule \[\Prob(\theta \mid s) \;=\; \frac{\Prob(s \mid \theta)\, \Prob(\theta)} {\sum_{\theta'} \Prob(s \mid \theta')\, \Prob(\theta')},\] which drives every updating argument in Chapters [ch:bayesian] –[ch:dynamicincomplete]; independence; and for auction theory, order statistics: with \(n\) i.i.d. draws from \(F\), the maximum has CDF \(F(v)^n\), and for \(U[0,1]\) the expected \(k\)-th highest of \(n\) is \(\frac{n+1-k}{n+1}\).
Fixed points
Stated as Theorems [thm:brouwer] and [thm:kakutani]. Intuition for Brouwer in one dimension: a continuous \(f : [0,1] \to [0,1]\) must cross the diagonal (intermediate value theorem applied to \(f(x) - x\)). Kakutani generalizes to correspondences; convex-valuedness cannot be dropped (rotating the circle has no fixed point when values are allowed to be disconnected). Sperner’s lemma provides the standard combinatorial proof route and also explains the computational hardness of finding fixed points (Chapter [ch:algorithmic]).
Linear programming and duality
The primal–dual pair \[\max\{ c^\top x : Ax \le b,\, x \ge 0 \} \qquad\longleftrightarrow\qquad \min\{ b^\top y : A^\top y \ge c,\, y \ge 0 \}\] satisfies weak duality (any feasible pair has \(c^\top x \le b^\top y\)) and strong duality (optimal values coincide when either problem is feasible and bounded). Complementary slackness links optimal solutions. Applications in this book: the Minimax Theorem (Chapter [ch:zerosum]), the Bondareva–Shapley theorem (Chapter [ch:cooperative]), and polynomial-time computation of correlated equilibria (Chapter [ch:algorithmic]).
Basic dynamical systems
For an ODE \(\dot x = f(x)\) on the simplex: rest points satisfy \(f(x^*) = 0\); a rest point is Lyapunov stable if trajectories starting nearby stay nearby, and asymptotically stable if they also converge to it. In one dimension, stability is read off the sign of \(f\) around the rest point; in higher dimensions, from the eigenvalues of the Jacobian or via a Lyapunov function. These suffice for the replicator analyses of Chapter [ch:evolutionary].