期末考试 考试时间：2016年6月21日周二下午2点至3点半 考试地点：3511 考试范围：期中考试之后的内容。

Presentation on theme: "期末考试 考试时间：2016年6月21日周二下午2点至3点半 考试地点：3511 考试范围：期中考试之后的内容。"— Presentation transcript:

1 期末考试 考试时间：2016年6月21日周二下午2点至3点半 考试地点：3511 考试范围：期中考试之后的内容。

2 博 弈 论 game theory 1 引 言 2 纳什均衡 Nash Equilibrium 3 反应函数法
1 引 言 2 纳什均衡 Nash Equilibrium 3 反应函数法 Method of reaction function 4 有限二人零和博弈 Two person finite zero-sum game 5 有限二人非零和博弈 Two person finite non-zero-sum game

3 3 反应函数法 【例12-6】设有3个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为 成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。 【解】各农户的得益函数分别为

4 3 反应函数法 反应函数 因此该博弈的纳什均衡为（18，18，18）

5 4.2 纯策略矩阵博弈 【例12-9】 设有矩阵博弈G={ S1，S2；A }，赢得矩阵为 S1={α1 , α2 , α3 , α4 }
4.2 纯策略矩阵博弈 【例12-9】 设有矩阵博弈G={ S1，S2；A }，赢得矩阵为 S1={α1 , α2 , α3 , α4 } S2={β1 , β2 , β3 ， β4 } 求纳什均衡

6 4.2 纯策略矩阵博弈 A= β1 β2 β3 β4 α1 【解】 α2 α3 α4
4.2 纯策略矩阵博弈 β1 β2 β β4 α1 α2 α3 α4 【解】 A= 纳什均衡为：(α1 ,β2 )， (α1 ,β4 ) ， (α3 ,β2 ) ， (α3 ,β4 ) 博弈值VG=5 局中人Ⅰ的最优纯策略为α1 ，α3 局中人Ⅱ的最优纯策略为β2 ，β4

7 作业 分钱计划： 参与人1 和参与人2 因为如何分配10 美元的问题争执不休。每个参与人都说出了一个自己预期金额 ，该金额在0 到10 之间且允许出现小数。两人需要同时做出选择。参与人的收益就是她分得的钱款。这个博弈有两条规则。  无论按哪条规则来分钱，如果出现S1+S2<=10 的情况，每人获得自己的预期金额，剩余的钱款被销毁。  (a).第一条规则是，如果S1+S2>10 ，那么每个参与人都一无所获并且钱会被销毁。这种情况下的（纯策略）纳什均衡是什么？  (b).第二条规则是，  如果S1+S2>10 ，并且每个人的预期金额是不同的，那么预期金额最小的参与人分得等值的钱款而剩余的钱款归另一个参与人。  如果S1+S2>10 ，并且S1=S2 ，那么每个人  都分得5 美元。这种情况下的（纯策略）纳什均衡是什么？  (c).假如我们为前两条规则增加一个限制条件，即预期金额必须是整数。这是否会改变前两条规则下的（纯策略）纳什均衡？

8 4.3 混合策略矩阵博弈 矩阵博弈满足纯策略纳什均衡是指： 满足局中人Ⅰ有把握的至少赢得是局中人Ⅱ有把握的至多损失，即
当V1≠V2 时，这时不存在纯策略意义下的纳什均衡 。

9 4.3 混合策略矩阵博弈 齐王田忌赛马 利用最小最大和最大最小原则，发现不存在使得 成立的点，即不存在纯策略纳什均衡。

10 4.3 混合策略矩阵博弈 【定义6】设矩阵博弈 ，其中 记 则分别称 为局中人Ⅰ、Ⅱ的混合策略集； 、
【定义6】设矩阵博弈 ，其中 记 则分别称 为局中人Ⅰ、Ⅱ的混合策略集； 、 分别称为局中人Ⅰ、Ⅱ的混合策略， 为一个混合局势。 称为G 的混合扩充。E是局中人Ⅰ的赢得期望值

11 4.3 混合策略矩阵博弈 纯策略与混合策略的关系 纯策略是混合策略的特殊情形。一个混合策略X=(x1, x2, …，xm)可理解为：如果进行多局博弈的话，局中人I分别选取纯策略α1,α2,…，αm的频率；若只进行一次博弈，则反映了局中人I对各纯策略的偏爱程度。

12 4.3 混合策略矩阵博弈 【定义6′】设G*={S1*,S2*,E}是矩阵博弈G={S1,S2,A}的混 合扩充，当
称为局中人Ⅰ的赢得函数，VG 称为G*的值。 【定义6′】设G*={S1*,S2*,E}是矩阵博弈G={S1,S2,A}的混 合扩充，当 时，称 为局中人Ⅰ、Ⅱ在混合策略中的纳什均衡。 【定理2】矩阵博弈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）

13 4.3 混合策略矩阵博弈 【例12-11】 考虑矩阵博弈G={ S1，S2；A }，其中 试求纳什均衡 y1 y2 x1 x2
【解】 纯策略纳什均衡不存在。设x=（x1，x2）为局中人Ⅰ的混合策略，y=(y1，y2)为局中人Ⅱ的混合策略，则： 局中人Ⅰ的赢得期望值：

14 4.3 混合策略矩阵博弈 取 ， ，则 该博弈的纳什均衡为： (x*, y*) 其中 局中人Ⅰ和Ⅱ的最优策略分别为： x*, y* 博弈值

15 4.4 纳什均衡存在定理 【定理3】 设x*∈S1*，y*∈S2*,则（x*，y*）为博弈G的纳什均衡的条件是：对任意i=1,…，m，j=1,…，n，有 E(i , y*)≤E(x*, y*)≤E(x*, j) 【定理4】 设x*∈S1*，y*∈S2*，则（x*，y*）是博弈G的纳什均衡的充要条件是：存在数V，使得x*，y*分别满足： 且V=VG

16 4.4 纳什均衡存在定理 定理4-6说明了矩阵博弈总是有解的，并给出了解所应满足的条件。
【定理5】 对任一矩阵博弈G={S1，S2；A}，一定存在混合策略意义下的纳什均衡。 【定理6】 设（x*，y*）为矩阵博弈G的一个纳什均衡， V=VG，则 （1）若 xi*＞0，则 （2）若 yj* ＞0，则 （3）若 ，则 （4）若 ，则 定理4-6说明了矩阵博弈总是有解的，并给出了解所应满足的条件。

17 4.4 纳什均衡存在定理 例12-11

18 4.4 纳什均衡存在定理 【定理7】 设有两个矩阵博弈 G1={S1，S2；A}, G2={S1，S2；kA} 其中k＞0为一常数。
则G1与G2有相同的解，且： 【补充定理】 G1={S1，S2；A1=(aij)m×n} G2={S1，S2；A2=(aij+d)m×n} d为常数，则G1与G2有相同的解，且：

19 4.5 矩阵博弈求解方法 图解法 【补充例1】用图解法求解 【解】设x=(x1,1-x1)，y=(y1,1-y1) 对于局中人Ⅰ：
4.5 矩阵博弈求解方法 图解法 【补充例1】用图解法求解 【解】设x=(x1,1-x1)，y=(y1,1-y1) 对于局中人Ⅰ： 如果局中Ⅱ人选取 β1 ，则有 V=20-15x1 如果局中Ⅱ人选取 β2 ，则有 V=25x1+10 l1 l2 C B A o x1 v 1 点B(1/4, 65/4)为局中人Ⅰ的极值点

20 4.5 矩阵博弈求解方法 同理 V=35-30y1 V=10+10y1 解得 该矩阵博弈的纳什均衡为：(x*, y*) VG=16.25

21 4.5 矩阵博弈求解方法 【补充例2】某公司有甲、乙两个工厂，每年的税额是400万元和1200万元。对于每个工厂，公司可如实申报税款，或者篡改账目，声称税额为零，而税务局由于人力所限，每年只能检查一个工厂的账目，如果税务局发现工厂偷税，则不但要工厂如数缴纳税款，而且还要缴纳相当于一半税款的罚金。（1）试将该问题表示为一个矩阵博弈模型；（2）求出税务局和公司的最优策略及税务局从公司征收税款（含罚金）。 【解】税务局：S1={查甲工厂，查乙工厂} 公司： S2={甲乙都实报，甲乙都报零，甲实报乙报零，甲报零乙实报}

22 利用定理7及补充定理化简 设 x =(x1, 1-x1) y=(y1, y2, y3, y4) V=6 (1) V=-6x1+7 (2)
l1 l2 l4 l3 C B A o v 1 D 4 9 7 6 设 x =(x1, 1-x1) y=(y1, y2, y3, y4) V= (1) V=-6x (2) V=-9x (3) V=3x (4) 点B(1/3, 5)为局中人Ⅰ的极值点 =5

23 同理可得 V=6y1+y2+7y4 (5) V=6y1+7y2+9y3+4y4 (6)
点B(1/3, 5)不满足方程（1）、（3），由定理6 y1=y3=0 解(5) (6)组成的方程组 该矩阵博弈的纳什均衡为：(x*, y*) 税务局最优策略是以1/3的概率检查甲公司，2/3的概率检查乙公司，这样至少能征收到1400万元的税款

24 4.5 矩阵博弈求解方法 解矩阵博弈的一般步骤 1.A2×n或Am×2，图解法。 2.A2×2，图解法，方程组法 有无纯 策略解 定理7化简
4.5 矩阵博弈求解方法 解矩阵博弈的一般步骤 1.A2×n或Am×2，图解法。 2.A2×2，图解法，方程组法 有无纯 策略解 无 定理7化简

25 习题1 【补充例2】用图解法求解 【解】设x=(x1,1-x1) y=(y1, y2, y3, y4) 则 V=4-2x1 (1)
l1 l2 l4 l3 C B A o x1 v 1 【补充例2】用图解法求解 【解】设x=(x1,1-x1) y=(y1, y2, y3, y4) 则 V=4-2x1 (1) V=2x (2) V=-5x1+6 (3) V=5x (4) 点B(5/7,17/7)为局中人Ⅰ的极值点 V=17/7

26 习题1 同理可得 V=2y1+3y2+y3+5y4 (5) V=4y1+y2+6y3 (6) 将 x1=5/7 代人方程（1）—（4）
解方程组得 该博弈的纳什均衡为 ( x*, y* ) 博弈值为VG=17/7

27 复习 目标规划 目标规划定义：根据条件写出目标规划模型 目标规划求解：图解法

28 复习 动态规划 动态规划原理：写子问题与递推公式 动态规划问题求解： 最短路 投资分配问题 背包问题 机器负荷问题 其他问题

29 复习 图与网络模型 图的定义：有向图、无向图、弧、边、赋权图、简单图、子图、支撑子图，树 图的性质： 图问题求解：
最小支撑子树：加边法，破圈法 单源最短路：Dijkstra算法 最大流问题 最大二分匹配

30 复习 博弈论 博弈类型：零和、非零和、动态、静态、单人、多人 纯策略与混合策略 纳什均衡： 定义：判断博弈策略是否为纳什均衡
求连续策略纳什均衡：反应函数法 求二人零和博弈纯策略纳什均衡：画圈法 求二人零和博弈（混合/纯）策略纳什均衡：图解法