博弈论与纳什均衡

博弈论基本知识

一般来说提到博弈论就想到的是纳什均衡, 那就直接来看看纳什做了什么工作.

纳什的博弈理论是基于缺乏联盟的非合作博弈形式, 即假设每个参与者的行动是独立的, 只关心自己利益的最大化. 考虑到每个人可以按照事先决定的概率分布在自己的策略空间混合, 对每个人来说, 对自己选取的每一种确定的行动, 就对应一个期望收益. 在非合作的前提下, 给定别人的策略, 每个人都希望自己的策略能够最大化自己的期望收益. 当每个人都不能通过仅仅改变自己的策略来提升自己的效益的时候, 就达到了一个纳什均衡点. 也就是说, 在一个均衡中, 某个人 $i$ 的策略 $\alpha$ 如果被以正的概率选择, 则给定其他人的策略时, 这个策略一定是可以最大化自己期望效用的策略中的某一个, 这也是纳什均衡的另一个充要条件.

以下是数学化的描述：

有限博弈：博弈中有 $n$ 个人, 每个人有有限个纯策略, 以及收益函数 $p_i: (\pi_1,\pi_2,\cdots \pi_n) \rightarrow \mathbb{R}$ 把所有人可能的纯策略映射到实数上.

混合策略 $s_i$：

玩家 $i$ 的混合策略是指在自己的纯策略空间上以非负的概率混合. 可以记 $s_i = \Sigma_\alpha c_{i\alpha}\pi_{i\alpha}$, 其中 $c_{i\alpha} \ge 0$ 且 $\Sigma_\alpha c_{i\alpha} = 1$. 在这里, $i, j, k$ 表示不同的玩家, $\alpha, \beta, \gamma$ 表示一个玩家的不同纯策略, $s_i, t_i, r_i$ 表示不同的混合策略, $\pi_{i\alpha}$ 表示玩家 $i$ 的纯策略 $\alpha$.

（完整的) 收益函数 $p_i$：

作为对上文收益函数的推广, 在混合策略是即是各个纯策略收益按照实现概率的线性组合, 用$\mathfrak{s}$ 来表示混合策略的 $n$ 元组, 这样的n元组 $\mathfrak{s}$ 也可以看做包含混合战略的积向量空间中的一点. 并且, 所有的n元组构成的集合是一个凸的多面体. 为了方便引入替代记号 $(\mathfrak{s};t_i)$ 表示 $s_1,\cdots , s_{i-1}, t_i, s_{t+1}, \cdots, s_n)$.

一个 $n$ 元组 $\mathfrak{s}$ 是均衡点当且仅当对于任意 $i$, 满足

$$p_i(\mathfrak{s}) = \max_{r_i}[p_i(\mathfrak{s};r_i)]$$

由线性性可得, 考虑最优时不用考虑所有的混合策略, 只要考虑玩家 $i$ 当前的混合策略能否实现自己采用任何纯策略的最大收益, 有 $\max_{r_i}[p_i(\mathfrak{s};r_i)] = \max_\alpha[p_i(\mathfrak{s};\pi_{i\alpha})]$. 所以另一个等价条件可以写作

$$p_i(\mathfrak{s}) = \max_\alpha p_i(\mathfrak{s}, \pi_{i\alpha})$$

由对每个人的以上等式可得, 均衡点可被表达为一个 $n$ 元组中 $n$ 个连续函数的等式同时满足, 因此均衡点形成了这个空间中的一个紧的子集. 事实上, 这个子集是由一些代数变元切割另一些代数变元形成的.

Since a criterion (3) for an eq. pt. can be expressed by the equating of n pairs of continuous functions on the space of n-tuples $\mathfrak{s}$, the eq. pts. obviously form a closed subset of this space. Actually, this subset is formed from a number of pieces of algebbraic varieties, cut out by other algebraic varieties.

对于 $n$ 个人的有限博弈 (每个人的策略空间有限), 纳什证明了均衡点一定存在.

另外的一篇文章 (Proc. Nat. Acad. Sci. U.S.A.,36,pp.48-49) 基于角谷静夫不动点定理 (Kakutani’s generalized fixed point theorem) 证明了均衡点的存在性. 纳什的文章直接基于布劳威尔定理 (Brouwer theorem) 给出证明. 我们构造一个 $n$ 元组构成的策略空间上的满足若干性质的连续变换 $T$, 使得 $T$ 的不动点就是博弈的均衡点.

定理1：任何一个有限博弈都存在均衡点.

证明： 记给定混合策略 $\mathfrak{s}$, 而玩家 $i$ 采用纯策略 $\alpha$ 时对应玩家 $i$ 的收益为 $p_{i\alpha}(\mathfrak{s})$. 定义关于 $\mathfrak{s}$ 的连续函数

$$\varphi_{i\alpha} (\mathfrak{s}) = \max (0, p_{i\alpha}(\mathfrak{s}) - p_i(\mathfrak{s}))$$

并且, 对于每一个 $\mathfrak{s}$ 中的战略 $s_i$, 我们定义其调整：

$$s_i'=\frac{s_i + \Sigma_\alpha \varphi_{i\alpha}(\mathfrak{s}) \pi_{i\alpha}}{1 + \Sigma_\alpha \varphi_{i\alpha}(\mathfrak{s})}$$

记 $\mathfrak{s}' = (s_1',\cdots , s_n')$

接下来证明变换 $T: (\mathfrak{s}) \rightarrow \mathfrak{s}'$ 的不动点就是均衡点.

对于任意的 $n$ 元组 $\mathfrak{s}$, 考虑玩家 $i$ 的策略. 对于任意被赋予正的概率的策略 $\beta$, 都应当满足 $p_{i\beta}(\mathfrak{s}) = p_i(\mathfrak{s})$, 所以 $\varphi_{i\beta} (\mathfrak{s}) = 0$.

如果 $\mathfrak{s}$ 是 $T$ 的不动点, 对于上述纯策略 $\beta$ 的概率应当不变, 考虑变换中 $\pi_{i\beta}$ 策略的概率在变换前后相等, 则 $\Sigma_\alpha \varphi_{i\alpha}(\mathfrak{s}) = 0$, 即对所有的 $i, \alpha$, 都有 $\varphi_{i\alpha}(\mathfrak{s})$, 即没有人可以通过偏离自己的策略获得更高的收益.

布劳威尔定理证明了这样的变换 $T$ 一定存在不动点, 所以均衡点一定存在.

注意到这里的空间是凸且闭的, 并且函数连续

博弈的对称性

一个在博弈上的自同构, 或者说变换, 是在它的纯战略集上进行的满足一定条件的置换.

如果某两个战略同属于一个玩家, 那么在这个变换下, 它们仍然属于同一个玩家

如果 $\phi$ 是纯策略的一个置换, 它引导了玩家的置换 $\psi$.

每个纯策略的 $n$ 元组因此可以被置换为另一个纯策略的 $n$ 元组. 我们称 $\chi$ 为其诱导的 $n$ 元组上的置换；$\xi$ 为纯战略的 $n$ 元组, 那么我们要求：

$$j = i^\psi\quad \text{then } p_j(\xi^\chi) =p_i(\xi)$$

从置换 $\phi$ 可以从 $s_i$ 线性拓展出混合策略

$$(s_i)^\phi = \Sigma_\alpha c_{i\alpha}(\pi_{i\alpha})^\phi$$

由此 $\chi$ 也可以拓展到混合策略上, 我们定义对称 $n$ 元组

$$\mathfrak{s}^\chi = \mathfrak{s}, \forall \chi$$

定理2：任何一个有限博弈都存在一个对称均衡点.

证明： 首先我们注意到 $s_{i0} = \Sigma_\alpha \pi_{i\alpha} / \Sigma_\alpha 1$ 具有性质 $(s_{i0})^\phi = s_{j0}$, 其中 $j = i^\psi$. 所以 $\mathfrak{s}_0 = (s_{10}, \cdots, s_{n0})$ 是一个对称n元组.

如果 $\mathfrak{s}, \mathfrak{t}$ 都是对称的, 则 $\frac{\mathfrak{s} + \mathfrak{t}}{2}$ 也是对称 $n$ 元组, 满足以上性质, 因此

$$(\frac{\mathfrak{s} + \mathfrak{t}}{2})^\chi = \frac{\mathfrak{s} + \mathfrak{t}}{2}$$

因此, 在 $n$ 元组构成的空间中, 对称 $n$ 元组构成的子空间仍然是凸空间.

现在考虑映射 $T: \mathfrak{s} \rightarrow \mathfrak{s}'$,

如果

$$\mathfrak{s}_2 = T\mathfrak{s}_1$$

且 $\chi$ 来自博弈的自同构我们有 $\mathfrak{s}_2^\chi = T\mathfrak{s}_1^\chi$.

如果 $\mathfrak{s}_1$ 对称（即 $\mathfrak{s}^\chi = \mathfrak{s}_1$), $\mathfrak{s}_2\chi = T\mathfrak{s}_1 = \mathfrak{s}_2$.

因此, 在对称n元组空间中使用变换T的不动点定理, 同样可以得到一个不动点. 由此可见, 必定存在一个对称的均衡点.

---

布劳威尔定理与角谷静夫不动点定理

**布威劳尔不动点定理：**设 $A$ 为$\mathbb{R}^n$ 中的一紧致凸集, $f$ 为将 $A$ 映射到 $A$ 的一连续函数, 则 $A$ 中至少存在一点 $x$ 使得 $x = f(x)$.

其后, 角谷静夫于1941年将此定理推广到点到集映射上. 函数是从点到点的映射, 而多值函数是从点到集合的映射, 所以角谷不动点定理可以看作布劳威尔不动点定理的一般化. 设对每一 $x \in A$, $f(x)$ 为 $A$ 的一子集. 若 $f(x)$ 具有性质：对 $A$ 的任一收敛序列 $x_i \rightarrow x_0$, 若 $y_i \in f(x_i)$ 且 $y_i \rightarrow y_0$, 则有 $y_0 \in f(x_0)$, 如此的 $f(x)$ 称为在 $A$ 上半连续.

角谷静夫不动点定理：设 $A$ 为$\mathbb{R}^n$ 中的一个非空紧凸集, 对于任何 $x \in A$, 若 $f(x)$ 为 $A$ 的一非空凸集, 且 $f(x)$ 在 $A$ 上为上半连续, 则存在 x^\* \in A, 使得 x^* \in f(x^\*).