运筹学第六讲对策论.ppt

对策论 Game Theory 运筹学 Operations Research 对策论 game theory (1) 1713年，瓦德格拉夫提出两人对策的经典模型； 对策论历史简介： (2) 古诺和博特兰分别在1838年与1883年提出对策论最经典的模型； (4) 1944年，冯诺依曼和摩根斯坦合著出版博弈论与经济行为一书，被 看作是对策论真正发展的起点； (3) 中国古代的“齐王赛马”； (5) 1994年，瑞典皇家科学院决定将诺贝尔经济学奖授予纳什、哈萨尼和泽 尔腾三人，表彰他们在博弈理论和应用方面作出的杰出贡献； (6) 目前，博弈论在定价、招投标、谈判、拍卖、委托代理以及很多的经营 决策中得到应用，它已成为现代经济学的重要基础。现代对策论总体上是一门 新兴的发展中的学科。 Nash对对策论的贡献有： (i) 合作对策中的讨价还价模型，称为Nash讨价还价解； (ii) 非合作对策的均衡分析。 对策论 game theory 1，1 10， 0 0， 10 5，5 囚徒1 囚徒 2 坦 白 不 坦 白 坦白 不坦白 (囚徒的困境)引例 警察抓住两个合伙犯罪的嫌疑犯，但缺乏足够的证据指证他 们的罪刑，若其中一个供认犯罪，就能确认罪名成立。为得到所 需的口供，警察将两嫌疑犯分开关押并给他们同样的选择机会， 若两人都拒不认罪，则他们会以较轻的妨碍公务罪各判一年徒刑 ；若有一人坦白认罪，则坦白者立即释放，而另一个人则判10年 徒刑，若两人同时认罪，则他们各被判5年徒刑，现两个嫌疑犯 该如何采取各自的策略(坦白、不坦白)对自己有利？ 这是一个二人非零和对策问题，可用一个矩阵来表示两囚徒 的得益，如下表所示： 对策论 game theory 对策论(game theory)亦称博弈论: 是研究具有对抗或竞争性质现象的数学理 论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。 对策论概述 引言 对策行为: 是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞 争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方 案,并力图选择对自己最为有利或最为合理的方案 。 对策：是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则 下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得 相应结果的过程。 对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及 如何找到这个合理方案的数学理论和方法。是研究决策主体的行为发生直接 相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策 者在冲突或合作中的策略选择理论。它将成为当代经济管理学科的前沿领城。 对策论 game theory 一个对策需要3个基本要素： (1)局中人(players) (2)策略集(strategies) (3)得益函数(payoffs) 对策三要素 引言 策略集： 在一局对策中，可供局中人选择的一个实际可行的完整的行动方案 称为一个策略，所有行动方案的集合成为策略集。每个局中人i 都有自己的 策略集，每一局中人的策略集中至少包含两个策略。 全体局势的集合S可用各局中人的策略集的迪卡尔集表示, 即 局中人：在一个决策行为中，有权决定自己行动方案的对策参加者，常用I 表示局中人的集合。一般要求一个对策中至少要有两个局中人。 是一个局势。 得益函数(也称赢得函数)：在一局对策中，对应于各参与方每一组可能的决策 选择，都应有一个结果表示该策略组合下每个参与方的得益，常用得益函数表 示。若一个策略中有n个参与方，则他们可形成一个策略组 对策论 game theory 对策的结构和分类 引言 纳什均衡 Nash Equilibrium 对于对策中的每一个局中人，真正成功的措施应该是针对于其他局中 人所采取的每次行动，相应地采取有利于自己地反应策略，于是每一 个局中人应采取的必定是他对其他局中人策略的预测的最佳反应。 对策论 game theory 【定义 】 在对策G=S1，S2，Sn；h1，h2hn中，如果由各个对策方的各 选取一个策略组成的某个策略组合(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*)对任意 SijSi 都成立，则称(S1*，Sn*)为G的一个纯策略意义下的“纳什均衡 ”(Nash Equilibrium) 用G 表示一个对策，若一个对策中有 n 个局中人，则每个局中人可选策略的 集合称为策略集，分别用 S1，S2，Sn 表示；Sij 表示局中人i 的第 j 个策 略，其中 j 可取有限个值(有限策略对策)，也可取无限个值(无限策略对策)； 对策方 i 的得益则用 hi 表示；hi 是各对策方策略的多元函数，n个局中人的对 策G常写成： G=S1，Sn；h1，hn 纳什均衡 纳什均衡定义 定义中各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为 纯策略意义下的最优局势 对策论 game theory 纳什均衡 【例1】 假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自 的产量分别用m1、m2和m3表示，再假设m1、m2和m3只能取1、2、3等正整 数值市场出清价格一定是市场总产量Q=m1+m2+m3的函数，假设该函数为 ： 为简化计算，假设各厂商的生产无成本，并且各厂商同时决定各自产量，求 整个市场会均衡怎样的产量和价格水平？ 分析：采用比较和试探的方法来确定本决策的均衡产量。不妨先假设三个厂 商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产 量，要从利润进行分析。由于产量不能超过20，则第i个厂商的利润函数为 对策论 game theory 根据上述公式可算出在产量组合为(3，9，6)时，市场价格为2，三厂商的利 润分别为6，18和12，再作其它产量组合时亦会有不同的结果，如表12.2 表12.2 三厂商离散产量结合对应价格和利润 m1m2m3p123 396261812 386392418 5564202024 5555252525 33311333333 6338482424 纳什均衡 对策论 game theory 注: (1)上述产量组合给各厂商带来的利润并不是市场能给他们的最大利润； (2) 三厂商开始并不一定选取这种产量组合，而是在长期的对策过程中逐渐调 整到这个产量组合，这个组合就是一个纳什均衡。 m1m2m3p123 396261812 386392418 5564202024 5555252525 33311333333 6338482424 由表可看出(5, 5, 5)这组产量组合是比较稳定的，因为在该组合下，任何一个 厂商单独提高或降低产量，都只会减少利润，因此该产量组合是一个均衡。 纳什均衡 对策论 game theory 【定义】 在对策G=S1，Sn；h1，hn中，局中人 i 的策略集为Si=Si1 ，Sik，则他以概率分布pi=(pi1，pik)随机在其k个可选策略中选择的“ 策略”称为一个混合策略，其中 0pij1 对 j1, , k 都成立，且pi1+pik=1 混合策略纳什均衡 纳什均衡 注：纯策略可看作混合策略的一种特殊情况，只是选择相应纯策略的概率函 数服从(0-1)分布 【定义】 如果一个策略G=S1, , Sn; h1, , hn中，参予者i 的策略集为Si=Si1, , Sik，如果由各个对策方的策略组成策略集合G*=S1*, S2*, , Sn*，其中 都是对其余对策方策略组合的最佳策略，即 i(S1*,S2*, , Si-1*, Si*, , Sn*)i(S1*, S2*, , Si-1*, Si*, , Sn*) 对任意SijSi都成立，则称(S1*, ,Sn*)为G 的一个混合策略纳什均衡 反应函数法 反应函数法是对策论中一种常用的方法，尤其适用于确定决策 变量为产量或价格这样的连续函数策略。当得益是对策的多元连续 函数时，求出每个对策方的反应函数，而各个反应函数的交点就是 纳什均衡。 对策论 game theory 反应函数法 【例3】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产 量为Q=q1+q2，市场出清价格是市场总产量的函数P6Q。设产品产量的边际 成本相等，C1=C2=2。求解两厂商的纳什均衡(假设产量连续可分)。 分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润 分别为各自的销售收益减去各自成本，即： 从得益函数表达式中可以看出，两者的利润取决于对方的策略即产量，要寻找 一个纳什均衡，即对厂商2的任意产量，厂商1有一个最佳的对应产量，实现利 润最大化，即求解 用求极值方法求得同理厂商2的最佳产量为 对策论 game theory 反应函数法 作反应函数： (0,4) (0,2) (2,0) (4,0) (4/3,4/3) 纳什均衡：(4/3,4/3) 由上面两个式子，得出对于厂商2的每一个可能的产量，厂商1的最佳产量是 厂商2产量的一个连续函数，我们称这个连续函数为厂商1对厂商2产量的一个 反应函数。 对策论 game theory 反应函数法 【例4】 考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假 设产量与价格的函数关系为： 其它条件不变，边际成本为C1、C2，试求解其纳什均衡。 【解】设P1max, P2max为两厂商所能选择的最高价格，则其各自的策略空间为 两方的得益就是各自的利润 利用得益函数在偏导数为0时有最大值，各自的反应函数分别为： 对策论 game theory 反应函数法 为该对策唯一的纳什均衡 对策论 game theory 反应函数法 【例4】设有3个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于 草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设 每只羊的产出函数为 成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决 策，试求出该决策问题的纳什均衡。 【解】各农户的得益函数分别为 反应函数 因此该对策的纳什均衡为(18，18，18) 。 有限二人零和对策 有限二人零和对策也称矩阵对策或二人有限零和对策，其对 策中存在两个局中人，并且局中人都只有有限个决策可供选择， 在任一局势下，两个局中人的赢得之和总是等于零，双方的利益 是激烈对抗的。 对策论 game theory 有限二人零和对策 用、表示两个局中人，并设局中人有 m个纯策略 ， 局中人有n个纯策略 ，则按对策论的相关要素定义，局 中人、的策略集分别为： 通常矩阵用来表示局中人I 的赢得，局中人 II 的支付。 显然，局中人、所 构成的策略组合共有mn个，记局中人在策略(i ,j)下的赢得aij，则在每个 策略的赢得构成一个矩阵 数学定义 称A为局中人的赢得矩阵(或为的支付矩阵)，由于对策为零和的，故局中 人的赢得矩阵为A。 对策论 game theory 当局中人、的策略集S1, S2及I的赢得矩阵确定后，一个矩阵对策就给定了 通常将矩阵对策记为： 有限二人零和对策 矩阵对策纯策略纳什均衡：矩阵对策模型给定后，对各局中人而言，就是如 何选取对自己最有利的策略以获得最大得益。 纯策略矩阵对策 【例6】求矩阵对策，其中 ， 由A可以看出局中人 I 的最大得益是7，要想得到这个得益，他需选择策略 3， 而局中人2也是理智的，他会考虑用策略3来对付，这样局中人1不但得不到 7 反 而会失去11，故双方都不愿意冒险，而是考虑到双方必使自己获得最少这 一点。 对策论 game theory 则有 对策G的解为： 有限二人零和对策 【定义】 设G=S1，S2；A为矩阵对策，其中 S1=1, 2, , m，S2=1, 2 , , n， , 若等式 成立 ， ，则称VG 为对策G 的值，对应的策 略组合 称为该对策的纳什均衡 对策论 game theory 【定理】矩阵对策G=S1，S2；A在纯策略定义下有纳 什均衡的充要条件是：存在策略组合 使得对一切i=1, , m, j =1, , n 有： 注：矩阵对策在纯策略意义下有解且VG=ai*j*的充要 条件是：ai*j*是A的鞍点，在对策论中，矩阵A的鞍点 也称为对策的鞍点 有限二人零和对策 【定义】设f(x，y)为一个定义在xA及yB上的实函 数 , 如果存在x*A及y*B, 使得对一切xA及yB 有 则称为函数 f 的一个鞍点。 对策论 game theory 可知 =5，i *=1,3，j *=2, 4, 故 (1,2)(1, 4)(2,2)(2,4) 为对策的纳什均衡，VG=5 有限二人零和对策 【解】 直接在赢得表上计算，有 【例7】 设有矩阵对策 G= S1，S2；A ， 求纳什均衡 对策论 game theory 【性质1】 无差别性 若 和 为G的两个解 ，则： 注：以上方法也称“上策均衡法”(Dominant-stratege Eqyilibrium) 有限二人零和对策 也是对策的解及 【性质2】 可交换性若 和 为G 的两个解 ，则 纯策略意义下对策解的性质： 对策论 game theory 混合策略矩阵对策 纯策略矩阵对策的满足纳什均衡是满足局中人有把握的至 少赢得, 也是局中人有把握的至多损失即： 当V1V2 时，这时不存在纯策略意义下的纳什均衡 。如： 有限二人零和对策 对局中人1来说，V1=2，i *=3，对局中人2来说，V2=3，j *=1， V1V2 , 没有鞍点。 对策论 game theory 有限二人零和对策 当 时，称 为局中人、在混合策略中的纳什均衡。 称为局中人在选取混合策略S*1时的赢得函数。 【定义 】 设矩阵对策 ，其中 记 则分别称 为局中人,的混合策略集； , 分别称为局中人I、II的混合策略， 为一个混合局势。 称为G 的混合扩充。 对策论 game theory 【定理 】矩阵对象G=S1，S2；A在混合策略意义下有解的充 要条件是：存在x*S1*，y*S2*，使(x*，y*)为函数E(x，y)的一 个鞍点，即对一切xS1*，yS2*有 E(x，y*)E(x*，y*)E(x*，y) 有限二人零和对策 【例9】 考虑矩阵对策G= S1，S2；A ，其中 试求纳什均衡 【解】 纯策略纳什均衡不存在设 x=(x1，x2)为局中人的混合 策略， y=(y1，y2)为局中人的混合策略，则： 对策论 game theory 局中人I 的赢得期望值： 有限二人零和对策 即取 ， 满足 则 分别为局中人I, II的最优策略， 对策论 game theory 纳什均衡存在定理 【定理 】 设x*S1*，y*S2*,则(x*，y*)为对策G的纳什均衡的 充 要条件是： 对任意 i=1, , m，j=1, n, 有 E(i, y*)E(x*,y*)E(x*, j) 其中： 有限二人零和对策 对策论 game theory 【定理】 设x*S1*，y*S2*，则(x*，y*)是对策G的纳什均衡的 充要条件是：存在数V，使得x*，y*分别满足： 且V=VG . 【定理】 对任一矩阵对策G=S1，S2；A，一定存在混合策略意 义下的纳什均衡 有限二人零和对策 对策论 game theory 【定理】 设(x*，y *)为矩阵对策G 的一个纳什均衡， V =VG ，则 (1)若xi*0，则 (2)若yi* 0，则 (3)若 ，则 (4)若 , 则 有限二人零和对策 【定理】 设有两个矩阵对策 G1=S1，S2；A, G2=S1，S2； A，则 (1) VG2=VG1 (2) T(G1)=T(G2) ，其中0为一常 数，T(G1)、T(G2)为两个对策的解集合。 对策论 game theory 矩阵对策求解方法 1、2n 矩阵对策的求解方法: 思路: 先研究简单的22矩阵对策，然后推广到2n 情形。 22矩阵对策的公式法(适用于无最优纯策略) 在无最优纯策略情形下可证明 ，且 设矩阵对策中各局中人的最优混合策略为 由定理12.5可知，该矩阵对策一定存在混合