毕业论文(设计)题目: 二人零和有限对策问题的研究学院: 数理与信息学院学生姓名: 梁世龙学号：060503202专业：数学与应用数学班级：B06数学(2)班指导老师：金丽起止日期：2010.03.01~2010.05.072010 年6 月18 日摘要二人零和有限对策是对策论的分支问题. 而对策论是应用数学的一个分支问题, 目前在生物学, 经济学, 国际关系, 计算机科学, 政治学, 军事战略和其他很多学科都有广泛的应用. 二人零和有限对策是一种最基本的策略, 它的一套比较成熟的理论和算法是研究其他各种对策的基础. 本文主要讨论二人零和有限对策问题的基本理论和算法, 并了解在实际问题中的应用.关键词: 二人零和有限对策; 对策论; 鞍点Finite Two Person Zero-sum GamesAbstractFinite two person zero-sums game is a branch of game theory, and game theory is a branch problem of applied mathematics. It has a wide range of application in biology, economics, international relations, computer science, political science, military strategy and many other disciplines at present. Finite two person zero-sum games is a basic strategy, it has the mature theory and algorithms, it is the basis for study the other game problems. This article focuses on the basic theory and algorithms of Finite two person zero-sums game, and understands the applications of practical problems.Keywords:Finite two person zero-sums game; Game theory; Saddle point目录摘要 (I)Abstract (II)1 前言 (1)2 对策 (2)2.1对策的例子 (2)2.2对策的基本要素 (2)2.3展开型对策 (5)2.4对策的分类 (11)3 二人零和有限对策 (12)3.1矩阵对策的基本概念 (12)3.2混合策略 (17)3.3最大最小定理 (25)3.4矩阵对策的最优策略 (27)3.5矩阵对策与线性规划的关系 (36)3.6矩阵对策的求解 (42)4小结 (54)致谢 (56)1 前言对策论是研究竞争性行为的数学分支. 在日常生活中的下棋、打牌、体育竞赛等, 在社会生活中如战争、企业的竞争等, 都具有竞争或对抗的性质, 我们把这一类行为称为对策行为. 在对策行为里, 参加竞争的个体有不同的目标和利益. 为了实现各自的目标, 每个个体必须考虑对手的各种行动方案, 并尽量选取对自己最有利的策略.二人零和对策是指参与对策的局中人只有两个, 每个人的策略集均是有限集并且两个局中人的赢利之和为零(或某个常数). 在对策论中理论最简单又最完善的部分是二人零和对策, 它是其他各部分理论的基础. 在一个二人对策问题中(例如两人进行对抗性竞赛), 参加者分别为局中人甲和乙, 他们都有自己的策略. 若甲有m 个策略, 乙有n 个策略. 当甲选取第i 个策略时，乙选取第j 个策略, 这便形成一种局势. 此时甲、乙双方会有赢得或损失. 若甲所得为()()(),,1,2,,;1,2,,i j a f x i j i m j n ==== , 乙的所得为(),i ja -, 则(),i ja 为甲取第i 个策略、乙取第j 个策略时甲的支付(或赢得).[1]上述问题可用矩阵方法进行处理. 因此这类对策也称为二人零和矩阵对策. 对策论的中心问题是局中人采取何种策略才能使自己赢得最多(或损失最少).从数学角度看, 二人零和对策问题可以分为二人零和有限对策和二人零和无限对策, 在这里我们只讨论二人零和有限对策.二人零和有限对策是一种最简单、最基本的策略. 说它简单是因为只有两个局中人, 并且每个局中人只有有限个策略; 说他基本是因为它有比较成熟的理论和算法，是研究其他对策的基础. 二人零和有限对策也称为矩阵对策. 在每局中, 两个局中人独立选择一个策略(互相都不知道对方的策略), 而两人的收益总和为零. 在这种对策中, 两个局中人的利益是完全相反的, 因此不可能合作.本文中我们主要介绍二人零和有限对策的理论和矩阵对策问题的求解方法.2 对策2.1 对策的例子[2]例 2.1田忌赛马问题. 战国时期, 齐国的国王与一名叫田忌的大将进行赛马. 双方各出三匹马, 分别为上(等)马、中(等)马、下(等)马各一匹. 比赛时, 每次双方各从自己的三匹马中任选一匹马来比, 输者付给胜者1千两黄金, 共赛三次. 当时, 三种不同等级的马相差非常悬殊, 而同等级的马, 齐王的比田忌的要强. 谋士孙膑给田忌出了个主意: 每次比赛先让齐王牵出他要参赛的马, 然后用下马对齐王的上马, 用中马对齐王的下马, 用上马对齐王的中马. 结果田忌二胜一负, 赢得1千两黄金. 由此看来, 两人采取什么样的策略(出马次序)对胜负是至关重要的.例 2.2 冬季取暖问题. 某单位要在秋季决定冬季取暖所用煤的储量. 在正常的冬季气温下，需要消耗15吨煤, 但在较暖或较冷的时候分别需要10吨和20吨煤. 设煤的价格随着冬季的冷暖程度而有所变动: 在较暖、正常、较冷的气温下分别为每吨100元、120元、150元. 假设在秋季煤价为每吨100元. 问在没有当年冬季准确的气象预报条件下, 秋季储存多少吨煤才合理?例 2.3罪犯两难问题. 甲、乙两人因犯罪而牵涉于某案件中, 但法院只掌握其部分罪证. 如果他们都不承认, 则他们将被作为较小的违法案件的被告而受到惩罚(例如各判刑一年); 如果两人都认罪, 则两人都被判刑, 但考虑其认罪态度, 可以给予减刑(例如各判刑六年); 如果一人认罪, 而另一人拒不承认, 则认罪的可以宽大处理(例如判刑3年), 而拒不认罪者将受到严惩(例如判刑10年), 问甲、乙应该怎样选择才能对自己有利?2.2对策的基本要素对策模型的形式千差万别, 但都必须包括三个基本要素: 局中人, 策略集和支付函数.(1)局中人对策中, 有权决定自己行动方案的参加者称为局中人(player), 一般的用N表示局中人的集合. 在一个对策中至少要有两个局中人. 局中人除了可以是一个自然人外, 还可以是代表着共同利益的一个集团, 例如球队、企业、国家. 在研究人与大自然作斗争时, 人和自然都是局中人.(2) 策略集对策中, 局中人选择的一个实际可行且完整的行动方案称为一个策略(strategy). 参加对策的每个局中人i 都有自己的策略集(strategy set)i S , i N ∈, 它是局中人i 的所有策略的集合.在任何一个对策中, 每个局中人至少要有两个策略, 这是因为, 若某个局中人只有一个策略, 则策略的结果将完全听凭别人摆布, 该局中人就是去了作局中人的资格.例2.1 中, 如果用(上, 中, 下)表示用上马、中马、下马这样一个顺序参加比赛,这 就是一个完整的行动方案, 即一个策略. 则齐王和田忌都有六个策略: (上, 中, 下), (上, 下, 中), (中, 上, 下), (中, 下, 上), (下, 中, 上), (下, 上, 中), 把齐王的策略记为123456,,,,,αααααα, 田忌的策略记为123456,,,,,ββββββ. 例2.2 中, 人有三个策略: 秋季买煤10吨、15吨和20吨, 记为123,,ααα; 大自然也有三个策略: 冬天的气温较暖、正常、较冷, 记为123,,βββ.例2.3中, 罪犯甲有两个策略: 不承认和承认, 记为1α和2α; 罪犯乙同甲一样，也有两个策略: 不承认和承认, 记为1β和2β.要注意的是, 这里的策略强调“完整性”, 并不是指对策中所采取的局部行动方案, 例如, 在下象棋时, 在一局棋中, 某一步走“当头炮”, 只是作为一个策略的组成部分, 而不是一个完整的策略. 又如在田忌赛马问题中, 齐王的三匹马的出场顺序是一个策略, 但每次出哪匹马只是一个策略的一个部分, 并不是一个完整的行动方案.我们从策中每一个局中人的策略集中，各取一个策略组成策略组，则它称之为对策的局势(situation). (3) 支付函数对策的结果是由局势唯一确定的. 对策的结果决定了每个局中人的得失, 这种得与失称之为局中人的支付(payoff). 可见, 局中人的支付都是局势的函数, 因此称支付为支付函数(payoff function). 局中人i 的支付函数可记为,i P i N ∈.通常, 局中人的集合N , 策略集{}i S 和支付函数{}i P , 确定这三个基本要素之后, 一个对策Γ就完全确定了. 记{}{}(),,.i i N S P Γ=这种对策称之为策略型(strategy form)对策或正规型(normal form)对策.在田忌赛马的问题中, 齐王的支付函数可以写成表 2.1 所示的表格:表2. 1 田忌赛马问题中齐王的支付函数1 β2 β3 β4 β5 β6 β1α 3 1 1 1 1 -1 2α1 3 1 1 -1 1 3α 1 -1 3 1 1 1 4α -1 1 1 3 1 5α 1 1 -1 1 3 1 6α1111-13若只考虑数字, 则齐王的支付函数就是一个矩阵:311111131111113111111311111131111113-⎡⎤⎢⎥-⎢⎥⎢⎥-⎢⎥-⎢⎥⎢⎥-⎢⎥-⎣⎦; 相同的, 田忌的支付函数也可写成矩阵:311111131111113111111311111131111113-----⎡⎤⎢⎥-----⎢⎥⎢⎥----⎢⎥-----⎢⎥⎢⎥-----⎢⎥-----⎣⎦. 冬季取暖问题中, 人的支付函数为123123100016002500150015002250200020002000βββααα---⎡⎤⎢⎥---⎢⎥⎢⎥---⎣⎦, 这也是一个矩阵, 大自然的支付函数是100016002500150015002250200020002000⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦.罪犯两难问题, 甲、乙的支付函数分别为12 12120372ββαα--⎡⎤⎢⎥--⎣⎦, 1212 12312072ββαα--⎡⎤⎢⎥--⎣⎦.这也是矩阵的形式.2.3 展开型对策策略型对策中, 局中人的策略集在对策开始之前就已确定了, 但是, 有的对策无法提前确定局中人的一个完整行动方案. 那么, 局中人的每一步需要依据其他局中人的前一步来确定, 我们把这类对策称为展开型(extensive form)对策. (1) 定义定义 2.1[3] 有向图(),D X A =指由一个非空有限集X 和X 中的某些元素的有序对集合A 所构成的二元组(),X A . X 称之为D 的顶点集, 其中的元素称之为顶点; A 称为D 的弧集, 其中的元素称之为弧.若, A 中的元素a 是X 中元素x 与y 的有序对, 即(),a x y =, 那么称x 为a 的尾,y 为a 的头; a 为x 的出弧, 也称为y 的入弧; 还称x 与y 相邻.x X ∀∈, 此时记()(){}()(){},,,,D DN x y Xx y A N x y X y x A +-=∈∈=∈∈分别称为顶点x 在D 中的出邻域(out-neighbour)和入邻域(in-neighbour).若D 中有k 个相异顶点i x X∈()1,2,,i k = , 使()()1,2,3,,i i x x A i k -∈= , 那么称序列12k x x x 为D 的一条从1x 到k x 的路(path).定义2.2 若有向图(),T X A =满足 （1） 存在0x X ∈, 且0x 没有入弧; （2） {}0\,x X x x ∀∈有一条入弧;（3） {}0\,x X x D ∀∈中有唯一的从0x 到x 的路,则称T 为树形图, 并称0x 为T 的根(root), T 中没有出弧的顶点称为T 的梢(tree-top), 记T 中所有树梢的集合为X ∂.定义2.3 假设{}1,2,,N n = 是局中人的集合, 若 (1) 存在树形图(),T X A =, 且X X ≠∂; (2) 存在映射:\X X N ϕ∂→; (3) 存在映射:n p X ∂→ℜ,于是称四元组(),,,N T p ϕ∑=为n 人对策树.下面对对策树中的概念作一些解释.若0x 为树形图T 的根, 并且()0x i N ϕ=∈, 其表示在0x 处行动的局中人为i . 假设局中人i 选取0x 的一条出弧()01,x x , 在1x 处行动的局中人为j , 即()1x j N ϕ=∈, 而且局中人j 又选取弧()12,x x , , 诸如此类.由树形图T 的定义可得, X ω∀∈∂, T 中存在唯一的一条从根0x 到梢ω的路10l i i x x x ω , 我们把这条路称为通往ω的局(play).对于通往ω的局, 对应的有()()()()()12,,,,nn p p p p ωωωω=∈ℜ其中()i p ω表示局中人i 在通往ω的局中所得到的支付, 1,2,,i n = ; 向量()p ω则表示所有局中人通往ω的局中所得到的支付的分布情况.i N ∀∈, 引入集合(){}\,i X x X X x i ϕ=∈∂=它表示局中人i 的行动顶点的集合, 也可以记为()1i ϕ-. 再记()0\\,i i NX X XX ∈⎛⎫=∂ ⎪⎝⎭那么01,,,n X X X 是\X X ∂的一个划分. 若有0x X ∈, 则表示在顶点x 处, 是随机选择行动的. 所以, 我们设: 0x X ∀∈, 在x 的出弧集上给定一个概率分布, 且x 的每条出弧上的概率均为正, 记x p .有了上述概念, 现在可以给出展开型对策的定义. 定义 2.4 展开型n 人对策Γ指定了一下的四个条件: (1) 对策树(),,,N T p ϕ∑=;(2) \X X ∂划分成1n +个子集01,,,n X X X ; (3) 0,x X x ∀∈的出弧集上的概率分布0x p >;(4) i N ∀∈, i X 有一个划分为12,,,ii i it X X X , 则称()1,2,,il i X l t = 为局中人i 的信息集(information set), 其中,il x y X ∀∈, x 与y 不相邻, 并且()()TTN x N y ++=.简单来说, 展开型对策Γ就是一个六元组, 如下所示{}{}()12,,,,,,,,ix i i it i NN T p p X X X ϕ∈Γ= .在展开型对策中, 引进了信息集的概念是为了表达一种情况: 当轮到局中人i 行动时, 他只了解自己处于该信息集内的某个顶点处, 但又不能确定自己到底在哪个顶点上.假设Γ是展开型n 人对策, i N ∈, 如果存在信息集it X 满足2it X ≥, 那么局中人i 只知道自己处于it X 内, 而不能确定具体的位置, 则称局中人i 在it X 中有着不完全信息(imperfect information); 若{}1,2,,i l k ∀∈ , 有1it X =, 那么称Γ有完全信息(perfect information). 如果Γ中的每个局中人都有完全信息, 则Γ有完全信息. 棋类比赛就是具有完全信息的对策, 而桥牌则不是.展开型对策与策略型对策虽然在定义上有所不同, 但它们是可以互相转化的. (2) 策略型对策化为展开型对策假设策略型对策{}{}(),,i i N S P Γ=, 其中{}()()(){}()121,2,,,,,, 1,2,,.i i i i i m N n S s s s i n ===就可以构造一个对策树: 其以0x 为根, 0x 有1m 条出弧()()110,k x x , 111,2,,km = , 分别对应局中人1的1m 个策略; 每个顶点()()11111k x k m ≤≤有2m 条出弧()()()1212,k kx x ,()'22121k k k m =+-, '221,2,,k m = , 它们对应局中人2的2m 个策略; 像这样继续下去,对每个顶点()()1111211n n k n n x k m m m ----≤≤ , 有n m 条出弧()()()11,n nn n k k x x --,()'11n n n n k k k m -=+-, '1,2,,n n k m = , 对应于局中人n 的n m 个策略. 这里{}(){}(){}010112112, ,1, 2,3,,,1;i ni i k ii n k nnX X x X x k m m m i n Xx km m m --=∅==≤≤=∂=≤≤ ()n n k x X ∀∈∂, 在对策树中从根0x 到梢()n n k x 的唯一路对应于Γ的唯一局势s , 则()()()()()()12,,,.nn k np x P s P s P s =说明策略型对策可以转化为展开型对策. 若策略型对策Γ中局中人对自己所采用的策略保密, 则Γ所对应的展开型对策具有不完全信息. (3) 展开型对策化为策略型对策定义 2.5[4]展开型对策Γ中局中人i 的一个策略()i s是定义在局中人i 的信息集{}12,,,i i i it XX X 上的一个映射, 使1i l t ∀≤≤, ()()i il s X 对应于ilX 中, 以顶点为尾的一条弧. 局中人i 的所有策略构成的策略集记为i S , 1,2,,i n = .该定义说明: 策略()i s是局中人i 的一个行动方案, 它指明局中人i 在自己的每一个信息集上该选择哪一条出弧. 每个局中人i 在选定一个策略()()1,2,,i i s S i n ∈= 后, 就组成一个局势()()()()12,,,n s s ss= .x X ∀∈, 对策树中存在从根到x 的唯一的路, 这条路上的弧的集合记为()A x . 特殊的, 局势s 对应对策树只能从根到梢ω的唯一的路, 即s 对应于通往ω的局.在局势()()()()12,,,n s s ss= 下, 在顶点x 处选择出弧(),x y 的概率为()(),,,1, 0, x p x y s x y ⎧⎪=⎨⎪⎩()()()0,,,.i it it x X x X s X x y ∈∈=且其他所以, 在局势s 下, 顶点x 出现的概率为[]()()(),,.y z A x s x s y z ∈=∏则, 在在局势s 下, 到达树梢ω的概率为[]s x , 局中人i 在树梢ω上得到的支付为()i p ω, 所以局中人i 在局势s 下的支付是()()[].i i XP s p s ωωω∈∂=∑则, 当0X =∅时, 假设局势s 对应于通往ω的局, 那么()().i i P s p ω=例 2.4 对于翻摊游戏问题, 在桌上放五根火柴, 甲、乙二人轮流取走一根或两根, 谁取走最后一根或两根则为胜者, 胜者得一分, 输者失1分. 则甲的策略为()()()()()()()()()()11121314152,1,2,2,1,2,1,1,1,1,1,s s s s s ===== 策略中第j 个数为第j 次取的火柴的数量; 乙的策略为()()()()()()()()212223242,1,1,2,1,1,2,s s s s ====相同的, 第j 个数为乙第j 次取的火柴数; 甲的支付函数如表2.2所示.表2.2 翻摊游戏问题中甲的支付函数()21s()22s()23s()24s()11s 1 -1 1 -1 ()12s 1 1 1 1 ()13s 1 -1 1 -1 ()14s -1 1 -1 1 ()15s-11-11而乙的支付函数是上表中数字反号所得的表.下面为0X ≠∅的例子.例 2.5 两张纸牌游戏问题. 设游戏开始时, 甲(局中人1)和乙(局中人2)都压上一元的赌注, 然后甲从两张牌A 和2中抽一张牌给乙, 乙看了后再说话. 如果是A, 乙必须告诉甲是“A”; 如果是2, 乙可以说“A”, 也可以说是“2”. 但若乙说了“2”, 则判定为乙输, 他所压的一元钱就输给甲. 若说“A”, 则乙要再压上一元的赌注, 然后再由甲去判断. 甲如果相信乙, 就等于他输掉了自己所压的一元钱; 甲如果不信, 那么必须同样再压上一元, 然后去翻牌. 如果翻开后是A, 则乙赢甲2元; 如果是2, 则甲赢乙2元.在该对策中, 显然有{}{}{}00134212,,,,.X x X x x X x x ===且这是一个具有不完全信息的对策.可知, 甲有两个策略()11s ={乙说“A ”, 甲相信},(){12s =乙说“A ”, 甲不信};乙也有两个策略(){21s =牌为2, 说2}, (){22s =牌为2, 说A};甲的支付函数如表2.3所示.表2.3 两张纸牌游戏中甲的支付函数()21 s()22 s()11s 0-1()12s1-2因为两张牌中抽一张为A 或2的概率各为12, 则0X 中顶点0x 的两条出弧的概率均为12, 所以()()()()()()()()()()()()()()()()()1211112112121211212211,110,2211,111,22111,21,22211,220.22P s s P s s P s s P s s =⨯-+⨯==⨯-+⨯-=-=⨯-+⨯=-=⨯-+⨯=乙的支付函数是表2.3中数字反号所得的表.由于策略型对策已经有了一套较完善的求局中人“最合理”的行为方案的方法, 而展开型对策不是, 所以任何展开型对策都可转化为策略型对策来求解, 这个转化在展开型对策中有重要的作用. 但是, 展开型对策自身有它的固有特性, 而这些特性在转化为策略型对策之后就失去了, 所以, 就展开型对策本身考虑, 上述转化是否有必要还需研究.2.4 对策的分类对策的种类非常多, 可以根据不同的原则进行分类.(1) 根据每个局中人的策略是否可以在对策开始之前确定, 对策可以分为策略型对策和展开型对策.(2) 根据对策的过程是否和时间有关, 可以把对策分成动态对策和静态对策. 动态对策又称为微分对策(differential game).还有以下分类.只有两个局中人的对策称之为二人对策(two-person game). 有两个以上局中人的对策称之为多人对策(multi-person game). n 个局中人的对策称为n 人对策(n-person game). 如, 例2.1, 例2.2和例2.3都是二人对策.若对策中每个局中人的策略集都是有限的, 则称为有限对策(finite game), 否则称为无限对策(infinite game). 例2.1, 例2.2, 例2.3都为有限对策.在对策中, 若在任一局势中所有局中人的支付之和都为零, 则称为零和对策(zero-sum game); 若在任一局势中的支付之和为一个常数σ, 则称为常和对策(constant-sum game). 显然, 零和对策也为常和对策. 例2.1, 例2.2都为零和对策, 但例2.3不是零和对策, 也不是常和对策.3 二人零和有限对策二人零和有限对策是一种最简单、最基本的策略. 简单是因为只有两个局中人, 而且每个局中人都只有有限个策略; 说它基本是因为它有比较成熟的理论和算法，它是研究其他对策的基础.下文介绍二人零和有限对策的基本概念、解的存在性定理，即最大最小定理、最优策略的性质、与线性规划的关系、求解方法和求最有策略集的方法等内容.3.1 矩阵对策的基本概念假设Γ是二人零和有限对策, 局中人甲和乙的策略集为{}{}112212,,,,,,,.m n S S αααβββ==假设在局势(),i j αβ中, 甲的支付为()1,2,,;1,2,,ij a i m j n == , 那么甲的支付函数可以写成矩阵的形式()ij m nA a ⨯=; 又设在局势(),i j αβ中, 乙的支付为()1,2,,;1,2,,ij b i m j n == , 那么乙的支付函数也可以写成矩阵的形式()ij m nB b ⨯=.由于Γ是零和对策, 那么0ij ij a b +=, 1,2,,;1,2,,,i m j n ==则有B A =-, 所以Γ由甲的支付函数(矩阵)A 唯一确定. 那么二人零和有限对策可以记为()12,;S S A Γ=.因此二人零和有限对策也可称为矩阵对策(matrix game), A 称之为支付矩阵(payoff matrix).矩阵对策中一个局中人的所得就是另一个局中人的损失, 所以矩阵对策是完全对抗的, 则两个局中人绝对不可能合作, 即矩阵对策是非合作二人对策.若甲采用策略i α, 那么他至少可以得到1min i ij j np a ≤≤=.因为甲希望i p 越大越好, 所以它可以选择策略*i α, 使他的所得不少于*111m ax m ax m in i i ij j ni mi n p p a ≤≤≤≤≤≤==.同样的, 若乙采用策略j β, 则他至多损失1max j ij i mq a ≤≤=.因为乙希望j q 越小越少, 所以他可以选择策略*j β, 使他的所失不多于*111m in m in m ax j j ij j nj n i mq q a ≤≤≤≤≤≤==,也就是说, 若乙处理的合适, 甲的所得不会大于*j q .既然甲可以选择策略*i α, 使他至少可以得到*i p , 而乙可以选择策略*j β, 使甲至多得到*j q , 那么这两个值之间的关系是什么样的呢?以田忌赛马问题为例,*1616*1616m ax m in 1,m in m ax 3,i ij j i jij j i p a q a ≤≤≤≤≤≤≤≤==-==即**i j p q <.在冬季取暖问题中,*1313*1313m ax m in 2000,m in m ax 2000,i ij j i j ij j i p a q a ≤≤≤≤≤≤≤≤==-==-即**i j p q =.那么, 我们得到以下的结论.引理 3.1[5] 对于矩阵对策()12,;S S A Γ=, 有1111m ax m in m in m ax ij ij j nj n i m i ma a ≤≤≤≤≤≤≤≤≤ (3.1)证明 因为11m in ,1,2,,;1,2,,,m ax ,1,2,,;1,2,,,ij ij j nij ij i ma a i m j n a a j n i m ≤≤≤≤≤==≤==所以11min max ,1,2,,;1,2,,.ij ij j ni ma a i m j n ≤≤≤≤≤==上式左边与j 无关, 两边对j 取最小值, 得111min min max ,1,2,,,ij ij j nj n i ma a i m ≤≤≤≤≤≤≤=两边再对i 取最大值, 得11max min min max ,ij ij j nj n i mi ma a ≤≤≤≤≤≤≤≤≤这就证明了(3.1)式.定理 3.1[6]矩阵对策()12,;S S A Γ=有等式1111m ax m in m in m ax ij ij j nj n i m i ma a ≤≤≤≤≤≤≤≤= (3.2)成立的充要条件是存在局势()**,i j αβ, 使得****,1,2,,;1,2,,.ij i j i j a a a i m j n ≤≤== (3.3)证明 ()⇐假设Γ存在局势()**,i j αβ使得(3. 3)成立, 从而****1max min ,ij i j i j i j ni ma a a ≤≤≤≤≤≤所以**11min max max min ,ij ij i j i j n i j ni mi m a a a ≤≤≤≤≤≤≤≤≤≤另一方面, 由引理3.1, 有1111m ax m in m in m ax ij ij j nj n i m i ma a ≤≤≤≤≤≤≤≤≤因此**1111max min min max .ij ij i j j nj n i m i ma a a ≤≤≤≤≤≤≤≤==()⇒设(3.2)式成立. 容易知道有**1,1i m j n ≤≤≤≤, 使**111111m in m ax m in ,m ax m in m ax ,ij i j j nj ni m ij ij j n i mi ma a a a ≤≤≤≤≤≤≤≤≤≤≤≤==则由(3.2)式得******1111max min max min ,ij i j i j ij i j j nj ni mi ma a a a a ≤≤≤≤≤≤≤≤=≤≤=于是****,1,2,,;1,2,,.ij i j i j a a a i m j n ≤≤==从(3.3)式可以看出: 当局中人甲采取策略*i α时, 局中人乙为了使自己所失最少, 只有选择策略*j β, 否则就可能失去更多; 同样, 当局中人乙采取策略*j β时, 甲为了得到最多, 也只能选择策略*i α, 否则得到的将更少. 有此可知, 双方的竞争在局势()**,i j αβ下达到一个平衡的状态. 由此给出下面的定义.定义 3.1[6]设矩阵对策()12,;S S A Γ=, 如果存在**12,i j S S αβ∈∈, 使得****,1,2,,;1,2,,,ij i j i j a a a i m j n ≤≤==则称局势()**,i j αβ为Γ的平衡局势(equilibrium situation)或解(solution); *i α与*j β分别称为局中人甲与乙的最优策略(optimal strategy); **i j a 称为Γ的值(value), 记为v Γ.由定理3.1的必要性的证明可得**1111max min min max ij ij i j j nj n i m i mv a a a Γ≤≤≤≤≤≤≤≤===,因此有以下的推论.推论 3.1 如果矩阵对策()12,;S S A Γ=使(3.2)式成立, 那么Γ有解, 而且Γ的值等于(3.2)式的值.在冬季取暖问题中, 由前面的计算可得13131313max min min max 2000,ij ij j j i i a a ≤≤≤≤≤≤≤≤==-所以该对策有解()33,αβ, 即秋季存20吨煤最为合理, 对策的值为-2000.仿照二元函数中鞍点的定义, 又称满足(3.3)式的局势()**,i j αβ是对策Γ的鞍点(saddle point).根据以上讨论, 我们可以给出求矩阵对策()12,;S S A Γ=和鞍点的一个方法[6]: 分别求出支付矩阵A 中第i 行的最小元素()1,2,,i p i m = 和第j 列的最大元素()1,2,,j q j n = , 如果11max min i j j ni mp q ≤≤≤≤=,则Γ有解, 并且满足**11m ax ,m in i i i mjj j np p q q ≤≤≤≤==的局势()**,i j αβ是Γ的鞍点, **i jv p q Γ==.一个矩阵对策的鞍点可能有许多个. 如, 假设矩阵对策的支付矩阵为6595142185750263A ⎡⎤⎢⎥-⎢⎥=⎢⎥⎢⎥⎣⎦, 那么Γ有四个鞍点()()()()12143234,,,,,,,,αβαβαβαβ 且5v Γ=.当对策的鞍点不惟一时, 鞍点之间有如下关系. 定理 3.4[6] 在矩阵对策()12,;S S A Γ=中, 若()11,i jαβ和()22,i j αβ是Γ的两个鞍点,则有 (1) 对策值的无差别性: 1122i j ij a a =;(2)鞍点的可交换性: ()12,i jαβ和()21,i j αβ都是Γ的鞍点.证明 (1) 由鞍点的定义, 有211112122221,,i j i j i j i j i j i j a a a a a a ≤≤≤≤从而2221111222,i j i j i j i j i j a a a a a ≤≤≤≤于是22211112i j i j i j i j v a a a a Γ====.(2) 由鞍点的定义可知, {}1,2,,,i m ∀∈ 有1112122212,,ij i j i j ij i j i j a a a a a a ≤=≤=并且{}1,2,,,j n ∀∈ 有1211121222,,i j i j i j i j i j i j a a a a a a =≤=≤从而21211212,1,2,,;1,2,,,,1,2,,;1,2,,.ij i j i j ij i j i j a a a i m j n a a a i m j n ≤≤==≤≤==这就证明了()12,i jαβ和()21,i j αβ都是Γ的鞍点.3.2 混合策略由3.1节的讨论可知, 在田忌赛马问题中16161616max min 13min max ij ij j j i i a a ≤≤≤≤≤≤≤≤=-<=所以对策无解, 即局中人都找不到各自的最优策略, 也就求不出对策的值.例 3.1 给定矩阵对策()12,;S S A Γ=, 其中3654A ⎡⎤=⎢⎥⎣⎦, 此时12121212m ax m in 4,m in m ax 5.ij j i ij j i a a ≤≤≤≤≤≤≤≤==可知12121212m ax m in m in m ax ij ij j j i i a a ≤≤≤≤≤≤≤≤<.所以Γ无解.这说明按定义3.1中的对策的解的概念会导致许多矩阵对策无解, 因此有必要把对策的解的定义作一些修改.由之前的讨论可以看出, 当两个局中人根据“从最不利情形中选取最有利的结果”的原则选取策略时, 例3.1中的局中人甲应选取2α, 局中人乙应选取1β, 此时甲将会得到5, 比期望得到的4还要多, 所以1β对乙来说并非是最优策略, 所以乙将会考虑采用策略2β. 那么, 甲也会采取相应的办法, 改选1α, 以使他得到6, 而乙又可能仍选1β来对付甲的策略1α. 那么, 甲选1α或2α以及乙选1β或2β的可能性都不能被排除, 对甲、乙双方来说, 不存在一个双方均可接受的平衡局势. 在这样的情形下, 一个相对自然的并且符合实际的想法是: 既然甲、乙双方都没有最优策略可选, 那是不是可以给出一个选取策略的概率分布?若局中人甲选取策略1α的概率是1x , 选取2α的概率是2x ; 乙选取1β的概率是1y ,选取2β的概率是2y , 那么{}{}()1122121212,,,,,,,,,1,1.m m ij m nS S A a x x y y αααβββ⨯===+=+=记()12,x x x =, ()12,y y y =, 则局中人甲的支付的期望值为()()()()111221221111111111(,) 3654 36151411119 4422E x y xAyx y x y x y x y x y x y y x x y x y T==+++=+-+-+--⎛⎫⎛⎫=---+⎪ ⎪⎝⎭⎝⎭ 由上式可知, 当114x =时, (,)E x y =92, 也就是说, 当局中人甲以概率14选取1α时, 他可以得到92, 但这并不能保证他的支付的期望值会超过92. 这是因为, 只要当乙以12的概率选取1β, 就可以控制局中人甲的期望值不会超过92. 所以92是局中人甲的支付的期望值. 同样, 局中人乙以概率12选取1β时, 他的所失的期望值也是92. 于是, 当据局中人甲分别以概率14与34选取1α与2α, 局中人乙以概率12分别选取1β与2β时, 对双方都是最好的选择.若把上述方法推广到一般情况中, 引入如下的概念. 定义 3.2[6] 假设有矩阵对策()12,;S S A Γ=, 其中{}{}()112212,,,,,,,,,m n ij m nS S A a αααβββ⨯=== 记()()*11*2101,2,,, 1,01,2,,, 1,mmi i i n nj j j S x x i m x S y y j n y ==⎧⎫=∈ℜ≥==⎨⎬⎩⎭⎧⎫⎪⎪=∈ℜ≥==⎨⎬⎪⎪⎩⎭∑∑称*1S 和*2S 分别为局中人甲和乙的混合策略集(mixed strategy set); **12,x S y S ∈∈分别为局中人甲和乙的混合策略; **12,x S y S ∀∈∀∈, 称(),x y 为Γ的一个混合局势(mixedsituation), 并称11(,)mniji j i j E x y xAy ax y T====∑∑为局中人甲的期望支付函数(expected payoff function), 或者简称为支付函数. 这样得到的一个新的对策记为()***12,;S SE Γ=,称之为Γ的混合扩充(mixed extension).由定义 3.2, Γ中的策略为*Γ中混合策略的特例, 或称*Γ中的混合策略是Γ中策略的一种扩充. 如, 局中人甲的策略k α等价于局中人甲的混合策略()12,,,m x x x x = , 其中1,0,i x ⎧=⎨⎩,.i k i k =≠为了便于区分, 我们把Γ的策略()1,2,,i i m α= 和()1,2,,j j n β= 统称为纯策略(pure strategy).一个混合策略()*121,,,m x x x x S =∈ 可以假设为两个局中人重复进行对策Γ时, 局中人甲分别采取纯策略12,,,m ααα 的频率. 如果只进行一次对策, 那么混合策略()12,,,m x x x x = 可以假设为局中人甲对各个纯策略的偏爱程度.同3.1节一样, 若两个局中人均按照“从最不利情形中选取最有利的结果”的原则, 那么局中人甲可以保证自己的支付的期望值不少于()**211m ax m in ,;y S x S v E x y ∈∈=。
