二人零和对策解法solution of zero-sum two-person games

对于P有m个纯策略，Q有n个纯策略，P的赢得矩阵为m×n矩阵B=(b_ij)的（二人零和对策），双方的最优混合策略p和q的解法如下：
首先，选取适当的常数τ加到B的每个元素上去，得到一个所有元素都是正数的新矩阵：

A=(a_ij)=(b_ij+τ)

然后，记e为分量都是1的适当维数的向量，将对策问题转化为下述线性规划问题来解：考虑m维列向量u和n维列向量v，在u≥0和u^TA≥e的约束之下，求出使得目标函数σ=u₁+u₂+…+u_m达到最小的u=(u₁,u₂，…，u_m)^T，上标T表示转置，这时p=(u₁/σ,u₂/σ，…，u_m/σ)就是P的最优混合策略，均衡值是w=(1/σ)-τ。类似地，在v≥0和Av≤e的约束之下，求出使得目标函数σ=v₁+v₂+…+v_n达到最大的v=(v₁,v₂，…，v_n)^T，则q=(v₁/σ,v₂/σ，…，v_n/σ)就是Q的最优混合策略，均衡值也将是w=(1/σ)-τ。这种求解方法称为二人零和对策的线性规划解法。可以证明，解二人零和对策问题与解线性规划问题是等价的。
简单的二人零和对策也可以用最小最大定理直接求解。当m=2或n=2，即当P和Q中之一方只有两个可供选择的纯策略时，还可以用图解法求解二人零和对策。