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

对策论_运筹学

  • 格式：doc
  • 大小：278.00 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

运筹学-第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

运筹学_对策论

运筹学_对策论
第17页
混合策略
• 混合扩充
矩阵对策扩充 N人有限对策
• 混合平衡解
矩阵对策 N人有限对策
• 均衡解的存在性
第18页
混 合 扩 充—矩阵对策
策略集
m
S * 1
{X
( x1 , x2 ,..., xm )
xi 1, xi 0, i 1,2,..., m}
i 1
nS* 2{Y( y1 ,y2 ,...,
yn )
y j 1, y j 0, j 1,2,..., n}
j 1
支付函数
mn
E( X ,Y )
aij xi y j
i1 j1
混合扩充： *
{
S1*
,
S
* 2
,
E
(
x
,
y),
x
S1* ,
y
S
* 2
}
第19页
混 合 扩 充—N人有限对策
N 人有限对策 I {1,2,..., N }, Si , i I , H i (s), i I
• 定理1 N人有限对策的混合扩充存在平衡局势. • 定理2 矩阵对策的混合扩充存在平衡局势.
第23页
矩阵对策的解法
• 问题的简化
优超 算例
• 线性规划方法
基本思想 算例
第24页
优超
给定矩阵对策 {S1 , S2 , A} ， A 是 m n 的矩阵，如果
akj alj , j 1,2,..., n
则称局中人 1 的策略 k 优超于策略 l。如果
aik ail , i 1,2,..., m
则称局中人 2 的策略 k 优超于策略 l。
注：局中人 1 的策略 k 优超于策略 l 则说明对局中人 1

运筹学-第六讲对策论

运筹学-第六讲对策论
S S1 S2 Sn
引言
对策论 game theory
对策的结构和分类

按对策方式非 合合 作作 对对 策策有 完限 全理 理性 性
对策分类按对策人数二人对策二 二人 人非 零零 和和 对对 策策

多人对策
按对策状态动 静态 态对 对策 策不 完 不 完完 全 完 全全 信 全 信信 息 信 息息 动 息 静动 态 静 态态 对 态 对对 策 对 策策 策
Nash对对策论的贡献有： (i) 合作对策中的讨价还价模型，称为Nash讨价还价解； (ii) 非合作对策的均衡分析。
(6) 目前，博弈论在定价、招投标、谈判、拍卖、委托—代理以及很多的经营 决策中得到应用，它已成为现代经济学的重要基础。现代对策论总体上是一门 新兴的发展中的学科。
对策论 game theory
数服从(0-1)分布．
【定义】 如果一个策略G={S1, …, Sn; h1, … , hn}中，参予者i 的策略集为
Si={Si1, … , Sik}，如果由各个对策方的策略组成策略集合G*={S1*, S2*, …, Sn*}，
其中
Si*

xi

E mi
| xi
0,i 1,2,, mi ,
纳什均衡
Nash Equilibrium
对于对策中的每一个局中人，真正成功的措施应该是针对于其他局中 人所采取的每次行动，相应地采取有利于自己地反应策略，于是每一 个局中人应采取的必定是他对其他局中人策略的预测的最佳反应。
纳什均衡
对策论 game theory
纳什均衡定义
用G 表示一个对策，若一个对策中有 n 个局中人，则每个局中人可选策略的 集合称为策略集，分别用 S1，S2，…，Sn 表示；Sij 表示局中人i 的第 j 个策 略，其中 j 可取有限个值(有限策略对策)，也可取无限个值(无限策略对策)； 对策方 i 的得益则用 hi 表示；hi 是各对策方策略的多元函数，n个局中人的

运筹学-对策论

运筹学-对策论

3.矩阵对策的混合策略
例：设一个赢得矩阵如下:
5 A = 8 max 8 6 9 6 min
j
9
min 5 max
i
6 策略α2
8 策略β1
• 思路：对甲（乙）给出一个选取不同策 略的概率分布，以使甲（乙）在各种情 况下的平均赢得（损失）最多（最少）。 -----即混合策略
重要定理
定理 任一矩阵对策G {S1,S2;A}， 任一矩阵对策G＝{S1,S2;A}，一定存在混 合策略意义下的解。 合策略意义下的解。 • 定理 设有两个矩阵对策 • G1＝ G2＝ G1＝{S1,S2;A1} G2＝{S1,S2;A2} • 其中A1＝(aij)，A2＝(aij+L)，L为任一常数。 A1＝ 其中A1 (aij)，A2＝(aij+L)， 为任一常数。 则 • (1)G1 G2同解 G1与 同解； (1)G1与G2同解； • (2)VG2 VG2＝ (2)VG2＝VG1+L
7.4 矩阵对策的解法
• (1) 2×2矩阵对策的线性方程组法 2× • 所谓2 所谓2×2矩阵对策是指局中人Ⅰ的赢得矩阵为2×2阶的，即 矩阵对策是指局中人Ⅰ的赢得矩阵为2 是指局中人 阶的， A = a11 a12 • a21 a22 • 如果此对策有纯策略意义下的解，则很容易求解； 如果此对策有纯策略意义下的解，则很容易求解；如果没有 纯策略意义下的解， 纯策略意义下的解，则为求出各局中人的最优混合策略可求解下 列方程组： 列方程组： • a11x1＋a21x2＝ a11y1＋a12y2＝ a11x1＋a21x2＝v a11y1＋a12y2＝v • a12x1＋a22x2＝ a21y1＋a22y2＝ a12x1＋a22x2＝v a21y1＋a22y2＝v • y1＋y2＝ x1＋x2＝ y1＋y2＝1 x1＋x2＝1 • 当没有纯策略意义下的解时，方程组一定有严格非负解 x*= 当没有纯策略意义下的解时， x1* x2* y*=（y1*，y2*）， （x1*，x2*）和y*=（y1*，y2*）， 即为各局中人的最优混合策 略。

运筹学对策论全解

运筹学对策论全解

赢 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) 非合作对策旳均衡分析。

运筹学—对策论(一)

运筹学—对策论(一)

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
不存在上述纯策略意义下的解。

第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 个策略，表示为:

运筹学12-1对策论

运筹学12-1对策论
第十二章 对策论
对策：具有对抗性质的问题。 对策：具有对抗性质的问题。在竞争中寻找有利 于自己的策略。 于自己的策略。 对策论：竞争中的决策论。 对策论：竞争中的决策论。
前一页
后一页
退出
§12.1 对策论的基本Байду номын сангаас念
一、引例
1) 猜硬币：甲、乙各出示一枚硬币，如果两个 猜硬币： 乙各出示一枚硬币， 硬币都呈正面或者反面，甲得1分 硬币都呈正面或者反面，甲得 分，同时乙损 失1分，反之，甲损失 分，乙得 分。 分 反之，甲损失1分 乙得1分
前一页 前一页 后一页 退出 退 出
1 2 111 解之， 解之，得到 X = ( ,0, ),Y = ( , , ) 7 7 777 3 3 3 ∑ xi = ∑ y j = 7 i =1 j =1 1 7 V= 3 = 则原矩阵对策的值， 则原矩阵对策的值， 3 最优混合策略为： 最优混合策略为： ∑ xi
前一页
后一页
退出
§12.1 对策论的基本概念
二、基本要素： 基本要素： 1.局中人：参与对抗的各方； 局中人： 局中人 2.策略集：局中人选择对付其它局中人的行动方 策略集： 策略集
案称为策略。 某局中人的所有可能策略全体称为策略集；
3.收益函数：当每一个局中人都选定了一个策略 收益函数： 收益函数
后一页
退出 退 出
i j j i
成立的充分必要条件是：存在局势(i )， 成立的充分必要条件是：存在局势(i*,j*)，使得
aij* ≤ ai * j* ≤ ai * j ( i = 1,...m , j = 1,...n)
前一页 前一页
后一页
退出 退 出
A} 定义9.1 对于矩阵对策 Γ = { S1 , S 2 ,，如果存在 定义 局势(i 局势 *,j*)，使得 ， aij* ≤ ai * j* ≤ ai * j ( i = 1,...m , j = 1,...n)

运筹学第八章对策论

运筹学第八章对策论
上述两个案例均为矩阵对策。
一般地，用 和 分别表示两个局中人，并设局中人 和 的策略集分别为 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*

第十二章-对策论(运筹学讲义)课件

第十二章-对策论(运筹学讲义)课件

局中人2 出1指
5 －5
出2指 －5 5
局中人1从局中人2该如何选择策略，已获得利益？
-
3
例2 囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在 不同的屋子里审讯。警察告诉他们: 如果两人都坦白，各 判刑8年；如果两人都抵赖，由于证据不充分，两人将各 判刑2年；如果其中一人坦白，，另一人抵赖，则坦白者 立即释放，抵赖者判刑10年。在这个例子中两人嫌疑犯 都有两种策略: 坦白或抵赖。可以用一个矩阵表示两个嫌 疑犯的策略的损益
3.一局势对策的益损值: 局中人各自使用一个对策就形成了一 个局势，一个局势决定了各局中人的对策结果（量化）称 为该局势对策的益损值。
赢得函数(payoff function): 定义在局势上，取值为相应益 损值的函数
4. 纳什均衡: 纳什均衡指所有局中人最优策略组成的一种局势，
既在给定其他局中人策略的情况下，没有任何局中人有积
A
1
4
3
2
解因
m i a x m j in a ij 2 , m j in m i a x a ij 3
m a ixm jina ij m jinm a ixa ij
不符合鞍点条件, 故G的鞍点不存在。
例6 求解矩阵对策，其中: 解 容易得到
A 11
0 1
1 1
v a i * j * 1i * 1 ,2 ;j * 3
A
a
2
1
a22
a1m
a2
m
a
m
1
am2
amn
aij为局中人甲在局势
( i , j )下的赢得 -
9
“齐王赛马”是一个矩阵策略。
其中: 齐王的策略集: S1={ 1, 2, 3, 4, 5, 6 }，

运筹学：chap12_对策论 (简)

运筹学：chap12_对策论 (简)

上策与上策均衡
上策：无论其它局中人如何选择都使自己利益 极大化的策略。
上策均衡：对策的各局中人都有一个上策，各 自选择自己的上策就达到了均衡状态。
囚犯困境
两个嫌疑犯涉嫌一大案被警官拘留，并被分别进行审讯。 根据法律，如果两人均认罪，则每人将各判刑7年；如 果两人均不认罪，根据已掌握的证据，则每人将各判刑 1年；如果只有一人认罪，则认罪者将被宽大释放，不 认罪者则将判刑9年。
S S1 S2 Sn
赢得函数（支付函数）
对于任意一个局势s，应该为每一个局中人i规定一个赢得值
Hi (s) ,称为局中人i的赢得函数。
个人的赢得函数不仅依赖于自己的选择，而且依赖于他 人的选择；
个体的最优选择是他人选择的函数。
对策现象举例---田忌赛马
战国时期，齐王提出要与田忌赛马，双方约定： 1. 从各自的上、中、下三个等级的马中各选一匹
囚犯A
认罪 不认罪
囚犯B
认罪 -7,-7 -9,0
不认罪 0,-9 -1,-1
囚犯困境决策树
认罪 认罪
0,-9
认罪
-9,0
不认罪
-1,-1
囚犯困境引发的思考
➢经济学的经典理论：个体利益的极大化必 然导致整体利益的提高，个体理性与整体理 性是一致的。
➢囚犯困境的上策均衡：个体的最优选择带 来了总体最不利的结局，个体理性与整体理 性发生了冲突。
i
j
aij
min j
max i
aij
，存在最优纯策略。
若
max i
min j
aij
min j
max i
aij，情况会怎样？
矩阵对策的混合策略示例
3 6 A 5 4
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

习题解答1. 已知矩阵博弈局中人I 的赢得矩阵如下，求最优纯策略及博弈值。

（1） ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡8354667565443494 （2） ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------------21221405126331222210 解: (1) ()8695 35438354667565443494⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡ 所以),(13βα,V=5(2) 2- 3 2- 2 2 2562)2(1)2(214051263312)2(2)2(10----⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------------所以 ),(31βα,),(51βα,),(33βα,),(53βα,V=-22． 甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。

甲国的人员根据不同的组合可组成4个队，乙国的人员可组成3个队，根据以往的比赛记解:62828276128184)2(3715---⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------ 所以),(22βα,V=2 答: 双方应均派第2队出场3. 对任意一个m 行n 列的实数矩阵A=（a ij ）,试证有下式成立ij mi n j ij nj m i a a ≤≤≤≤≤≤≤≤≤1111max min min max证:ijmi n j ij nj m i ijmi ij nj m i ijij nj a a a a j a a n j m i j i ≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤∴≤∀∴≤≤≤≤≤∀11111111max min min max max min max ,min : 1,1,,有有4. 某城区有A 、B 、C 三个居民小区，分别居住着40％，30%，30%的居民，有两个公司甲和乙都计划在区内建造超市，公司甲计划建两个，公司乙计划建一个，每个公司都知道，如果在某个小区内设有两个超市，那么这两个超市将平分该区的消费，如果在某个小区只有一个超市，则该超市将独揽这个小区的消费。

如果在一个小区没有超市，则该小区的消费将平分给三个超市。

每个公司都想使自己的营业额尽可能地多．试把这个问题表示成一个矩阵博弈，写出公司甲的赢得矩阵，井求两个公司的最优策略以及各占有多大的市场份额。

解: 甲公司的策略集为{(A,B), (A,C), (B,C)}乙公司的策略集为{A,B,C}甲的赢得矩阵为: 75.075.07.06.07.07.0717.0717.06.075.07.0)7.0(7.075.0)7.0(),(),(),(⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡C B C A B A CB A 所以甲选(A,B)或(A,C),占70%份额。

乙选A,占30%份额.5． 一个病人的症状说明他可能患a ，b ，c 三种病中的一种，有两种药C ，D 可解: 8.04.07.01.04.08.01.07.06.0)4.0(5.0⎥⎦⎤⎢⎣⎡ 最优策略为),(21βα答:应开C 药较为稳妥.6．设矩阵博弈局中人I 的赢得为A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--203233(1) 当局中人I 采用策略x=(0.2，0.5，0.3)时，Ⅱ应采用什么策略? (2) 当局中人Ⅱ采用策略y=(5/7，2/7)时，I 应采用什么策略?(2) x 和y 是否是最优策略?为什么?若是，试给出另一个局中人的最优策略和博弈值。

解: (1)设II 的策略为Y=(y 1,y 2),则3.023.0)3(5.033.04.003.025.0)3(2.0-=⨯+-⨯+⨯=⨯+⨯+-⨯1y y s.t.0.3y -0.4y min 2121=+得:y 1=0,y 2=1,V 1=-0.3,所以最优解为(0,1),V=-0.3 (2) 设II 的策略为X=(x 1,x 2,x 3),则74275074)3(7227579372)3(75=⨯+=-⨯+⨯-=⨯+-⨯ 1x s.t.x 74x 74x 79- max 321321=++++x x 所以13211],1,0[,0x x x x -=∈=,即I 的最优策略为7/4],1,0[),1,,0(=∈-V ααα (3) 对于(x 1,x 2,x 3)=(0.2,0.5,0.3),因为∑∑==-=≠==≠31231133),1,0(*,0i j j i j j i y a y a Y x 但所以(0.2,0.5,0.3)不是最优解.对于(y 1,y 2)=(5/7,2/7),因为)1,,0(*,0αα-=≠X y i 满足:72,52252)1(2)3()3(02)1(02)3(0=-=-=-⨯+⨯-+⨯=-⨯+⨯+-⨯ααααααααα得令 所以(5/7,2/7)是II 的最优解,对应I 的最优策略为(0,2/7,5/7),V=4/77.给定矩阵博弈局中人I 的赢得为A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-113331135试验证x*=(1/2，1/2，0)和y*=(1/4，0，3/4)分别是局中人I 和Ⅱ的最优混合策略，井求博弈值。

解:可验证满足:(1)若;,01**V ya x nj jij i=≠∑=则(2)若V x a y mi i ij j=≠∑=1**,0则(3)若;0,*1*=<∑=i nj j ij x V ya 则(4)若0,*1*=>∑=j mi i ij y V xa 则且V=28. 已知矩阵博弈的赢得矩阵如下，试用线性方程组法求最优混合策略及博弈值。

（1） ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡2282102622 （2） ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡021102210 解: (1)将矩阵中各元素减2得:A- 2=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡006080400 ⎪⎪⎩⎪⎪⎨⎧=++===1486321123x x x v x vx vx ⎪⎪⎩⎪⎪⎨⎧=++===1684321123y y y v y v y v y 解得: X *=(6/13,3/13,4/13),Y *=(4/13,3/13,6/13),V=50/13(2)⎪⎪⎩⎪⎪⎨⎧=++=+=+=+1222321213132x x x v x x vx x vx x ⎪⎪⎩⎪⎪⎨⎧=++=+=+=+1222321213132y y y v y y v y y v y y 解得: X *=(1/3,1/3,1/3),Y *=(1/3,1/3,1/3),V=19．用简便方法（降阶或化零元）求给定矩阵博弈的解与值，赢得矩阵如下（1） ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--0311221020430231 （2） ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0683874768375990559243300解: (1) 用优超法简化矩阵得:⎪⎪⎭⎫ ⎝⎛03204243ααββ ⎪⎩⎪⎨⎧=+==1234224x x v x v x ⎪⎩⎪⎨⎧=+==1234343y y v y v y 解方程组得: X *=(0,3/5,0,2/5),Y *=(0,0,2/5,3/5),V=6/5 (2) 用优超法则简化矩阵得:⎪⎪⎭⎫ ⎝⎛74374354ααββ 各元素减7得: ⎪⎪⎭⎫ ⎝⎛--03404354ααββ 则 ⎪⎩⎪⎨⎧=+=-=-1434334x x v x v x ⎪⎩⎪⎨⎧=+=-=-1435454y y v y vy 解方程组得: 7/3,7/4,7/12,7/3,7/45434==-===y y v x x所以得X *=(0,0,3/7,4/7,0),Y *=(0,0,0,4/7,3/7),V=37/710．用线性规划求下述矩阵博弈的混合策略解及博弈值，已知其赢得矩阵为（1） ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡112103220 （2） ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--622241423 解: (1) 线性规划:x ,x ,x 1x x x v x x 2x v x 2x v 2x 3x s.t.max v3213213213132≥=++≥++≥+≥+y ,y ,y 1y y y v y y 2y v y 3y v 2y 2y s.t.min v3213213213132≥=++≤++≤+≤+解得: X *=(1/3,0,2/3),Y *=(1/3,1/3,1/3),V=4/3(2) 矩阵各元素加2得:A+2=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡844461605 线性规划为:x ,x ,x 1x x x v x 8x 46x v x 46x v 4x x 5x s.t.max v 32132132132321≥=++≥++≥+≥++y ,y ,y 1y y y v y 8y 44y v y 46y v 6y 5y s.t.min v32132132132131≥=++≤++≤++≤+y解得: X *=(0,0,1),Y *=(2/5,3/5,0),V=4-2=211. 甲、乙两方交战。

乙方用三个师守城，有两条公路通入该城，甲方用两个师攻城，可能两个师各走一条公路，也可能从一条公路进攻。

乙方可用三个师防守某一条公路，也可用两个师防守一条公路，用第三个师防守另一条公路．哪方军队在一条公路上数量多，哪方军队就控制住这条公路．如果双方在同一条公路上的数量相同，则乙方控制住公路和甲方攻入城的机会各半，试把这个问题构成一个博弈模型。

并求甲、乙双方的最优策略以及甲方攻入城的可能性。

解: 设两条路为A,B甲方攻城的策略集为:{2A,AB,2B}乙方宁城的策略集为:{3A,2AB,A2B,3B}, 甲方赢得矩阵为:⎪⎪⎪⎭⎫ ⎝⎛=00.51110.50.51110.50A线性方程组为: ⎪⎪⎪⎩⎪⎪⎪⎨⎧=++=+=++=++=+15.05.05.05.03212132132132x x x vx x v x x x vx x x v x x ⎪⎪⎩⎪⎪⎨⎧=+++=++=+++=++15.05.05.05.043213214321432y y y y v y y y v y y y y v y y y 解得:x*=(1/3,1/3,1/3), v=2/3, y*=(1/6,1/3,1/3,1/6)即甲均以1/3的概率取两个师同走第一条路、各走一条路及同走第二条路。

攻入城的机会为2/3。

乙分别以1/6,1/3,1/3,1/6的概率取三个师同守第一条路、两师守第一条路和另一师守第二条路、一师守第一条路和两师守第二条路、以及三个师同守第二条路。

12．设矩阵博弈G l =(S 1,S 2,Ａ)和G 2=(S 1,S 2,B)，其中A=(a ij )m ╳n , B=(b ij )m ╳n 。

如果b ij =k a ij i ＝1,2,…,m j ＝1,2,…,n其中k>0，试证明G l 和G 2具有相同的最优策略且它们的博弈值V 1和V 2之间有关系：V 2= kV 1证: 设G *1=(X,Y ,E 1), G *2=(X,Y ,E 2)为G 1,G 2的混合扩充,则对X 和Y 中任意的x,y,有:y)(x,E min max y)(x,E min max y)(x,E y)(x,E 1y Xx 2y Xx 11111112YYm i n j m i nj j i ij j i ij m i n j j i ij k k y x a k y x ka y x b ∈∈∈∈=======∴====∑∑∑∑∑∑因此(x *,y *)是G 1的最优策略当且仅当(x *,y *)是G 2的最优策略,且V 2=kV 113．甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来．如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，如果两个人都猜对或都猜错，则算平局，都不得分。