Hero Image
极小极大定理:怎样出招才不被猜中

在猜单双游戏里,没有好招。如果你总是伸一根手指,对手学会了就会每次都赢。唯一的防御是不可预测:随机出招,一半时间出一根,一半时间出两根。这样,无论对手怎么做,你都能赢一半的局。 1928 年,冯·诺依曼在一篇名为《论室内游戏的理论》的论文中证明,这个想法适用于所有两人零和博弈,即一方之所得恰是另一方之所失的博弈。而且它总会给出一个确切的数,即博弈的值。 一个小游戏 行方选 A 或 B,列方选 C 或 D,两人同时出招。下表给出行方得到(也即列方付出)多少: C D A $3$ $-1$ B $-2$ $1$ 没有显而易见的选择。如果行方总出 A,列方就用 D 应对,行方输 $1$。如果行方总出 B,列方就用 C 应对,行方输 $2$。那么假设行方随机出招:以概率 $p$ 出 A,以概率 $1 - p$ 出 B。行方的期望收益是 $$\text{对 C:} 3p - 2(1-p) = 5p - 2, \qquad \text{对 D:} -p + (1-p) = 1 - 2p.$$列方会选择让行方得得少的那种应对。所以行方只能指望两个值中较小的那个,并希望选择 $p$ 使这个最小值尽可能大。这发生在两条直线的交点处: $$5p - 2 = 1 - 2p \;\Longrightarrow\; p = \frac{3}{7}, \qquad \text{有保证的收益} = 5 \cdot \frac{3}{7} - 2 = \frac{1}{7}.$$ 请启用 JavaScript 以使用这个交互图形。完整的推理见正文。