一个博弈的四个零件

两人零和博弈由以下要素组成：

• 行玩家 Alice，有 $m$ 个策略（矩阵的 $m$ 行）；
• 列玩家 Bob，有 $n$ 个策略（矩阵的 $n$ 列）；
• 支付矩阵 $C\in\mathbb R^{m\times n}$，其中 $C_{ij}$ 是 Alice 选择 $i$、Bob 选择 $j$ 时，Bob 付给 Alice 的钱数。负数表示 Alice 付钱给 Bob；
• 之所以叫「零和」，是因为两人盈亏相加恒为 $0$：Alice 赢多少，Bob 就输多少。

一般博弈可以给两人各一个支付矩阵；但只有零和时，「用一个矩阵描述全部信息」才成立，后面的线性规划也才写得出来。

时间轴

例子一：匹配硬币

两人同时出示硬币的正面（H）或反面（T）。相同则 Alice 赢 $1$，不同则 Alice 输 $1$。支付矩阵（行是 Alice，列是 Bob）：

$$C=\begin{bmatrix} 1&-1\\ -1&1 \end{bmatrix}.$$

（第一行 H、第二行 T；第一列 H、第二列 T。）这个矩阵关于转置对称，所以两人处境相同——直觉上谁也没有优势。

例子二：一个 $3\times3$ 的博弈

课堂上让两位同学实际对局，支付矩阵是

$$C=\begin{bmatrix} 2&-1&3\\ 2&2&-3\\ -1&2&-3 \end{bmatrix}.$$

仅仅 $3\times3$，就已经看不出谁占优了。这正是需要理论的地方：靠盯着矩阵猜是猜不出来的。

纯策略纳什均衡

策略对 $(i,j)$ 是纯策略纳什均衡，如果任何一方单独改变策略都不会变得更好。由于是零和博弈，写成不等式：

• 行玩家不偏离：对所有 $i'$，$C_{i'j}\le C_{ij}$；
• 列玩家不偏离：对所有 $j'$，$C_{ij'}\ge C_{ij}$。

两个不等号方向相反，因为 Bob 的支付是 $-C_{ij}$：Bob 想让自己亏得少，就是想让 Alice 赢得少，乘 $-1$ 后方向翻转。

匹配硬币没有纯纳什均衡。 四个格子逐一检查：若双方都出 H，Bob 改为 T 就赢 $1$；若 Alice 出 H、Bob 出 T，Alice 改为 T 就赢 $1$；其余同理。无论落在哪个格子，总有一方想改。所以纯纳什均衡不存在。

更深的原因：纯策略是公开宣布且可被利用的。一旦对手知道你的确定性选择，他总能针对你调整。

混合策略

混合策略是把策略集上的概率分布作为选择。记

$$\Delta_m=\Big\{x\in\mathbb R^m: x_i\ge0,\ \sum_i x_i=1\Big\},$$

$\Delta_n$ 同理。玩家宣布的是分布 $x$（或 $y$），而不是某个具体策略。

期望支付：

$$\mathbb E[C]=x^TCy=\sum_{i=1}^{m}\sum_{j=1}^{n}x_iC_{ij}y_j .$$

混合纳什均衡是一对 $(x,y)$，$x\in\Delta_m$、$y\in\Delta_n$，使任何一方都没有正收益的偏离：

• 行玩家：对所有 $i'$，$(C^Ty)_{i'}\le x^TCy$；
• 列玩家：对所有 $j'$，$(Cx)_{j'}\ge x^TCy$。

为什么只检查偏离到纯策略

定义里只检查「从 $x$ 偏离到某个纯策略 $i'$」，没有检查偏离到另一个分布 $x'$。原因是一个平均：

$$(x')^TCy=\sum_{i'}x'_{i'}(C^Ty)_{i'} .$$

如果对每个 $i'$ 都有 $(C^Ty)_{i'}\le x^TCy$，那么对任意分布 $x'$，加权平均也不会超过 $x^TCy$；反之，若某个分布 $x'$ 能带来更高收益，那么它的某个正概率坐标 $i'$ 也必须带来更高收益。所以检查纯偏离等价于检查全部偏离，约束从无穷多条降到了有限条。

这正是把博弈写成线性规划的关键一步。

极小极大定理

定理（von Neumann）。 存在实数 $\lambda^*$，使

$$\lambda^*=\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^TCy =\min_{y\in\Delta_n}\max_{x\in\Delta_m}x^TCy .$$

这个式子的分量比看上去重得多。

• 左边的顺序：行玩家先选定分布 $x$，列玩家看到之后再针对。这对行玩家不利——他是「先承诺」的一方。
• 右边的顺序：列玩家先选定 $y$，行玩家再针对。对列玩家不利。

纯策略时，先后手是天壤之别：匹配硬币里若 Alice 必须先出，Bob 必胜。但定理说，换成混合策略后，谁先承诺都一样，两种顺序得到同一个值 $\lambda^*$，这个值称为博弈值。双方同时出策略的情形也与这两种顺序等价。

推论：零和博弈必有混合纳什均衡

取 $x^*$ 为右边内层的最优解、$y^*$ 为左边内层的最优解。由博弈值的含义：

$$\text{对一切 }y\in\Delta_n:\quad (x^*)^TCy\ge\lambda^*, \qquad \text{对一切 }x\in\Delta_m:\quad x^TCy^*\le\lambda^* .$$

两式分别说明：$x^*$ 保证行玩家至少拿到 $\lambda^*$，$y^*$ 保证列玩家最多只输 $\lambda^*$。再取 $x=x^*$、$y=y^*$：

$$(x^*)^TCy^*\ge\lambda^*\quad\text{且}\quad (x^*)^TCy^*\le\lambda^*,$$

所以 $(x^*)^TCy^*=\lambda^*$。于是双方都没有偏离动机，$(x^*,y^*)$ 是混合纳什均衡。

用线性规划对偶证明

一个引理

把无穷多条约束化成有限条：

$$\Big(\forall y\in\Delta_n:\ x^TCy\ge\lambda\Big) \iff \Big(\forall j:\ x^TCe_j\ge\lambda\Big),$$

其中 $e_j$ 是第 $j$ 个标准基向量（即纯策略 $j$）。

「$\Rightarrow$」显然。反方向：任意 $y\in\Delta_n$ 可以写成 $y=\sum_j y_je_j$，权重非负且和为 $1$。由线性性，

$$x^TCy=\sum_j y_j\,(x^TCe_j)\ge\sum_j y_j\lambda=\lambda .$$

所以只要对每个纯策略成立，对所有分布都成立。

两个互为对偶的 LP

情景 2（行玩家先承诺）：

$$\begin{aligned} \max\quad & \lambda\\ \text{s.t.}\quad & x^TCe_j\ge\lambda &&\forall j\\ & \textstyle\sum_i x_i=1\\ & x\ge0 . \end{aligned}$$

含义：找一个分布 $x$，使无论 Bob 怎么应对，期望收益至少是 $\lambda$；并把 $\lambda$ 尽量抬高。

情景 1（列玩家先承诺）：

$$\begin{aligned} \min\quad & \lambda\\ \text{s.t.}\quad & e_i^TCy\le\lambda &&\forall i\\ & \textstyle\sum_j y_j=1\\ & y\ge0 . \end{aligned}$$

含义：找一个分布 $y$，使无论 Alice 怎么应对，期望损失至多 $\lambda$；并把 $\lambda$ 压到最低。

两者互为对偶。 每个约束配一个对偶变量：$m$ 条行约束对应 $x$ 的坐标，$n$ 条列约束对应 $y$ 的坐标；等式 $\sum x_i=1$ 与 $\sum y_j=1$ 的自由对偶变量正好是 $\lambda$。把两个 LP 写成矩阵形式（$C^Tx\ge\lambda\mathbf 1$ 对 $Cy\le\lambda\mathbf 1$）后逐项对照，就能看出转置关系。

两者都可行：任取 $x\in\Delta_m$、$y\in\Delta_n$，相应的 $\lambda$ 取足够小（或足够大）即可。由强对偶，最优值相等，即

$$\max_x\min_y x^TCy=\min_y\max_x x^TCy .$$

这正是极小极大定理。课程也借这个证明重新解释了弱对偶：一个情景的可行解，就是另一个情景最优值的证书——给 Bob 一个策略，就能证明 Alice 拿不到更多。

回到 $3\times3$ 例子

把矩阵喂给求解器（或手算），得到博弈值与最优策略：

$$\lambda^*=\frac13,\qquad x^*=\Big(\tfrac59,0,\tfrac49\Big),\qquad y^*=\Big(0,\tfrac23,\tfrac13\Big).$$

验证：

$$(x^*)^TC=\Big(\tfrac23,\tfrac13,\tfrac13\Big), \qquad Cy^*=\Big(\tfrac13,\tfrac13,\tfrac13\Big)^T,$$

于是 $(x^*)^TCy^*=\frac59\cdot\frac13+\frac49\cdot\frac13=\frac13$。

两个结论：

• 行玩家占优：博弈值为正，意味着理性对局下 Alice 平均每局赢 $\frac13$ 美元。课堂上的现场对局由 Bob 一方短暂领先，但那只是还没收敛到均衡。
• 有些策略永远不该用：行玩家的策略 2 概率为 $0$，列玩家的策略 1 概率为 $0$。即使课堂上真的出现过这些选择，它们也不是最优策略的一部分。

互补松弛的解释

$(x^*)^TC$ 的第 1 个分量是 $\frac23>\frac13$，其余两个恰为 $\frac13$。为什么 $y^*_1=0$？

这正是互补松弛：对偶约束（这里对应 Bob 的列）若不是紧的，其对应的原变量必须为零。若 Bob 在列 1 上放了正概率，Alice 的期望收益会超过 $\frac13$，与博弈值为 $\frac13$ 矛盾。所以列 1 的概率必须为 $0$。反过来，$Cy^*$ 的三个分量都等于 $\frac13$，没有给 $x^*$ 施加额外约束。

互补松弛在这里的含义就是：双方的最优策略与各自的期望收益向量必须相容——哪里收益不紧，哪里就不能下注。

本节结论

• 零和博弈由支付矩阵 $C$ 完全描述；Alice 的收益是 $C_{ij}$，Bob 的收益是 $-C_{ij}$。
• 纯纳什均衡是「公开宣布后无人愿改」的策略对，匹配硬币没有纯纳什均衡。
• 混合策略是策略集上的概率分布，期望支付为 $x^TCy$。
• 只需检查偏离到纯策略，因为分布收益是纯策略收益的加权平均。
• 极小极大定理：$\max_x\min_y x^TCy=\min_y\max_x x^TCy=\lambda^*$，先承诺与否不影响结果。
• 每个零和博弈都有混合纳什均衡；证明是线性规划强对偶。
• 博弈值 $\lambda^*$ 回答「谁占优」；互补松弛解释哪些策略概率为零。

理解检验

1. 写出匹配硬币的支付矩阵，并证明它没有纯纳什均衡。

参考答案：

$$C=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}.$$

检查四个格子：$(H,H)$ 时 Bob 改出 T 得 $+1$；$(H,T)$ 时 Alice 改出 T 得 $+1$；$(T,H)$ 时 Alice 改出 H 得 $+1$；$(T,T)$ 时 Bob 改出 H 得 $+1$。每个格子都至少有一方愿意偏离，所以没有纯纳什均衡。

2. 为什么混合纳什均衡只需检查偏离到纯策略，而不必检查偏离到任意分布？

参考答案：设 Bob 固定 $y$。任意分布 $x'$ 的收益是 $(x')^TCy=\sum_i x'_i(C^Ty)_i$，是各纯策略收益以 $x'$ 为权重的平均。若每个纯策略收益都不超过 $x^TCy$，则任何平均也不超过它；反之，若某个分布收益更高，则至少有一个正概率的纯策略收益更高。所以两类偏离条件等价。

3. 陈述极小极大定理，并解释两个 max-min 顺序的博弈含义。

参考答案：$\max_{x}\min_{y}x^TCy=\min_{y}\max_{x}x^TCy=\lambda^*$。左边是行玩家先公开分布 $x$、列玩家后针对，对应「对行玩家不利」的顺序；右边是列玩家先公开 $y$、行玩家后针对。定理说换成混合策略后，两种先后顺序得到同一个值，因此先承诺没有额外代价。

4. 用线性规划对偶证明极小极大定理。

参考答案：写出情景 2 的 LP：$\max\lambda$，约束 $x^TCe_j\ge\lambda$、$\sum x_i=1$、$x\ge0$；情景 1 的 LP：$\min\lambda$，约束 $e_i^TCy\le\lambda$、$\sum y_j=1$、$y\ge0$。两者互为对偶（转置矩阵、目标与右端互换，等式约束的对偶变量即 $\lambda$）。两者都可行（任取分布并取合适的 $\lambda$），由强对偶最优值相等，即极小极大定理。

5. 对 $3\times3$ 例子验证 $x^*=(5/9,0,4/9)$、$y^*=(0,2/3,1/3)$ 给出博弈值 $1/3$，并用互补松弛解释 $y^*_1=0$。

参考答案：$(x^*)^TC$ 是两行的凸组合：$\frac59(2,-1,3)+\frac49(-1,2,-3)=(2/3,1/3,1/3)$。$Cy^*$ 是两列的凸组合：$\frac23(-1,2,2)+\frac13(3,-3,-3)=(1/3,1/3,1/3)$。于是 $(x^*)^TCy^*=\frac59\cdot\frac13+\frac49\cdot\frac13=\frac13$。因为 $(x^*)^TC$ 的第 1 个分量 $2/3>1/3$ 不是紧约束，由互补松弛对应的 $y^*_1$ 必须为 $0$；否则 Bob 在列 1 上下注会让 Alice 的收益超过博弈值。

与前后课的关系

上一讲的强对偶与互补松弛在这里第一次获得博弈论解释：原问题与对偶分别是两位玩家的最优策略，博弈值就是共同的最优值。下一讲把同一套 LP 工具搬到网络流上，用对偶推出最大流最小割定理；那将是「写 LP、取对偶、读出组合意义」这一模板的第三次完整演示。

Four ingredients of a game

A two-player zero-sum game consists of:

• the row player, Alice, with $m$ strategies (the $m$ rows);
• the column player, Bob, with $n$ strategies (the $n$ columns);
• a payoff matrix $C\in\mathbb R^{m\times n}$, where $C_{ij}$ is the amount Bob pays Alice when Alice plays $i$ and Bob plays $j$ (negative means Alice pays Bob);
• the name "zero-sum" because the two players' gains add to $0$: whatever Alice wins, Bob loses.

General games can give each player their own payoff matrix; only in the zero-sum case does one matrix carry all the information, and only then can the linear programs be written.

Timeline

Example 1: matching pennies

Both players reveal heads (H) or tails (T). If the coins match, Alice wins \1$; otherwise she loses$$1$. The payoff matrix (rows for Alice, columns for Bob) is

$$C=\begin{bmatrix} 1&-1\\ -1&1 \end{bmatrix}.$$

(first row H, second T; first column H, second T). The matrix is symmetric under transposition, so the players are in identical positions — intuitively neither has an edge.

Example 2: a $3\times3$ game

Two students play live in class with payoff matrix

$$C=\begin{bmatrix} 2&-1&3\\ 2&2&-3\\ -1&2&-3 \end{bmatrix}.$$

Even at $3\times3$ it is no longer obvious who is favoured. That is exactly where theory is needed: staring at the matrix does not answer the question.

Pure Nash equilibrium

A strategy pair $(i,j)$ is a pure Nash equilibrium if neither player gains by changing unilaterally. In a zero-sum game this becomes a pair of inequalities:

• row player does not deviate: for all $i'$, $C_{i'j}\le C_{ij}$;
• column player does not deviate: for all $j'$, $C_{ij'}\ge C_{ij}$.

The directions are opposite because Bob's payoff is $-C_{ij}$: Bob wants to lose less, which means Alice wins less, and multiplying by $-1$ flips the inequality.

Matching pennies has no pure equilibrium. Check the four cells: at $(H,H)$ Bob switches to T and wins \1$; at$(H,T)$Alice switches to T and wins$$1$; at$(T,H)$Alice switches to H and wins; at$(T,T)$ Bob switches to H and wins. Every cell gives someone a profitable deviation.

The deeper reason: a pure strategy is announced and exploitable. Once the opponent knows your deterministic choice, they can always respond to it.

Mixed strategies

A mixed strategy is a probability distribution over the strategy set. Write

$$\Delta_m=\Big\{x\in\mathbb R^m: x_i\ge0,\ \sum_i x_i=1\Big\},$$

and $\Delta_n$ similarly. A player announces a distribution $x$ (or $y$), not a single strategy.

Expected payoff:

$$\mathbb E[C]=x^TCy=\sum_{i=1}^{m}\sum_{j=1}^{n}x_iC_{ij}y_j .$$

A mixed Nash equilibrium is a pair $(x,y)$ with $x\in\Delta_m$, $y\in\Delta_n$ such that neither player has a profitable deviation:

• row: for all $i'$, $(C^Ty)_{i'}\le x^TCy$;
• column: for all $j'$, $(Cx)_{j'}\ge x^TCy$.

Why checking deviations to pure strategies suffices

The definition checks "deviate from $x$ to some pure strategy $i'$" and never checks another distribution $x'$. The reason is an averaging identity:

$$(x')^TCy=\sum_{i'}x'_{i'}(C^Ty)_{i'} .$$

If every pure payoff $(C^Ty)_{i'}$ is at most $x^TCy$, then every weighted average is too. Conversely, if some distribution $x'$ did better, some coordinate with positive probability would have to do better. So checking pure deviations is equivalent to checking all deviations, and the constraints collapse from infinitely many to finitely many.

That reduction is what makes the game writable as a linear program.

The minimax theorem

Theorem (von Neumann). There is a real number $\lambda^*$ with

$$\lambda^*=\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^TCy =\min_{y\in\Delta_n}\max_{x\in\Delta_m}x^TCy .$$

This carries far more meaning than it appears to.

• The left order: the row player picks $x$ first and the column player responds. That disadvantages the row player — they must commit.
• The right order: the column player picks $y$ first and the row player responds. That disadvantages the column player.

With pure strategies the order matters enormously: in matching pennies, if Alice must reveal first, Bob always wins. The theorem says that with mixed strategies the order no longer matters: both orders produce the same number $\lambda^*$, the value of the game. Simultaneous play is equivalent to either.

Corollary: every zero-sum game has a mixed equilibrium

Take $x^*$ optimal for the inner problem on the right and $y^*$ optimal for the inner problem on the left. By the meaning of the value,

$$\text{for all }y\in\Delta_n:\quad (x^*)^TCy\ge\lambda^*, \qquad \text{for all }x\in\Delta_m:\quad x^TCy^*\le\lambda^* .$$

The first says $x^*$ guarantees Alice at least $\lambda^*$; the second says $y^*$ holds Bob's loss to at most $\lambda^*$. Taking $x=x^*$, $y=y^*$,

$$(x^*)^TCy^*\ge\lambda^*\quad\text{and}\quad (x^*)^TCy^*\le\lambda^*,$$

so $(x^*)^TCy^*=\lambda^*$. Neither player can improve, so $(x^*,y^*)$ is a mixed Nash equilibrium.

Proof by linear programming duality

A lemma

Turn infinitely many constraints into finitely many:

$$\Big(\forall y\in\Delta_n:\ x^TCy\ge\lambda\Big) \iff \Big(\forall j:\ x^TCe_j\ge\lambda\Big),$$

where $e_j$ is the $j$-th standard basis vector (the pure strategy $j$).

"$\Rightarrow$" is immediate. For the converse, any $y\in\Delta_n$ is $y=\sum_j y_je_j$ with non-negative weights summing to one, so by linearity

$$x^TCy=\sum_j y_j\,(x^TCe_j)\ge\sum_j y_j\lambda=\lambda .$$

Hence constraints over all distributions follow from constraints over pure strategies.

Two mutually dual programs

Scenario 2 (row commits first):

$$\begin{aligned} \max\quad & \lambda\\ \text{s.t.}\quad & x^TCe_j\ge\lambda &&\forall j\\ & \textstyle\sum_i x_i=1\\ & x\ge0 . \end{aligned}$$

Find a distribution $x$ guaranteeing expected payoff at least $\lambda$ however Bob responds, and make $\lambda$ as large as possible.

Scenario 1 (column commits first):

$$\begin{aligned} \min\quad & \lambda\\ \text{s.t.}\quad & e_i^TCy\le\lambda &&\forall i\\ & \textstyle\sum_j y_j=1\\ & y\ge0 . \end{aligned}$$

Find a distribution $y$ holding expected loss to at most $\lambda$ however Alice responds, and make $\lambda$ as small as possible.

They are dual. Each constraint supplies a dual variable: the $m$ row constraints give the coordinates of $x$, the $n$ column constraints the coordinates of $y$, and the free dual variables of the two equality constraints are exactly $\lambda$. In matrix form, $C^Tx\ge\lambda\mathbf 1$ is dual to $Cy\le\lambda\mathbf 1$ with the transpose relation.

Both are feasible: pick any $x\in\Delta_m$ and $y\in\Delta_n$ and choose $\lambda$ small (or large) enough. Strong duality then gives equal optimal values:

$$\max_x\min_y x^TCy=\min_y\max_x x^TCy .$$

That is the minimax theorem. The lecture also reads weak duality this way: a feasible solution in one scenario is a certificate for the other — exhibiting a strategy for Bob proves Alice cannot do better.

Back to the $3\times3$ game

Feeding the matrix to a solver (or solving by hand) gives

$$\lambda^*=\frac13,\qquad x^*=\Big(\tfrac59,0,\tfrac49\Big),\qquad y^*=\Big(0,\tfrac23,\tfrac13\Big).$$

Check:

$$(x^*)^TC=\Big(\tfrac23,\tfrac13,\tfrac13\Big), \qquad Cy^*=\Big(\tfrac13,\tfrac13,\tfrac13\Big)^T,$$

so $(x^*)^TCy^*=\frac59\cdot\frac13+\frac49\cdot\frac13=\frac13$.

Two conclusions:

• The row player is favoured. The positive game value means that under rational play Alice averages \1/3$ per round. The live classroom game briefly favoured Bob, but that was before play converged to equilibrium.
• Some strategies should never be played. Alice's strategy 2 has probability $0$ and Bob's strategy 1 has probability $0$, even if both appeared in class; they are not part of optimal play.

Reading it with complementary slackness

The first component of $(x^*)^TC$ is $\frac23>\frac13$; the other two equal $\frac13$. Why is $y^*_1=0$?

Complementary slackness: a dual constraint that is not tight forces its primal variable to zero. If Bob put positive probability on column 1, Alice's expected payoff would exceed $\frac13$, contradicting the value. So column 1 must receive probability zero. Conversely, all three components of $Cy^*$ equal $\frac13$, so no extra constraint is placed on $x^*$.

The game-theoretic reading is: optimal strategies and the vectors of expected payoffs must be compatible — where the payoff is not tight, no weight may be placed.

What this lecture establishes

• A zero-sum game is fully described by $C$; Alice receives $C_{ij}$, Bob receives $-C_{ij}$.
• A pure Nash equilibrium is a pair nobody wants to leave after announcing; matching pennies has none.
• A mixed strategy is a distribution; expected payoff is $x^TCy$.
• Only deviations to pure strategies need checking, since distribution payoffs are weighted averages.
• Minimax: $\max_x\min_y x^TCy=\min_y\max_x x^TCy=\lambda^*$; commitment order is irrelevant.
• Every zero-sum game has a mixed equilibrium, proved by strong LP duality.
• The game value says who is favoured; complementary slackness explains which strategies get zero probability.

Comprehension check

1. Write the matching-pennies matrix and prove there is no pure Nash equilibrium.

Reference answer:

$$C=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}.$$

Check all four cells: at $(H,H)$ Bob gains by switching to T; at $(H,T)$ Alice gains by switching to T; at $(T,H)$ Alice gains by switching to H; at $(T,T)$ Bob gains by switching to H. Every cell admits a profitable deviation, so no pure equilibrium exists.

2. Why is it enough to check deviations to pure strategies in a mixed equilibrium?

Reference answer: Fix $y$. The payoff of any distribution $x'$ is $(x')^TCy=\sum_i x'_i(C^Ty)_i$, a weighted average of pure-strategy payoffs. If every pure payoff is at most $x^TCy$, so is every average; conversely, a better distribution implies a better pure strategy with positive weight. The two conditions are therefore equivalent.

3. State the minimax theorem and explain the game-theoretic meaning of the two orders.

Reference answer: $\max_x\min_y x^TCy=\min_y\max_x x^TCy=\lambda^*$. The left side has the row player commit to $x$ first and the column player respond — the order that disadvantages the row player; the right side has the column player commit first. The theorem says that with mixed strategies both orders give the same value, so committing first costs nothing.

4. Prove the minimax theorem with LP duality.

Reference answer: Scenario 2 is $\max\lambda$ subject to $x^TCe_j\ge\lambda$, $\sum x_i=1$, $x\ge0$. Scenario 1 is $\min\lambda$ subject to $e_i^TCy\le\lambda$, $\sum y_j=1$, $y\ge0$. They are dual: the constraint matrices transpose, objective and right-hand sides swap, and the free dual variables of the equalities are $\lambda$. Both are feasible (any distributions, with suitable $\lambda$), so strong duality makes the optimal values equal — the minimax theorem.

5. For the $3\times3$ example verify $x^*=(5/9,0,4/9)$, $y^*=(0,2/3,1/3)$ gives value $1/3$, and explain $y^*_1=0$ via complementary slackness.

Reference answer: $(x^*)^TC=\frac59(2,-1,3)+\frac49(-1,2,-3)=(2/3,1/3,1/3)$ and $Cy^*=\frac23(-1,2,2)+\frac13(3,-3,-3)=(1/3,1/3,1/3)$. Hence $(x^*)^TCy^*=\frac59\cdot\frac13+\frac49\cdot\frac13=\frac13$. Since the first component of $(x^*)^TC$ is $2/3>1/3$, that dual constraint is not tight, so complementary slackness forces $y^*_1=0$; otherwise Bob's weight on column 1 would raise Alice's payoff above the value.

Relation to neighbouring lectures

The previous lecture's strong duality and complementary slackness receive their first game-theoretic reading here: primal and dual are the two players' optimal strategies and the game value is their common optimum. The next lecture carries the same LP machinery to network flows, deriving max-flow min-cut as the dual — the third full run of the "write the LP, take the dual, read off the combinatorial meaning" template.