沈阳网站排名公司,网站建站套餐,互联网包括哪些方面,郑州品牌网站建设官网文章目录博弈论什么是博弈论#xff1f;博弈的前提博弈的要素博弈的分类非合作博弈——有限两人博弈囚徒困境合作博弈——无限多人博弈囚徒困境常见的博弈定律零和博弈重复博弈智猪博弈斗鸡博弈猎鹿博弈蜈蚣博弈酒吧博弈枪手博弈警匪博弈海盗分金巴什博弈博弈论
什么是博弈论…
文章目录博弈论什么是博弈论博弈的前提博弈的要素博弈的分类非合作博弈——有限两人博弈囚徒困境合作博弈——无限多人博弈囚徒困境常见的博弈定律零和博弈重复博弈智猪博弈斗鸡博弈猎鹿博弈蜈蚣博弈酒吧博弈枪手博弈警匪博弈海盗分金巴什博弈博弈论
什么是博弈论
我个人的理解是通过分析与事情有关的所有元素在力所能及的范围内寻求最好的结果 前半句即博弈后半句为博弈的意义。
博弈的深层意义在于所得的最优策略与对手在博弈中的操作没有依存关系。简言之其理性思想就是 抱最好的希望做最坏的打算。 博弈的前提
博弈理论假定参与博弈的人必须是理性的理性的人在博弈过程中会将 自身利益最大化 作为目标。其实这未必不是博弈的局限性记得前段时间看到的一篇博客很有意思在一个狼吃羊的AI智障游戏中狼发现自己吃不到羊直接选择了「自杀」。然而狼选择撞石的原因竟是「自杀分数高」全文在这里
出现自杀这一博弈结果的主要原因当然是在训练过程中将分数设置成了权重最大的项甚至重于生命但也侧面印证了 局中人的绝对理性 。 博弈的要素
博弈需要具备的要素通常有五个方面 局中人 两人博弈 or 多人博弈 策略 有限博弈每个参与人明确的知道交易次数。不用给自己留后路此种博弈下信誉没有保障。无限博弈每个参与人不知道博弈会在什么时候停止谁都考虑为自己留后路。此种博弈中妥协会比较多信誉也比较好。 得失 局中人博弈的得失与两个因素相关一是其自身所选定的策略二是其他局中人所选定的策略。每个局中人在博弈结束时的得失可根据所有局中人选定的一组策略函数来判定这个函数称为 支付函数 。 次序 动态博弈局中人的行动有先后顺序且 后做出选择的人 知道 先做出选择之人 的行动。静态博弈局中人同时选择要采取的策略。或者 后做出选择的人 不知道 先做出选择之人 的行动。 均衡 博弈通常都有一个 稳定的结果 谓之均衡或称平衡。 博弈的分类
上面讲到的 动态博弈 与 静态博弈 的划分有限博弈 与 无限博弈 的划分。都是博弈的分类方法。而经济学中通常将博弈分为非合作博弈 和 合作博弈。
非合作博弈比合作博弈更简单理论也更成熟。根据复合特征来划分非合作博弈可分为四类 完全信息静态博弈 对应的均衡概念是 纳什均衡 。 完全信息动态博弈 对应的均衡概念是 子博弈精炼纳什均衡 。 不完全信息静态博弈 对应的均衡概念是 贝叶斯纳什均衡 。 不完全信息动态博弈 对应的均衡概念是 精炼贝叶斯纳什均衡 。 完全信息博弈每位参与者都能准确地知道所有其他参与者的行为以及整个博弈结构 不完全信息博弈在这类博弈中每位参与者对所有其他参与者的信息不够了解或不了解整个博弈结构。 非合作博弈——有限两人博弈囚徒困境
在上文中提到博弈的意义在于找到 最好结果但要明白的是在 有限博弈 中这个最好结果是是个人最优解而非团体最优解。也就是 在保障自身利益的前提下每个人的策略都是对其他人的策略的最优反应。 我们通过 约翰·纳什 创造的 囚徒困境 博弈故事进一步解释
两个共谋犯罪的人被关入监狱不能互相沟通情况。如果两个人都不揭发对方则由于证据不确定每个人都坐牢五年若一人揭发而另一人沉默则揭发者因为立功而坐牢一年沉默者因不合作而判十年若互相揭发则因证据确凿二者都判刑八年。
虽然对于团体而言最优解是大家都不揭发对方然而对于囚徒而言
如果对方沉默自己揭发的话判一年、沉默的话判一年揭发更好如果同伙揭发自己揭发的话判八年、沉默的话判十年揭发更好。
这个结果说明了 纳什平衡 的存在即在非合作博弈中存在一个均衡解这个解可使博弈双方的利益都获得保障这个解并非团队最优解却是个人最优解。
囚徒困境是一个 非合作博弈 原因在于博弈次数只有一次即有限博弈。有限博弈下无论之前选择了多少次合作最后一次局中人必然会选择背叛对方以寻求个人利益最大化可以理解为
如果不是最后一次博弈你背叛人家的话人家一定会报复你对方也一样大家都怕背叛对方的话下一次博弈中对方的报复导致本来可以拿到的团队最优解拿不到了。但如果是最后一次博弈的话万一对方背叛你你就没有报复机会了那不如我先报复他。
但是如果是 无限博弈 并且是 多人博弈 的话就会呈现 合作博弈 。 合作博弈——无限多人博弈囚徒困境
在上一个囚徒困境的基础上如果抓紧来的是犯罪团伙并且不告诉它们要审问他们多少次只告诉他们还是刚才的规矩不过每个人的坐牢时间是根据每次审讯结果累加。在这种情况下囚徒们就会意识到如果持续选择都沉默大家一起每轮多坐五年牢如果持续选择彼此揭发大家每轮多坐八年牢。通过这样的思考参与者之间合作的动机就非常明显了。
针对 无限多人博弈 罗伯特·阿克塞尔罗德制定了类似的实验最终取得 最好结果对于变种囚徒困境而言就是坐牢时间最少的囚徒阿克塞尔罗德的实验中是得分最高的程序 的程序一般具有三个特点
善良性从不主动背叛别人可激怒性对于别人的背叛会进行报复宽容性对于别人的背叛不会无休止的报复。
这种一报还一报的策略不仅优秀而且清晰其特性通常在几次博弈后就能被清晰地辨识出来其他程序这个程序是个狼灭不好惹只有主动和他合作才能赢而其他复杂的策略并没有得到优秀的结果对手无法总结与其相处的规律。
罗伯特·阿克塞尔罗德的研究揭示了合作的必要条件
博弈要持续进行下去参与者在一次或几次的博弈中是找不到合作动机的要对对手的行为做出回报这个回报可以是好的也可以是坏的若一个人永远选择合作那么是不会有太多人与他合作的。 常见的博弈定律
零和博弈
零和博弈是最常见的博弈零和博弈属于非合作博弈。即参与博弈赛局的双方在严格遵守博弈规则的前提条件下若是其中一方可以获得利益也就意味着另一方的利益必然受损。所以博弈双方的收益和损失之和永远为零即博弈双方不存在合作的可能。
与之对应的是 合作双赢即在某种程度上保证双方达成 利己且不损人 的合作关系。通常是因为在零和博弈中双方都没有很大把握能一定胜出、而失败的成本太大的情况下。 重复博弈
通过两种囚徒困境的探讨我们发现当博弈仅进行一次人们往往更加关心它的最终结果当博弈重复多次人们将舍弃眼前利益而选取更长远的利益即如单次博弈结果的利益让步与总体博弈结果的利益。影响重复博弈最终结果的因素主要是重复博弈所进行的次数以及信息的完整性。
可以将重复博弈总结成三个基础特征
在进行重复博弈的过程中并没有结果上的关联简言之就是 上一个阶段所进行的博弈并不会改变接下来所要进行的博弈结构。在进行重复博弈的每个阶段所有的参与者都能够看到前面的参与者所做出的决策。对于参与重复博弈的参与者而言他们所获得的收益是在每个阶段所获得收益的加权平均数。 智猪博弈
智猪有智慧的猪哼哼~
智猪博弈是纳什理论中的一个经典例子。若一个猪圈里有一头大猪还有一头小猪在猪圈的一边有一个投放饲料的猪槽猪槽旁边安放着一个可以控制猪槽投食量的按钮假设我们按一下这个投食按钮猪槽内便会出现 10 个单位的猪食但是想要按这个按钮则需要拿出 2 个单位的猪食作为成本。在此种情况下
假设大猪先走到猪槽边它跟小猪的进食量之比为 9:1假设大猪和小猪同时到达猪槽它们的进食量之比则为 7:3若是小猪先走到猪槽那么它们的进食量之比则为 6:4。
若是两头猪都非常有智慧那么小猪便会在猪槽边等待着。
若是小猪去按投食开关大猪在猪槽边等待那么大猪小猪的进食量之比为 9:1 这样计算得出小猪最后的净收益为吃掉的 1 个单位减去按开关损失的 2 个单位1-2-1单位的猪食。即当大猪去按下按钮时大猪小猪的进食量之比为 6:4扣除按开关所需要的 2 个单位的猪食大猪最终得到的只有 4 个单位的猪食若是小猪和大猪同时去按开关同时到达猪槽那么它们所获得猪食的比例为 1:5 减去按开关的成本。假设两头猪不去按开关那么他们的纯收益都将为 0。
而对于博弈中的劣势方小猪来讲自己去按开关得到的纯收益必定是 -1但是如果自己不去按开关一、大猪按开关得到的纯收益为 4。二、大猪也不按开关两只猪的纯收益都是 0 .由此看来不论大猪是选择主动行动还是等待小猪都选择等待的收益要高于选择行动所获得的利益这便是小猪在此次博弈中的占优策略。
通常将小猪的这种方法称为 坐船 或 搭便车 暗示人们在博弈中如果占据劣势且时间损失不会对最终受益造成影响时等待也是一种明智之举。 斗鸡博弈
Chicken Game 又名懦夫博弈。假定这样一种情景狭路相逢
一方后退、另一方前进称前进一方胜利两方都后退则称平局两方都前进则都失败。
这种博弈思想的价值私以为在于进一步证明纳什均衡原理。在此博弈中有两个纳什均衡点A 进 B 退A 退 B 进。
纳什均衡点其他参与者策略保持不变时当前参与者的选择是最优的这样就组成了一个混合收益最大化的策略组。 猎鹿博弈
最早出现在卢梭的《论人类不平等的起源和基础》一书中又名安全博弈、协调博弈。
猎鹿博弈源于一则故事在一个村庄中有两个猎人这个村庄主要有两种猎物鹿和兔子。一个猎人只能捕捉到 4 只兔子如果两个猎人合作就能捕到 1 只鹿。而站在填饱肚子的角度看捕到 4 只兔子能够成为 4 天的食物但是 1 只鹿足以让两个猎人在 10 天内都不用外出捕猎。
由此一来这两个猎人的行动策略就会产生两个纳什均衡点即
两个猎人单独行动每个人获得4只兔子并且每人能够吃饱4天或者两个猎人建立合作那么每个人可以吃饱10天。
虽然两个猎人合作可以获得的收益远超单独行动的收益。但是这要求两个猎人在合作过程中个人能力和付出是相等的。能力不等的情况下大家都是理性人当然会要求付出多的收获占比多啦。 蜈蚣博弈
蜈蚣博弈的提出者是罗森塞尔它指参加博弈的 A 和 B 分别有 合作、背叛 两种策略可供选择。规则是 A 先进行选择再由 B 做出选择再轮 A 做出选择……
举个例子如果双方需要博弈十轮 网上的资料中没有对收益结果进行解释所以我一直对最后一次不合作的结果是 811而不是911而感到困惑我个人分析收益是这样计算的
根据第一轮 A 就不合作双方的收益仍是11可以推测博弈开始前双方手里就各有一个筹码。根据第一轮 A 合作、B 不合作双方的收益是03会发现 A 手里的一个筹码没了但 B 多了两个筹码。
因此合作的前提可能是 A、B 都拿出来一个筹码如果双方选择合作则都收获一个筹码之前拿出来的筹码也可以收回如果 A 选择背叛则 B 不需要拿出来筹码博弈结束如果 B 选择背叛则 A 失去它拿出来的筹码B 自己获得两个筹码。
如果一直合作那么最终总体收益可达最大值 20 但根据理性人原则B 会在最后一轮博弈中选择背叛以拿到 11 的收益大于选择合作的 10 收益。那么 A 亦会在 B 选择背叛前先背叛那么它就能拿到 9 收益大于 B 背叛时的 8 收益……以此类推得到的答案是 A 会在刚开始就选择不合作那么 A 和 B 所获得的最终收益是 1 。 蜈蚣博弈的悖论 不难看出在上面的推理过程中运用的是逆推法。从逻辑推理来看逆推法是严密的但结论是不合理的。虽然 A 一开始采取合作性策略有可能获得 0 但 1 或者 0 与 10 相比实在是很小。直觉告诉我们采取 合作 策略是好的。而从逻辑的角度看A一开始应选择 不合作 的策略。人们在博弈中的真实行动偏离了运用逆推法关于博弈的理论预测造成二者间的矛盾和不一致。 酒吧博弈
假设有 100 个人都喜欢去酒吧消遣娱乐若我们设定酒吧的座位数是 60那么想要去酒吧的人便会有两种决策一种是不去待在家中另外一种是去。假设所有的人都去酒吧那么去酒吧的人就会感到不舒服而这时他们会觉得待在家中要比去酒吧更好。那么这 100 个喜欢去酒吧的人最终将会做何选择呢
其实这些喜欢去酒吧的人往往会受上一次酒吧人数的影响进而产生一些人数上的浮动久而久之便会形成一种持续性波动的情况。这是由切斯特·艾伦·阿瑟博士提出的他的理论如下
假设每个想要去酒吧的人都是理性的那么酒吧每天接待的人数几乎不会有过大的浮动。就会产生 神奇的 60% 客满率定理 即当人们选择去酒吧时最初的观察结果并未找到任何规律但是通过长时间的观察发现每次去酒吧的人数和不去酒吧的人数之比接近 60:40 。但是人并不总能保持理性当人们在第一次去酒吧时若发现酒吧人数非常多那么这种现象会成为他们下次选择的一个参考他们会认为酒吧人数太多、十分拥挤、喧闹大部分下次就不来了但是少数人可能会选择下次依然去酒吧这时他们发现酒吧的人数并不多然后便会在下一次叫上自己的朋友一起去酒吧由此一来循环便正式开始了。
从心理学的角度来看最初去酒吧的那些人可能互相不熟悉但是由于经常去酒吧而且能够遇见对方久而久之便会由陌生人变成朋友那么在这种情况下便会由零散的个体变成一个大的群体而这个整体中又会分支出小团体而且这些小团体中的人有一部分会占据主导地位另一部分人会处在服从地位。这就意味着团体中的每个人的决策都会受到他人的影响。 枪手博弈
枪手博弈是指枪手甲乙丙三人相互怨恨以决斗的形式进行一场博弈。其中甲的枪法最准命中率 80%。乙的枪法在甲之下命中率 60%。丙的枪法最差命中率 40%。假设在三人都了解彼此实力并能理性判断的情况下会出现以下两种情况
三人同时开枪谁活下来的可能最大若由丙开第一枪随后轮流开枪他会如何选择 第一种情况 第一轮
甲最佳的策略是先对准乙因为乙的枪法比丙好。乙最佳的策略是先对准甲因为三人中甲的枪法最准这样在乙丙两人中乙活下来的概率更大。丙同样也会先解决枪法最准的甲干掉甲后再考虑如何应对乙。
现在我们可以分别计算三人活下来的概率
甲活即乙和丙都未命中。两人都射偏的概率为40%×60%所以甲活下来的概率为 24%。乙活即甲射偏。甲有 20% 的未命中率就相当于乙的存活率为 20%。丙活根据上面的分析在这一种情况下没有任何人对准丙因此丙的存活概率为 100%。
由此我们可以看到在这一轮的决斗中丙枪法最差但活下来的概率却最大。而甲和乙的枪法都远大于丙存活率却都比丙低。
第二轮
第一轮过后有三种情况
若甲乙中有一方打偏那么丙会面对甲或乙若都打偏那丙将同时面对甲乙两人甲乙都命中甲乙皆死。
现在我们可以分别计算三人活下来的概率
如果丙只面对甲或乙那丙的存活率最低。如果同时面对甲乙两人则返回第一轮的场景。如果甲乙皆死那么无疑丙最终存活。 第二种情况 由丙先开第一枪那么可能如下
丙射中甲乙与丙对决且只能由乙先开枪丙会处于不利位置。丙射中乙同上甲的命中率最高丙的处境会更糟。丙都未射中的话甲乙都不会选择先射击丙而是会在甲乙双方之间一决胜负直至其中一人死亡而这时就会又轮到丙。可以这样说只要丙谁都不打中在接下来的对决中他就处于相对而言最有利的位置。
我们会发现优势最小的丙反而可能是不是最先死掉的因此在多方非合作博弈中优势最小的往往可以在暂时安全的环境下抓紧机会提升自己。当然如果不能在暂时安全的环境下提升能力的话当面对双人非合作博弈时难免处于失败者的位置。简言之实力最差的并不一定是输的最快的但终究是需要提升自我的否则即使能安全一时、但仍然难免落入败局。 警匪博弈
在某个小镇上只有一名警察整个小镇的治安全部由他负责。此时我们假设这个小镇上的一头有一家银行存了 2 万元而小镇的另一头有一个酒馆存了 1 万元。若这个小镇上还有一名小偷当这个小镇上的警察在小镇的一头巡视时小偷只能去小镇的另一头进行偷盗。
假想一下当小镇的警察正好在小偷采取行动的地方巡视便能不费吹灰之力地抓住小偷若是小镇的警察的巡视方向恰好与小偷采取偷盗行为的方向相反那么小偷便能在不被警察抓到的情况下成功偷盗。那么如何才能将小镇的损失降到最低呢
警察最好的做法是利用抽签的方式决定去小镇的银行还是酒店。由于小镇银行中所需保护的财产是酒馆的两倍因此用 1、2 号两个签表示小镇的银行用 3 号签表示酒馆这样一来警察去银行巡视的机会将达到 2/3而去酒馆巡视的机会将是 1/3。
在小镇警察的此种策略下小偷的占优策略则要与警察相反同样采用抽签的方式与警察不同的是小偷用 1、2 号签表示去酒馆行动而用 3 号签表示去银行由此一来小偷去酒馆行动的概率是 2/3而去银行的概率仅有 1/3。
如果双方都选择最佳占优策略的话警察和小偷的成功率是相等的过程有些繁琐可选择跳过分析如下
如果警察和小偷都是理性人的话警察可以猜到小偷的概率小偷也可以猜到警察的概率。
双方如果单纯都是第一层的话警察成功概率 2/3*1/31/3*2/34/9小偷成功概率 1-4/95/9但是如果警察在第二层警察反概率行动小偷在第一层警察成功概率 1/3*1/32/3*2/35/9小偷成功概率 1-5/94/9警察在第一层小偷在第二层那么和上一个情况一样警察成功概率 5/9小偷成功概率 4/9双方都是第二层都以相反概率行动警察成功概率 4/9小偷 5/9。
最后相加综合期望双方成功概率都为 1/2。这波啊这波叠加就是千层饼~
而如果警察和小偷扔硬币去决定守、偷哪出地点。这样就模糊了自己策略的倾向性结果就具有偶然性。博弈取胜的要点在于运用其中的偶然性针对对方是否发现你的某些策略性行为做出及时应对进而保证自己成功的概率。总结来讲还是说明信息在博弈中的重要性。 海盗分金
有五个海盗记为1、2、3、4、5号掠得 10 枚金币决定以抽签的方式依次提出分金方案并由五人共同表决。要想通过方案必须有超半数的人同意才可以否则这个人将会被扔进大海。
与其从前往后一个一个地想每个人会怎样选择不如先把问题简单化若只剩下最后两人的话他们会怎么做呢
倒推来看若1、2、3号都被投入海中那么 5 号必定反对 4 号把一百枚金币全部收入囊中。因此 4 号只有同意 3 号的方案才有可能保命。3号猜到这一点就会采取 100、0、0 的分金方案因为他清楚地知道即便4号一枚金币也分不到也仍然会同意他的方案。2 号猜到 3 号的策略就会采取 98、0、1、1 的方案因为 2 号只要稍微照顾到 4、5 号的利益4、5 号就会向他投赞成票而不希望 2 号出局让 3 号分配。1 号同样猜到 2 号的意图就会采取 97、0、1、2、0 或者 97、0、1、0、2 的方案。对于 1 号来说只要放弃 2 号再分给 3 号一枚金币给 4 号或 5 号两枚金币。 巴什博弈
巴什博弈 一堆物品有 n 个两个人轮流从这堆物品中取物规定每次至少取一个最多取 m 个。最后取光者得胜。
巴什博弈是一种 动态、完全信息博弈 即局中人的行动有先后顺序且后做出选择的人知道先做出选择之人的行动。
如果一方拿取时还剩 m1 个那便是 必败局因为此时不论你拿走多少个下次对方一定可以全部拿完。
其他情况则是 必胜局 。因为如果还剩 m1k 个0 k m我只要拿走 k 个那么对方就面临 m1 个。可能有人在想 0 k -m 怎么办没什么多说的还是必胜局我直接拿走剩下的全部。
扩展如果 n x(m1) 先拿的依然面对必败局先拿的拿 p 个后拿的拿 m1-p 个先拿的第二轮拿的时候还剩 x-1(m1) 重复 x-2 轮先拿的又面对 m1 了。
反之如果 nx(m1)k 先拿的面对必胜局先拿的拿走 k 个则后拿的面对 x(m1) 重复上一段的过程。
因此可以得到代码
#includeiostream
using namespace std;
int main()
{int n, m;cin n m;if (n % (m 1) 0)cout second win endl;else cout first win endl;return 0;
}
