基于线性规划的博弈论混合策略纳什均衡求解示例

字数 2957 2025-11-01 09:19:03

基于线性规划的博弈论混合策略纳什均衡求解示例

题目描述

考虑一个二人零和博弈（two-player zero-sum game），其中玩家A有$m$个纯策略，玩家B有$n$个纯策略。玩家A的收益矩阵为$A \in \mathbb{R}^{m \times n}$（玩家B的收益矩阵为$-A$）。双方均以一定概率选择纯策略（即混合策略），目标是找到纳什均衡——玩家A的一个概率分布$x \in \mathbb{R}^m$和玩家B的一个概率分布$y \in \mathbb{R}^n$，使得在对方策略固定时，己方无法通过单方面改变策略提高期望收益。

问题可转化为以下线性规划模型（以玩家A的视角）：

\[\begin{aligned} \max_{x, v} \quad & v \\ \text{s.t.} \quad & \sum_{i=1}^m a_{ij} x_i \geq v, \quad j=1,\dots,n \quad \text{(玩家B选择策略$j$时，A的收益至少为$v$)} \\ & \sum_{i=1}^m x_i = 1, \quad x_i \geq 0 \end{aligned} \]

其中$v$表示玩家A的最小保证收益（博弈值），$x_i$是玩家A选择策略$i$的概率。类似地，玩家B的问题可转化为对偶线性规划。

解题步骤

步骤1：问题线性化

原始博弈问题是非线性的（因涉及双方策略的相互优化），但通过冯·诺依曼最小最大定理，可将其转化为线性规划：

玩家A的目标是最大化其最小收益（即$\max_x \min_y x^T A y$），等价于上述线性规划。
约束$\sum_{i} a_{ij} x_i \geq v$确保无论玩家B选择何种策略，玩家A的收益不低于$v$。

示例矩阵：
设收益矩阵$A = \begin{bmatrix} 2 & -1 \\ -1 & 1 \end{bmatrix}$，则线性规划为：

\[\begin{aligned} \max_{x_1,x_2,v} \quad & v \\ \text{s.t.} \quad & 2x_1 - x_2 \geq v \quad \text{(B选策略1)} \\ & -x_1 + x_2 \geq v \quad \text{(B选策略2)} \\ & x_1 + x_2 = 1, \quad x_1, x_2 \geq 0 \end{aligned} \]

步骤2：转换为标准形式

引入松弛变量$s_j \geq 0$，将不等式约束转为等式：

\[\begin{aligned} 2x_1 - x_2 - s_1 = v \\ -x_1 + x_2 - s_2 = v \end{aligned} \]

但$v$是自由变量，需进一步处理。更直接的方法是将问题写为：

\[\begin{aligned} \max \quad & v \\ \text{s.t.} \quad & 2x_1 - x_2 - v \geq 0 \\ & -x_1 + x_2 - v \geq 0 \\ & x_1 + x_2 = 1, \quad x_1, x_2 \geq 0 \end{aligned} \]

令$x_i' = x_i / v$（当$v > 0$时），可转化为另一种常见形式。但本例直接求解更直观。

步骤3：代入消元

由$x_2 = 1 - x_1$，代入约束：

约束1：$2x_1 - (1-x_1) \geq v \implies 3x_1 - 1 \geq v$
约束2：$-x_1 + (1-x_1) \geq v \implies 1 - 2x_1 \geq v$

问题变为：

\[\max_{x_1 \in [0,1], v} v \quad \text{s.t.} \quad v \leq 3x_1 - 1, \quad v \leq 1 - 2x_1 \]

由于目标是最大化$v$，等价于要求$v$尽可能大但不超过两个上界，因此最优解在$3x_1 - 1 = 1 - 2x_1$时取得（两条约束的交点）。

步骤4：求解方程

解$3x_1 - 1 = 1 - 2x_1$得：

\[5x_1 = 2 \implies x_1 = 0.4, \quad x_2 = 0.6 \]

代入得$v = 3 \times 0.4 - 1 = 0.2$。

步骤5：求玩家B的策略

通过线性规划的对偶性，玩家B的最小化问题为：

\[\begin{aligned} \min_{y, u} \quad & u \\ \text{s.t.} \quad & \sum_{j=1}^n a_{ij} y_j \leq u, \quad i=1,\dots,m \\ & \sum_{j=1}^n y_j = 1, \quad y_j \geq 0 \end{aligned} \]

代入矩阵$A$：

\[\begin{aligned} \min_{y_1,y_2,u} \quad & u \\ \text{s.t.} \quad & 2y_1 - y_2 \leq u \quad \text{(A选策略1)} \\ & -y_1 + y_2 \leq u \quad \text{(A选策略2)} \\ & y_1 + y_2 = 1, \quad y_1, y_2 \geq 0 \end{aligned} \]

同理消元（$y_2 = 1 - y_1$）得：

\[u \geq 2y_1 - (1-y_1) = 3y_1 - 1, \quad u \geq -y_1 + (1-y_1) = 1 - 2y_1 \]

最小化$u$需使$u = \max(3y_1 - 1, 1 - 2y_1)$，最优解在$3y_1 - 1 = 1 - 2y_1$时，解得$y_1 = 0.4, y_2 = 0.6, u = 0.2$。

步骤6：验证纳什均衡

玩家A的策略$x = (0.4, 0.6)$，玩家B的策略$y = (0.4, 0.6)$，博弈值$v = 0.2$。

若玩家B固定策略，玩家A的期望收益为$x^T A y = 0.2$，与$v$一致。
若玩家A固定策略，玩家B的期望收益为$-x^T A y = -0.2$，与对偶问题结果一致。
双方均无动机偏离策略，达成纳什均衡。

关键点总结

零和博弈的线性规划转化：利用最小最大定理将博弈问题转为线性规划。
对偶性：玩家A和玩家B的规划互为对偶，博弈值相同。
概率约束：策略概率和为1的约束是线性规划中的关键条件。
实际应用：此方法可用于求解石头剪刀布、扑克等博弈的混合策略均衡。

基于线性规划的博弈论混合策略纳什均衡求解示例题目描述考虑一个二人零和博弈（two-player zero-sum game），其中玩家A有$m$个纯策略，玩家B有$n$个纯策略。玩家A的收益矩阵为$A \in \mathbb{R}^{m \times n}$（玩家B的收益矩阵为$-A$）。双方均以一定概率选择纯策略（即混合策略），目标是找到纳什均衡——玩家A的一个概率分布$x \in \mathbb{R}^m$和玩家B的一个概率分布$y \in \mathbb{R}^n$，使得在对方策略固定时，己方无法通过单方面改变策略提高期望收益。问题可转化为以下线性规划模型（以玩家A的视角）： \[ \begin{aligned} \max_ {x, v} \quad & v \\ \text{s.t.} \quad & \sum_ {i=1}^m a_ {ij} x_ i \geq v, \quad j=1,\dots,n \quad \text{(玩家B选择策略$j$时，A的收益至少为$v$)} \\ & \sum_ {i=1}^m x_ i = 1, \quad x_ i \geq 0 \end{aligned} \] 其中$v$表示玩家A的最小保证收益（博弈值），$x_ i$是玩家A选择策略$i$的概率。类似地，玩家B的问题可转化为对偶线性规划。解题步骤步骤1：问题线性化原始博弈问题是非线性的（因涉及双方策略的相互优化），但通过冯·诺依曼最小最大定理，可将其转化为线性规划：玩家A的目标是最大化其最小收益（即$\max_ x \min_ y x^T A y$），等价于上述线性规划。约束$\sum_ {i} a_ {ij} x_ i \geq v$确保无论玩家B选择何种策略，玩家A的收益不低于$v$。示例矩阵：设收益矩阵$A = \begin{bmatrix} 2 & -1 \\ -1 & 1 \end{bmatrix}$，则线性规划为： \[ \begin{aligned} \max_ {x_ 1,x_ 2,v} \quad & v \\ \text{s.t.} \quad & 2x_ 1 - x_ 2 \geq v \quad \text{(B选策略1)} \\ & -x_ 1 + x_ 2 \geq v \quad \text{(B选策略2)} \\ & x_ 1 + x_ 2 = 1, \quad x_ 1, x_ 2 \geq 0 \end{aligned} \] 步骤2：转换为标准形式引入松弛变量$s_ j \geq 0$，将不等式约束转为等式： \[ \begin{aligned} 2x_ 1 - x_ 2 - s_ 1 = v \\ -x_ 1 + x_ 2 - s_ 2 = v \end{aligned} \] 但$v$是自由变量，需进一步处理。更直接的方法是将问题写为： \[ \begin{aligned} \max \quad & v \\ \text{s.t.} \quad & 2x_ 1 - x_ 2 - v \geq 0 \\ & -x_ 1 + x_ 2 - v \geq 0 \\ & x_ 1 + x_ 2 = 1, \quad x_ 1, x_ 2 \geq 0 \end{aligned} \] 令$x_ i' = x_ i / v$（当$v > 0$时），可转化为另一种常见形式。但本例直接求解更直观。步骤3：代入消元由$x_ 2 = 1 - x_ 1$，代入约束：约束1：$2x_ 1 - (1-x_ 1) \geq v \implies 3x_ 1 - 1 \geq v$ 约束2：$-x_ 1 + (1-x_ 1) \geq v \implies 1 - 2x_ 1 \geq v$ 问题变为： \[ \max_ {x_ 1 \in [ 0,1], v} v \quad \text{s.t.} \quad v \leq 3x_ 1 - 1, \quad v \leq 1 - 2x_ 1 \] 由于目标是最大化$v$，等价于要求$v$尽可能大但不超过两个上界，因此最优解在$3x_ 1 - 1 = 1 - 2x_ 1$时取得（两条约束的交点）。步骤4：求解方程解$3x_ 1 - 1 = 1 - 2x_ 1$得： \[ 5x_ 1 = 2 \implies x_ 1 = 0.4, \quad x_ 2 = 0.6 \] 代入得$v = 3 \times 0.4 - 1 = 0.2$。步骤5：求玩家B的策略通过线性规划的对偶性，玩家B的最小化问题为： \[ \begin{aligned} \min_ {y, u} \quad & u \\ \text{s.t.} \quad & \sum_ {j=1}^n a_ {ij} y_ j \leq u, \quad i=1,\dots,m \\ & \sum_ {j=1}^n y_ j = 1, \quad y_ j \geq 0 \end{aligned} \] 代入矩阵$A$： \[ \begin{aligned} \min_ {y_ 1,y_ 2,u} \quad & u \\ \text{s.t.} \quad & 2y_ 1 - y_ 2 \leq u \quad \text{(A选策略1)} \\ & -y_ 1 + y_ 2 \leq u \quad \text{(A选策略2)} \\ & y_ 1 + y_ 2 = 1, \quad y_ 1, y_ 2 \geq 0 \end{aligned} \] 同理消元（$y_ 2 = 1 - y_ 1$）得： \[ u \geq 2y_ 1 - (1-y_ 1) = 3y_ 1 - 1, \quad u \geq -y_ 1 + (1-y_ 1) = 1 - 2y_ 1 \] 最小化$u$需使$u = \max(3y_ 1 - 1, 1 - 2y_ 1)$，最优解在$3y_ 1 - 1 = 1 - 2y_ 1$时，解得$y_ 1 = 0.4, y_ 2 = 0.6, u = 0.2$。步骤6：验证纳什均衡玩家A的策略$x = (0.4, 0.6)$，玩家B的策略$y = (0.4, 0.6)$，博弈值$v = 0.2$。若玩家B固定策略，玩家A的期望收益为$x^T A y = 0.2$，与$v$一致。若玩家A固定策略，玩家B的期望收益为$-x^T A y = -0.2$，与对偶问题结果一致。双方均无动机偏离策略，达成纳什均衡。关键点总结零和博弈的线性规划转化：利用最小最大定理将博弈问题转为线性规划。对偶性：玩家A和玩家B的规划互为对偶，博弈值相同。概率约束：策略概率和为1的约束是线性规划中的关键条件。实际应用：此方法可用于求解石头剪刀布、扑克等博弈的混合策略均衡。