线性规划运用¶

零和游戏¶

石头剪刀布¶

这个例子用"石头剪刀布"来说明博弈论. 首先要做的就是建立一个收益矩阵(payoff matrix), 将游戏结果数字化. 比如, 我作为玩家1, 赢就是+1, 输是-1, 平局是0. 这样我的所有选择和结果就一目了然了.

这里的一个核心思想是, 不能使用固定的纯策略(pure strategy). 如果我总是出石头, 对手肯定会一直出布来赢我. 最优的解法是采用混合策略(mixed strategy), 也就是随机化. 当我以⅓的均等概率出石头, 剪刀或布时, 不管对手怎么出, 我的期望收益都是0. 这样他就找不到我的规律来利用了.

最后还有一个关键定义, 叫零和博弈(zero-sum game). 意思很简单, 就是我的收益完全等于对手的损失, 我们双方的收益总和永远是零.

零和游戏¶

零和博弈是一种双人博弈, 其中一个玩家的收益等于另一个玩家的损失. 在这个定义中, S1和S2分别代表玩家1和玩家2的纯策略集合, P是收益矩阵, 当玩家选择策略(ai,bj)时, 玩家1获得收益pij而玩家2损失pij.

纯策略均衡¶

在一个二人零和博弈中, 如果存在一个策略组合\((a_i, b_j)\), 使得这个选择同时满足以下两个条件, 那么这个策略组合就是一个纯策略均衡点.

对于玩家1: 在玩家2选择策略\(b_j\)的前提下, 玩家1选择\(a_i\)能够获得最大收益. 任何其他的策略\(a_k\)都不会比\(a_i\)更好. 这就是\(p_{ij} \ge p_{kj}\)的含义.
对于玩家2: 在玩家1选择策略\(a_i\)的前提下, 玩家2选择\(b_j\)能够使自己的损失最小化(因为这是零和博弈, 最小化对方的收益就是最大化自己的收益). 任何其他的策略\(b_k\)都不会比\(b_j\)更好. 这就是\(p_{ij} \le p_{ik}\)的含义.

在这个均衡点上, 任何一个玩家单方面改变自己的策略, 都不会得到比当前更好的结果, 甚至可能会更糟. 因此, 双方都没有动力去改变策略, 整个系统达到了一个稳定的状态.

混合策略均衡¶

不是所有的博弈都存在之前讨论的纯策略均衡(鞍点). 例如, 在"石头剪刀布"中, 任何一个纯策略(比如一直出石头)都会被对手轻易击败, 所以不存在一个稳定的纯策略解.

为了解决这个问题, 玩家可以采用混合策略, 也就是不固定出某一个选择, 而是以一定的概率随机选择不同的策略. \(x\)和\(y\)是代表这种概率分布的向量.

向量\(x = (x_1, x_2, ..., x_n)\)表示玩家1以概率\(x_i\)选择第\(i\)个纯策略.
向量\(y = (y_1, y_2, ..., y_m)\)表示玩家2以概率\(y_j\)选择第\(j\)个纯策略.
概率的性质决定了\(\sum x_i = 1\)且\(x_i \ge 0\), 对\(y\)同理.

当双方都使用混合策略时, 我们无法预测单次博弈的确切收益, 只能计算期望收益(Expected Payoff). 这个期望收益是所有可能结果\((p_{ij})\)的加权平均值, 权重就是该结果发生的概率\((x_i y_j)\). 其计算公式为:

\[E(x, y) = \sum_i \sum_j x_i y_j p_{ij}\]

混合策略均衡的定义: 一个策略组合\((x, y)\)被称为混合策略均衡, 如果在这个组合下, 没有任何一个玩家有动机单方面改变自己的混合策略. 也就是说, 双方都认为自己当前的概率分布已经是针对对方策略的最优选择了.

对玩家2而言, 假设玩家1的策略\(x\)不变, 玩家2无论换成任何其他的混合策略\(\hat{y}\), 其期望收益(玩家1的收益)都不会比当前的\(y\)更低. 这保证了玩家2没有动机改变策略.

\[\sum_i \sum_j x_i y_j p_{ij} \le \sum_i \sum_j x_i \hat{y}_j p_{ij} \quad \text{for any } \hat{y}\]
对玩家1而言, 假设玩家2的策略\(y\)不变, 玩家1无论换成任何其他的混合策略\(\hat{x}\), 其期望收益都不会比当前的\(x\)更高. 这保证了玩家1没有动机改变策略.

\[\sum_i \sum_j x_i y_j p_{ij} \ge \sum_i \sum_j \hat{x}_i y_j p_{ij} \quad \text{for any } \hat{x}\]

混合策略均衡是一个更普适的概念. 它表明, 即使在一个没有稳定纯策略解的博弈中, 也必定存在一个稳定的概率混合方案, 使得双方都没有单方面偏离这个方案的理由. 约翰·纳什(John Nash)证明了任何有限博弈都至少存在一个这样的混合策略均衡, 这就是定理5.1, 下面我们给出它的证明, 需要使用上节讲到的对偶理论:

从玩家1的视角建模 (Primal Problem)
- 目标: 玩家1希望选择一个混合策略\(x\), 使得自己的期望收益最大化. 但他必须考虑到, 一旦他选定了\(x\), 理性的玩家2一定会选择一个策略\(y\)来让他的收益最小化.
- 策略: 因此, 玩家1的目标是最大化自己"最坏情况下的收益". 这可以表示为:
  
  \[\max_x \min_y \sum_i \sum_j x_i y_j p_{ij} = \max_x \min_j \sum_i x_i p_{ij}\]
- 线性规划形式: 这个"最大化最小值"问题可以被转换成一个标准的线性规划问题.
  - 引入一个变量\(z\), 代表玩家1在策略\(x\)下能获得的最低保证收益.
  - 目标是最大化\(z\).
  - 约束条件\(\sum_i x_i p_{ij} \ge z\)对所有\(j\)成立, 意味着无论玩家2选择哪个纯策略\(j\), 玩家1的收益都不会低于\(z\). 其他约束是概率的基本要求.
从玩家2的视角建模 (Dual Problem)
- 对偶问题: 在线性规划中, 每一个最大化问题(称为原始问题, Primal Problem)都有一个对应的最小化问题(称为对偶问题, Dual Problem).
- 玩家2的目标: 这个对偶问题恰好描述了玩家2的视角. 玩家2希望选择一个混合策略\(y\), 使得玩家1能获得的"最好情况下的收益"最小化. 这可以表示为:
  
  \[\min_y \max_i \sum_j y_j p_{ij} = \min_y \max_x \sum_i \sum_j x_i y_j p_{ij}\]
- 线性规划形式: 对偶问题的目标是最小化变量\(t\), \(t\)代表玩家2在策略\(y\)下, 玩家1可能获得的最高收益. 约束条件保证了无论玩家1选择哪个纯策略\(i\), 他的收益都不会高于\(t\).
强对偶定理与均衡证明 (Strong Duality)
- 核心定理: 线性规划的强对偶定理(Strong Duality Theorem)指出, 如果原始问题和对偶问题都有可行解, 那么它们的最优解相等. 在这里, 即\(z^* = t^*\).
- 均衡的意义: 这个等式意味着:
  
  \[\max_x \min_y \sum_i \sum_j x_i y_j p_{ij} = \min_y \max_x \sum_i \sum_j x_i y_j p_{ij}\]
- 证明无偏离动机: 文末的两行长公式正是利用这个\(z^*=t^*\)的结论以及原始和对偶问题的约束条件来证明, 在这个最优解\((x^*, y^*)\)下, 任何一方单方面改变策略都不会得到更好的结果.
  - 第一行公式证明了玩家2没有动机从\(y^*\)偏离.
  - 第二行公式证明了玩家1没有动机从\(x^*\)偏离.