《运筹学》课程教学资源（参考资料）9 博弈对策模型

9博弈对策模型 9.1引言 在大多数决策问题中，我们的收益（和损失）不仅仅由我们的决策来确定，而且还受外 部力量（例如，竞争对手和气候）的影响。我们可以将这种外部力量分为两大类：一类是无 关紧要的外部力量，一类是有害的外部力量。这种分类是有作用的。例如，如果我们对在暴 风雨期间有没有带雨伞和是否刚洗过车并不介意，那么，我们就认为气候也是属于无关紧要 的外部力量。当然，作为一个竞争对手通常要考虑我们可以做的各种可能的决策，选择那些 可以使得我们的利益受损的对策。在这一章里，我们要分析一些具有害外部力量的对策问题。 用标准的学术术语来说就是研究博弈。在市场或价格策略的选择过程中，在国际事物，军事 对抗和商务谈判中都会遇到博弈问题。例如，面对竞争对手可能的石油禁运，我们就要对是 否需要建立一个石油战略储备策略做出选择。博弈问题的实质常常是确定两个或更多的合作 成员如何“分馅饼”。也就是如何分配一个联合项目的利润。 9.2两人博弈 在所谓的两人博弈理论中，关键是任何一个局中人要在不考虑对方决策的条件做出一个 确定性的决策。只有在两个人都承诺做出了决策以后，一个人才可以知道另一个人的决策。 任何一个人的赢利取决于两个独立的决策。两人博弈又可以按照赢利总和是否为常数分为常 数赢利总博弈和或非常数赢利总和博弈两大类。在两人常数总和博弈中，各个局中人的赢利 总和是常数。通常，这个常数是零。所以，一个局中人的赢利就是另一个局中人的损失。下 面的例子就是一个两人常数总和博弈。 假设Blue和Gold玩一个同时移动博弈。每一个局中人要在不知对方决策的前提下，做 出一个移动的决定。两个局中人的移动结果确定以后，一个局中人将按照下面表格规定的数 据向另一个局中人收取（或支付）赢利

1 9 博弈对策模型 9.1 引言 在大多数决策问题中，我们的收益（和损失）不仅仅由我们的决策来确定，而且还受外 部力量（例如，竞争对手和气候）的影响。我们可以将这种外部力量分为两大类：一类是无 关紧要的外部力量，一类是有害的外部力量。这种分类是有作用的。例如，如果我们对在暴 风雨期间有没有带雨伞和是否刚洗过车并不介意，那么，我们就认为气候也是属于无关紧要 的外部力量。当然，作为一个竞争对手通常要考虑我们可以做的各种可能的决策，选择那些 可以使得我们的利益受损的对策。在这一章里，我们要分析一些具有害外部力量的对策问题。 用标准的学术术语来说就是研究博弈。在市场或价格策略的选择过程中，在国际事物，军事 对抗和商务谈判中都会遇到博弈问题。例如，面对竞争对手可能的石油禁运，我们就要对是 否需要建立一个石油战略储备策略做出选择。博弈问题的实质常常是确定两个或更多的合作 成员如何“分馅饼”。也就是如何分配一个联合项目的利润。 9.2 两人博弈 在所谓的两人博弈理论中，关键是任何一个局中人要在不考虑对方决策的条件做出一个 确定性的决策。只有在两个人都承诺做出了决策以后，一个人才可以知道另一个人的决策。 任何一个人的赢利取决于两个独立的决策。两人博弈又可以按照赢利总和是否为常数分为常 数赢利总博弈和或非常数赢利总和博弈两大类。在两人常数总和博弈中，各个局中人的赢利 总和是常数。通常，这个常数是零。所以，一个局中人的赢利就是另一个局中人的损失。下 面的例子就是一个两人常数总和博弈。 假设 Blue 和 Gold 玩一个同时移动博弈。每一个局中人要在不知对方决策的前提下，做 出一个移动的决定。两个局中人的移动结果确定以后，一个局中人将按照下面表格规定的数 据向另一个局中人收取（或支付）赢利

2 Gold从Blue中得到的赢利矩阵： Blue的移动 -6 Gold的移动 b -5 8 c 3 4 Blue必须在两个移动(a)或(b)中选择一个，而Gold可以在三个移动(a)、(b)和(c)中选择 一个。例如，如果Gold选择了移动(b),Blue选择了移动(a),那么，Gold要支付给Blue5美 元：如果Gold选择(c),Blue选择(a),那么，Blue要支付给Gold3美元。 ●最小最大策略 对于博奔来说，任何一个局中人都不会有显而易见的策略。如果Gold试图移动到(b)以 便获得8美元的奖金，而Blue将试图移动到(a)以便获得5美元的奖金。就这个例子而言， 很显然，每一个决策者都要考虑一个随机策略。如果任何一个局中人总是做出同样的移动， 那么，他马上就会失败。所以，我们定义： BM=Blue做出移动i的概率，i=a或b, GM:=Gold做出移动i的概率，i=ab或c. Blue将如何选择概率BM,?Blue也许注意到： 如果Gold选择移动(a),Blue的期望损失是： 4 BMA -6 BMB 如果Gold选择移动(b),Blue的期望损失是： -5 BMA +8 BMB 如果Gold选择移动(c),Blue的期望损失是： 3 BMA-4 BMB 所以，按照Gold做出的可能决策，Blue有三种可能的期望损失。如果Blue比较保守， 那么，一个比较合理的决策标准是选择BM使得最大的期望损失达到最小。这种观点就是最 小最大损失决策标准。换句话说就是：无论Gold做出什么样的决策，Blue要选择概率BM

2 Gold 从 Blue 中得到的赢利矩阵： Blue 的移动 a b a 4 -6 Gold 的移动 b -5 8 c 3 -4 Blue 必须在两个移动(a)或(b)中选择一个，而 Gold 可以在三个移动 (a)、(b)和(c)中选择 一个。例如，如果 Gold 选择了移动(b)，Blue 选择了移动(a)，那么，Gold 要支付给 Blue 5 美 元；如果 Gold 选择(c)，Blue 选择(a)，那么，Blue 要支付给 Gold 3 美元。 ⚫ 最小最大策略 对于博弈来说，任何一个局中人都不会有显而易见的策略。如果 Gold 试图移动到(b)以 便获得 8 美元的奖金，而 Blue 将试图移动到(a)以便获得 5 美元的奖金。就这个例子而言， 很显然，每一个决策者都要考虑一个随机策略。如果任何一个局中人总是做出同样的移动， 那么，他马上就会失败。所以，我们定义： BMi = Blue 做出移动 i 的概率， i = a 或 b, GMi = Gold 做出移动 i 的概率， i = a, b 或 c. Blue 将如何选择概率 BMi？Blue 也许注意到： 如果 Gold 选择移动(a)，Blue 的期望损失是： 4 BMA - 6 BMB 如果 Gold 选择移动(b)，Blue 的期望损失是： -5 BMA + 8 BMB 如果 Gold 选择移动(c)，Blue 的期望损失是： 3 BMA – 4 BMB 所以，按照 Gold 做出的可能决策，Blue 有三种可能的期望损失。如果 Blue 比较保守， 那么，一个比较合理的决策标准是选择 BMi 使得最大的期望损失达到最小。这种观点就是最 小最大损失决策标准。换句话说就是：无论 Gold 做出什么样的决策，Blue 要选择概率 BMi

3 使得Blue的最大期望损失达到最小。如果LB表示Blue最大的期望损失，这个问题就可以 用下面的LP模型表示： MODEL: MIN LB; ！概率总和等于1； BMA BMB =1; ！如果Gold选择(a),B1ue的期望损失： -LB 4 BMA -6 BMB <0; ！如果Gold选择(b),B1ue的期望损失； -LB -5 BMA 8 BMB <=0; ！如果Gold选择(c),Blue的期望损失： -LB 3 BMA 4 BMB <0; END 解答是： Global optimal solution found at step: 5 Objective value: 0.2000000 Variable Value Reduced Cost LB 0.2000000 0.0000000 BMA 0.6000000 0.0000000 BMB 0.4000000 0.0000000 从上面的解答中可知：如果Blue选择移动到(a)的概率是0.6，选择移动到(b)的概率是0.4， 那么，无论Gold采取怎样的决策，Bue的期望损失决不会超过0.2。 如果我们对Gold也进行类似的讨论，不过我们考察的是赢利而不是损失。我们所用的 决策标准是最大最小期望赢利决策标准，那么，Gold的模型是： MODEL: MAX PG; ！概率总和等于1； GMA GMB +GMC =1; ！如果Blue选择(a),Gold的期望赢利；

3 使得 Blue 的最大期望损失达到最小。如果 LB 表示 Blue 最大的期望损失，这个问题就可以 用下面的 LP 模型表示: MODEL: MIN = LB; ! 概率总和等于 1; BMA + BMB = 1; ! 如果Gold选择(a)，Blue的期望损失; -LB + 4 * BMA - 6 * BMB <= 0; ! 如果Gold选择(b)，Blue的期望损失; -LB - 5 * BMA + 8 * BMB <= 0; ! 如果Gold选择(c)，Blue的期望损失; -LB + 3 * BMA - 4 * BMB <= 0; END 解答是： Global optimal solution found at step: 5 Objective value: 0.2000000 Variable Value Reduced Cost LB 0.2000000 0.0000000 BMA 0.6000000 0.0000000 BMB 0.4000000 0.0000000 从上面的解答中可知：如果 Blue 选择移动到(a)的概率是 0.6，选择移动到(b)的概率是 0.4， 那么，无论 Gold 采取怎样的决策，Blue 的期望损失决不会超过 0.2。 如果我们对 Gold 也进行类似的讨论，不过我们考察的是赢利而不是损失。我们所用的 决策标准是最大最小期望赢利决策标准，那么，Gold 的模型是： MODEL: MAX = PG; ! 概率总和等于 1; GMA + GMB + GMC = 1; ! 如果Blue选择(a)，Gold的期望赢利;

4 -PG 4 GMA -5 GMB 3 GMC >=0; ！如果Blue选择(b),Gold的期望赢利； -PG -6 GMA +8 GMB -4 GMC >=0; END Gold问题的解答是： Global optimal solution found at step: 5 Objective value: 0.2000000 Variable Value Reduced Cost PG 0.2000000 0.0000000 GMA 0.0000000 0.1999999 GMB 0.3500000 0.0000000 GMC 0.6500000 0.0000000 从上面的解答中可知：如果Gold选择移动到(b)的概率是0.35，选择移动到(c)的概率是 0.65,从不选择移动(a),那么，无论Blue采取怎样的决策，Gold的期望赢利决不会少于0.2。 注意，Gold的最低期望赢利就是Blue的最高期望损失。从Blue的观点来看，至少有O.2的 赢利转移到Gold。最可能转移量就是0.2。这意味着如果两个局中人都按照各自的随机决策 玩博弈，一天下来，将会有0.2的赢利从Blue转到Gold。这个博奔是以Gold一天赢利0.2 美元为基础而设计的。这种可以进行随机的选择以对付对手的猜测的策略有时也被称为一个 混合策略。 如果你再仔细看看Blue模型和Gold模型的解答，你将会注意到它们与我们前面介绍的 对偶问题非常相似。Blue模型的对偶价格等于Gold模型的概率，而Gold模型的对偶价格的 负值等于Bue模型的概率。再看仔细一下，你会注意到，两个模型确实互为对偶问题。这个 结论在我们刚刚讨论的两人零和博弈中成立。数学家曾经为这样的事实而兴奋不已。 9.3两人非常数总和博弈 在许多情况下，一个人的福利、效用和赢利不仅仅取决于自己的决策，而且也取决于其 他人的决策。上面介绍的两人博弈只是其中的一个特殊情况： 1)只有两个局中人/决策者

4 -PG + 4 * GMA - 5 * GMB + 3 * GMC >= 0; ! 如果Blue选择(b)，Gold的期望赢利; -PG - 6 * GMA + 8 * GMB - 4 * GMC >= 0; END Gold 问题的解答是： Global optimal solution found at step: 5 Objective value: 0.2000000 Variable Value Reduced Cost PG 0.2000000 0.0000000 GMA 0.0000000 0.1999999 GMB 0.3500000 0.0000000 GMC 0.6500000 0.0000000 从上面的解答中可知：如果 Gold 选择移动到(b)的概率是 0.35，选择移动到(c)的概率是 0.65，从不选择移动(a)，那么，无论 Blue 采取怎样的决策，Gold 的期望赢利决不会少于 0.2。 注意，Gold 的最低期望赢利就是 Blue 的最高期望损失。从 Blue 的观点来看，至少有 0.2 的 赢利转移到 Gold。最可能转移量就是 0.2。这意味着如果两个局中人都按照各自的随机决策 玩博弈，一天下来，将会有 0.2 的赢利从 Blue 转到 Gold。这个博弈是以 Gold 一天赢利 0.2 美元为基础而设计的。这种可以进行随机的选择以对付对手的猜测的策略有时也被称为一个 混合策略。 如果你再仔细看看 Blue 模型和 Gold 模型的解答，你将会注意到它们与我们前面介绍的 对偶问题非常相似。Blue 模型的对偶价格等于 Gold 模型的概率，而 Gold 模型的对偶价格的 负值等于 Blue 模型的概率。再看仔细一下，你会注意到, 两个模型确实互为对偶问题。这个 结论在我们刚刚讨论的两人零和博弈中成立。数学家曾经为这样的事实而兴奋不已。 9.3 两人非常数总和博弈 在许多情况下，一个人的福利、效用和赢利不仅仅取决于自己的决策，而且也取决于其 他人的决策。上面介绍的两人博弈只是其中的一个特殊情况： 1） 只有两个局中人/决策者

5 2)每一个局中人必须做出一个决策， 3)无视其他局中人的决策， 4)有一个取决于两个局中人决策的损失函数。 两人常数总和博弈（通常常数取为0，称为零和博弈）就是上面的一种特殊情况： 4a)双方的损失都是用同一个标准来度量（例如，美元）， 4b)总损失是不受决策影响的一个常数。 因此，在一个两人常数总和博弈中，决策的唯一效果就是确定如何分配常数大小的馅饼。 普通的线性规划模型可以用来求解两人常数总和博弈问题。 当(1)、(2)和(3)成立，而(4b)不成立时，那么，我们得到一个两人非常数总和博弈问题。 普通的线性规划算法是不能用于求解两人非常数总和博弈问题的。当然，我们可以用一些线 性规划的补充算法来求解他们。有时，两人非常数总和博弈也被称为是一个双矩阵博弈。 下面我们来介绍一个实例。假设有两个公司，他们都打算引进一种家喻户晓的消费产品 的改进型。这些改进型也是很类似的，所以，一个公司的利润不仅仅受自己广告决策的影响， 也受竞争对手广告决策的影响。假设每个公司的主要决策就是做广告。损失函数由图9.1确 定（单位是美元）。这个例子说明了每一个局中人的收益总和不需要严格相等。 图9.1两人非常数总和博弈 公司A 无广告 中等广告 高广告 -4 -3 无广告 -4 -2 1 公司B -1 -2 -1 有广告 -5 0 注意，损失的负值就是利润

5 2) 每一个局中人必须做出一个决策， 3) 无视其他局中人的决策， 4) 有一个取决于两个局中人决策的损失函数。 两人常数总和博弈(通常常数取为 0，称为零和博弈)就是上面的一种特殊情况： 4a) 双方的损失都是用同一个标准来度量(例如，美元)， 4b) 总损失是不受决策影响的一个常数。 因此，在一个两人常数总和博弈中，决策的唯一效果就是确定如何分配常数大小的馅饼。 普通的线性规划模型可以用来求解两人常数总和博弈问题。 当(1)、(2)和(3)成立，而(4b)不成立时，那么，我们得到一个两人非常数总和博弈问题。 普通的线性规划算法是不能用于求解两人非常数总和博弈问题的。当然，我们可以用一些线 性规划的补充算法来求解他们。有时，两人非常数总和博弈也被称为是一个双矩阵博弈。 下面我们来介绍一个实例。假设有两个公司，他们都打算引进一种家喻户晓的消费产品 的改进型。这些改进型也是很类似的，所以，一个公司的利润不仅仅受自己广告决策的影响， 也受竞争对手广告决策的影响。假设每个公司的主要决策就是做广告。损失函数由图 9.1 确 定（单位是美元）。这个例子说明了每一个局中人的收益总和不需要严格相等。 图 9.1 两人非常数总和博弈 公司 A 无广告 中等广告 高广告 公司 B 无广告 -4 -4 -3 -2 -5 1 有广告 -1 -5 -2 -1 -1 0 注意，损失的负值就是利润

6 9.3.1囚犯的困境 这个损失矩阵具有所谓的囚犯的困境结构。囚犯的困境来源于这样一个假设：假定有两 个同案犯发现他们已经被关进了各自的牢房。如果他们都不与警察合作，他们将受到中等程 度惩罚：如果有一个囚犯提供另一个囚犯犯罪的证据而另一个囚犯没有提供该囚犯犯罪的证 据，那么，前者将受到较轻的惩罚，而后者将受到严厉的惩罚：如果双方都提供了对方犯罪 的证据，那么，两个犯人都将受到严厉的惩罚。很显然，对于这两个囚犯来说，最好的结局 是他们相互协作。然而，就个别人来说，有很强的诱惑导致损失惨重。 囚犯的困境现象在现实问题常常出现，尤其是在做广告的时候。到密歇根州北部的 Mackinac岛的唯一线路是在Mackinaw市的渡口坐渡船前往。有三家公司Sheplers、Arnold Line和Star Line从事摆渡生意。当你坐车接近Mackinaw市的时候，你也许注意到在离摆渡 码头还有一英里的地方，每家公司在路边都有一个或多个出售自己公司船票的小亭子。如果 你是经常往来该岛的人，你会直接把车开到有显著标记的码头空地并停好车，并在上渡船之 前买一张票（不允许任何汽车进入Mackinac岛）。由于没有预定的座位，提前在小亭子买票没 有什么意义。然而，如果你是头一次到Mackinac岛去，当你看到“提前买票绝对保险”的标 语时，你就有可能到一个公司的小亭子那里预先买一张船票。有经验的人是不会在这种小亭 子预先买票的。如果一个公司没有这样的小亭子，而他的竞争对手有这样的小亭子，那么这 个公司就可能失去头一次访问该岛的数量可观的顾客群体。 这种情况同样在我们的例子中也存在。对于这个例子，如果A不作广告，而B作广告， 那么，A可赢利1美元，而B可赢利5美元。如都不作广告，总的赢利可以达到最大化。当 然，如果有一方知道另一方不作广告，那么他（他认为他有这样的观察能力）必然会做广告。 最后，我们设法将损失表中的数据都变成严格的正数（这样做非常有用）。如果我们将 所有的数据都加上一个常数，那么求出的结果与原来的结果实质上一样。图9.2是通过对图 9.1中全部加上+6而得到。 图9.2非常数总和两人博弈 公司A 无广告 中等广告 高广告

6 9.3.1 囚犯的困境 这个损失矩阵具有所谓的囚犯的困境结构。囚犯的困境来源于这样一个假设：假定有两 个同案犯发现他们已经被关进了各自的牢房。如果他们都不与警察合作，他们将受到中等程 度惩罚；如果有一个囚犯提供另一个囚犯犯罪的证据而另一个囚犯没有提供该囚犯犯罪的证 据，那么，前者将受到较轻的惩罚，而后者将受到严厉的惩罚；如果双方都提供了对方犯罪 的证据，那么，两个犯人都将受到严厉的惩罚。很显然，对于这两个囚犯来说，最好的结局 是他们相互协作。然而，就个别人来说，有很强的诱惑导致损失惨重。 囚犯的困境现象在现实问题常常出现，尤其是在做广告的时候。到密歇根州北部的 Mackinac 岛的唯一线路是在 Mackinaw 市的渡口坐渡船前往。有三家公司 Sheplers、Arnold Line 和 Star Line 从事摆渡生意。当你坐车接近 Mackinaw 市的时候，你也许注意到在离摆渡 码头还有一英里的地方，每家公司在路边都有一个或多个出售自己公司船票的小亭子。如果 你是经常往来该岛的人，你会直接把车开到有显著标记的码头空地并停好车，并在上渡船之 前买一张票(不允许任何汽车进入 Mackinac 岛)。由于没有预定的座位，提前在小亭子买票没 有什么意义。然而，如果你是头一次到 Mackinac 岛去，当你看到“提前买票绝对保险”的标 语时，你就有可能到一个公司的小亭子那里预先买一张船票。有经验的人是不会在这种小亭 子预先买票的。如果一个公司没有这样的小亭子，而他的竞争对手有这样的小亭子，那么这 个公司就可能失去头一次访问该岛的数量可观的顾客群体。 这种情况同样在我们的例子中也存在。对于这个例子，如果 A 不作广告，而 B 作广告， 那么，A 可赢利 1 美元，而 B 可赢利 5 美元。如都不作广告，总的赢利可以达到最大化。当 然，如果有一方知道另一方不作广告，那么他（他认为他有这样的观察能力）必然会做广告。 最后，我们设法将损失表中的数据都变成严格的正数（这样做非常有用）。如果我们将 所有的数据都加上一个常数，那么求出的结果与原来的结果实质上一样。图 9.2 是通过对图 9.1 中全部加上+6 而得到。 图 9.2 非常数总和两人博弈 公司 A 无广告 中等广告 高广告

7 2 3 无广告 2 7 公司B 5 4 有广告 6 以后，我们就用图9.2的数据。 9.3.2选择一个策略 我们希望我们自己的选择满足： ⅰ.某种程度上说我们的竞争对手无法预料： ⅱ.除了竞争对手无法预料以外，力争我们的期望利润达到最高。 因此，我们再一次利用随机或混合策略的方法。由于我们的决策是随机的（例如，借助 于投掷一个钱币)，满足（①没有什么问题。又由于我们对货币的偏爱，这也导致我们尽量满足 (i)。 对于这个例子，我们定义，a2,a分别为A选择"无广告"，"适度广告"和"大量广告"的 概率。类似地，b1和b2分别表示B选择"无广告"和"有广告"的概率。那么，A将如何选择， a和a3,B将如何选择b1和b2? 对于一个双矩阵博弈来说，困难之处是如何定义一个解，使得双方都达到最优。当然， 我们可以定义一个稳定的策略。一个稳定的策略具有这样的特性：假设已知B对b,和b2的 选择，A不会去改变am,a和as的概率。同样，假设已知A对于a,a和a的选择，B不会 去改变b,和b2的概率。如果一个策略满足：没有局中人愿意单方面地去改变他或她的决策， 这样的策略有时就称为一个Nsh均衡点。一个双矩阵博弈问题可以有多个稳定策略。 关于A的一个稳定策略我们可以预先知道些什么呢？有些a的值可能是0，有些a的值 可能大于0。有一个不太显然但很重要的结论：对于一个稳定策略来说，如果a>0,A的任 何替代选择的期望损失应该大于原来的期望损失。如果这个条件不能得到满足，那么，在某 一个选择下，A就可以通过增加对应期望损失较小的概率，减少对应期望损失较大的概率， 使得A的总期望损失有所减少。我们用VA表示A的期望损失。同样，=0也暗示：如果

7 公司 B 无广告 2 2 3 4 1 7 有广告 5 1 4 5 5 6 以后，我们就用图 9.2 的数据。 9.3.2 选择一个策略 我们希望我们自己的选择满足： i. 某种程度上说我们的竞争对手无法预料； ii. 除了竞争对手无法预料以外，力争我们的期望利润达到最高。 因此，我们再一次利用随机或混合策略的方法。由于我们的决策是随机的（例如，借助 于投掷一个钱币），满足(i)没有什么问题。又由于我们对货币的偏爱，这也导致我们尽量满足 (ii)。 对于这个例子，我们定义 al, a2, a3 分别为 A 选择"无广告"，"适度广告"和"大量广告"的 概率。类似地，b1 和 b2 分别表示 B 选择"无广告"和"有广告"的概率。那么，A 将如何选择 al, a2 和 a3，B 将如何选择 b1 和 b2？ 对于一个双矩阵博弈来说，困难之处是如何定义一个解，使得双方都达到最优。当然， 我们可以定义一个稳定的策略。一个稳定的策略具有这样的特性：假设已知 B 对 b1 和 b2 的 选择，A 不会去改变 al, a2 和 a3 的概率。同样，假设已知 A 对于 al, a2 和 a3 的选择， B 不会 去改变 b1 和 b2 的概率。如果一个策略满足：没有局中人愿意单方面地去改变他或她的决策， 这样的策略有时就称为一个 Nash 均衡点。一个双矩阵博弈问题可以有多个稳定策略。 关于 A 的一个稳定策略我们可以预先知道些什么呢？有些 ai 的值可能是 0，有些 ai 的值 可能大于 0。有一个不太显然但很重要的结论：对于一个稳定策略来说，如果 ai > 0，A 的任 何替代选择的期望损失应该大于原来的期望损失。如果这个条件不能得到满足，那么，在某 一个选择下，A 就可以通过增加对应期望损失较小的概率，减少对应期望损失较大的概率， 使得 A 的总期望损失有所减少。我们用 VA 表示 A 的期望损失。同样，ai = 0 也暗示：如果

8 选择i(使a>0),那么相应的期望损失一定大于VA。利用这些观察可知A的行为一定满足： 2b1+5b2 =>Va(如果a>0,则等号成立)， 3b1+4b2 =>vA(如果2>0，则等号成立)， b1+5b2 =>vA(如果a>0,则等号成立)。 同样，根据对称性有： 2a+4a+7a3>vB(如果b1>0,则等号成立)， a+5a2+6a>vB(如果b2>0,则等号成立) 同时，也有下面的非负性约束： a=>0和b=>0,对所有的i成立。 由于a和b:是概率，我们增加约束a+a2+a3=1和b1+b2=1。 如果我们增加松弛变量，就可以将上面的部分约束写成下面的形式： 2b1+5b2-slka VA 3b1+4b2 slka2 VA b1 +5 b2 slka3 VA 2a +4 a2 +7 a3 -slkb VB a+5 a2 +6 a3-slkb2 VB al+a2+a3=1 b1+b2=1 a=>0,b:>0,slkai=>0,和slkb=>0,对所有的i成立 slkai*a=0 slkaz*a2=0 slkas*a3=0 slkb*b=0 slkb2*b2=0 最后5个约束是补充条件。整个模型可以认为是一个弱线性问题。 我们不用专门的弱线性规划计算程序而是用LNGO提供的整数规划功能来建立这个问 题的数学模型： MODE工：！两人非常数总和博弈模型； SETS: OPTA/1.3/:PA,SLKA,NOTUA,COSA; OPTB/1.2/:PB,SLKB,NOTUB,COSB; BXA(OPTB,OPTA):C2A,C2B;

8 选择 i（使 ai > 0），那么相应的期望损失一定大于 VA。利用这些观察可知 A 的行为一定满足： 2 b1 + 5 b2 => vA (如果 al > 0，则等号成立), 3 b1 + 4 b2 => vA (如果 a2 > 0，则等号成立), b1 + 5 b2 => vA (如果 a3 > 0，则等号成立)。 同样，根据对称性有： 2al + 4 a2 + 7 a3 > vB (如果 b1 > 0，则等号成立), al + 5 a2 + 6 a3 > vB (如果 b2 > 0，则等号成立)。 同时，也有下面的非负性约束： ai => 0 和 bi => 0，对所有的 i 成立。 由于 ai 和 bi 是概率，我们增加约束 al + a2 + a3 = 1 和 b1 + b2 = 1。 如果我们增加松弛变量，就可以将上面的部分约束写成下面的形式： 2b1 + 5b2 - slkal = vA 3b1 + 4 b2 - slka2 = vA b1 + 5 b2 - slka3 = vA 2al + 4 a2 + 7 a3 - slkbl = vB al + 5 a2 + 6 a3 - slkb2 = vB al + a2 + a3 = 1 b1 + b2 = 1 ai => 0, bi > 0, slkai =>0, 和 slkbi => 0，对所有的 i 成立 slkal* al = 0 slka2* a2 = 0 slka3* a3 = 0 slkbl* bl = 0 slkb2* b2 = 0 最后 5 个约束是补充条件。整个模型可以认为是一个弱线性问题。 我们不用专门的弱线性规划计算程序而是用 LINGO 提供的整数规划功能来建立这个问 题的数学模型： MODEL: !两人非常数总和博弈模型; SETS: OPTA/1.3/: PA, SLKA, NOTUA, COSA; OPTB/1.2/: PB, SLKB, NOTUB, COSB; BXA( OPTB, OPTA): C2A, C2B;

9 ENDSETS DATA: C2A=231!如果B选择第I行，A选择第J列时，A的成本C2A(I,J): 545: C2B=247!如果B选择第I行，A选择第J列时，B的成本C2B(I,J)； 156: ENDDATA !A选择任何一个J的条件： @FOR(OPTA(J):!如果J被A使用，令CBSTA=策略J的成本； CBSTA COSA(J)-SLKA(J); COSA(J)=@SUM(OPTB(I):C2A(I,J)*PB(I)); !如果策略J被使用，迫使SLKA(J)=0; SLKA(J)<=NOTUA(J)*@MAX (OPTB (I): C2A(I,J)): !如果策略J未被使用，迫使NOTUA(J)=1: PA(J)<=1 -NOTUA(J); !无论灯是否被使用： @BIN(NOTUA(J)); ）: !A必须做出一个决策； @SUM(OPTA(J):PA(J))=1; !B选择任何一个I的条件； @FOR(OPTB(I): !如果I被B使用，令CBSTB=策略J的成本； CBSTB COSB(I)-SLKB(I); COSB(I)=@SUM(OPTA(J):C2B(I,J)*PA(J)); !如果策略I被使用，迫使SLKB(I)=O; SLKB(I)<=NOTUB(I)*@MAX(OPTA(J): C2B(I,J)): !如果策略I未被使用，迫使NOTUB(I)=1: PB(I)<=1 -NOTUB(I); !无论I是否被使用：

9 ENDSETS DATA: C2A = 2 3 1 !如果B选择第I行，A选择第J列时,A的成本C2A( I, J); 5 4 5; C2B = 2 4 7 !如果B选择第I行，A选择第J列时,B的成本C2B( I, J); 1 5 6; ENDDATA !A选择任何一个J的条件; @FOR(OPTA(J):!如果J被A使用，令CBSTA=策略J的成本; CBSTA = COSA(J) - SLKA(J); COSA(J) = @SUM( OPTB(I): C2A(I,J) * PB(I)); !如果策略J被使用，迫使SLKA( J) = 0; SLKA(J) <= NOTUA(J) * @MAX(OPTB(I): C2A(I,J)); !如果策略J未被使用，迫使NOTUA(J) = 1; PA(J) <= 1 - NOTUA(J); !无论J是否被使用; @BIN( NOTUA(J)); ); !A必须做出一个决策; @SUM(OPTA(J): PA(J)) = 1; !B选择任何一个I的条件; @FOR(OPTB(I): !如果I被B使用，令CBSTB=策略J的成本; CBSTB = COSB(I) - SLKB(I); COSB(I) = @SUM(OPTA(J): C2B(I,J) * PA(J)); !如果策略I被使用，迫使SLKB( I) = 0; SLKB(I) <= NOTUB(I) * @MAX(OPTA(J): C2B(I,J)); !如果策略I未被使用，迫使NOTUB(I) = 1; PB(I) <= 1 - NOTUB(I); !无论I是否被使用;

10 @BIN(NOTUB(I)); ） !B必须做出一个决策： @SUM(OPTB(I):PB(I))=1; END 解答是： Feasible solution found at step: 129 Variable Value PA(1) 0.0000000 PA(2) 0.5000000 PA(3) 0.5000000 PB(1) 0.3333333 PB(2) 0.6666667 这个解答表明公司将不会选择第1个决策，将随机地选择第2和第3个决策，而且选择 的概率相等。公司B也将随机地选择第1个选择和第2个选择，但是选择前者的概率只是后 者的一半。 目标函数值、减量成本和对偶价格都忽略了。利用我们原始的损失表，我们可以得到下 面的结果： 状态 总损失的加权分布 B 概率 B 无广告 无广告 0×1/3 0 0 无广告 有广告 0×2/3 0 0 普通广告 无广告 1/2×1/3 (1/6)×(-3) (1/6)×(-2) 普通广告 有广告 1/2×2/3 (1/3)×(-2) (1/3)×(-1) 大量广告 无广告 1/2×1/3 (1/6)×(-5) (1/6)×(1) 大量广告 有广告 1/2×2/3 (1/3)×(-1) (1/3)×(0) -2.3333 -0.5 因此，这个解答暗示：A将有一个233美元的期望利润：而B将有0.5美元的期望利润

10 @BIN( NOTUB(I)); ); !B必须做出一个决策; @SUM(OPTB(I): PB(I)) = 1; END 解答是： Feasible solution found at step: 129 Variable Value PA( 1) 0.0000000 PA( 2) 0.5000000 PA( 3) 0.5000000 PB( 1) 0.3333333 PB( 2) 0.6666667 这个解答表明公司将不会选择第 1 个决策，将随机地选择第 2 和第 3 个决策，而且选择 的概率相等。公司 B 也将随机地选择第 1 个选择和第 2 个选择，但是选择前者的概率只是后 者的一半。 目标函数值、减量成本和对偶价格都忽略了。利用我们原始的损失表，我们可以得到下 面的结果： 状态 总损失的加权分布 A B 概率 A B 无广告 无广告 0 ×1/3 0 0 无广告 有广告 0 × 2/3 0 0 普通广告 无广告 1/2 × 1/3 (1/6) × (-3) (1/6) × (-2) 普通广告 有广告 1/2 × 2/3 (1/3) × (-2) (1/3) × (-1) 大量广告 无广告 1/2 × 1/3 (1/6) × (-5) (1/6) × (1) 大量广告 有广告 1/2 × 2/3 (1/3) × (-1) (1/3) × (0) -2.3333 -0.5 因此，这个解答暗示：A 将有一个 2.33 美元的期望利润；而 B 将有 0.5 美元的期望利润