07. 对策论

定义

对策论亦称竞赛论或博弈论，是研究具有斗争或竞争性质现象的数学理论和方法。

基本要素：

局中人：在一个对策行为中，有权决定自己行动方案的对策参加者，通常用表示局中人集合；
策略集：一局对策中，可供局中人选择的一个实际可行的完整行动方案称一个策略，每个局中人都有自己的策略集；
赢得函数 (支付函数)：一局对策中，各局中人所选定的策略形成的策略组称一个局势，即若是第个局中人的一个策略，则策略组就是一个局势。全体局势的集合可用各局中人策略集的笛卡尔积表示，即对任意局势，局中人可以得到一个赢得，称赢得函数。

零和对策 (矩阵对策)

零和对策是一类特殊的对策问题，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于 0。

设局中人 1、2 的策略集当局中人 1 选定策略，局中人 2 选定策略后，就形成局势。对任一局势，记局中人 1 的赢得为，称为局中人 1 的赢得矩阵，由于对策零和，因此局中人 2 的赢得矩阵就是。

因此记零和对策为

稳定解和最优纯策略

设为矩阵对策，其中 ,，若等式成立，则称为的稳定解，分别为局中人 1、2 的最优纯策略。

如何理解上述定理？

对于前者，表示局中人 1 在策略中坏中取优，即计算所有策略的最坏结果，再从中挑选最好的一个策略。

对于后者，表示局中人 2 同样坏中取优，只不过局中人 2 的赢得矩阵为，因此先取大再取小，原式可以化为如果两者相等，说明存在一个形势，当局中人 1 取其最优纯策略时，局中人 2 取其他策略都比取其最优纯策略时收益小 (同样，局中人 1 的收益大)；反之亦然。即对于任意，有

混合策略

然而很多时候，等式并不成立，此时不存在稳定解和最优纯策略。引入混合策略。

设局中人 1 选用策略的概率为，局中人 2 选用策略的概率为，记则局中人 1 的期望赢得为则有向量使得等式成立，此时即为稳定解。

线性规划求稳定解

对于将混合策略看作纯策略，可以化为记，则即为线性规划问题

的解，同理即为线性规划问题

的解。

例子与 Python 代码

对赢得矩阵求局中人 1、2 的混合策略。

选取局中人 1，化为线性规划问题

选取局中人 2，化为线性规划问题

使用 Python 求解上述问题，代码如下：

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @ author: Koorye
# @ date: 2021-7-25
# @ function: 使用 cvxpy 包进行矩阵对策混合策略求解

# %%

import numpy as np
import cvxpy as cp

# %%

# 赢得矩阵
A = np.array([[3, 0, 2, 0],
              [0, 2, 1, 5],
              [1, 2, 3, 4]])

# %%

# 不等式约束形如 A * x <= b
A1 = A.copy().T
A2 = A.copy()

# 决策变量
x = cp.Variable(A1.shape[1]+1)
y = cp.Variable(A2.shape[1]+1)

# 约束条件
con1 = [
    A1 @ x[:-1] >= x[-1],
    sum(x[:-1]) == 1,
    x[:-1] >= 0,
]
con2 = [
    A2 @ y[:-1] <= y[-1],
    sum(y[:-1]) == 1,
    y[:-1] >= 0,
]

# 目标函数
obj1 = cp.Maximize(x[-1])
obj2 = cp.Minimize(y[-1])

# %%

p1 = cp.Problem(obj1, con1)
p2 = cp.Problem(obj2, con2)
p1.solve(solver='GLPK_MI', verbose=True)
p2.solve(solver='GLPK_MI', verbose=True)

# %%

print('x =', x.value[:-1])
print('y =', y.value[:-1])
print('x exp =', x.value[-1])
print('y exp =', y.value[-1])

输出如下：

x = [ 0.25 -0.    0.75]
y = [ 0.5  0.5 -0.  -0. ]
x exp = 1.5
y exp = 1.5

于是有

吴世涵的博客

【数学建模笔记 07】数学建模的对策论