第9讲 策略思考的数学模型 —博弈论模型.

Presentation on theme: "第9讲 策略思考的数学模型 —博弈论模型."— Presentation transcript:

1 第9讲 策略思考的数学模型 —博弈论模型

2 数学建模 数学建模 【本讲简介】 　　　本讲介绍博弈模型，包括博弈论中最基本的一些概念，以及非合作博弈中的Nash平衡和Pareto最优概念，同时，介绍博弈论中的几个著名案例：囚徒困境，智猪博弈，脏脸之谜，以及不完全信息静态博弈模型的贝叶斯纳什均衡的一个应用案例——拍卖模型。 。

3 博弈论（Game Theory） ＊博弈论是在策略性环境下进行思考并作出决策的工具。 —— 日本经济学家梶井厚志
数学建模 博弈论（Game Theory） 　　＊博弈论是在策略性环境下进行思考并作出决策的工具。 ——　日本经济学家梶井厚志 　 ＊ 博弈是策略交往的一种建模方式。 ——　美国经济学家Samuel Bowles ＊ 要在现代社会做一个有文化的人，你必须对博弈论有一个大致的了解。—— 美国经济学家萨缪尔森 数学建模 我们先来看看学者们是如何表述博弈论的。 关键词：策略。学习博弈论，就是学习“策略性思考”，建立起两个意识：对手意识，对策意识。 “策略性思考” 对手意识 对策意识

4 数学建模 数学建模 博弈有５个基本要素： １．局中人（选手）——参与博弈的个人或团体。 ２．策略（对策）——可供局中人选择的行动方案。 ３．赢利（效用）——局中人的收益或支付。 ４．信息——在策略选择中，信息是最关键的因素。 ５．均衡——博弈的最终结果。 上述要素中，局中人、策略、赢利及信息规定了一局博弈的游戏规则。均衡是游戏的最终结局。 中国古代最有名的博弈案例相信大家都听说过：田忌赛马。齐王的马比田忌好，为何齐王败、田忌胜？区别就在于“信息”。

5 n人博弈模型的几个符号约定： 选手集： 策略集： 决策集： 赢利函数： 数学建模 数学建模
每个人的策略集可以不同。“田忌赛马”案例中齐王与田忌各有３！＝６个策略。 局中各方每人出一个策略，放到一起，便构成一个决策。

6 数学建模 数学建模 例如：“田忌赛马” S 齐＝S 田＝｛(上中下), (中下上),(下上中), (上下中), (中上下),(下中上)｝ f 齐((上中下),(下上中)) ＝ ０ f 田((上中下),(下上中)) ＝ １ 双方若随机抽取策略，则齐王有六分之五的获胜概率，田忌只有六分之一。 在博弈问题中，每一方的“最佳策略”都必须依赖对方的“策略”。 这种即互相冲突又互相依赖，“我中有你，你中有我”的问题正是博弈论研究的问题。

7 如果选手 k 知道了其他选手的策略xi , ( i =1,2, …,n, i≠k )，自然希望取策略 xk ∈ Sk 使得：
数学建模 　下面讨论非合作情形下的博弈。 如果选手 k 知道了其他选手的策略xi , ( i =1,2, …,n, i≠k )，自然希望取策略　xk ∈ Sk 　使得： 定义选手 k 的合理反应集为 各选手都希望决策在各自的合理反应集中，故此称 为 n 人非合作对策的一个Nash平衡点。 数学建模 注意，Ｒｋ是选手ｋ的合理反应集，是决策集而不是选手ｋ的策略集，是在别的选手的策略都取定的前提下，对选手ｋ最有利的决策。

8 Nash定理 非零和非合作博弈的Nash平衡点一定存在。
数学建模 数学建模 对于Nash平衡点，在别人不改变对策的情形下，每个选手的对策都是最好的，故他们都不会轻易去改变自己的对策。所以，非合作博弈的解将在 Nash平衡点处出现。 Nash定理 非零和非合作博弈的Nash平衡点一定存在。 如果决策不在Ｎａｓｈ平衡点处，则博弈各方有调整策略的冲动，无法稳定。而一旦到达Ｎａｓｈ平衡点，则各方不会再轻易改变自己的策略，从而达到稳定。 零和指博弈各方的收益之和为０，非零和博弈则可以实现共赢。 Ｎａｓｈ平衡点可能不唯一

9 数学建模 数学建模 ※分钱游戏：两人分100元钱，每人写下自己主张得到的数字x与y，若x+y≤100，则各自得到自己主张的钱数，否则，此100元钱充公。 问题：该游戏的纳什均衡点在哪儿？ 直观结论：（50，50）是纳什均衡解。 一般结论： （x，y）（x+y =100）都是纳什均衡解。 举个简单例子加深对纳什均衡概念的理解。

10 问题： Nash平衡点对博弈各方是否一定是最优的？
数学建模 问题： Nash平衡点对博弈各方是否一定是最优的？ 数学建模 乙方获利 B １ 3 2 5 4 A Ｎａｓｈ平衡点对各方来说都未必是最优的，甚至可能存在这样一种情形：所有各方的利益都可以得到改善，甚至是大幅度的改善。有这样的好事！那为什么不去实现它？这是由于是非合作对策，没有商量的机会，谁也不敢首先改变自己的策略，因为若自己改变了策略，而别人不改变，则利益肯定受损。这就引出了一个有意思的结论。(见图） a,b都是Ｎａｓｈ平衡点。为什么会取ａ而不取ｂ？由于双方都认为自己是当前情形下最好的选择，故都不会先动。如果商量，则是合作情形 再来看另一种情形，假设蓝点是非Ｎａｓｈ平衡点，甲方认为这时对自己不是最优的，因此会改变策略，使对自己最有利。但乙方也不甘心，也改变策略，使对自己最优。甲方再次改变策略。乙方也再次改变策略…，最终到达ａ点，大家都满意了，终于消停了。 这里揭示了一个深刻道理：损人不利己。 甲方获利 Nash平衡点示意图

11 数学建模 数学建模 通过追求自身利益，人们常常会比其实际上想做的那样更有效地促进社会利益。 ——亚当·斯密 纳什均衡理论引出了亚当·斯密的“看不见的手”的市场经济理论的一个悖论：从利己目的出发，结果可能是损人不利己。 亚当．斯密，大经济学家，经典经济学巨著《国富论》的作者。“主观利己，客观利他”。

12 你可以将一只鹦鹉训练成经济学家，因为它只需要学习两个词：供给与需求。
数学建模 数学建模 　　　你可以将一只鹦鹉训练成经济学家，因为它只需要学习两个词：供给与需求。 　　　　　　　　　　　　　　——萨缪尔森 要成为现代经济学家，这只鹦鹉必须再多学一个词，这个词是“纳什均衡”。 　　　　　　　　　　　　　　——坎多瑞 关于“纳什均衡”在经济学上的地位，有这样一种说法。

13 １９５０年，在他那篇仅仅27页的博士论文中提出了后来被称为“纳什均衡”的博弈理论。
数学建模 数学建模 １９５０年，在他那篇仅仅27页的博士论文中提出了后来被称为“纳什均衡”的博弈理论。 1958年起20多年严重精神病折磨。 1994年与人分享诺贝尔经济学奖 。 John F. Nash,

14 数学建模 数学建模 决策 x ∈ D 称为是帕累托（Pareto）最优的是指：D中不存在决策 y 使得 f (y ) > f (x) 。 社会资源如何才能实现最优配置，只有资源配置已经达到这样一种状态，也就是在不使其中一个变得更坏的情况下，另一个也不能变得更好。 ——意大利经济学家帕累托 通俗地说，若博弈中任一方的利益的提升，必然要以某一方的利益受损为代价，则这个决策是帕累托最优的。 说到帕累托，还有一个著名的帕累托法则：８０／２０法则。 Ｎａｓｈ平衡点未必是帕累托最优的。见下图。

15 数学建模 数学建模 乙方获利 B A 好，概念介绍到此，下面我们看一些博弈论中的著名案例。 甲方获利 Nash平衡点示意图

16 囚徒困境—非零和博弈 设两偷盗犯因被发现藏有被盗物品而被拘留。现被分别单独关押。两人都知道，如果都不承认偷盗，将以窝赃罪各判1年监禁；如果都承认，将以偷盗罪各判5年。但如果一人招认而另一人不承认，则坦白者将从宽处理获得释放，而抗拒者从严被判10年。这两个囚犯该如何选择自己的最优策略？

17 两位囚犯的策略集都是{x (招认)， y (不招认)}，赢利函数分别为：
f1 ( x, x ) = -5 , f1 ( x, y ) = 0 f1 ( y, x ) = -10 , f1 ( y, y ) = -1 f2 ( x, x ) = -5 , f2 ( x, y ) = -10 f2 ( y, x ) = 0 , f2 ( y, y ) = -1 各自的合理反应集为： R1 = { ( x, x ) , ( x, y ) } R2 = { ( x, x ) , ( y, x ) } 所以该问题的Nash平衡点只有一个： ( x, x ) 即在非合作条件下，坦白是双方的最好选择。

18 智猪博弈—弱势方的抉择 猪圈里有一头大猪，一头小猪。猪圈的一头有一个食槽，另一头有一个控制猪食供应的按钮。按一次按钮，有10个单位的猪食入槽，但是按按钮要付出两个单位的跑动成本。若大猪先到食槽，则大猪吃到9个单位猪食，小猪吃到1个单位；若两猪同时到达食槽，大猪吃7个单位猪食，小猪吃3个单位；若小猪先到，大猪吃6个单位，小猪吃4个单位。

19 数学建模 数学建模 大、小猪策略集 同为： { 0(不动) , 1(按钮) } 大猪的合理反应集为: { (0,1) , (1,0 ) } 小猪的合理集反应为: { (1,0) , (0,0 ) } 所以最终结果为：大猪按钮，小猪不动。 激励机制需合理制定。 　小猪 　大猪　 1 (5,1) (4,4) (9,-1) (0,0)

20 脏脸之谜—共同知识 三姐妹 从外面回到家里，她们的脸都是脏的，但她们自己并不知道。母亲见到她们后说道：“你们三人中至少有一个人的脸是脏的”，她们没有反应，因为这是一个显然的事实，她们认为母亲说的是一句“废话”。但当母亲追问一句：“你们知道是谁吗？”，她们先是互相看了一下，然后都脸红了，都知道自己的脸是脏的，这是为什么？

21 数学建模 数学建模 推理过程：其中任一人会想：如果我的脸是干净的，那么她们两人都可以从对方的犹豫中知道自己的脸是脏的，但她们没有脸红，说明我的脸也是脏的。 首先，每个人都知道“没有两张干净的脸”这个事实（这是废话！）。 根据别人的犹豫，每个人又知道了这样一个事实：“每个人都知道‘没有两张干净的脸’” （这不是废话！） 通过这个案例，我们还想得到更深刻一些的结论。 为什么一句“废话”会引出正确的结论？其实，“废话”引出了各方的反应，因此引出了新的信息（尽管这个信息没有用语言表达）。

22 共同知识——每个人都知道这个事实，每个人都知道每个人都知道这个事实，每个人都知道每个人都知道每个人都知道这个事实，…
共同知识的直观但并不严格的定义。 “皇帝的新装”是一个解释共同知识的好例子。在小孩没有说话前，每个人都知道“皇帝没有穿衣服”这个事实，但是它还不是共同知识。当小孩喊出“他没有穿衣服”这句话以后，“皇帝没有穿衣服”就由大家都知道的事实变成了共同知识。 最后作个小结。

23 数学建模 不完全信息静态博弈模型 完全信息博弈：每个参与人的特征、收益以及策略空间都是所有参与人的共同知识。 不完全信息博弈：至少上述信息之一不是共同知识 数学建模 在现实中，许多博弈不满足完全信息博弈模型的要求，例如，产品推销员推销产品时，不了解消费者的偏好与支付函数；市场竞争各方不知道对方的成本函数；

24 “市场扩张”博弈模型 企业甲、乙对市场概率分布是已知的，企业甲了解企业乙的收益情况，但企业乙不知道企业甲的生产成本
扩张（K） 保持（B） 市场需求高 （0.2） 扩张 3，2 5，1 保持 0，3 2，1 市场需求低 （0.8） -2，-2 -1，0 0，-1

25 数学建模 数学建模 由于存在不确定因素，这时的纳什均衡解是指在期望收益最大条件下的策略组合，称为贝叶斯纳什均衡解。 以“市场扩张”模型为例。 企业甲的纯策略有： a(K,K), b(K,B), c(B,B), d(B,K) 企业乙由于不知道企业甲的所有信息，从而必须考虑甲采取的策略，故有： w(K/K,B/K), x(K/K,B/B),y(K/B,B/K),z(K/B,B/B) 从而甲乙双方的策略组合共有12种。 甲如果采取纯扩张策略，则aw组合与ax组合的效果是一样的，ay和az也是一样的效果。所以与a的不同组合只有两种。同理，与c的不同组合也只有两种。我们以下来计算以下所有策略组合的期望收益。 （说明：甲的策略是对应市场的两种情况，采用不同的策略；乙的策略是根据甲的策略，采取不同的策略。）

26 此时唯一的贝叶斯纳什均衡点为：b(K,B) x(K/K,B/B)，即甲乙双方都采取“高扩低保”的策略。
数学建模 数学建模 “市场扩张”模型期望收益矩阵 w x y z a -1，-1.2 —— 0.2，0.2 b 0.6，-0.4 2.2，1.2 1，-0.6 2.6，1 c 0，-0.2 2，1 d -1.6，-1 -0.6，0 -1.2，-1.4 -0.4，0.2 此时唯一的贝叶斯纳什均衡点为：b(K,B) x(K/K,B/B)，即甲乙双方都采取“高扩低保”的策略。 在实际操作中乙采取跟随策略在时间上需要滞后。

27 拍卖（召投标）模型 拍卖机制分析 信息经济学 威廉·维克瑞 （William Vickrey，1914-1996) ● 美国经济学家
数学建模 拍卖（召投标）模型 数学建模 拍卖机制分析 信息经济学 威廉·维克瑞 （William Vickrey， ) ● 美国经济学家 ● 在信息经济学方面作出开创性研究 ● 1996年获诺贝尔经济学奖 对拍卖及拍卖机制的分析直接成为信息经济学的发端，

28 拍卖（召投标）模型 数学建模 数学建模 最高价密封拍卖：每个竞买者出个报价，密封后交予拍卖方，所有报价同时解封，出价最高者获得该拍品，按最高报价成交。 次高价密封拍卖：每个竞买者出个报价，密封后交予拍卖方，所有报价同时解封，出价最高者获得该拍品，按次最高报价成交。 次高价成交方案的目的是鼓励竞买者出更高价。 竞拍者的出价是一种策略，这个出价依赖于竞拍人自己对拍品的价值的估计，还依赖于对其他竞拍人的估价的估计。由于其他竞拍人的估价是未知的，所以这是一个不完全信息博弈问题。

29 数学建模 数学建模 最高价成交模型 假设有N个竞拍人，第i个竞拍人的估价为 vi ，出价为bi。 根据竞拍规则，竞拍人的收益函数为： 竞拍人都无法知道其他人的估价，但假设知道它是区间[0,1]上均匀分布的一个随机变量。设竞拍人的出价策略为 其中βi 是严格递增函数。 设每个竞拍人都是理智的，他们希望获得拍品且物有所值。

30 数学建模 先讨论两个局中人的情形。 数学建模 求期望过程中，自己的估价v1不是随机变量，随机性来自于对方的估价不知道。

31 考虑对称情形，假定所有局中人的出价策略相同，记为 则局中人1的优化目标为 极值条件为：
数学建模 数学建模

32 结论：仅有两个竞拍人的情形，此竞拍博弈模型的贝叶斯纳什均衡解是：每个竞拍人的出价是自己估价的一半。
数学建模 数学建模 结论：仅有两个竞拍人的情形，此竞拍博弈模型的贝叶斯纳什均衡解是：每个竞拍人的出价是自己估价的一半。 两条关键假设：1、每人估价是[0,1]内均匀分布随机变量；2、每人出价策略相同，且相互独立。

33 回到N人竞拍情形，假设同前。 极值条件： 数学建模 数学建模
两条关键假设：1、每人估价是[0,1]内均匀分布随机变量；2、每人出价策略相同，且相互独立。

34 结论：最高价成交N人竞拍模型的贝叶斯纳什均衡解为：每个竞拍人按自己估价的(N-1)/N出价。
数学建模 数学建模 结论：最高价成交N人竞拍模型的贝叶斯纳什均衡解为：每个竞拍人按自己估价的(N-1)/N出价。 也就是说：竞拍者越多对拍卖者越有利。

35 次高价成交模型 可以得出结论：此时的贝叶斯纳什均衡解为：各竞拍方按各自的估价出价。 接下来分别计算两种拍卖方案下的成交价期望值。 最高价成交方案中，成交价期望为
数学建模 数学建模

36 数学建模 数学建模 次高价成交方案中，成交价期望为 最高价成交方案的效率更高一些。

37 进一步计算方差可得：

38 二手车市场—逆向选择 二手车市场上，买者往往不能得到车辆质量的完全信息，所以他只愿意按二手车的平均质量支付价格，于是，质量高出平均质量的车辆便会选择退出这个市场， 于是此市场的二手车平均质量降低，又进一步导致价格降低，…。

39 逆向选择：在信息不对称背景下，交易中的卖方往往有意隐瞒某些真实信息，使得买方作出的选择并非最有利于自己，故称为逆向选择。 ——信息不对称！ 劣币驱逐良币！
质 量 价 格

40 数学建模 1964年3月13号凌晨3点， 纽约市民Kitty Genovese在 即将回到住处时，遭到持刀暴 徒的侵犯，她惊恐的尖叫并恳 求帮助。但她的38户邻居，很 多人走到窗户前观望了片刻， 目睹她在歹徒手中挣扎，但直到歹徒离开，才有人打电话 报警。但Genovese却未能得到及时救治很快就死去了。 心理学家的解释——旁观者效应。 为什么围观者会见死不救？ 数学建模 大量的实验和研究显示在公共场所观看危机事件的旁观者越多，愿意提供帮助的人就越少。当旁观者的数目增加时，任何一个旁观者都会更少地认为自己有采取行动的责任。这被称为 旁观者效应 。

41 数学建模 我们来看看这一现象的博弈论解释。 假设1：人类的行为总是倾向于最大化自己的效用。 假设2：有人提供帮助时，围观者每人可以获得固定收益a。 假设3：提供帮助者会有损失b。 假设4：每个旁观者在事件中的地位是相同的。 设共有n人旁观，其中任一人A的收益矩阵为 数学建模 其他人不帮助 其他人有人帮助 A不帮助 a A帮助 a-b

42 假设每个人 不帮助的概率为 p，那么： A不帮助的期望收益 Q1= 0. p n-1 + a
假设每个人 不帮助的概率为 p，那么： A不帮助的期望收益 Q1= 0 * p n-1 + a * (1- p n-1 ) A帮助的期望收益 Q2 =（a-b）* p n-1 +（a-b）* (1- p n-1 ) 则A总的期望收益 Q（p）= p * Q1 +（1-p） * Q2 = a - b –apn + bp 令dQ(p)/dp = 0,解得 p = （b/(na)） 1/(n-1) 容易验证，不帮助的概率p关于围观人数n是递增的。 数学建模 数学建模

43 数学建模 数学建模 结论： 1、围观者越多，围观者施以援手的愿望越低； 2、和谐社会，需要增加 a 值，比如给予助人为乐者金 钱上或者精神上的奖励。 3、和谐社会，需要降低 b 值，营造一个信任度高的社会环境。而诸如钓鱼执法，南京老太这样的事件，却大大提高了 b 值，使社会成本大大增加。 本案例取材于果壳网。

44 思考题：如果旁观者的收益矩阵改变如下，有 何结论?
其他人不帮助 其他人有人帮助 A不帮助 a A帮助 a-b a-b/2

45 了解博弈论的基本思想，加强思维中的“对手意识”与“对策意识”，对增强决策力是很有益处的。
　 本讲小结： 　　　了解博弈论的基本思想，加强思维中的“对手意识”与“对策意识”，对增强决策力是很有益处的。

46 作业： 9. 1. 在最高价成交模型中，若各竞拍方的估价是独立的两点分布随机变量，且分布参数已知，则此时的贝叶斯纳什均衡解如何？ 9. 2
作业： 9.1.在最高价成交模型中，若各竞拍方的估价是独立的两点分布随机变量，且分布参数已知，则此时的贝叶斯纳什均衡解如何？ 9.2. 思考题

47 谢 谢 ！