ari H.
2021-04-14T02:11:14+00:00
首先简单科普一下囚徒困境:
囚徒困境的故事讲的是,两个嫌疑犯作案后被警察抓住,分别关在不同的屋子里接受审讯。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判八年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年。
在这个例子里,对于这个犯罪团伙来说,最佳结局是两个人都抵赖。问题在于对于任意一个嫌犯来说,最佳的策略都是坦白:如果同伙坦白,自己抵赖判10年而坦白只判8年;如果同伙抵赖,抵赖判1年而坦白无罪释放。如果两个人都选择了自己的最佳策略坦白,那么两个人都判8年,无法达到最佳结果。这种在博弈中每个人都选择了对自己来说的最佳策略,结果导致整体上利益受损的情况,就叫做囚徒困境。
下图是一个典型的囚徒困境博弈的收益表
[img]https://img.nga.178.com/attachments/mon_202104/18/-7Q16v-gejvKiT3cSjd-62.jpg[/img]
表中竖排是甲的策略,横行是乙的策略。4组收益数字,每一组第一个数字是甲的收益,第二个数字是乙的收益。
举例来说,坐上角的数字(3,3)是甲乙双方都选择合作时的收益,甲的收益是3,乙的收益也是3;右上角是甲选择合作,乙选择背叛时的收益,甲是0,乙是5;左下角是甲选择背叛,乙选择合作的收益,甲是5,乙是0;右下角是双方都选择背叛时的收益,双方都是1。
可以看到,对于甲乙这个整体来说,合作时最佳选择,因为这时双方的收益之和是6;但是对于甲或者乙个人来说,背叛都是最佳选择:如果对方合作,自己选择合作收益是3,选择背叛收益是5;如果对方选择背叛,自己选择合作收益是0,选择背叛收益是1。无论对方怎么选择,自己的最佳选择都是背叛。甲乙双方都选择背叛,博弈的结果就是(1,1),双方收益之和只有2。
下面说一下重复囚徒博弈。甲乙双方坐下来,不是进行一次囚徒困境的博弈,而是连续进行100次博弈,每个人的收益就是这100次博弈的收益之和。在这种情况下,背叛就不一定是最佳策略,因为对方可能在下一个回合同样选择背叛来惩罚你;在这样的情况下,双方有可能达成一定的默契,都选择合作从而摆脱囚徒困境,达到双赢。
以上就是《合作的进化》这本书的理论基础。在这本书里,作者提出了一个锦标赛的模式:参与者每个人提出一个参加100次重复博弈的策略,然后这些策略依次与其它的参赛策略进行重复博弈。比如说一共有30个策略参赛,那么每个策略都要与其它29个策略进行一次重复100回合的囚徒困境博弈。最后获得最多收益的策略就是冠军。
那么下面就是本次锦标赛策略的要求:提交的策略不能接触博弈对象的源代码;可以获得博弈双方在本轮的博弈结果,比如说在每轮博弈的第2轮,可以知道第1轮双方的选择,第30轮的时候可以知道双方在前29轮的选择,在100轮时可以知道双方在前99轮的选择;可以使用概率性策略(比如30%的几率选择合作70%的几率选择背叛);不能使用对方在其它轮次的结果,比如说本轮策略A与策略B博弈,下一轮策略A与策略C博弈,这个时候策略C无法知道前一轮A与B的博弈结果。
假如你有兴趣,可以自己写一个你认为可以获胜的策略,注意最好用汉语来写,或者用伪代码的形式。真的自己用代码实现的话请做好我无法理解还要回去问你的准备。
策略请发到 1500978475@qq.com 请注明自己策略想要用的名字,或者以无名氏的身份参赛。
假如参与者足够多,我会在一周内完成编程(其实有别人写好的包,自己随便调整一下就行),并写一个报告出来。
囚徒困境的故事讲的是,两个嫌疑犯作案后被警察抓住,分别关在不同的屋子里接受审讯。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判八年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年。
在这个例子里,对于这个犯罪团伙来说,最佳结局是两个人都抵赖。问题在于对于任意一个嫌犯来说,最佳的策略都是坦白:如果同伙坦白,自己抵赖判10年而坦白只判8年;如果同伙抵赖,抵赖判1年而坦白无罪释放。如果两个人都选择了自己的最佳策略坦白,那么两个人都判8年,无法达到最佳结果。这种在博弈中每个人都选择了对自己来说的最佳策略,结果导致整体上利益受损的情况,就叫做囚徒困境。
下图是一个典型的囚徒困境博弈的收益表
[img]https://img.nga.178.com/attachments/mon_202104/18/-7Q16v-gejvKiT3cSjd-62.jpg[/img]
表中竖排是甲的策略,横行是乙的策略。4组收益数字,每一组第一个数字是甲的收益,第二个数字是乙的收益。
举例来说,坐上角的数字(3,3)是甲乙双方都选择合作时的收益,甲的收益是3,乙的收益也是3;右上角是甲选择合作,乙选择背叛时的收益,甲是0,乙是5;左下角是甲选择背叛,乙选择合作的收益,甲是5,乙是0;右下角是双方都选择背叛时的收益,双方都是1。
可以看到,对于甲乙这个整体来说,合作时最佳选择,因为这时双方的收益之和是6;但是对于甲或者乙个人来说,背叛都是最佳选择:如果对方合作,自己选择合作收益是3,选择背叛收益是5;如果对方选择背叛,自己选择合作收益是0,选择背叛收益是1。无论对方怎么选择,自己的最佳选择都是背叛。甲乙双方都选择背叛,博弈的结果就是(1,1),双方收益之和只有2。
下面说一下重复囚徒博弈。甲乙双方坐下来,不是进行一次囚徒困境的博弈,而是连续进行100次博弈,每个人的收益就是这100次博弈的收益之和。在这种情况下,背叛就不一定是最佳策略,因为对方可能在下一个回合同样选择背叛来惩罚你;在这样的情况下,双方有可能达成一定的默契,都选择合作从而摆脱囚徒困境,达到双赢。
以上就是《合作的进化》这本书的理论基础。在这本书里,作者提出了一个锦标赛的模式:参与者每个人提出一个参加100次重复博弈的策略,然后这些策略依次与其它的参赛策略进行重复博弈。比如说一共有30个策略参赛,那么每个策略都要与其它29个策略进行一次重复100回合的囚徒困境博弈。最后获得最多收益的策略就是冠军。
那么下面就是本次锦标赛策略的要求:提交的策略不能接触博弈对象的源代码;可以获得博弈双方在本轮的博弈结果,比如说在每轮博弈的第2轮,可以知道第1轮双方的选择,第30轮的时候可以知道双方在前29轮的选择,在100轮时可以知道双方在前99轮的选择;可以使用概率性策略(比如30%的几率选择合作70%的几率选择背叛);不能使用对方在其它轮次的结果,比如说本轮策略A与策略B博弈,下一轮策略A与策略C博弈,这个时候策略C无法知道前一轮A与B的博弈结果。
假如你有兴趣,可以自己写一个你认为可以获胜的策略,注意最好用汉语来写,或者用伪代码的形式。真的自己用代码实现的话请做好我无法理解还要回去问你的准备。
策略请发到 1500978475@qq.com 请注明自己策略想要用的名字,或者以无名氏的身份参赛。
假如参与者足够多,我会在一周内完成编程(其实有别人写好的包,自己随便调整一下就行),并写一个报告出来。