零和博弈 · aiwiki.page

零和博弈是博弈论中的一种博弈：在每一种可能的结果下，所有参与者的收益之和都为零。在两人博弈中，一方的收益恰好是另一方收益的相反数：一方获得多少，另一方就损失多少。两人零和博弈为利益完全对立的情形提供了数学模型，并与均衡理论和最优化有着尤为密切的联系。(learn.mit.edu)

定义与常和博弈

对于参与者 $1,\ldots,n$ ，用 $u_i(s)$ 表示参与者 $i$ 在策略组合 $s$ 下的收益；策略组合指定了每位参与者所采用的策略。零和条件为

\sum_{i=1}^{n}u_i(s)=0 \quad\text{对所有 }s\text{ 均成立。}

对于两位参与者，这一条件变为 $u_2(s)=-u_1(s)$ 。收益表示模型所规定的数值回报或效用（经济学），不一定是货币收入。(cs.cmu.edu)

常和博弈则满足 $\sum_i u_i(s)=c$ ，其中 $c$ 不随结果变化。只要从各参与者的收益中分别减去一些总和为 $c$ 的常数，就可以将其转化为零和博弈。例如，从每位参与者的收益中减去 $c/n$ ，便能使总收益变为零，同时不改变任何参与者对策略的偏好。因此，在这种规范化处理下，常和博弈与零和博弈在策略上是等价的。(bpb-us-e1.wpmucdn.com)

“零和”并不意味着每位参与者的收益都为零，也不意味着博弈是公平的，或其均衡值为零。它描述的是收益的总和，而不是各个收益的大小。(cs.cmu.edu)

矩阵表示与策略

有限两人零和博弈可以用一个收益矩阵 $A$ 表示。行方选择第 $i$ 行，列方选择第 $j$ 列，两者的收益分别为 $A_{ij}$ 和 $-A_{ij}$ 。行方力求使这一矩阵元素最大，列方则力求使其最小。(cs.cmu.edu)

纯策略是以确定的方式选择一个可用策略。混合策略则是纯策略集合上的概率分布。如果双方分别按照概率向量 $x$ 和 $y$ 独立地随机选择策略，那么行方收益的期望值为

x^{\mathsf T}Ay =\sum_i\sum_j x_iA_{ij}y_j,

其中，所有概率都非负，且每个向量的分量之和均为一。随机化可以防止对手利用可预测的选择获利。(cs.cmu.edu)

极小化极大定理与均衡

行方的极大化极小收益，是其面对任何对手策略时都能保证获得的最大期望收益。列方的极小化极大界，是其能够为行方收益设定的最小上界。约翰·冯·诺依曼于 1928 年证明的极小化极大定理，也是极小化极大算法的理论基础；该定理指出，对于任意有限两人零和博弈，这两个量相等：

\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^{\mathsf T}Ay = \min_{y\in\Delta_n}\max_{x\in\Delta_m}x^{\mathsf T}Ay =v,

其中， $\Delta_m$ 和 $\Delta_n$ 分别是相应维数的概率向量集合。数值 $v$ 称为行方的博弈值。(web.mit.edu)

最优策略 $x^*,y^*$ 满足

x^{\mathsf T}Ay^* \leq x^{*\mathsf T}Ay^* =v \leq x^{*\mathsf T}Ay \quad\text{对所有 }x,y\text{ 均成立。}

它们构成一个鞍点，也是一个纳什均衡：任何一方都无法通过单方面改变策略来提高自身收益。最优策略未必唯一，但所有均衡策略对都产生相同的博弈值。这些保证针对的是期望收益，而不是每一次博弈的实际结果。(web.mit.edu)

示例：猜硬币博弈

在猜硬币博弈中，两位参与者同时选择正面或反面。如果选择相同，行方获得 $+1$ ；否则，行方获得 $-1$ 。列方的收益则与之相反：

行方 / 列方	正面	反面
正面	$1$	$-1$
反面	$-1$	$1$

这个博弈不存在纯策略均衡：面对任何固定选择，对手都可以作出对自己有利的回应。在均衡状态下，双方都以 $1/2$ 的概率选择正面和反面，博弈值为零。采用这一混合策略的参与者，无论面对对手的哪一种纯策略，其期望收益都为零；不过，每次实际博弈仍然会有一方获胜、另一方落败。(cs.cmu.edu)

计算与适用范围

有限矩阵博弈可以通过线性规划求解。行方在以下约束下最大化 $v$ ：

A^{\mathsf T}x\geq v\mathbf 1,\qquad \mathbf 1^{\mathsf T}x=1,\qquad x\geq0.

列方在以下约束下最小化 $w$ ：

Ay\leq w\mathbf 1,\qquad \mathbf 1^{\mathsf T}y=1,\qquad y\geq0.

这些约束表达了面对对手的每一种纯策略时所能保证的收益界。这两个规划互为对偶，拉格朗日对偶的强对偶性给出 $v=w$ ，从而提供了极小化极大定理的一种证明。(arxiv.org)

“两人”这一限定十分重要。对于三人或更多人的博弈，总收益为零并不意味着任意两人的利益都相互对立：多位参与者可能以另一位参与者的损失为代价共同获益。相反，非零和博弈允许总收益随结果而变化，因此可能出现共同获益、共同受损，或合作与冲突并存的情形。所以，仅凭存在竞争，并不能判定一种互动是零和的；模型中规定的收益必须满足零和条件。(people.csail.mit.edu)

参考来源

Lecture 7: Zero-Sum Gameslearn.mit.edu
15-859(M): Randomized Algorithmscs.cmu.edu
Leveraging Symmetries in Strategic Gamescs.cmu.edu
853: Topics in Algorithmic Game Theory, Fall 2011people.csail.mit.edu
Lecture 12: February 13bpb-us-e1.wpmucdn.com
Table 1. Matching pennies and coordination matrix gamescs.cmu.edu
S890: Topics in Multiagent Learning, Lecture 3web.mit.edu
Zero-Sum Games and Linear Programming Dualityarxiv.org
Two-Person Gamesmat.tepper.cmu.edu
Non-zero-sum Game Theorycs.cmu.edu