警察与小偷博弈.ppt

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