当前位置：文档之家 › 运筹学教学对策论

运筹学教学对策论

  • 格式：pptx
  • 大小：843.34 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

运筹学-第15章--对策论

运筹学-第15章--对策论

1 8 5 8 5 5*
2 2 3 2 1 1
3 4
9 0
5 2
6 3
5 5*
3
0
max 9 5* 8 5*
可知 ai* j* =5，i*=1,3，j*=2,4．故（α1，β2）（α1，β4）（α2，
β2）（α2，β4）为对策的纳管 什理均运衡，筹 V学G=5．
15
• 最优纯策略求解步骤：
• 1、行中取小，小中取大得最大化最小收益 值；
• 2、列中取大，大中取小得最小化最大支付 值；
• 3、比较两值是否相等。若相等便存在最优 纯策略。若不等，则不存在最优纯策略。
管理运筹学
16
§3 矩阵对策的混合策略
设矩阵对策 G = { S1, S2, A }。当
max
i
min
j
aij
min
j
max
i
aij
时，不存在最优纯策略。
例：设一个赢得矩阵如下:
一个局势，一个局势决定了各局中人的对策结果（量化） 称为该局势对策的益损值。
管理运筹学
3
§1 对策论的基本概念
出赛的次序是一个策略 “齐王赛马”齐王在各局势中的益损值表（单位：千金）
管理运筹学
4
§1 对策论的基本概念
其中：齐王的策略集: S1={ 1, 2, 3, 4, 5, 6 }， 田忌的策略集：S2={ 1, 2, 3, 4, 5, 6 }。
A=[aij]m×n i 行代表甲方策略 i=1, 2, …, m；j 列代表乙方策略 j=1, 2, …, n；aij 代表甲方取策略 i，乙方取策略 j，这一局势下甲方的 益损值。此时乙方的益损值为 -aij（零和性质）。

《管理运筹学-对策论》

《管理运筹学-对策论》

博弈与均衡
04
对策分析方法
CHAPTER
VS
静态分析法是一种不考虑时间因素的分析方法，主要适用于解决一次性决策问题。
详细描述
静态分析法将问题视为一个静态系统，不考虑时间变化和过程发展，只关注决策变量的当前状态和最优解。这种方法适用于确定性和静态的环境，如线性规划、整数规划等。
总结词
静态分析法
总结词
《管理运筹学-对策论》
目录
对策论概述 对策模型 对策论的基本概念 对策分析方法 对策论的应用实例 对策论的未来发展
CONTENTS
01
对策论概述
CHAPTER
对策论，也称为博弈论，是研究决策主体在相互竞争、相互依存的环境中如何进行策略选择和行动的学科。
对策论强调理性、优化和均衡，通过数学模型和逻辑推理来描述和分析竞争行为，尤其关注在不确定性和信息不对称情况下的决策问题。
对策论的定义与特点
特点
定义
竞争策略分析
对策论可以用于分析企业或组织在市场竞争中的策略选择，例如定价策略、产品差异化、市场份额争夺等。
合作协议
在某些情况下，企业间可能通过对策论的方法找到合作的可能性，例如供应链协调、合作研发等。
人力资源决策
在招聘、晋升、激励设计等方面，对策论可以帮助理解个体和团队的行为反应，优化人力资源决策。
03
对策论的基本概念
CHAPTER
策略与行动
策略
在对策中，参与者为达到目标所采取的行动方案。策略是完整的、具体的行动计划，它规定了参与者在所有可能情况下应采取的行动。
行动
在对策中，参与者实际采取的行动。行动是实现策略的具体行为或决策。
在对策中，如果一个参与者的某个策略能够使其获得比其他参与者更好的结果，则称该策略为优势策略。优势策略是相对于其他参与者的策略而言的。

运筹学第9章 对策论

运筹学第9章 对策论

3. 赢得函数(支付函数)(payoff function)
一个对策中，每一个局中人所出策略形成的策略 组称为一个局势。 即设 s i 是第 i 个局中人的一个策略， 则n个局中人的策略形成的策略组 s ( s1 , s2 ,, sn )
s 就是一个局势。
在“齐王VS田忌赛马”中，
齐王有6个策略： 2 ( 上，下，中)、 1 (上，中，下)、 4 (中，下，上)、 5 ( 下，上，中)、
1 2
设局中人I采用纯策略 1和 2的概率 分别为 x1 和 x2 ，x1 x2 1, x1,2 0 设局中人II采用纯策略 1和 2的概率 分别为 y1 和 y2 ，y1 y2 1, y1,2 0
SI 1 , 2 设局中人I的策略集原来为： 那么在没找到纯策略的前提下，局中人I的策略集变为： 局中人I的策略 SI X ( x1, x2 )T x1 x2 1, x12 0 有无穷多个 S II 1 , 2 设局中人I的策略集原来为： 那么在没找到纯策略的前提下，局中人II的策略集变为：
当一个局势 s 出现后，每一局中人就会面对
一个赢得值或损失值，记作 Hi (s)。
Hi (s) 是定义在局势上的函数，
所以称为局中人 i 的赢得函数。
通常的分类方式有： (1) 根据局中人的个数，分为二人对策和多人对策； (2) 根据各局中人的赢得函数的代数和是否为零，分 为零和对策与非零和对策； (3) 根据各局中人间是否允许合作，分为合作对策和 非合作对策； (4) 根据局中人的策略集中的策略个数，分为有限对 策和无限对策等等。
max VG X 1 E ( X 1 , 1 ) E ( X 1 , 2 ) X 2 E ( X 2 , 1 ) E ( X 2 , 2 ) 5 x1 8 x2 VG E s . t . X 3 E ( X 3 , 1 ) E ( X 3 , 2 ) 9 x1 6 x2 VG x x 1 , x , x 0 1 2 1 2

《运筹学教学资料》ch14对策论

《运筹学教学资料》ch14对策论

寡头垄断市场上的价格竞争案例中，存在几 家大型企业，它们通过价格策略来争夺市场 份额。如果企业都选择降价，将导致价格战； 如果都选择维持高价，将获得更多利润。但 企业往往会选择降价来争夺市场，最终导致 双方受损。
THANK YOU
感谢聆听
纯策略均衡
在纳什均衡中，每个参与者都采用单 一策略。如果所有参与者的纯策略组 合构成纳什均衡，则称为纯策略均衡。
混合与者以一定的概率分布随机选择不同的策略，使得对手无法通过预测获 得优势。在混合策略均衡中，每个参与者的预期收益达到相对稳定的状态。
混合策略纳什均衡
在经济学中，帕累托前沿表示在所有可能的资源配置中，能够使得所有
玩家的利益都得到最大化的配置集合。帕累托前沿用于衡量资源配置的
效率和公平性。
03
应用
纳什均衡和帕累托前沿是评价博弈结果和资源配置的重要工具，可以帮
助理解在竞争和合作中的最优选择和资源配置问题。
04
多人对策
合作博弈与非合作博弈
合作博弈
参与者通过合作达成协议，以最 大化共同利益。合作博弈强调联 盟和集体行动，通常使用夏普里 值来分配收益。
运筹学教学资料
目
CONTENCT
录
• 对策论简介 • 二人有限零和对策 • 二人有限非零和对策 • 多人对策 • 对策论案例分析
01
对策论简介
对策论的定义与特点
定义
对策论，也称为博弈论，是研究决策主体在相互竞争、对抗或合 作中的行为和决策的数学分支。
特点
对策论强调理性个体之间的策略互动，通过数学模型描述和预测 主体之间的行为和结果，为决策者提供最优策略和解决方案。
对策论的应用领域
01
02

运筹学对策论

运筹学对策论
第六章 对
策
论
第一节 对策论的基本概念
第二节 矩阵对策 第三节 矩阵对策的解法
第一节 对策论的基本概念
一、简例
二、对策问题的数学模型 三、对策问题的分类 四、均衡的意义
一、简例
例1 战国时期，齐王与大夫田忌每年要赛马，双方约定：每方出上、中、 下三个等级的马各1匹，每匹马都参赛一次，共赛3次。每次赛后，负者要 付给胜者千金。当时的情况是，在各个等级的马中，齐王的马都稍强于田 忌的马。每次赛马，田忌经常要输三千金。有一次，田忌的谋士孙膑出了 个主意：让田忌用下等马对齐王的上等马，用中等马对齐王的下等马，用 上等马对齐王的中等马。这样，比赛结果田忌一负两胜，反而赢得了一千 金。由此可见，掌握准确的信息，制定正确的行动方案是制胜的关键。在 现实生活中，例如乒乓球团体赛，选手的排序不同，往往导致比赛的结果 不同。在各种冲突的现象中，参与者如何决策是关系重大的问题。
一、简例
例2 Von Neumann根据福尔摩斯探案中的情节，略加修改，把对策论的精 神融会其中，使大侦探与巨盗的斗争，更加引人入胜。大侦探福尔摩斯严 重妨碍了当时邪恶势力的头子莫里亚蒂。此人诡计多端，心黑手狠，多次 扬言要对福尔摩斯下毒手。风声传到福尔摩斯耳朵里，他感到，当时自己 势孤力单，“三十六计，走为上计”，决定暂时离开英国，福尔摩斯匆忙 上了从伦敦到多佛尔的火车。从车窗里，他突然发现莫里亚蒂也在站台上， 并且觉察到对手已发现他坐在火车里，火车正要开动，下车躲避已不可能。 福尔摩斯在火车里，紧张地盘算着对策。从伦敦到多佛尔，火车只停靠一 个中间站坎特伯雷，他是否要在那里下车，中途脱逃呢？另一方面，莫里 亚蒂分析问题的本领毫不逊色于福尔摩斯，他当然会考虑到福尔摩斯中途 是否会下车。两人各自应该采取怎样的对策才更有利于自己？这些问题都 是对策论所要研究的。

运筹学课程09-对策论(胡运权 清华大学)

运筹学课程09-对策论(胡运权 清华大学)
18
设s i是第i个局中人的一个策略，则n个局中人的策略形成的 策略组合s＝(s1，s2,…,sn) 就是一个局势。若记S为全部局势的集合，则 S＝S1×S2×…×Sn
NEUQ
当一个局势s出现后，应该为每一局中人 i规定一个赢得值 (或所失值)Hi(s)。显然，Hi(s)是定义在S上的函数，称为局中 人i的赢得函数。在“齐王赛马”中，局中人集合I＝{1,2}，齐 王和田忌的策略集可分别用 S1 {1 , 2 ,L , 6 }、S2 {1 , 2 ,L , 6 } 表示。这样 , 齐王的任一策略α i 和田忌的任一策略β j 就构成 了—个局势sij，如果α1=(上,中,下)，βl＝(上,中,下)．则在 局势s11下，齐王的赢得为H1(s11)＝3，田忌的赢得为H2(s11)= -3 当局中人、策略集和赢得函数这3个要素确定后，一个对策 模型也就给定了。 19
矩阵对策问题解的假设：
具有鞍点的矩阵对策
例：设有一矩阵博弈G={S1，S2；H}，其中
－6 １ －8 ３ ２ ４ ９ － 1 － 10 －3 ０ ６
26
H=
NEUQ 如果双方部不想冒险、都不存在侥幸心理，而是考虑到 对方必然会设法使自己所得最少这一点，就应该从各自 可能出现的最不利的情形中选择一个最有利的情形作为 决策的依据，这就是所谓“理智行为”，也是对策双方 实际上可以接受并采取的一‘种稳妥的方法。 从各自可能出现的最不利的情形中选择一个最有利的 情形作为决策的依据
6
约翰· 福布斯· 纳什
NEUQ
7
NEUQ
《美丽心灵》是一部关于一个真实天才的极富人 性的剧情片。故事的原型是数学家小约翰-福布斯 -纳什(Nash),普林斯顿大学的著名教授，诺贝尔 经济学奖的获得者(1994年)，他在博弈理论方面 的巨大发现甚至改变了我们的日常生活。但另一 方面，纳什也是一个悲剧人物，他的一生为精神 分裂症所困。在历经苦痛的人生里，纳什一方面 在运用自己那优美绝伦的大脑，另一方面也在与 他的大脑进行着顽强的抗争。最终理性为他带来 了心灵的和平，纳什终于摘取了科学事业上的桂 冠。

运筹学教学-对策论公开课获奖课件百校联赛一等奖课件

运筹学教学-对策论公开课获奖课件百校联赛一等奖课件
局中人称为“i旳对手”，记为-i。
对策中利益一致旳参加者只能看成一种局中人，例：桥牌中 旳东、西两方。 对策论中对局中人旳一种主要假设：每个局中人都是“理智 旳”，即每一种局中人都不存在侥幸心理，不存在利用其他 局中人决策旳失误来扩大本身利益旳行为。
基本概念
在策略型博奕中，一种对策有下列几种基本要素： 一．局中人 二．策略(strategies)：
-1
1
布
1
0
-1
剪刀
-1
1
0
第三节 矩阵对策旳纯策略
例：设有一矩阵对策 G {S1, S2; A} 其中
6 1 8
A
3
2
4
9 1 10
3 0
6
解：对局中人I而言，最大赢得是9，若想得到这个赢得，
他要选择纯策略 ，3因为局中人II也是理智旳竞争 者，他已考虑到局中人I打算出 旳3心理，则准备 以 3对付之，使局中人I不但得不到9，反而失掉10. 局中人I当然也会猜到局中人II旳心理，故而出 4
I {1,2,..., n}
Si ;i 1,2,..., n
局势----状态
n
S Si i 1
支付函数
支付有关局势旳函数----决策根据和原则 H i (s);i 1,2,..., n, s S
模型 I {1,2,..., N }, Si , i I , H i (s), i I
二人：参加对策旳局中人有两个；
有限：局中人旳策略集都为有限集；
零和：在任一局势下，两个局中人旳赢得之和总等于0，即，
一种局中人旳所得值恰好是另一种局中人旳所失值，双方旳 利益是完全对抗旳。
设局中人I和II旳策略集分别为
S1 {1,2 ,...,m } S2 {1, 2 ,..., n}

运筹学对策论全解

运筹学对策论全解

赢 A
B
石头
剪子
布
石头 0 1 -1
剪子 -1 0 1
布
1 -1
0
分析：无确定最优解，可用“混合策略”求解。
4.齐王赛马
战国时期，齐国国王有一天提出要与大将军田忌赛马。 田忌答应后，双方约定： 1)每人从上中下三个等级中各出一匹马，共出三匹； 2) 一共比赛三次，每一次比赛各出一匹马； 3) 每匹被选中的马都得参加比赛，而且只能参加一次； 4) 每次比赛后输者要付给胜者一千金。
例：囚犯困境中，每个囚犯均有2个策略：
{坦白，抵赖}
（3）局势
坦白 抵赖
坦白 抵赖 -9，-9 0，-10 -10，0 -1，-1
当每个局中人从各自策略集合中选择一策略而组 成的策略组成为一个局势，用 (si , d j )来表示。
（4）赢得（支付）
局中人采用某局势时的收益值。
例:当局中人甲选择策略si ，局中人乙选策略 dj 时，局中人甲的赢得值可用 R甲（si , d j )表示。
九十年代以来博弈理论在金融、管理和经济领域中 得到广泛应用
• 九十年代以来对策理论在金融、管理和经济领域 中得到广泛应用
• 博弈论和诺贝尔经济奖
1994：非合作博弈：纳什(Nash)、泽尔腾（Selten） 、海萨尼 （Harsanyi） 1996：不对称信息激励理论：莫里斯（Mirrlees）和维克瑞（Vickrey） 2001：不完全信息市场博弈：阿克罗夫（Akerlof）（商品市场）、斯潘 塞（Spence）（教育市场）、斯蒂格里兹（Stiglitze）（保险市场） 2005: 授予罗伯特·奥曼与托马斯·谢林，以表彰他们通过博弈理论的分析 增强世人对合作与冲突的理解。 2007年，授予赫维茨（Leonid Hurwicz）、马斯金(Eric S. Maskin）以及 迈尔森(Roger B. Myerson）。三者的研究为机制设计理论奠定了基础。 2012年，授予罗斯（Alvin E. Roth）与沙普利（Lloyd S. Shapley）。他 们创建“稳定分配”的理论，并进行“市场设计”的实践。

运筹学--对策论

运筹学--对策论

max min E(X,Y)= min max E(X,Y)
X S1* Y S2*
Y S2* X S1*
则称这个公共值为对策G在混合意义 下的值，记为V*G，而达到V*G 的混 合局势（X*，Y*）称为对策G在混合 策略意义下的解，而X*和Y*分别称 为局中人I，II的最优混合策略。
定理14-2：矩阵对策 G = S1，S2；A
0 2 3 0
赢得矩阵为 A 2 0 3 0
0
3
0 4
0
3
4
0
14.2 矩阵对策的混合策略
定义:对给定的矩阵对策
G = Ⅰ，Ⅱ；S1,S2;A
其中 S1= 1, 2…m
S2= 1 , 2… n
A=(aij)mn
把纯策略集合对应的概率向量
X=(x1, x2 … xm) 其中 xi 0 xi=1 和 Y=(y1 , y2 … yn ) 其中 yj 0 yj=1
分别称为局中人I和局中人II的混合策略。
如果局中人I选取的策略为
X=(x1, x2 … xm) 局中人II选取的策略为
Y=(y1 , y2 … yn )，则期望值 E（X，Y）= xi aij yj=XAYT 称为局中人I期望赢得，而局势（X，Y） 称为“混合局势”，局中人I，II的混合 策略集合记为S1*， S2*。
S1= 1、 2…… m
同样，局中人II有n个策略：1、 2。。。 n ；用S2表示这些策略的集合： S2= 1、 2… n 局中人I的赢得矩阵是：
a11 a12 …… a1n a21 a22 …… a2n A= …… …… …… a m1 a m2 … a mn
局中人II的赢得矩阵是 -A 把一个对策记为G： G= S1，S2；A

运筹学-第六讲对策论

运筹学-第六讲对策论
对策G常写成： G={S1，…，Sn；h1，…hn}
【定义 】 在对策G={S1，S2…，Sn；h1，h2…hn}中，假如由各个对策方旳各 选用一种策略构成旳某个策略组合(S1*，S2*…，Sn*)中，任一对策方i 旳策略 Si*，都是对其他策略方策略旳组合 (S1*，…，S*i-1，S*i+1…，Sn*)旳最佳策略， 即h i(S1*, … , S*i-1, Si*, S*i+1,…Sn*)≥hi(S1*, …, S*i-1, Sij, S*i+1 , …, Sn*)对任意 Sij∈Si 都成立，则称(S1*，…，Sn*)为G旳一种纯策略意义下旳“纳什均 衡”(Nash Equilibrium)．
(2,0)
(4,0)
反应函数法
对策论 game theory
【例4】 考虑上述模型旳另一种情况即各厂商所选择旳是价格而不是产量，假 设产量与价格旳函数关系为：
q1 ( p2 ) a1 b1 p1 d1 p2
q2 ( p1 ) a2 b2 p2 d 2 p1
其他条件不变，边际成本为C1、C2，试求解其纳什均衡。
P2
R2 ( p1 )
1 2b2
(a2
b2 c2
d 2 p1 )
p1*
p2*
1 2b1 1 2b2
(a1b1c1ຫໍສະໝຸດ d1p* 2
)
(a2 b2c2 d 2 p1* )
P1*
d1 4b1b2 d1d 2
(a2
b2c2 )
2b2 4b1b2 d1d 2
(a1
b1c1 )
P2*
d2 4b1b2 d1d 2
Nash对对策论旳贡献有： (i) 合作对策中旳讨价还价模型，称为Nash讨价还价解； (ii) 非合作对策旳均衡分析。

运筹学教材课件(第九章 对策论)

运筹学教材课件(第九章 对策论)

j
ai* j
a a i* j*
i* j
同理有
因此 max i
aij*
ai* j
a a i* j*
ij*
由式（9－6）和式（9－7）得
aij* ai* j* ai* j i=1,2, ,m ;j=1,2, ,n
证得 (i* , j* )是G的纯策略解。
（9－6） （9－7）
9.2.1 最优纯策略和鞍点
4
2*
3
－3
8
1
4
－3
4
0
1
－5
3
－5
max
2*
8
i
2*
5
2
(1, 1), (1, 3), (2, 1), (2, 3) 都是G的鞍点，因而它们也都是最优纯策略
解，对策值VG＝2 ，Ⅰ的最优纯策略解是1,2，Ⅱ的最优纯策略解 是 1, 3。
9.2.1 最优纯策略和鞍点
纯策略解有下述两条性质： （1）无差别性
定义9－4 设G* {X ,Y ; E},是矩阵对策 G {s1, s2; A}的混和扩充， 如果存在混合局势(x*, y*)使得对所有x∈X,y∈Y，有
E(x, y*) E(x*, y*) E(x*, y)
（9－10）
则称(x*, y*)是对策G的混合策略解，简称对策G的解，或称最优
混合局势，简称最优局势。称 x*, y*分别是局中人Ⅰ和Ⅱ的最
ai*
j
又因为
min j
max i
aij
max i
aij*
;
min j
ai*
j
max min
i
j
aij
所以
min j

运筹学—对策论(一)

运筹学—对策论(一)

3﹒赢得函数
局势: 在一局对策中，各局中人所选定的策略形 成的策略组称为一个局势。即若设si是第i个局中人的 一个策略，则n个局中人的策略组s={s1， s2，…， sn} 就是一个局势。
全体局势的集合S可用各局中人策略集的笛卡尔 乘积表示，即S=S1× S2×… × Sn
赢得函数：当局势出现后，对策的结果也就确定 了。也就是说，对任一局势s∈S，局中人i可以得到 一个赢得Hi(s)。
对
二人
动 策无
态
限
对 策
微分对策等
多人
重点
零和
学习
的对
非零和 策。
零和
非零和 零和
非零和
零和
非零和
§2矩阵对策的基本定理 一﹑矩阵对策的数学模型
1﹒二人有限零和对策： 是指有两个参加对策的局中人， 每个局中人都只有有限个策略可供选择，在任一局势 下，两个局中人的赢得之和总等于零。
2﹒矩阵对策：就是二人有限零和对策。 3﹒矩阵对策模型
总之，局中人Ⅰ﹑Ⅱ的最优察纯策略分别为α2 ，β 2。
5﹒矩阵对策的解 定义1 设G={S1 ， S2；A}为矩阵对策，其中
S1={α1,α2, …,αm}，S2={ β 1, β 2, …, β n} ， A=（aij）m×n
若等式
max
i
min
j
aij=minj
max
i
aij
=ai*j*
成立，记VG= ai*j* 。则称VG为对策G的值，称上 述等式成立的纯局势（ α i* , β j* ）为G在纯策略下的 解（或平衡局势）， α i*与β j*分别称为局中人Ⅰ﹑Ⅱ 的最优纯策略。
由于假定对策为零和，所以局中人Ⅱ的赢得矩阵

运筹学-10、对策论

运筹学-10、对策论
第五章
对策论
第一节 引言
一、对策行为与对策论
对策论又称博弈论，是运筹学的一个重要分 支。对策论所研究的主要对象是带有斗争或竞争性 质的现象。由于对策论研究的对象与政治、军事、 工业、农业、交通、运输等领域有密切关系，处理 问题的方法又有着明显的特色，所以越来越受到人 们的重视。
1
在日常生活中，我们经常看到一些相互之间的 竞争、比赛性质的现象，如下棋、打扑克、体育竞 赛等。
所以：min max aij
j i
max min aij (1)
i j
i
j
另一方面，对任意i，j均有：
min aij aij max aij j i max min aij max aij
i j i
j j
max min aij min max aij (2)
i
所以： max min aij
7
例1:设有矩阵对策，局中人Ⅱ的支付矩阵如下：
7 3 A 16 3
1 8 2 4 1 9 0 5
解： α3 → β3 → α4 → β1 → α 3
如果各局中人都不想冒险，必须考虑对方会 选择策略使他得到最差的收入。因此各局中人都 选择理智的决策行为。
对策的值为VG＝ 5。
17
二、矩阵对策的混合策略
矩阵对策G有鞍点时，就存在最优解(最优纯策 略)，但是否一切矩阵对策问题中，各局中人都有 上述意义的最优纯策略呢?答案是否定的。
1 1 0 A 1 0 1 例1：石头、剪刀、布 1 1 0
max min aij 1 min max aij 1
i j j i
不存在上述纯策略意义下的解。

《运筹学教程》胡云权 第五版 运筹学--6对策论--矩阵对策

《运筹学教程》胡云权 第五版 运筹学--6对策论--矩阵对策

13
矩阵对策的纯策略
4、矩阵对策的鞍点与解 多鞍点与无鞍点对策 例: 设有一矩阵对策如下，求它的解。
6 5 6 5
A 1 4 2 1 8 5 7 5
0 2 6
2
局势（α1, β2），（α1, β4），（α3, 均构成鞍点，此对策有多个解。
β2）（α3,
β4） 14
矩阵对策的纯策略
5、矩阵对策纯策略的性质
作业
P385 习题 • 12.2 • 12.3 • 12.4
16
矩阵对策的混合策略
1、混合策略
对于 G {S1, S2; A}
局中人Ⅰ有把握的赢得至少为 v1
max i
min j
aij
局中人Ⅱ有把握的支付至多为 v2
min max
j
i
aij
一般为 v1 v2 ，特别地当 v1 v2 时，则称对策 G 在
yS
* 2
xS1*
20
矩阵对策的混合策略
5、最优混合策略
定义 4：设 G* {S1*, S2*; E} 是矩阵对策 G {S1, S2; A}的混合扩充。
如果
maxmin E(x,
xS1* yS2*
y)
m in m ax E ( x,
yS2* xS1*
y)
，其值为 VG
，则称
VG 为
对策 G* 的值，相应的混合局势 (x*, y*) 称为在混合策略意义下的
44
22
23
对策的值（局中人
I
的赢得期望值）VG
9 2
。
矩阵对策的解法
24
图解法
仅适用于赢得矩阵为2×n或m×2阶的矩阵对策问题。

第8章：对策论《运筹学》

第8章：对策论《运筹学》

S2 {1, 2 , 3}
4 2 6
A
4
3
5
8 1 10
3 0
6
试求出双方的最优纯策略和对策值。
S1 {，1,2 ,3,4}
1 2 3
1 4 2 6
2
4
3
5
3 8 1 10
4 3 0
6
解：由 A 可以看出，局中人甲的最大赢得是8，要想得到这 个赢得，他就得选择纯策略α3 。
3
0
6
-3
836
定义1：设G={S1,S2;A}为矩阵对策，其中双方的策略集和赢
得矩阵分别为 S1 {1,2、, ,m} S2 、{1, 2, 。,若n有} 等A式 {：aij}mn
mai x[mjin(aij )] mjin[mai x(aij )] ai j
成立，则称 ai为 j 对策G的值，局势（ i） , 为j对策G的解或平
意义上的解；
x* 和 y* 分别称为局中人甲和乙的最优混合策略；
VG 为矩阵对策G={S1,S2;A}或G’={X,Y;E}的值。
定理2： 局势(x*,y*)是矩阵对策G={S1,S2;A}在混合策略意义 上解的充分必要条件是对于一切 x∈X、y∈Y均存在：
E(x, y) E(x, y) E(x, y)
第二节 矩阵对策的基本理论
有限二人零和对策，即参加对策的局中人只有两个，而每个局
中人都有有限个可供选择的策略。而且在任一局势中，两个局中
人的得失之和总等于零（一个局中人的所得即为另一个局中人的
所失）。局中人的利益是冲突的，也称为对抗对策。
一、矩阵对策的数学模型
用甲、乙表示两个局中人，假设甲有 m 个策略，表示为:

运筹学第八章对策论

运筹学第八章对策论
上述两个案例均为矩阵对策。
一般地，用 和 分别表示两个局中人，并设局中人 和 的策略集分别为 S, S， 局中人 的收益矩阵为A, 则矩
阵对策的模型记为 S,S.;A
如案例2中，双方策略集同为{（上,中,下）,（上,下中）,
（中,上,下）,（中,下,上）, （下,中,上,（下,上,中）},为了
区别，相应地记为 S {1 和, 2, 3 , 4 , 5 , 6 ，}则局中人 ，
即齐S 王 的{赢1 ,得2 ,矩3 ,阵4 为, 5 , 6 }
1 2 3 4 5 6
1 3 1 1 1 1 1
2
1
3
1
1
1
1
A 3 4
1 1
1
1
3 1
1 3
1 1
1
1
5
1
1 1 1
3
1
6 1 1 1 1 1 3
纯策略矩阵对策
定义1：设 S,S;A 为矩阵对策，其中
赢得矩阵（支付）：当每个局中人在确定了所采 取的策略后，他们就会获得相应的收益或损失， 此收益或损失的值称为赢得（支付）。赢得与策 略之间的对应关系称为赢得（支付）函数。
矩阵对策的模型
矩阵对策即二人有限零和对策。 “二人”是指参加对策的局中人有两个； “有限”是指每个局中人的策略集均为 有限集；“零和”是指在任一局势下， 两个局中人的赢得之和总等于零，即一 个局中人的所得值恰好等于另一局中人 的所失值，双方的利益是完全对抗的。
定理 1 矩阵对策在纯策略意义下有解的充要条件是
aij* ai*j* ai*j 。
证：充分性: 由 aij* ai*j* ai*j可以得到 m i aaij*xai*j* m j a iin *j 。

管理运筹学11对策论

管理运筹学11对策论

A= 4 3 5
3
8 -1 -10 -10
-3 0 6 -3
Max 3
局中人甲应选择2 ，此时不管局中人乙采取什么策略，甲的
赢得均不小于3。
2024/3/29
2. 矩阵对策解的问题
设矩阵对策G={S1，S2，A}，其中：
S1 ={1，2，3，4}， S2 = {1 ，2 ， 3}
Min
-4 2 -6 -6
对策矩阵G={S1，S2，A}在混合策略意义下有 解的充分必要条件是存在着
x * S1* ， y * S2*使（x *，y *） 为E (x,y) 的 一个鞍点，即对于一切x S1* ， y S2* 有
E (x,y *) E (x *,y *) E (x *,y)
2024/3/29
3. 矩阵对策的混合策略
A= 4 3 5
3
8 -1 -10 -10
-3 0 6 -3
Max 3
Max
8 36
Min 3
局中人甲应选择2 ，乙应采取2策略；结果甲赢得3，乙付
出3。
2024/3/29
2. 矩阵对策解的问题
定义1：设矩阵对策G={S1，S2，A}，其中：
S1 ={1，2，…，m}， S2 = {1 ，2 ， …， n}
6 5 7 5 5 0 1 -1 2 -1
Max 7 5 9 5
Min = 5
i = 1, 3 ，j = 2, 4，ai*j* = 5，四个局势均为矩 阵对策的解。
2024/3/29
3. 矩阵对策的混合策略
对矩阵对策G={S1，S2，A}来说，局中人甲 有把握的最小赢得是：
v1 = max min aij
x S1* y S2*
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
即指每个局中人在对策中可以选择采用的行动 方案，但这个方案必须是一个完整的行动，而不是 行动的某一步。每个局中人均有可供选择的多种策 略。
基本概念
在策略型博奕中，一个对策有以下几种基本要素：
一．局中人 二．策略 三．支付或收益(payoffs):
是指一局博奕的得失。或者说是局中人从各种策 略组合中获得的效用，它是策略组合的函数。如果 局中人得失的总和为零，则称这种对策为零和对策 （博弈）；否则，称为非零和对策(博奕)。
则I的赢得矩阵为
a11 a12 a1n
A
a21
a22
a2n
am1 am2
amn
例：甲、乙各出示一枚硬币，在不让对方看见的情况 下，将硬币放在桌子上，若两个硬币都呈正面或都 呈反面则甲得1分，乙付出1分；若两个硬币一个呈 正面另一个呈反面则乙得1分，甲付出1分
局中人：甲、乙
策略： Si {正 面， 反 面}; i 1,2,
I {1,2,...,n}
Si ;i 1,2,..., n
局势----状态
n
S Si i 1
支付函数
支付关于局势的函数----决策依据和标准 H i (s); i 1,2,..., n, s S
模型 I {1,2,..., N }, Si , i I , H i (s), i I
局势： S {（正，反）（正，正）（反，正）（反，反）}
支 付 函 数 ： H1 (正，反）=-1 ， H1 (正，正）=1 ， H1 (反，正）=-1 ，
H1 (反，反）=1； H 2 (反，正）=1， H 2 (正，正）=-1， H 2 (反，正）=1，
H 2 (反，反）=-1。
甲的赢得矩阵为
运筹学课件
运
决
幄
里
之
之
中
Game Theory
外
第一节 对策论的基本概念和分类
发展简史
• 博奕论( Game Theory)也就是运筹学中的对策论。 • 对策思想最早产生于我国古代。 • 早在两千多年前的春秋时期，孙武在《孙子兵法》
中论述的军事思想和治国策略，就蕴育了丰富和深 刻的对策论思想。孙武的后代孙膑，为田忌谋划， 巧胜齐王，这个著名的“田忌赛马”，就是典型的 对策思想的成功运用。
二人：参加对策的局中人有两个；
有限：局中人的策略集都为有限集；
零和：在任一局势下，两个局中人的赢得之和总等于0，即，
一个局中人的所得值恰好是另一个局中人的所失值，双方的 利益是完全对抗的。
设局中人I和II的策略集分别为
S1 {1,2,..., m } S2 {1, 2 ,..., n}
对任一纯局势(i , j ) ，记局中人I的赢得值为 aij
局势：一个对策中，每一个局中人所出策略形成的 策略组称为一个局势。
设si是第i个局中人的一个策略，则n个局中人的策略 形成的策略组s={s1,s2,…,sn},就是一个局势。 全部局势的集合S记为：
S S1 S2 ... Sn
模型
局中人 两个或两个以上---决策者
策略集合 策略----决策
分类
• 局中人
两人对策、多人对策
• 策略
有限对策、无限对策；非合作对策、合作对策
• 支付
零和对策、非零和对策
• 时间
单阶段对策、多阶段对策
对策模型众多，但占有重要地位的是二人有限零和 对策（矩阵对策）。它是一类最简单的对策模型， 它的结果也是研究其他对策模型的基础。
第二节 二人有限零和对策模型
二人有限零和对策
1
布
1
0
-1
剪刀
-1
1
0
第三节 矩阵对策的纯策略
例：设有一矩阵对策 G {S1, S2; A} 其中
6 1 8
A
3
2
4
9 1 10
3
0
6
解：对局中人I而言，最大赢得是9，若想得到这个赢得，
他要选择纯策略 ， 3由于局中人II也是理智的竞争 者，他已考虑到局中人I打算出 的 心3 理，则准备 以 3对付之，使局中人I不但得不到9，反而失掉10. 局中人I当然也会猜到局中人II的心理，故而出 4
1912年E.Zermelo “关于集合论在象棋对策中的应用” 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想
• 产生标志
作为一门学科的创立，则是以美国数学家冯.诺依曼 (John Von Neumann)和经济学家奥斯卡.摩根斯坦 (Oskar Morgenstern)合著的《博奕论与经济行为》 (The Game Theory and Economic Behavior) (1944) 一书出版为标志，他们奠定和形成了这门学科的理 论与方法论基础。
来对付，使局中人II得不到10，反而失掉6，……
1
1
1
1 1 3 1 1 1
A 1 1
1
3
1
1
1 1 1 1 3 1
1 1 1 1 1 3
例：甲乙两人玩猜拳游戏，游戏中双方同时分别出石 头、布或剪刀。规则是剪刀赢布，布赢石头，石头 赢剪刀，赢者得一分。若出的相同，算和局都不得 分。试列出甲的赢得矩阵。
乙
石头
布
剪刀
甲
石头
0
-1
局中人称为“i的对手”，记为-i。
对策中利益一致的参加者只能看成一个局中人，例：桥牌中 的东、西两方。 对策论中对局中人的一个重要假设：每个局中人都是“理智 的”，即每一个局中人都不存在侥幸心理，不存在利用其他 局中人决策的失误来扩大自身利益的行为。
基本概念
在策略型博奕中，一个对策有以下几种基本要素： 一．局中人 二．策略(strategies)：
• 发展成熟
• Nash均衡、经济博奕论、信息不对称对策和广义 对策
基本概念
在策略型博奕中，一个对策有以下几种基本要素：
一．局中人(players)：
即博奕的参与者，他们是博奕的决策主体。根据自己的利益 要求决定自己的决策，记第i个局中人为i，局中人集合为 {1,2,…,I}，即共有I个局中人。我们将某个局中人以外的其它
A
1 1
1
1
例（齐王与田忌赛马）
这个问题中齐王和田忌各自拥有的策略为：
S1={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)} S2={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)} 则对应的齐王的赢得矩阵为
3 1 1 1 1 1
1
3
1