《八、警察与小偷博弈【基础教学】》由会员分享,可在线阅读,更多相关《八、警察与小偷博弈【基础教学】(22页珍藏版)》请在金锄头文库上搜索。
1、 警察与小偷博弈警察与小偷博弈 不按套路出牌不按套路出牌1苍松优选8.1 警察与小偷博弈警察与小偷博弈 某个小镇上只有一名警察,他负责整个镇的某个小镇上只有一名警察,他负责整个镇的治安。现在我们假定,小镇的一头有一家酒馆,治安。现在我们假定,小镇的一头有一家酒馆,另一头有一家银行。另一头有一家银行。 再假定该地只有一个小偷。因为分身乏术,再假定该地只有一个小偷。因为分身乏术,警察一次只能在一个地方巡逻;而小偷也只能去警察一次只能在一个地方巡逻;而小偷也只能去一个地方。一个地方。 2苍松优选8.1 警察与小偷博弈警察与小偷博弈 假定银行需要保护的财产价格为假定银行需要保护的财产价格为2万元,酒万
2、元,酒馆的财产价格为馆的财产价格为1万元。警察怎么巡逻才能使效万元。警察怎么巡逻才能使效果最好果最好? 若警察选择了小偷偷盗的地方巡逻,就能把若警察选择了小偷偷盗的地方巡逻,就能把小偷抓住;而如果小偷选择了没有警察巡逻的地小偷抓住;而如果小偷选择了没有警察巡逻的地方偷盗,就能够偷窃成功。方偷盗,就能够偷窃成功。 3苍松优选8.1 警察与小偷博弈警察与小偷博弈解析:解析: 一种最容易被警察采用而且确实也更为常见的一种最容易被警察采用而且确实也更为常见的做法是,警察对银行进行巡逻。这样,警察可以保做法是,警察对银行进行巡逻。这样,警察可以保住住2万元的财产不被偷窃。万元的财产不被偷窃。 但是假如小
3、偷去了酒馆,偷窃一定成功。这种但是假如小偷去了酒馆,偷窃一定成功。这种做法是警察的最好做法吗?做法是警察的最好做法吗? 答案是否定的,因为我们完全可以通过博弈论的答案是否定的,因为我们完全可以通过博弈论的知识,对这种策略加以改进。知识,对这种策略加以改进。4苍松优选8.1 警察与小偷博弈警察与小偷博弈 警察的一个最好的策略是,抽签决定去银行还警察的一个最好的策略是,抽签决定去银行还是酒馆。因为银行的价值是酒馆的两倍,所以用两是酒馆。因为银行的价值是酒馆的两倍,所以用两个签代表,比如抽到个签代表,比如抽到1、2号签去银行,抽到号签去银行,抽到3号签号签去酒馆。这样警察有去酒馆。这样警察有2/3的
4、机会去银行进行巡逻,的机会去银行进行巡逻,1/3的机会去酒馆。的机会去酒馆。 5苍松优选8.1 警察与小偷博弈警察与小偷博弈 而在这种情况下,小偷的最优策略是:以同样而在这种情况下,小偷的最优策略是:以同样抽签的办法决定去银行还是去酒馆偷盗,与警察不抽签的办法决定去银行还是去酒馆偷盗,与警察不同的是抽到同的是抽到1、2号签去酒馆,抽到号签去酒馆,抽到3号签去银行。号签去银行。这样小偷有这样小偷有1/3的机会去银行,的机会去银行,2/3的机会去酒馆。的机会去酒馆。 6苍松优选8.1 警察与小偷博弈警察与小偷博弈 从警察和小偷的不同角度计算最佳混合策略,从警察和小偷的不同角度计算最佳混合策略,会得
5、到一个有趣的共同点:同样的成功概率。会得到一个有趣的共同点:同样的成功概率。 也就是说,警察若采用自己的最佳混合策略,就也就是说,警察若采用自己的最佳混合策略,就能将小偷逮到的成功概率能将小偷逮到的成功概率 (收益为收益为2*2/9+1*2/9=6/9) 小偷采用自己的最佳混合策略所能达到的成功概小偷采用自己的最佳混合策略所能达到的成功概率率 (收益为收益为2*1/9+1*4/9=6/9)。7苍松优选8.1 警察与小偷博弈警察与小偷博弈 警察与小偷之间的博弈,提供了警察与小偷之间的博弈,提供了混合策略混合策略的思的思路,但更形象的样板是路,但更形象的样板是“剪刀、石头、布剪刀、石头、布”的游戏
6、。的游戏。 在这样一个游戏中,在这样一个游戏中,不存在纯策略均衡不存在纯策略均衡。对每。对每个小孩来说,出个小孩来说,出“剪刀剪刀”、“布布”还是还是“石头石头”的的策略应当是随机的,不能让对方知道自己的策略,策略应当是随机的,不能让对方知道自己的策略,甚至是策略的倾向性。甚至是策略的倾向性。 一旦对方知道自己出某个策略的可能性增大,那一旦对方知道自己出某个策略的可能性增大,那么在游戏中输的可能性也就增大了。么在游戏中输的可能性也就增大了。8苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例 在传统政治中,有所谓在传统政治中,有所谓“君臣一日而百战君臣一日而百战”的的说法,来形容国君与大
7、臣之间博弈的激烈程度。因说法,来形容国君与大臣之间博弈的激烈程度。因为激烈,所以其层出不穷的招式,给博弈论的研究为激烈,所以其层出不穷的招式,给博弈论的研究提供了丰富的案例。提供了丰富的案例。9苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例 吕氏春秋吕氏春秋中记载了这样一个故事。战国时,中记载了这样一个故事。战国时,宋康王极端变态,整天喝酒,异常暴虐。凡群臣中有宋康王极端变态,整天喝酒,异常暴虐。凡群臣中有来劝谏的,都被他找理由撤职或者关押起来。臣下也来劝谏的,都被他找理由撤职或者关押起来。臣下也因此对他更加反感,经常非议他。他十分苦恼地对宰因此对他更加反感,经常非议他。他十分苦恼地
8、对宰相唐鞅说:相唐鞅说:“我处罚的人很多了,但是大臣们越发不我处罚的人很多了,但是大臣们越发不畏惧我,这是什么原因呢?畏惧我,这是什么原因呢?” 唐鞅说:唐鞅说:“您所治罪的,都是一些犯了法的人。惩您所治罪的,都是一些犯了法的人。惩罚他们,没有犯法的好人当然不会害怕。如果您要让您罚他们,没有犯法的好人当然不会害怕。如果您要让您的臣子们害怕,就必须不区分好人坏人,也不管他犯法的臣子们害怕,就必须不区分好人坏人,也不管他犯法没有犯法,随便抓住就治罪。这样的话,大臣们就知道没有犯法,随便抓住就治罪。这样的话,大臣们就知道害怕了。害怕了。”10苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例
9、唐鞅提出的这个建议,虽然缺德了一些,唐鞅提出的这个建议,虽然缺德了一些,但却不能不说是深刻地把握住了混合策略博弈但却不能不说是深刻地把握住了混合策略博弈的精髓之处。能够预测的惩罚,大臣总会想方的精髓之处。能够预测的惩罚,大臣总会想方设法地加以规避,而无法预测的惩罚,却是防设法地加以规避,而无法预测的惩罚,却是防不胜防的,因而也是更令人心惊胆战的。不胜防的,因而也是更令人心惊胆战的。11苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例 宋康王也是个聪明人,听了这个主意以后宋康王也是个聪明人,听了这个主意以后恍然大悟,深深地点了点头。不久,他就下令恍然大悟,深深地点了点头。不久,他就下令把
10、唐鞅杀了,大臣们果然十分害怕,每天上朝把唐鞅杀了,大臣们果然十分害怕,每天上朝时都战战兢兢不敢多说一句话。时都战战兢兢不敢多说一句话。12苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例车站警察与小偷的博弈车站警察与小偷的博弈 鉴于火车站偷窃活动猖獗,上级年年都会给车鉴于火车站偷窃活动猖獗,上级年年都会给车站警队下达严打任务。由于警力不足,车站警队只站警队下达严打任务。由于警力不足,车站警队只得抽调维护治安等其他人员,在牺牲其他工作的情得抽调维护治安等其他人员,在牺牲其他工作的情况下,方能集中精力,打掉几个最大的小偷团伙,况下,方能集中精力,打掉几个最大的小偷团伙,部分遏制偷窃活动。部
11、分遏制偷窃活动。 但是,车站每年此时都会因为秩序混乱等原因但是,车站每年此时都会因为秩序混乱等原因受到上级批评。受到上级批评。 13苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例 久而久之,车站警队开始思考怎么能在这个节久而久之,车站警队开始思考怎么能在这个节骨眼儿上两全其美。骨眼儿上两全其美。 其先,有小偷团伙向车站警队行贿。这个现象其先,有小偷团伙向车站警队行贿。这个现象引起了领导的高度重视。领导认为,在这个问题上引起了领导的高度重视。领导认为,在这个问题上只能实现合作双赢,才能实现车站政治利益的最大只能实现合作双赢,才能实现车站政治利益的最大化。化。 其关键是警队与最大的几个小
12、偷团伙建立沟通其关键是警队与最大的几个小偷团伙建立沟通机制,小偷在每天向警队交若干保证金的情况下,机制,小偷在每天向警队交若干保证金的情况下,业务活动不会受到干扰,但不能偷市民,只能偷外业务活动不会受到干扰,但不能偷市民,只能偷外地人。地人。 14苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例 当上级有严打任务时,这些小偷团伙立即隐匿,当上级有严打任务时,这些小偷团伙立即隐匿,警队可以正常的力量打击其他偷窃活动。警队可以正常的力量打击其他偷窃活动。 在这个博弈模式中,小偷保证了安全和业务活在这个博弈模式中,小偷保证了安全和业务活动,损失的不过是每天若干保证金和市民的钱包;动,损失的不
13、过是每天若干保证金和市民的钱包; 而警队保证了上级和市民的肯定,没有任何损而警队保证了上级和市民的肯定,没有任何损失,相反得到了每天若干保证金的收益。这是双方失,相反得到了每天若干保证金的收益。这是双方最佳的博弈结果。最佳的博弈结果。15苍松优选8.2 警察与小偷博弈的案例警察与小偷博弈的案例猜硬币游戏猜硬币游戏 比如在足球比赛开场,裁判将手中的硬币抛掷比如在足球比赛开场,裁判将手中的硬币抛掷到空中,让双方队长猜硬币落下后朝上的是正面还到空中,让双方队长猜硬币落下后朝上的是正面还是反面。是反面。 由于硬币落下地的正反是随机的,概率都是由于硬币落下地的正反是随机的,概率都是1/2。那么,猜硬币游
14、戏的参与者选择正反的概率。那么,猜硬币游戏的参与者选择正反的概率都是都是1/2,这时博弈达到混合策略纳什均衡。,这时博弈达到混合策略纳什均衡。 16苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到的启示 这一类博弈与囚徒困境博弈案例有一个很大的这一类博弈与囚徒困境博弈案例有一个很大的差别差别 。 就是没有纯策略纳什均衡点,只有就是没有纯策略纳什均衡点,只有混合策略均混合策略均衡点衡点。 这个均衡点下的策略选择是每个参与者的最优这个均衡点下的策略选择是每个参与者的最优(混合混合)策略选择。对混合策略的传统解释是,局中策略选择。对混合策略的传统解释是,局中人应用一种随机方法来决定所选择的
15、策略。人应用一种随机方法来决定所选择的策略。 17苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到的启示 “最小最大定理最小最大定理” 定理指出,在二人零和博弈中。参与者的利定理指出,在二人零和博弈中。参与者的利益严格相反益严格相反(一人所得等于另一人所失一人所得等于另一人所失),每个参,每个参与者尽量使对手的最大收益最小化,而他的对手与者尽量使对手的最大收益最小化,而他的对手则努力使自己的最小收益最大化。则努力使自己的最小收益最大化。 由数学家约翰由数学家约翰冯冯诺伊曼诺伊曼(John Von Neumann)创立创立 18苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到
16、的启示 他们这样做的时候,会出现一个令人惊讶的结果,他们这样做的时候,会出现一个令人惊讶的结果,即最大收益的最小值即最大收益的最小值(最小最大收益最小最大收益)等于最小收益的等于最小收益的最大值最大值(最大最小收益最大最小收益)。双方都没办法改善自己的收。双方都没办法改善自己的收益,因此这些策略形成这个博弈的一个均衡。益,因此这些策略形成这个博弈的一个均衡。 最小最大定理的证明相当复杂,不过,其结论最小最大定理的证明相当复杂,不过,其结论却很实用。假如你想知道的只不过是一个选手之得或却很实用。假如你想知道的只不过是一个选手之得或者另一个选手之失。你只要计算其中一个选手的最佳者另一个选手之失。你
17、只要计算其中一个选手的最佳混合策略并得出结果就行了。混合策略并得出结果就行了。19苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到的启示所有混合策略的均衡具有一个共同点:所有混合策略的均衡具有一个共同点: 每个参与者并不在意自己的任何具体策略。每个参与者并不在意自己的任何具体策略。 一旦有必要采取混合策略,找出你自己的策一旦有必要采取混合策略,找出你自己的策略的方法,就是让对手觉得他们的任何策略对你略的方法,就是让对手觉得他们的任何策略对你的下一步都没有影响。的下一步都没有影响。20苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到的启示 这听上去像是朝向混沌无为的一种倒退,
18、其实不这听上去像是朝向混沌无为的一种倒退,其实不然。因为它正好符合零和博弈的随机化动机:然。因为它正好符合零和博弈的随机化动机: 一方面要发现对手任何有规则的行为,并相应采一方面要发现对手任何有规则的行为,并相应采取行动。假如他们确实倾向于采取某一种特别的行取行动。假如他们确实倾向于采取某一种特别的行动,这只能表示他们选择了最糟糕的策略。动,这只能表示他们选择了最糟糕的策略。 另一方面,也要避免一切会被对方占便宜的模另一方面,也要避免一切会被对方占便宜的模式,坚持自己的最佳混合策略。式,坚持自己的最佳混合策略。21苍松优选8.3 警察与小偷博弈得到的启示警察与小偷博弈得到的启示 因此,采取混合或者随机策略,并不等同于因此,采取混合或者随机策略,并不等同于毫无策略地毫无策略地“瞎出瞎出”。 这里面仍然有很强的策略性。其这里面仍然有很强的策略性。其基本要点基本要点在在于,运用偶然性防止别人发现你的有规则行为并于,运用偶然性防止别人发现你的有规则行为并占你的便宜。占你的便宜。 22苍松优选