1.对策论
社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来 解决这样的问题开始于 17 世纪的科学家，如 C.，Huygens 和 W.，Leibnitz 等。现代对 策论起源于 1944 年 J.，Von Neumann 和 O.，Morgenstern 的著作《Theory of Games and Economic Behavior》。
对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。 一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展 的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常 生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。
在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并 力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。
2.对策问题
对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。
先考察一个实际例子。
| 嫌疑犯 B | 供认 不供认 | |
|---|---|---|
| 嫌疑犯A | 供认 | （3，3） （7，0） |
| 不供认 | （0，7） （1.5，1.5） |
表 1 中每对数字表示嫌疑犯 A、B 被判刑的年数。如果两名疑犯均担心对方供认并希 望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。
从这一简单实例中可以看出对策现象中包含有的几个基本要素。
2.1 对策的基本要素
（i）局中人
在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局 中人。通常用 I 表示局中人的集合．如果有 n 个局中人，则 I = {1,2,L, n} 。一般要求 一个对策中至少要有两个局中人。在例 1 中，局中人是 A、B 两名疑犯。
（ii）策略集
一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参 加对策的每一局中人 i ， i ∈ I ，都有自己的策略集 S i 。一般，每一局中人的策略集中 至少应包括两个策略。
（iii）赢得函数（支付函数） 在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若 s i 是第 i 个局中人的一个策略，则 n 个局中人的策略组
s = ( s 1 , s 2 ,L, s n )
就是一个局势。全体局势的集合 S 可用各局中人策略集的笛卡尔积表示，即
S = S 1 × S 2 ×L× Sn
笛卡尔积:笛卡尔积是指在数学中,两个集合X和Y的笛卡尔积(Cartesian product),又称直积,表示为X x Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员.
(类似的例子有,A表示某学校学生的集合,B表示该学校所有课程的集合,则A与B的笛卡尔积表示该学校所有学生的可能选课情况.)
假设集合A={a.b} B={0,1,2}则两个集合的笛卡尔积为{(a,0,(a,1),(1,2),(b,0),(b,1),(b,2)}.
当局势出现后，对策的结果也就确定了。也就是说，对任一局势， s ∈ S ，局中人 i 可以得到一个赢得 H i ( s ) 。显然， H i ( s ) 是局势 s 的函数，称之为第 i 个局中人的赢
得函数。这样，就得到一个向量赢得函数 H ( s ) = ( H 1 ( s ),…, H n ( s )) 。 本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中去。
2.2 零和对策（矩阵对策）
零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。
设局中人Ⅰ、Ⅱ的策略集分别为
S 1 = {α 1 ,…, α m } ， S 2 = {β 1 ,…, β n }
当局中人Ⅰ选定策略 α i 和局中人Ⅱ选定策略 β j 后，就形成了一个局势 (α i , β j ) ，可见
这样的局势共有 mn 个。对任一局势 (α i , β j ) ，记局中人Ⅰ的赢得值为 a ij ，并称
A=
⎡ a 11 a 12 L a 1 n ⎤
⎢ a 21 a 22 L a 2 n ⎥
⎢ ⎥ ⎢.. .. .. ..⎥ ⎢ ⎥
⎣ a m 1 a m 2 L a mn ⎦
为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定对策为零和的，故局中 人Ⅱ的赢得矩阵就是 − A 。 当局中人Ⅰ、Ⅱ和策略集 S 1 、 S 2 及局中人Ⅰ的赢得矩阵 A 确定后，一个零和对策 就给定了，零和对策又可称为矩阵对策并可简记成
例
G = {S 1 , S 2 ; A} 。
2
设 有 一 矩 阵 对 策 G = {S 1 , S 2 ; A} ， 其 中 S 1 = {α 1 , α 2 , α 3 } ，
S 2 = {β 1 , β 2 , β 3 , β 4 } ，
A =⎡ 12 − 6 30 − 22 ⎤
⎢14 2 18 10 ⎥ ⎢ − 6 0 − 10 16 ⎦
从 A 中可以看出，若局中人Ⅰ希望获得最大赢利 30，需采取策略 α 1 ，但此时若局 中人Ⅱ采取策略 β 4 ，局中人Ⅰ非但得不到 30，反而会失去 22。为了稳妥，双方都应考 虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人Ⅰ采取策 略 α1 、α2 、α 3 时，最坏的赢得结果分别为
min{12,−6,30,−22} = −22
min{14,2,18,10} = 2
min{−6,0,−10,16} = −10
其中最好的可能为 max{−22,2,−10} = 2 。如果局中人Ⅰ采取策略 α 2 ，无论局中人Ⅱ 采取什么策略，局中人Ⅰ的赢得均不会少于 2。
x{30,18,−10} = 30 ，和 max{−22,10,16} = 16 。当局中人Ⅱ采取策略 β 2时，其损
局中人Ⅱ采取各方案的最大损失为 max{12,14,−6} = 14 ， max{−6,2,0} = 2 ，
失不会超过 2。注意到在赢得矩阵中，2 既是所在行中的最小元素又是所在列中的最大 元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减 少损失，称这样的局势为对策的一个稳定点或稳定解。
定义 1 设 f ( x, y ) 为一个定义在 x ∈ A 及 y ∈ B 上的实值函数，如果存在 x* ∈ A ， y* ∈ B ，使得对一切 x ∈ A 和 y ∈ B ，有
f ( x, y) ≤ f ( x, y) ≤ f ( x, y )
则称 ( x, y) 为函数 f 的一个鞍点。
定义
2
设 G = {S 1 , S 2 ; A} 为 矩 阵 对 策 ， 其 中 S 1 = {α 1 , α 2 ,L, α m } ，
S 2 = {β 1 , β 2 ,L, β n } ， A = ( a ij ) m × n 。若等式
max min a ij = min max a ij = ai * j * i j j i (1)
成立，记 V G = a i * j * ，则称 V G 为对策 G 的值，称使（1）式成立的纯局势 (α i * , β j * ) 为
对策 G 的鞍点或稳定解，赢得矩阵中与 (α i * , β j * ) 相对应的元素 a i * j * 称为赢得矩阵的鞍
点， α i * 与 β j * 分别称为局中人Ⅰ与Ⅱ的最优纯策略。
给定一个对策 G ，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面 的极大极小原理:
定理 1 设 G = {S 1 , S 2 ; A} ， 记 μ = max min a ij ， ν = − min max a ij ， 则必有 i j j iμ +ν ≤ 0 。
证明:
ν = max min( − a ij ) ，易见 μ 为Ⅰ的最小赢得，ν 为Ⅱ的最小赢得，由于 G
j
i
是零和对策，故 μ + ν ≤ 0 必成立。 定理 2 零和对策 G 具有稳定解的充要条件为 μ + ν = 0 。 证明：（充分性）由 μ 和ν 的定义可知，存在一行例如 p 行， μ 为 p 行中的最小元 素，且存在一列例如 q 列， − ν 为 q 列中的最大元素。故有
a pq ≥ μ 且 a pq ≤ −ν
又因 μ + ν = 0 ，所以 μ = −ν ，从而得出 a pq = μ ， a pq 为赢得矩阵的鞍点， (α p , β q )
为 G 的稳定解。 （必要性）若 G 具有稳定解 (α p , β q ) ，则 a pq 为赢得矩阵的鞍点。故有
μ = max min a ij ≥ min a pj = apq i j j
− ν = min max a ij≤ max a iq= apq