假设有1个单位的攴付给贏者,石头一纸--剪刀对策的支 付矩阵由下列阵列给出 Min 纸剪刀石头 Max剪刀 [14] 石头 我们首先要指出Max得的就是Min输掉的,反之亦然.听以 这是个零和对策.其次,行极小(-1)的极大值不等于列极大 (+1)的极小值;因此,对策没有鞍点这就意味着如果Max“偷看” 他就能获得超过Mn的妇处,因为他能出剪刀对纸.石头对剪丿,以 及纸对石头,因此总是获胜因此如果两个竞争者都诚实地对局, 那么每个人都必须以随机的方式从这三个可能的选择中独立地选 择一个又由于支付矩阵的结构,关于这三种选择是完全无偏的,因 此没有先验的理由来偏爱某个选择甚于其他选择.因此,Max和 Min两人都将以相等的频率每个为,从二个选项中作出选择结 果是9个订能的纠合:纸纸,纸剪刀,…,石头石头中的每一个都将 以的可能性出现.于是,平均说来Max和Min两人的支付将是: (0-1+1+1+0-1-1+1+0)=0 现在假设Mn线以每个频率为的方式在纸剪刀和石 头中来选择但Max却改变他的频率为纸=3,刀=2以及石 头=1.现在Max的平均结果或期望结果为:正如结果所表明 的这也是Min的期望结果 1 I 14
×0)+ ×0=0 6 6 事实上,对于Max所选的这三种可能选择的任何可能性而 言,Max也将恰好得到同样的结果.从这个事实,我们得出结论: 就Min的等可能性混合策略而言,Max不可能改善其平均收益. 所以具有等可能性选择的混合策略是这个对策的一个平衡点 在同样的意义下,极小极大点是具有鞍点的对策的-个平衡点 因此,使用随机化其选择的策略,Max和Min每—人都能宣石他 或她对另…人的策略不必顾及对手能利用此信息来得到他或她15」 自已的更大的平均支付 现在出现的问题如下 ●对任何两人零和对策,我们怎么知道最优混合策略是存 在的?我们已看到这样一个策略在石头一纸一剪刀对策 中是存在的但是也许这是因为该对策有某些特殊性,而 般说来,不存在这种最优混合策略 ●如果这种最优混合策略的确存在,我们怎样计算它们呢? 对于石头一纸一剪刀对策的支付矩阵的对称结构,强烈地 暗示对每个局中人要做的“正确'"事情是混合具有等可能 性的纸、剪刀和石头的选择.但如果支付偏爱某些行动甚 于其他行动合乎情理的是按以下事实来挑选最优策略, 倾向于史频繁地以这些高支付行动的频率而不是不那么 偏爱的行动来对局所以,当有了一个特定的支付矩阵时, 我们怎样计算对不同的选择加权的最好方式呢? 这些正是冯·诺什曼在1928年发表的著名的极小极大定 ①译注:John; on Neumann,1903.12.3-~1957.2.8,美国数学家,出 生于匈牙利,对蟹f物理、数学逻辑、气象学和高速计算机的发展都有重 大贡献;关于对策的数学理论对经济学极有影晌 一15
理(对策的数学理论的关键结果)回答的问题.该定理断言对每 个两人零和对策每个局中人都有一-个最优混合策略 极小极大定理 让我们简要地看看为什么极小极大定理是如此的重要如 果一个对策有像在俾斯麦海战中那样的鞍点,那么每个局中人 要作什么的选拌是清楚的:采取导致鞍点的行动这确保了每个 局中人的最好可能的支付,假设每人都按他或她自己自私的最 大利益来行动而且,每个局中人都能事先宣布他或她的鞍点决 策,不必顾及对手能利用此信息以获得更好的支付,但这些性质 是在鞍点处极大极小等于极小极大这一事实的推论如果对策 没有鞍点,那么这些性质失去了,从而我们要面对的是对每个局 [16」中人而言不存在明显的最优方法. 极小极大定理向我们展示了在没有鞍点的对策中怎样重建 合理的行动步骤的概念极小极大定理表明重新把握住合理性 的方法是利用随机化局中人在所有可能的行动中的选择的策 略.如果局中人这样去做的话,极小极大定理保证对每个局中人 存在-…组概率,使得每个人都对他或她的行动按这些概率加权, 那么他或她每人都将得到同样的平均支付—一并如果对于是 合理地对局的话,这也将是每人能期望得到的最优支付.最后, 局中人能事先透露他们的概率集合而决不会以任何方式损害他 们自已的利益让我们用较长的篇幅来察看一下20世纪数学的 这个主要成果 紧跟法国数学家E·波莱尔①关于两人零和对策的1921年 ①译注: Emile borel,1871.1.7~1956.2.3,创立了点集测度的第 个有效埋论,与法国的鼠·贝尔和H·勒贝格一起开创∫实变函数的现代理 论 16
的工作,其中能供局中人攴配的行动不多于4个(即,纯策略) 策梅洛①猜想对于每个局中人而言,应存在能给他们双方以同 样期望支付的混合策路,而且与每个局中人能利用的行动数「 无关.并且,策梅洛卢称这个公共收益是支配着对策论学家所意 味的“合理对局”的不胞冒风险准则下局中人能希望得到的最好 的收益 我们早就知道、对于有鞍点对策的情形,这一定是必要的, 而且在这种情形中两个局中人有导致公共攴付的最佳纯策路 用对策论的行话来说,这个公共支付通常称之为对策的值.作对 于无鞍点的对策而’,论从几何或代数方面都不是如此简单 和清晰的∫.直到1928年,冯·诺伊曼通过给出…个无懈可击的 数学证明确认了策悔洛猜想的正确性,从而把整个对策论的研 究置于坚实的基础之.在这之前这些问题始终没有弄清楚.因 为极小极大定理构成了许多对策约数学理论赖以建立的基础 我们将用几节来详细地描述这定理 冯·诺伊曼的极小极大定理做出很强的断言.即对每个中 人而言总仔在至少一个混合策略,这样就使得当他们用这些策 略时,每个局中人的平均攴付是问样的.而且,若他或她的对手 是合理地对局的话这个平均支付是每个局中人就能指望得到 的最好的收益以下是这个重要结果的比较止式的陈述 「17] 极小极大定理对于每个两人零和对策,对每个局中人而 言都存在一个混合策略使得当局中人使用这些策略时双方的期 望支付有相同的值ψ.而且,ν也是每个局中人能指望从对策的 局中得到的最优支付;因此,这些混合策略是两个局中人所用 的最优策略 L译注: Fmsi Friedrich Ferdinand Zermelo、1871.7.27~1953.5.2 德国数学家,主要或献是集合论基础
这个定理所意味的就是对每个局中人存在…组概率,使得 如果他们按照这些概率对他们的行动加权的话,他们每个人都 恰好收到同样的平均收益V(实际上,因为对策是零和的,对极 小化的局中人来说期望支付是-V). 我们可以通过再次考虑前面给出的石头—纸—剪刀对策来 阐明这个结果这里我们声称(无需证明!)每个局中人的最优混 合策略是对纸、剪刀和石头这三种选择赋以相同的权.使用这些 概率,我们求出每个局中人的平均支付为V=0.冯诺伊曼结果 的困难部分是证明没有-个局中人能通过偏离由极小极大策略 规定的概率来得到较好的期望支付,这是我们在石头一剪 纸对策中通过直接计算证明的事实.十分令人关注的是为了证 明极小极大定理,冯·诺伊曼必须对早先由布劳威尔①建立的不 动点结果(见第2章)发展一个重要的推广想要了解这些细节 的读者请查阅文献目录中为本章列出的资料 所以正如引进复数重建了任何多项式方程的可解性,与极 小极大定理紧密相联的混合策略的概念通过确保平衡点存在性 而重建了任何两人零和对策的可解性——但现在是在混合策略 空间中而不是在纯策略空间中通过把我们所指的策略的概念 从单个的行动步骤(纯策略)推广为在所有可能行动上的随机化 (混合策略),冯·诺伊曼成功地建立了合理选择的存在性,即局 中人都能事先宣布其策略而不给他或她的对手丝毫好处;也没 18]有局中人能通过单方面背离最优混合策略而改善其收益.无怪 乎后来冯诺伊曼会说“就我所知道的,没有那个定理……就不 可能有对策论……我认为直到‘极小极大定理’被证明之前没有 什么东西是值得发表的.”现在让我们来看一个表明混合策略在 ①译注: Luitzen Egbertus Jan Brouwer,88.2.27~196612.2,荷兰 数学家,创立了数学中的近代直觉主义(一种认为作为思维构造的数学的 本质是受不言自明的规律所支配的学说)他的研究完全转变了拓扑学 18