上海怎么制作网站,江苏盐城建筑公司网站,培训机构网站,中国建筑人才网官网查询一、博弈论的概念
博弈论又被称为对策论#xff08;Game Theory#xff09;既是现代数学的一个新分支#xff0c;也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行…一、博弈论的概念
博弈论又被称为对策论Game Theory既是现代数学的一个新分支也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为并研究它们的优化策略。博弈论已经成为经济学的标准分析工具之一。
二、博弈论的发展历程
博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略达到取胜的目的。博弈论思想古已有之中国古代的《孙子兵法》等著作就不仅是一部军事著作而且算是最早的一部博弈论著作。博弈论最初主要研究象棋、桥牌、赌博中的胜负问题人们对博弈局势的把握只停留在经验上没有向理论化发展。
博弈论考虑游戏中的个体的预测行为和实际行为并研究它们的优化策略。
近代对于博弈论的研究开始于策梅洛Zermelo波莱尔Borel及冯·诺依曼von Neumann。
1928年冯·诺依曼证明了博弈论的基本原理从而宣告了博弈论的正式诞生。1944年冯·诺依曼和摩根斯坦共著的划时代巨著《博弈论与经济行为》将二人博弈推广到n人博弈结构并将博弈论系统地应用于经济领域从而奠定了这一学科的基础和理论体系。
19501951年约翰·福布斯·纳什John Forbes Nash Jr利用不动点定理证明了均衡点的存在为博弈论的一般化奠定了坚实的基础。纳什的开创性论文《n人博弈的均衡点》1950《非合作博弈》1951等等给出了纳什均衡的概念和均衡存在定理。此外莱因哈德·泽尔腾、约翰·海萨尼的研究也对博弈论发展起到推动作用。今天博弈论已发展成一门较完善的学科。
三、博弈论的要素
(1)局中人在一场竞赛或博弈中每一个有决策权的参与者成为一个局中人。只有两个局中人的博弈现象称为“两人博弈”,而多于两个局中人的博弈称为 “多人博弈”。
(2)策略一局博弈中每个局中人都有选择实际可行的完整的行动方案即方案不是某阶段的行动方案而是指导整个行动的一个方案一个局中人的一个可行的自始至终全局筹划的一个行动方案称为这个局中人的一个策略。如果在一个博弈中局中人都总共有有限个策略则称为“有限博弈”否则称为“无限博弈”。
(3)得失一局博弈结局时的结果称为得失。每个局中人在一局博弈结束时的得失不仅与该局中人自身所选择的策略有关而且与全局中人所取定的一组策略有关。所以一局博弈结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数通常称为支付payoff函数。
(4)对于博弈参与者来说存在着一博弈结果 。
(5)博弈涉及到均衡均衡是平衡的意思在经济学中均衡意即相关量处于稳定值。在供求关系中某一商品市场如果在某一价格下想以此价格买此商品的人均能买到而想卖的人均能卖出此时我们就说该商品的供求达到了均衡。所谓纳什均衡它是一稳定的博弈结果。
四、博弈论的目的
博弈策略求解是博弈问题中的一个重要内容另外一个重要的内容是博弈规则的设计 也就是说假设博弈的参与者都是足够理性的如何设计一个博弈规则能确保公正性或者达到设计者的最大利益。主要的难点是规则复杂计算量大。 主要应用于
拍卖竞价互联网广告投放、车牌竞价供需匹配污染权、学校录取公正选举选举制度、表决制度、议席分配
五、稳定分配理论(stable matchings theory)
稳定分配理论是由2012诺奖获得者沙普利使用合作博弈的方法来研究和对比不同的匹配方法而创立的理论。该理论的难点在于要保证一个配对是稳定的。 稳定匹配的核心思想是实现一种稳定状态在这种状态下在匹配完结时不再存在这样两个市场主体它们都更中意于他人胜过它们当前的另一半匹配对象。在现实中我们熟悉的8分钟相亲、学校和学生匹配等例子就是基于稳定市场匹配理论的思想发展而来的。其中双边模型和延迟接受算法是稳定匹配理论的两块重要基石。 双边匹配模型很多市场及社会制度的主要功能就是让其中的主体能和另一个主体相匹配例如学生和学校职员和公司适婚男女之间。这种市场匹配主要分为单边市场匹配(Single-Sided MarketMatch) 和 双边市场匹配(Two-Sided MarketMatch)。 “单边市场匹配”指市场中仅存在一个集合集合中的个体根据各自的偏好相互匹配。然而单边市场匹配中的“室友”现象会导致匹配的不稳定。当假设存在四个“室友”{1234其中1最偏好22最偏好33最偏好1且他们把4都列为最不偏好者。在这种情况下任何两两分组都无法实现稳定因为和4分在一起的人会结束当前匹配去和已经匹配的人再次匹配且这次新的匹配将会成功使得市场一直无法实现稳定(GaleShapley1962)。 “双边匹配模型”最早由Gale和Shapley(1962)从研究学生申请学校模型和婚姻稳定问题而提出。所谓的“双边市场”是指存在这样一个市场市场中有两类个体集合第一类集合中的个体只能和第二类集合中的个体相匹配。他们证明了在这样一个双边市场中只要个体的偏好具有完备性及可传递性以及市场足够的自由能允许个体进行任何潜在可能的匹配那么市场中总是存在稳定匹配。同样以4个室友为例假设任意2个人睡上铺2个人睡下铺现在要求只有睡不同铺的人相互匹配此时就形成了双边市场匹配模型。同时Gale和Sha-pley指出市场匹配稳定时满足以下两个条件(1)市场中不存在来自不同类的两个个体在偏好上可以实现相互匹配但没有匹配的情况(2)已经配对成功的个体不会尝试结束当前的配对并试图与来自另一类且已匹配成功的个体进行匹配。 双边匹配模型存在稳定匹配这一特性使得其在理论和实践上都得到了广泛的关注其中一个重要的运用就是劳动力市场的匹配。Shapley和Shubik(1972)利用数学模型抽象了一个充斥着不可分割商品的双边市场市场中的每一位参与者既是商品的需求者也是商品的供给者。他们发现在这更为一般化的市场中匹配稳定的性质依旧很稳健。 Roth最早对双边匹配模型在解决实践问题中的应用进行了研究。他意识到Shapley有关稳定市场匹配的理论和计算可让市场的运作方式变得更清晰。20世纪50年代美国内科医生的初级劳动力市场的组织方式能保证绝大多数个体匹配成功但这种匹配缺乏稳定性。Roth(1984)的后续实验研究将Shapley的匹配设计应用于内科医生的初级劳动力市场他的研究结果表明该种匹配方法能减少原有组织方式下所产生的匹配不稳定及其它存在的无序问题。 G-S算法(Gale-Shapley)
在规则设计里面有不同的算法比方说有GS算法 在生活中人们通常会碰到与资源匹配相关的决策问题(如求职就业、报考录取等)这些需要双向选择的情况被称为是双边匹配问题。在双边匹配问题中需要双方互相满足对方的需求才会达成匹配。 1962年美国数学家大卫·盖尔和博弈论学家沙普利提出了针对双边稳定匹配问题的解决算法并将其应用于稳定婚姻问题的求解。 稳定婚姻问题(stable marriage problem)是指在给定成员偏好的条件下分两组成员寻找稳定匹配。由于这种匹配并不是简单地价高者得所以匹配解法应考虑双方意愿。 稳定婚姻问题的稳定解是指不存在未达成匹配的两个人都更倾向于选择对方胜过自己当前的匹配对象。
最大交易圈算法(Top-Trading Cycle algorithm)
匹配问题中还有一类交换不可分的的标的物的匹配问题被称为单边匹配问题如远古时期以物易物、或者宿舍的床位分配。 1974年沙普利和斯夫提出了针对单边匹配问题的稳定匹配算法最大交易圈算法(TTC)算法过程如下 首先每个交易者连接一条指向他最喜欢的标的物的边并从每一个标的物连接到其占有者或者是具有最高优先权的交易者。 此时形成一张有向图且比存在交易圈对于交易圈中的交易者将每人指向节点所代表的标的物赋予其同时交易者放弃原先占有的标的物占有者和匹配成功的标的物离开匹配市场 接着从剩余的交易者和标的物之间重复进行交易圈匹配直到无法形成交易圈算法停止。
室友匹配问题 六、博弈论的类型
博弈的分类根据不同的基准也有不同的分类。
一般认为博弈主要可以分为合作博弈和非合作博弈。合作博弈和非合作博弈的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议如果有就是合作博弈如果没有就是非合作博弈。
从行为的时间序列性博弈论进一步分为静态博弈、动态博弈两类静态博弈是指在博弈中参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动动态博弈是指在博弈中参与人的行动有先后顺序且后行动者能够观察到先行动者所选择的行动。通俗的理解囚徒困境就是同时决策的属于静态博弈而棋牌类游戏等决策或行动有先后次序的属于动态博弈。
按照参与人对其他参与人的了解程度分为完全信息博弈和不完全信息博弈。完全博弈是指在博弈过程中每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息。不完全信息博弈是指如果参与人对其他参与人的特征、策略空间及收益函数信息了解的不够准确、或者不是对所有参与人的特征、策略空间及收益函数都有准确的信息在这种情况下进行的博弈就是不完全信息博弈。
经济学家们所谈的博弈论一般是指非合作博弈由于合作博弈论比非合作博弈论复杂在理论上的成熟度远远不如非合作博弈论。非合作博弈又分为完全信息静态博弈完全信息动态博弈不完全信息静态博弈不完全信息动态博弈。与上述四种博弈相对应的均衡概念为纳什均衡(Nash equilibrium子博弈精炼纳什均衡subgame perfect Nash equilibrium贝叶斯纳什均衡(Bayesian Nash equilibrium精炼贝叶斯纳什均衡(perfect Bayesian Nash equilibrium。
博弈论还有很多分类比如以博弈进行的次数或者持续长短可以分为有限博弈和无限博弈以表现形式也可以分为一般型战略型或者展开型以博弈的逻辑基础不同又可以分为传统博弈和演化博弈。
下面列举了一些我们经常会提到的博弈模型可以作为入门的兴趣导师——
智猪博弈——搭好顺风车借力成事 Boxed pigs game, 一个著名的纳什均衡的例子 枪手博弈——对比关系及策略决定强弱
囚徒困境——个人理性与集体的非理性 Prisoner’s Dilemma, 是博弈论的非零和博弈中具代表性的例子反映個人最佳選擇並非团体最佳選擇 斗鸡博弈——狭路相逢勇者未必胜 Chicken Game又叫草鸡博弈、懦夫博弈、胆小鬼博弈 分蛋糕博弈——讨价还价的策略
以牙还牙——有一种智慧叫宽恕 Tit for tat,是一个用于博弈论的重复囚徒困境Reiterated Prisoner’s Dilemma非常有效的策略 鹰鸽博弈——路径依赖法则新解 Hawk Dove game ——进化中的路径依赖 该模型的两个纯策略均衡类似于胆小鬼博弈而混合策略均衡则导出了进化稳定策略的概念。此外还有不完全信息条件下的贝叶斯博弈版本。 蜈蚣博弈——从后往前的推理 Centipede game 猎鹿博弈——合作是硬道理 Stag Hunt Game, 又称猎鹿模型(Stag Hunt Model)、猎人的帕累托效率 酒吧博弈——求同存异的智慧 Bar Problem 鲇鱼效应——有竞争才有发展 Catfish Effect 重复博弈——冲突与合作方能共享 Repeated Games, 是指同样结构的博弈重复许多次其中的每次博弈称为“阶段博弈”stage games。重复博弈是动态博弈中的重要内容它可以是完全信息的重复博弈也可以是不完全信息的重复博弈。 重复博弈所指的是一类特殊的扩展形式的博弈extensive form game。此类博弈中包含一个基础博弈base game——称为阶段博弈stage game在整个重复博弈中该阶段博弈会被重复一定次数。阶段博弈一般是一个大家熟悉的博弈如囚徒困境。类似的非重复博弈也可称为单一阶段博弈single stage game或单次博弈single shot game。 协和谬误——欲罢不能的错上加错 Coordination Problem, 即某件事情在投入了一定成本、进行到一定程度而后发现不宜继续下去却苦于各种原因而将错就错欲罢不能 信息甄别——酒好不怕巷子深
人质困境——雪上加霜的囚徒困境
脏脸博弈——都是共同知识惹的祸
成本博弈——摆脱沉没成本羁绊的策略
手表定律——标准不同结论就不同 Watch Law 策略均衡——谁也不得罪 strategy equilibrium 本文部分选自 作者深度学习与先进智能决策 链接https://juejin.im/post/5e33cf9f5188252c5232b039 来源掘金 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
