矩阵博弈 两人零和博弈描述了两人严格竞争情形。矩阵博弈（matrixgames）是伴随有限策 略集的两人零和博弈。矩阵博弈在很多方面都很有趣，而且它们比较容易分析，原因在 于它们比较简单而且结构特殊。冯·诺依曼和摩根斯坦证明，可用线性规划求这些博弈 的解。在本章，我们首先提供几个矩阵博弈的例子。然后，我们在纯策略背景下分析矩 阵博弈，在这个过程中，我们引入安全水平、安全策略、鞍点等概念。我们将证明，纯 策略纳什均衡（若存在）正好是鞍点。接下来，我们在混合策略背景下分析矩阵博弈。 我们将证明，两个参与人的最优策略可用线性规划描述，它们互为对偶。由此，我们得 到本章的主要结果，即最小最大值定理（minimaxtheorem），它表明每个矩阵博弈都有 混合策略纳什均衡。 两人零和博弈是一个策略型博弈（{1，2)，（S，S2），（u，u2）>，它满足u（s1，S2）十 u2（s1，S2）=0，Vs∈S，Vs∈S2。我们也使用符号（{1，2}，S1，S2，u1，一u>表示 两人零和博弈。这里值得注意的是，参与人使得自已的收益最大，等价于使得对手的收 益最小。因此，这些博弈也称为严格竞争博弈（strictlycompetitivegames）。根据惯 例，参与人1称为行参与人（rowplayer），参与人2称为列参与人（columnplayer）。 在本章，我们仅讨论伴随有限策略集的两人零和博弈。假设S={S11，S12，"，Sim）， S2={s21，S22，"，S2n）。在不至于混淆的情形下，我们从现在起使用符号S={1，2，， m），S2={1，2，"，n）[注意，不要将这里的n与本书其他地方的n（代表参与博弈 的人数）相混淆]。由于一个参与人的收益正好是另外一人收益的相反数，这些博弈可 用含有m行和n列的矩阵A表示，其中ag=u（i，j），Vi∈Si，Vi∈S2。a这个数是 当参与人1（行参与人）选择策略i且参与人2（列参与人）选择策略j时的收益，此时 参与人2的收益为一aj。因此，这样的博弈也称为矩阵博弈（matrixgames）。为简单

起见，我们直接称A是一个矩阵博弈。 9.1矩阵博弈的例子 例9.1（硬币配对）考虑硬币配对博弈的标准版本。它的收益矩阵见下表，假设 策略1对应着硬币正面，策略2对应着反面： 1，-1 -1，1 -1，1 1，-1 这个博弈可用下列矩阵A描述，它仅包含参与人1的收益： A= 口 例9.2（石头剪刀布）我们已在4.3节介绍了石头剪刀布博弈，这个博弈有两个 参与人，每个参与人有三个可能的策略：策略1（石头），策略2（布），策略3（剪刀）。 这是一个伴随下列矩阵的矩阵博弈： -1 A= 0-1 口 L-1 矩阵博弈 例9.3（产品预测博弈）假设有两个竞争公司1和2，它们在既定的时点上只能生 产X、Y和Z这三种产品中的一种。每个公司在既定的时点上只能生产一种产品，该公 司的收益取决于这两个公司所选择的产品。假设当一个公司获得利润时，另外一个公司 得到等额亏损。假设X、Y、Z分别为策略1、2和3，我们有S=S2={1，2，3}。一 个可能的收益矩阵为： A= 0-100 L-100 0-200 每个公司必须同时决定生产哪种产品。我们需要预测均衡时两公司生产的产品类型。口 例9.4（收益之和为常数的一个博弈）零和博弈的一个直接推广就是收益之和为 常数的博弈：（{1，2}，S1，S2，u1，u2>使得u（s1，S2）+u2（s1，S2）=C，Vs∈S1， Vs2ES2，其中C是一个已知常数。给定任何一个收益之和为常数的博弈，我们都可以 通过简单变换（比如，将每个参与人的每个收益减去该常数），把它变为一个零和博弈， 从而将其作为零和博弈进行分析。口

9.2矩阵博奔中的纯策略 在本节，我们分析仅允许纯策略情形的矩阵博弈。首先注意到，一个参与人收益的 最大化等价于另外一个参与人收益最小化。当行参与人选择策略i，列参与人选择能使 行参与人收益最小的策略： minaij jES2 上面的收益是当行参与人选择策略时，他能保证自已得到的最小收益。因此，行 参与人希望选择能使上述收益最大的纯策略i。也就是说，他希望选择策略i使得 maxminaij iESjES2 换句话说，行参与人的最优策略是最大最小化（maxminimization）。注意，这里隐含地 假设不管行参与人怎么做，列参与人总是选择能使得他（行参与人）损失尽可能大的策 略。行参与人在这个背景下选择能带给他最大收益的纯策略。行参与人的这种策略，称 为他的最大最小策略（maxminstrategy）或安全策略（security strategy）。 类似地，当列参与人选择纯策略j时，他保证他的收益等于 min（-a;）=-maxaj 博弈论与机制沿 iES ieS 也就是说，列参与人保证自已的损失不大于 maxaij iESI 设计 于是，列参与人的最优策略是使得这个损失最小： minmaxaij jESiES 这称为最小最大化（minmaximization）。列参与人的这种策略称为他的安全策略（secu- rity strategy)。 因此，最大最小值和最小最大值在描述矩阵博弈参与人的最优策略时起着自然而然 的作用。我们已在第6章定义了最大最小值和最小最大值，现在我们重温这些概念。 定义9.1（最大最小值）给定矩阵博弈A，最大最小值（maxminvalue）的定义为 =maxminaj iESjES2 注释最大最小值是行参与人在列参与人能自由选择任何策略时保证自己得到的 最小收益。若行参与人的策略能给他带来收益，则称其为他的一个最大最小策略。 注释最大最小值也称为行参与人的安全水平（securitylevel）或下限值（low- ervalue）。最大最小策略也称为行参与人的安全策略（securitystrategy）或最优策略 (optimal strategy)。 定义9.2（最小最大值）给定矩阵博弈A，最小最大值（minmaxvalue）的定义为

=minmaxaij jESiES 注释最小最大值是列参与人在行参与人能自由选择任何策略时遭受的最大可能 的损失。也称为上限值（uppervalue）。若列参与人的策略能给他带来收益一，则称 其为他的安全策略或最优策略。 注释我们已经在6.5节证明≤。如果=，那么我们有下列定义。 定义9.3（纯策略的值）给定矩阵博弈A，若=，则数==称为矩阵博弈 纯策略的值。 例9.5（最大最小值与最小最大值）考虑硬币配对博弈。如果行参与人选择策略 1，那么他的收益可能为1（若列参与人选择策略1），也可能为一1（若列参与人选择策 略2），因此，行参与人的最小收益为一1。类似地，如果行参与人选择策略2，最小收 益为一1。因此，最大最小值为 u=maxmina;=max{-1,-1}=-1 策略1和2都是行参与人的安全策略。最小最大值为 =minmaxag=min{1,1}=1 类似的分析可知，策略1和2都是列参与人的安全策略。这个博弈没有值，因为u≠。 下面我们考虑石头剪刀布博弈。我们有： =maxmina=max{-1,-1,-1)=-1 第 =minmaxag=min{1,1,1}=1 章 与上面的硬币配对博弈一样，这个博弈也没有值，因为≠。 矩阵博弈 最后，我们考虑产品预测博弈。我们有 =maxminag=max{100,-100,-200}=100 =minmaxa=min{100,200,200}=100 注意，=，而且收益v=100，这是纯策略组（1，1）带来的收益，因此这个博弈的 值为100。策略1是行参与人的安全策略，也是列参与人的安全策略。口 9.3 鞍点与纯策略纳什均衡 正如上面例子所指出的，给定矩阵博弈A，最大最小值与最小最大值总存在， 但未必相等。如果它们相等，那么矩阵至少有一个鞍点。我们现在给出矩阵的鞍点 定义。 定义9.4（矩阵的鞍点）给定矩阵A=[a］及其任一元素aj，如果 aj≥akVk=1,.…,m而且 a<al=1,.….n

即若a是它所在列的最大元素，同时又是它所在行的最小元素，那么a称为A的一个 鞍点（saddlepoint）。给定矩阵A，策略i称为行参与人的鞍点策略（saddlepoint strategy），策略i称为列参与人的鞍点策略。 我们现在对鞍点做出几个重要的观察性结论。首先，我们给出两个例子。 例9.6（鞍点）考虑产品预测博弈。我们已经看到这个博弈的值为v=100，它对 应于策略组（1，1）。注意，a1是它所在列的最大元素，同时又是它所在行的最小元 素，因此它是一个鞍点。我们还能注意到以下重要结论。 ·行参与人的鞍点策略1是对列参与人鞍点策略1的最优反应，列参与人的鞍点策 略1是对行参与人鞍点策略1的最优反应。因此，策略组（1，1）是一个纯策略纳什均 衡。策略组（1，1）显然满足纳什均衡的性质，即当对手坚持使用均衡策略时，任一参 与人选择任何其他策略的做法不能使自已的状况变得更好。 ·鞍点策略组（1，1）显然满足下列性质：当对手偏离自己的鞍点策略时，任一参 与人坚持使用鞍点策略的做法不会使自己的状况变得更差。 ·通过选择鞍点策略1，行参与人能保证自己的收益至少为100。通过选择鞍点策 略1，列参与人能保证行参与人的收益至多为100。 ·如果行参与人得到的收益小于100，那么他总可以通过选择鞍点策略1来改善自 已的状况。如果行参与人得到的收益大于100，那么列参与人可通过选择鞍点策略1和 迫使行参与人得到收益100来改善他自己（列参与人）的状况。 上面的这些观察描述了鞍点策略满足的很多性质。口 博 例9.7我们考察伴随下列矩阵的矩阵博弈： 奔 论与 [5353] 机 A=21-1-2 制 [4353] 设计 =maxminag=max{3，-2,3}=3 ij =minmaxag=min{5,3，5,3}=3 对于这个博弈，注意==3。该博弈有四个鞍点，即a12，a14，α32以及α34，它们产生 的收益相同，都为3。另外，所有四个策略组（1，2），（1，4），（3，2）和（3，4）都是 纯策略纳什均衡。事实上，它们是这个博奔仅有的纯策略纳什均衡。口 上面的两个例子促使我们得到下列结果。首先，下列定理说明了何时存在鞍点（必 要且充分条件）。 定理9.1矩阵A有鞍点当且仅当=。 我们把这个定理的证明留作习题。下列命题断言矩阵博弈的纯策略纳什均衡实际上 就是鞍点。 命题9.1对于伴随收益矩阵A的矩阵博弈，ag为鞍点当且仅当策略组（i，j）是 一个纯策略纳什均衡。 证明：假设a是A的一个鞍点。我们证明结果（i，j）是一个纯策略纳什均衡。 由于a是一个鞍点，因此a是第i列的最大元素，同时又是第i行的最小元素（这意味 着一a是第i行的最大元素）。这又意味着列参与人对行参与人选择的策略i做出了最优反

应，行参与人对列参与人选择的策略做出了最优反应。这意味着（i，i）是一个纯策略 纳什均衡。因此，如果a是一个鞍点，那么策略组（i，j）是一个纯策略纳什均衡。 现在证明另一个方向。假设策略组（i，j）是一个纯策略纳什均衡，那么不难证明 a是A的鞍点，只要反转上面的证明过程即可。■ 注释上面的命题意味着与其他矩阵相比，在矩阵博弈中，纯策略纳什均衡的功能 更强大。具体地说，在矩阵博弈中，参与人的纯策略纳什均衡策略也正好是他的安全策 略或最大最小策略。当然，对于除了两人零和博弈之外的其他博弈，这未必为真。 下面的命题说明了矩阵博弈鞍点的可互换性。 命题9.2给定伴随收益矩阵A的矩阵博弈，若a与au都是鞍点，那么ak与ah也 都是鞍点。另外，所有鞍点带给同一个参与人的收益相同。 这个命题的另外一种表达方法是，若（i，j）与（h，k）都是纯策略纳什均衡，那 么（i，k）与（h，j）也都是纯策略纳什均衡。我们将证明留作习题。这个命题意味着 如果存在多个鞍点，那么它们在下列意义上是可互换的（interchangeable）：参与人使 用任一鞍点策略来对付对手的任何鞍点策略，也会产生一个鞍点。而且，所有鞍点在下 列意义上是等价的，即它们带给同一个参与人的收益是相同的。 9.4矩阵博奔中的混合策略 第 我们已经看到，矩阵博弈可能没有鞍点或纯策略纳什均衡。然而，当我们允许混合策 略时，均衡必定存在。令x=（x，"，m）表示行参与人的混合策略，y=（y，，yn） 章 为列参与人的混合策略。注意，a是当行参与人以概率1选择第i行且列参与人以概率1 矩 选择第j列时行参与人的收益。此时，列参与人的收益为一a。在伴随上述混合策略x和 阵 博 y的情形下，行参与人的期望收益： 奔 =u（x，y）= xiya=xAy i=1j=1 其中x=（x，，xm）；y=（y，，yn）；A=[a］。在上面的表达式中，我们稍微 滥用了符号，因为我们本来应该用向量y的转置（即yT）但用了y本身（出于简单目 的，我们在本章都这么做，因为这不会导致混淆）。此时，列参与人的期望收益 为一xAy。当行参与人选择时，他保证自已的期望收益为 minxAy yE△(S2) 因此，行参与人应该选择使得上述收益最大的混合策略x。也就是说，他应该选择x 使得 maxminxAy E△(S)yE(S2) 换句话说，行参与人的最优策略是最大最小化（maxminimization）策略。注意，这里 隐含地假设不管行参与人怎么选择，列参与人都会选择对他（行参与人）最不利的策

略。行参与人在这样的背景下选择最优策略。行参与人选择的这种策略也称为行参与人 的安全策略。： 类似地，当列参与人选择时，他保证自己的收益 min-xAy xE△（S) maxxAy xE△（S) 也就是说，列参与人保证自己的损失不超过 maxxAy E△(S) 列参与人的最优策略应该使这个损失最小，即 min maxxAy y∈△（S）x∈△（S) 这称为最小最大化（minmaximization）。列参与人的这种策略也称为列参与人的安全 策略。 我们现在陈述和证明一个重要引理，它断言若行参与人选择x，则在列参与人的最 优反应策略中至少存在一个纯策略。 引理9.1给定矩阵博弈A以及混合策略x=（x1，，cm）和y=（y1，，yn）， minxAy= min aixi yE△(S) 证明：对于给定的j， aixi 这个加和给出了当行参与人选择x=（x1，，cm）且列参与人选择纯策略j时，行参 与人的收益。因此， min aixi

给出了当行参与人选择但列参与人能自由选择任何纯策略时行参与人的最小收益。由 于纯策略是混合策略的一种特殊情形，我们有 min aixi≥ minxAy (9.1) yE△(S) 另一方面， xAy=∑y（axi）≥∑y(minaci）=min ax;（因为 y=1） j=1 因此，我们有： xAy≥min ajxix∈（S),y∈(S2)

这意味着 minxAy≥ min (9.2) aijx yE△(S) =1 根据式（9.1）和式（9.2），我们有 minxAy min aijxi yE△(S) 这样，我们就完成了这个引理的证明。 作为上面引理的一个直接推论，可以证明 maxxAy max xE△(S) j=1 使用上面的结果，我们可以将行参与人以及列参与人的最优化问题描述如下。 口行参与人的最优化问题（最大最小化） 行参与人面对的最优化问题可以表示为 maxmin aix s.t. xi≥0，i=1，.",m 矩阵博弈 将上面这个问题称为问题P1。注意，这个问题可以简练地表示为 max min xAy E△（S）y(S) 口列参与人的最优化问题（最小最大化） 列参与人面对的最优化问题可以表示为 minmax ajyi j=1 s.t. y≥0,j=1,.…,n 将上面的问题称为问题P2。注意，这个问题可以简练地写为 min maxxAy yE△(S）E△(S) 下列命题说明问题P和P2分别等价于适当的线性规划（linearprogram，LP）。 命题9.3问题P等价于下列线性规划（我们将其称为线性规划LP1）：

maxz s.t. ajx;<0,j=1,.,n xi≥0,i=1,.….,m 证明：注意，P是一个最大化问题，因此，我们考察约束条件 ajxi<0,j=1,.….,n 任何最优解（z*，x*）将满足上述n个不等式中的一个。也就是， aixi 对于某个j∈{1，……，n} 令j就是满足上式的i值。于是 aixi 由于*是线性规划LP的一个可行解，我们有 ax²≤ajxVj=1,,n 这意味着 min 如若不然，我们有 ax;Vj=1,..,n 因此，下列两个线性规划分别描述了行参与人与列参与人面对的最优化问题。 行参与人的线性规划（LP） maxz s.t, ajx;<0,j=1,.….,n xi≥0Vi=1,…,m 列参与人的线性规划（LP2） minw

s.t. ajy;≥0,i=1,..,m y≥0Vj=1,…,n 例9.8（石头剪刀布博弈）对于石头剪刀布博弈，回忆一下，行参与人的收益矩 阵为 -1 A 行参与人的最优化问题P为： maxmin{x2—x3，-x+x3,x1-x2} s.t. x+x2+x=1 x1≥0;x2≥0;x≥0 上面的这个问题等价于线性规划LP： maxx s.t. x<x-xx<-x1+xx<x1-x2 矩阵博弈 x+x2+x3=1;x1≥0;x2≥0；x≥0 列参与人的最优化问题P2为 minmax{-y2+y3，y1-y3，-y+y2} s.t. y+y2+y3=1 y1≥0;y2≥0;y3≥0 上面这个问题等价于线性规划LP2： minw s.t. +<mK<m+-<m y+y2+y3=1;y1≥0；y2≥0;y3≥0 上面的线性规划问题使我们能够计算混合策略均衡。口

9.5最小最大定理 最小最大定理（minimaxtheorem）是博弈论发展初期的一个重要里程碑。冯·诺 依曼于1928年使用布劳威尔（Brouwer）不动点定理证明了这个结论。后来，他与摩根 斯坦使用线性规划对偶性给出了这个定理的漂亮证明。这个定理的重要寓意在于任何矩 阵博弈都存在着混合策略纳什均衡。 定理9.2（最小最大定理）对于每个伴随m×n阶矩阵A的矩阵博弈，存在着行参 与人的混合策略x*=（x，"，x）以及列参与人的混合策略y*=（y，…，y）使得 maxxAy*=minxAy。 xE△(S) yE△(S) 而且，策略组（r，y*）是一个混合策略纳什均衡。 证明：给定矩阵A，我们在上一节已定义了线性规划LP与LP2。线性规划LP 描述了行参与人的最优策略，而线性规划LP2描述了列参与人的最优策略。首先，我 们看到线性规划LP是LP的对偶。我们现在引用下面的强对偶定理：如果某个线性 规划（称为原问题）有最优解，那么它的对偶（称为对偶问题）也有最优解；而且，对 偶问题的最优值与原问题的最优值相同（参见第33章数学附录）。 为了在当前情形下使用强对偶定理，我们首先注意到，根据问题P的本质可知， 博奔论与机制设计 P有最优解。由于线性规划LP等价于问题P，这立即意味着LP有最优解。因此， 我们有两个线性规划LP与LP2，它们互为对偶，而且LP有最优解。于是，根据强 对偶定理可知，LP2也有最优解，而且LP2的最优值与LP的最优值相同。 令*，x，，为线性规划LP的一个最优解。于是，我们有 aix对于某个j∈{1，…，n} 根据LP最优解的可行性可知，我们有 aijxi 对于j=1，.，n 这意味着 min aijxi minAy（根据引理9.1）。 yE△(S) 因此， x=minxAy yE△(S) 类似地，令w，y，，y为线性规划LP的一个最优解。于是， w*=> a²jy对于某个i*∈{1，，m}

根据LP2最优解的可行性，我们有 aay 对于i=1，..，m 这意味着 ajy=maxxAy*（根据引理9.1) E（S) 因此， w*=maxxAy* E△(S) 根据强对偶定理可知，原问题的最优值与对偶问题的最优值相同，因此*=w*。这表明 minxAy=maxcAy (9.3) yE△(S2) E(S) 这样，我们就证明了最小最大定理的主要部分。 我们现在证明对于伴随矩阵A的矩阵博弈来说，混合策略组（x*，y*）是它的一 个混合策略纳什均衡。为了证明这一点，考虑 xAy≥minxAy= maxxAy≥xAyHx∈△（S）（根据式(9.3)) yE△(S) E△(S) 也就是说，xAy*≥xAy*，VcE△（S）。这意味着 u（x*，y*)≥u（x，y*)Hx∈△（S) (9.4) 另外， 矩阵博弈 xAy≤maxxAy* minxAy<xAyVy∈△（S2）（根据式（9.3)) x（S) yE△(S) 也就是说，xAy≤xAy，Vy∈△（S2）。这意味着 u2(x，y*)≥u2（x*，y)Vy∈△（S) 式（9.4）和式（9.5）立即意味着（x*，y*）是一个混合策略纳什均衡。这说明最小 最大定理保证了任何矩阵博弈都存在着混合策略纳什均衡。■ 例9.9对于石头剪刀布博弈，容易看到线性规划LP与LP2互为对偶。而且， 可以看出LP的最优解为 LP2的最优解为 因此，（(，，)，（，，))是这个博弈的一个混合策略纳什均衡。

口均衡解存在的必要充分条件 我们现在给出一个重要定理，它为矩阵博弈的一个混合策略组成为混合纳什均衡提 供了必要充分条件。我们将这个定理的证明留作习题。这个定理的证明关键依赖最小最 大定理。 定理9.3给定矩阵博弈（{1，2}，S1，S2，u1，一u>，混合策略组（x*，y*） 是一个纳什均衡当且仅当 xEargmax min xAy △(S)y△(S) yEargminmaxxAy y△（S)E△(S) 而且 u（x*，y*)=-u2（x*，y*)=xAy=maxminxAy=minmaxxAy E△（S）y△（S) y△(S）x∈△(S) 注释对于矩阵博弈，必须注意下列重要事实。纳什均衡和最大最小策略组一般是 两个不同的概念，但在矩阵博弈背景下，它们是相同的。另外，在矩阵博弈背景下，纳 什均衡不仅保证了每个参与人不单方面偏离均衡策略，也保证了另外一个参与人不偏离 均衡策略。 博 9.6小结与参考文献 奔 论 与机 两人零和博弈是一种策略型博弈，它已被深人研究和理解。如果策略集是有限的， 制 设 那么这样的博弈可以用矩阵A表示，其中元素a；是当行参与人选择纯策略i且列参与 计 人选择纯策略时行参与人的效用；此时，列参与人的效用为一a。本章主要涵盖了以 下重要结果： ·当我们只允许参与人选择纯策略时行参与人的最优策略是选择能最大化他在每个 纯策略得到最小收益的那个策略。列参与人的最优策略是选择能最小化行参与人在他 （列参与人）的每个纯策略得到最大收益的那个策略（这等价于列参与人最小化他在其 每个纯策略可能遭受的最大损失）。这些策略也称为参与人的安全策略。 ·最大最小值或称下限值以表示，最小最大值或称上限值以表示。可以证明， ≤。如果==，那么称为值。如果我们仅允许参与人选择纯策略，那么值可能 存在，也可能不存在。 ·给定矩阵A及其任一元素a，若a是它所在行的最小元素，同时又是它所在列 的最大元素，那么a是矩阵A的一个鞍点。给定矩阵A，鞍点存在当且仅当=。给 定矩阵A，它可能没有鞍点也可能有多个鞍点，而且如果存在鞍点，那么它们正好就是 该博弈的纯策略纳什均衡。 ·如果存在多个鞍点，那么它们都对应着相同值（这是博弈的值）。另外，鞍点策略 可互换；也就是说，给定矩阵博弈A，如果a与au都是鞍点，那么a与a也都是鞍点。

·在矩阵博弈中，参与人的鞍点策略（也称为最优策略）不仅保证参与人自身不单 方面偏离自己的策略，还能保证对方不单方面偏离自己的策略。 ·在矩阵博弈中，我们已经知道纯策略纳什均衡（或等价地，鞍点）可能存在，也 可能不存在。然而，混合策略纳什均衡总存在，这个事实是冯·诺依曼和摩根斯坦的最 小最大定理的一个结果。 ·最小最大定理可用线性规划对偶性证明。行参与人的最优策略可用线性规划计 算，该线性规划的对偶给出了列参与人的最优策略。在证明最小最大定理时，我们使用 了强对偶定理。 ·矩阵博弈的混合策略纳什均衡可用线性规划计算，因此这个问题的最坏情形的计 算复杂性可以用多项式时间表达（这在纳什均衡的计算中比较罕见）。 关于矩阵博弈的详细阐述（包括使用线性规划对偶性证明最小最大定理），可参见 vonNeumann andMorgenstern[1]这本经典著作。另外一本优秀参考书为Luceand Raiffa[2]。 本章行文方式受博弈论著作Myerson[3]以及线性规划著作Chvatal4]启发。读者还 可以参考以下文献：Maschler，Solan，andZamir[5]，Osborne[6]，Rapoport[7]，以及 Straffin[8] 口参考文献 [1]Johnvon Neumann and OskarMorgenstern.Theoryof Games and Economic Behavior.PrincetonUniversityPress,1944. 第 [2]R.D.Luce and H.Raiffa.Games and Decisions.Wiley，NewYork,1957. 章 [3]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard University 矩阵博弈 Press,Cambridge,Massachusetts,USA,1997. [4]Vasek Chvatal.LinearProgramming.W.H.Freeman&Company,1983. [5]Michael Maschler,Eilon Solan,and Shmuel Zamir. Game Theory.Cambridge U- niversityPress,2013. [6]Martin J.Osborne.AnIntroduction to GameTheory.TheMIT Press,2003. [7]Anatol Rapoport.TwoPerson GameTheory.DoverPublications,Inc.，New York,USA,1966. [8]Philip D.StraffinJr.Game Theory and Strategy.TheMathematical Associa- tion ofAmerica,1993. 9.7习题 （1）给定矩阵A=[ag]，回顾下列定义： =maxminai =minmaxaj

（a）证明u≤； （b）证明A有鞍点当且仅当u=。 （2）给定矩阵A=[a]，如果元素ag与a都是鞍点，证明a与a也都是鞍点。 这个命题的等价表示为：如果（i，j）与（h，k）都是纯策略纳什均衡，那么（i，k) 与（h，j）也都是纯策略纳什均衡。 （3）给定m×m矩阵A，如果它的每一行与每一列都是（1，，m）的一个排列 （permutation），那么A称为一个拉丁方（latinsquare）。对于矩阵博弈A，如果它的收 益矩阵是一个拉丁方，请比较它的纯策略纳什均衡（若存在）。 （4）考虑某个矩阵博弈，其中|S|=|S2|，使得矩阵A是反对称的。证明混合策 略的值等于零。 （5）考虑下面的博弈 A=[a 6] d. 问：为了保证这个博弈有鞍点，a，b，c，d应该满足什么条件？另外，计算这个博弈 的所有混合策略纳什均衡。 （6）在某矩阵博弈中，每个参与人都有3个纯策略。这个博弈的纯策略纳什均衡个 数不可能是{0，1，，9}中的哪些？为什么？ （7）分别给出满足下列条件的矩阵博弈的例子： ·只存在纯策略纳什均衡； ●正好存在一个纳什均衡； ·正好存在两个纳什均衡； ·存在无限个纳什均衡； ·存在强优势策略均衡。 （8）对于下列矩阵博弈，写出原线性规划和对偶线性规划并计算所有纳什均衡： A= [23] （9）对于下列矩阵博弈 [231] A=4 413] ·计算纯策略上的最大最小值和最小最大值； ●计算所有纯策略纳什均衡； ·计算混合策略上的最大最小值和最小最大值； ·计算所有混合策略纳什均衡。 （10）对于上面的博弈，写出原线性规划和对偶线性规划并计算所有纳什均衡。 （11）对于下列矩阵博弈，构造合适的线性规划并计算所有混合策略均衡：

A （12）定理9.3为矩阵博弈的混合策略组（x*，y*）成为纳什均衡提供了必要充分 条件，请证明。 （13）（编程题）给定矩阵博弈，写出用来求解混合策略纳什均衡的线性规划程序。 线性规划的解可被用于确定均衡。 矩阵博奔