对策论博弈论.ppt

2024/5/21 周二运筹学第12讲对策论（博弈论）简介广州大学地理科学学院 蔡砥12024/5/21 周二内容n对策现象及其三个要素n对策问题举例及对策的分类n矩阵对策（矩对策）的基本理论n关于纯策略与混合策略22024/5/21 周二对策现象及其三个要素32024/5/21 周二经典案例：囚徒困境n两个犯罪嫌疑人被捕并受到指控，但除非至少一个人招认犯罪，警方并无充足证据将他们按罪判刑。n警方把他们关入不同牢房，并对他们说明不同行动带来的后果：q如果两人都不坦白，将均被判为轻度犯罪，入狱一个月；如果双方都坦白招认，都将被判入狱6个月；最后，如果一人招认而另一人拒不坦白，招认的一方将马上获释，而另一人将判入狱9个月（所犯罪行6个月，干扰司法加判3个月）。q前提：两囚犯是非合作的。42024/5/21 周二囚徒困境的双变量矩阵表示n囚徒面临的问题可用上图的双变量矩阵表来描述。（“双变量”指的是在两个参与者的博奔中，每一单元格有两个数字分别表示两个参与者的收益）n习惯上，横行代表的参与者（囚徒1）的收益在两个数字中放前面；列代表的参与者（囚徒2）的收益置于其后。n无论囚徒1选择沉默（不坦白），或者招认，囚徒2都会选择招认；反之也然。52024/5/21 周二对策现象的三个要素一般，当局中人、策略集和赢得函数这3个要素确定后，一个对策模型也就给定。62024/5/21 周二局中人（players）n一个对策中，有权决定自己行动方案的对策参与者称为局中人，通常用I表示局中人的集合。一个对策中至少有两个局中人。q局中人是广义的，可以是单个个人，也可以是一个集体，利益完全一致的参与者只能看成一个局中人。q局中人都是“理性的”：遵从博弈（game）的规则并总是采取最利己的策略。72024/5/21 周二关于理性局中人的一个有趣例子n海盗分宝石：q5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。他们决定这么分：n1 抽签决定自己的号码（1，2，3，4，5）n2 首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则提案人将被扔入大海喂鲨鱼。n3 如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。n4 依次类推q问：最终的方案为如何？q前提：海盗们非常遵守规则，并谋求利益最大化n命不能丢n宝石要尽量多82024/5/21 周二理性的破坏n照三国，1命刀斧手埋伏于帐侧，到时候一声令下，将其他4个统统剁成肉泥！n照水浒，1奋起一脚掀掉桌子，挑一个最有主见的，抽刀砍了来个林冲刀砍王伦！其他几个立马跪地告饶：“哥哥息怒！哥哥但要独得尽管拿去就是了！”引自网易科技论坛，码帖人：乱话三千92024/5/21 周二策略（strategies）n博弈中，可供局中人选择的一个实际可行的完整的行动方案 称为一个策略。局中人i的策略集记为Si，一般的，每一个局中人的策略集中至少应包括2个策略。q囚徒困境问题中，囚徒的策略有2个：沉默或招认；q海盗问题中n提出方案的海盗有多个策略：各种可能的分配方案n其它海盗的策略有2个：支持或否决。102024/5/21 周二赢得函数（payoff function，支付函数）n博弈中，每一个局中人所出的策略形成的策略组称为一个局势。即设si是第i个局中人的一个策略，则n个局中人的策略形成的策略组s=(s1,s2,sn)就是一个局势。n当一个局势s出现后，应该为每一个局中人i规定一个赢得值（或所失值）Hi(s)。不同的局势对应的赢得值不同，Hi是s的函数，称为赢得函数。112024/5/21 周二对策问题举例及对策的分类122024/5/21 周二市场购买力争夺问题市场总购买力为4000万中心城市企业策略出售高档食品出售低档饮食品乡镇企业策略出售特色饮食品2000,20003000,1000出售一般饮食品1000,30003000,1000132024/5/21 周二销售竞争问题142024/5/21 周二费用分摊问题n假设沿某一河流有相邻的3个城市A，B，C，各城市可单独建立水厂，也可合作兴建一个大水厂。经估算，合建一个大水厂，加上敷设管道的费用，要比单独建3个小水厂的总费用少。但合建大厂的方案能否实施，显然要看总的建设费用分摊得是否合理。如果某个城市分摊到的费用比它单独建设水厂的费用还多的话，它显然不会接受合作的方案。问题是应如何合理地分摊费用，使合作兴建大水厂的方案得以实现？152024/5/21 周二对策的分类n根据局中人的个数，分为2人对策和多人对策；n根据各局中人的赢得函数的代数和是否为零，分为零和对策与非零和对策；n根据各局中人间是否允许合作、分为合作对策和非合作对策；n根据局中人的策略集里的策略个数，分为有限对策和无限对策等等。n此外，还有许多其它的分类方式q根据策略的选择是否与时间有关，可分为静态对策和动态对策；q根据对策模型的数学持征，可分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策等。162024/5/21 周二矩阵对策的基本理论仅讨论纯策略情况172024/5/21 周二矩阵对策n矩阵对策为2人有限零和对策。q博弈中的局中人只有2人（双方）；q“有限”是指每个局中人的策略集均为有限集；q“零和”是指在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得恰好等于另一个局中人的所失值，双方的利益是完全对抗的。q“田忌赛马”是一个典型的2人有限零和对策。182024/5/21 周二田忌赛马田忌策略上中下上下中中上下中下上下中上下上中齐王策略上中下3,-31,-11,-11,-11,-1-1,1上下中1,-13,-31,-11,-1-1,11,-1中上下1,-1-1,13,-31,-11,-11,-1中下上-1,11,-11,-13,-31,-11,-1下中上1,-11,-1-1,11,-13,-31,-1下上中1,-11,-11,-1-1,11,-13,-3192024/5/21 周二市场购买力争夺问题市场总购买力为4000万中心城市企业策略出售高档食品出售低档饮食品乡镇企业策略出售特色饮食品2000,20003000,1000出售一般饮食品1000,30003000,1000市场总购买力为4000万中心城市企业策略出售高档食品出售低档饮食品乡镇企业策略出售特色饮食品0,0+1000,-1000出售一般饮食品-1000,+1000+1000,-1000202024/5/21 周二矩阵表示n由于是零和对策，因此无须给出双变量矩阵，而简化为单变量矩阵。212024/5/21 周二Exp：一个矩阵对策的解222024/5/21 周二定义：平衡局势232024/5/21 周二矩阵对策有解的充要条件242024/5/21 周二田忌赛马问题无最优解（最优纯策略）252024/5/21 周二关于纯策略与混合策略262024/5/21 周二一个无纯策略解的问题n由于不满足前文的充要条件，因此，该问题如果博弈双方都只可能采用单纯的一个策略时，本问题没有解。所谓没有解，是指找不到一个双方都可以接受的平衡局势。272024/5/21 周二混合策略n既然局中人没有最优的策略可出，局中人的一个可能是：以一定的概率随机地挑选策略。n每一个策略有一定的概率，这就构成了混合策略，即一个混合策略是由多个纯策略按照一定的概率组合在一起的。n例如，上面问题中，局中人I以概率pI和(1-pI)选取纯策略1和2；而局中人II以概率pII和(1-pII)选取纯策略1和2。282024/5/21 周二田忌赛马中关于齐王的讨论n齐王在多次比赛中，均采用（上中下）的策略，赢得了多次比赛。由此可以看出，齐王在6个可选策略中，以100的概率偏好于（上中下）这个策略。这虽然看起来是一个纯策略，但其实应该看作是混合策略的特例，即其它策略的概率都为零。n孙膑正是利用了这一点，给田忌出了一个纯策略。n可以看出，在博弈中，双方并不要求一定都是纯策略，也不要求都是混合策略。29