基于线性规划的博弈论混合策略纳什均衡求解示例
我将为您讲解如何利用线性规划求解博弈论中的混合策略纳什均衡问题。这是一个将博弈论与线性规划相结合的经典应用。
问题描述
考虑一个二人零和博弈：玩家A和玩家B。玩家A有m个纯策略（行动选择），玩家B有n个纯策略。当玩家A选择策略i、玩家B选择策略j时，玩家A获得收益a_ij，玩家B则损失a_ij（因为是零和博弈）。每个玩家都希望最大化自己的期望收益。
在混合策略中，玩家A以概率x_i选择策略i（满足∑x_i=1, x_i≥0），玩家B以概率y_j选择策略j（满足∑y_j=1, y_j≥0）。纳什均衡是指一组混合策略，使得任何单方面偏离都不会带来额外收益。
解题过程
第一步：建立数学模型
根据博弈论的最小最大定理，在混合策略纳什均衡中，玩家A的最大最小期望收益等于玩家B的最小最大期望损失，这个共同值称为博弈值v。
对于玩家A，其线性规划问题为：
maximize v
subject to:
∑{i=1}^m a_ij × x_i ≥ v, for j = 1,...,n (保证无论B选什么策略，A的收益至少为v)
∑{i=1}^m x_i = 1
x_i ≥ 0, for i = 1,...,m
第二步：转化为标准线性规划形式
将原问题改写为标准形式：
maximize v
subject to:
∑{i=1}^m a_ij × x_i - v ≥ 0, for j = 1,...,n
∑{i=1}^m x_i = 1
x_i ≥ 0, for i = 1,...,m
这是一个含有m+1个变量（x_1,...,x_m, v）和n+1个约束的线性规划问题。
第三步：求解玩家A的最优混合策略
假设具体数值示例：玩家A有2个策略，玩家B有3个策略，收益矩阵为：
B1 B2 B3
A1: 3, 1, 4
A2: 2, 5, 1
玩家A的线性规划为：
maximize v
subject to:
3x₁ + 2x₂ ≥ v (当B选B1时)
1x₁ + 5x₂ ≥ v (当B选B2时)
4x₁ + 1x₂ ≥ v (当B选B3时)
x₁ + x₂ = 1
x₁, x₂ ≥ 0
第四步：求解玩家B的最优混合策略
根据对偶理论，玩家B的问题恰好是玩家A问题的对偶：
minimize u
subject to:
3y₁ + 1y₂ + 4y₃ ≤ u (当A选A1时)
2y₁ + 5y₂ + 1y₃ ≤ u (当A选A2时)
y₁ + y₂ + y₃ = 1
y₁, y₂, y₃ ≥ 0
第五步：具体计算过程
将玩家A的问题转化为标准线性规划：
maximize v
subject to:
3x₁ + 2x₂ - v ≥ 0
1x₁ + 5x₂ - v ≥ 0
4x₁ + 1x₂ - v ≥ 0
x₁ + x₂ = 1
x₁, x₂ ≥ 0
通过单纯形法求解，得到最优解：
x₁ = 4/7, x₂ = 3/7, v = 18/7
第六步：验证与解释
玩家A的最优混合策略是以4/7的概率选择A1，以3/7的概率选择A2，期望收益为18/7。
对应的玩家B最优混合策略为：
y₁ = 0, y₂ = 3/7, y₃ = 4/7, u = 18/7
这组混合策略构成了纳什均衡：任何玩家单方面改变策略都不会提高自己的期望收益。
总结
通过线性规划方法，我们可以系统地求解二人零和博弈的混合策略纳什均衡。这种方法保证了在多项式时间内找到最优解，为博弈分析提供了有效的计算工具。