囚徒困境答案 囚徒困境解题思路

  囚徒困境是一道经典的博弈方面的题目,我们一起来了解一下这个问题的解法吧。

囚徒困境答案 囚徒困境解题思路

  “囚徒困境”是1950年美国兰德公司提出的博弈论模型。两个共谋犯罪的人被关入监狱,不能互相沟通情况。如果两个人都不揭发对方,则由于证据不确定,每个人都坐牢一年;若一人揭发,而另一人沉默,则揭发者因为立功而立即获释,沉默者因不合作而入狱五年;若互相揭发,则因证据确实,二者都判刑两年。由于囚徒无法信任对方,因此倾向于互相揭发,而不是同守沉默。

  囚徒困境(prisoner dilemma):两个被捕的囚徒之间的一种特殊博弈,说明为什么甚至在合作对双方都有利时,保持合作也是困难的。囚徒困境是博弈论的非零和博弈中具代表性的例子,反映个人最佳选择并非团体最佳选择。虽然困境本身只属模型性质,但现实中的价格竞争、环境保护等方面,也会频繁出现类似情况。

  【解决思路】

  贝叶斯纳什均衡:如果对抗策略的统计分布能被确定(例如,50%以牙还牙,50%一直合作),就能从数学上获得最佳的相对策略[4]。

  已经有了人群的蒙特卡罗模拟,在这里低分个人消失了,高分个人一再被生产出来(一种获得最佳策略的天才算法)。决赛人群中的算法合成通常依赖于初赛人群中的算法合成。

  尽管以牙还牙始终被认为是最可靠的基本策略,但是在重复囚徒困境的20周年纪念赛中,来英国南安普敦大学的一个小组(由尼古拉斯·詹宁斯(NicholasJennings)[1]领导,包括了拉蒂普·达什(RajdeepDash)、萨瓦帕里·拉姆琼(SarvapaliRamchurn)、亚历克斯·罗杰斯(AlexRogers)斯和皮鲁克里士南·维特林根(PerukrishnenVytelingum))介绍了一个新的策略,这个策略证明了它比以牙还牙更成功。这个策略依赖于程序之间的合作,为单一程序中获得了最高的点数。

  南安普敦大学提交了60个程序参与竞赛,这些程序的开头被设计成通过一组5到10个的动作去彼此识别。一旦这些识别被作出,一个程序将总是合作,其他程序则总是背叛,保证背叛者得到最大的点数。如果程序识别出它在操作一个非南安普敦参与者,这程序将持续地背叛,企图去最小化竞争程序的得分。结果[5],这个策略以获得前3位结束了竞赛,也得到了大量接近底部的位置。虽然这个策略显著地证明了比以牙还牙有效,但是这是因为利用了下述事实:在这个特殊的竞赛中,多重通道是被允许的。在一方只能控制单一参与者的竞赛中,以牙还牙确实是更好的策略。

  如果重复囚徒困境将被精确地重复N次,已知N是一个常数,那么会产生另一个有趣的事实。纳什均衡就是每次都背叛。这很容易用归纳法证明。你也可以在最后的回合背叛,既然你的对手将没有机会惩罚你。因此,你们都将在最后的回合背叛。这时,你可以在倒数第二回合中背叛,既然最后一回无论你做什么,你的对手都将背叛。依此类推。为了合作以保持请求,这时未来必须对两个参与者来说是不确定的。一个解决方案是让博弈总次数N变成随机的。对未来的预期必须是无法确定的长度。

  另一个单独的案例是“永不停止”的囚徒困境。这个博弈被重复很多次,而且你的分数是一个平均数(当然是用计算机计算的)。

  囚徒困境博弈是某些人类合作和信任理论的基础。假定囚徒困境能够模拟需要信任的两人之间的交流,群体的合作行为可以用有多个参与者的、重复博弈的变体来模拟。这从而引起了许许多多学者经久不衰的兴趣。1975年,格罗夫曼(Grofman)和普尔(Pool)估计,致力于这方面研究的学术文章,数量超过2000篇。

分类:默认分类 时间:2015-03-07 人气:10
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.070 (s). 9 q(s)