非合作博弈及其应用 郑臻一.

Presentation on theme: "非合作博弈及其应用 郑臻一."— Presentation transcript:

1 非合作博弈及其应用 郑臻一

2 博弈（game） 什么是博弈？ 古语有云，世事如棋。生活中每个人如同棋手，其每一个行为如同在一张看不见的棋盘上布一个子，精明慎重的棋手们相互揣摩、相互牵制，人人争赢，下出诸多精彩纷呈、变化多端的棋局。博弈论是研究棋手们 “出棋” 着数中理性化、逻辑化的部分，并将其系统化为一门科学。换句话说，就是研究个体如何在错综复杂的相互影响中得出最合理的策略。

3 博弈的分类 博弈的三要素 参与人或者局中人（players）； 他们可选择的行动（actions）或策略（strategies）；
当事人能否公然串通、合谋：合作博弈和非合作博弈 完全信息静态博弈、完全信息动态博弈、不完全信息静态博弈、不完全信息动态博弈 博弈的三要素 参与人或者局中人（players）； 他们可选择的行动（actions）或策略（strategies）； 所有可能的对局的结果，支付（payoffs）

4 “看不见的手”的原理：在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。
亚当·斯密 《非合作博弈》 《n人中的博弈均衡点》 约翰·纳什

5 话说有一天，一位富翁在家中被杀，财物被盗。警方在此案的侦破过程中，抓到两个犯罪嫌疑人，斯卡尔菲丝和那库尔斯，并从他们的住处搜出被害人家中丢失的财物。但是，他们矢口否认曾杀过人，辩称是先发现富翁被杀，然后只是顺手牵羊偷了点儿东西。于是警方将两人隔离，分别关在不同的房间进行审讯。由地方检察官分别和每个人单独谈话。检察官说，“由于你们的偷盗罪已有确凿的证据，所以可以判你们3年刑期。但是，我可以和你做个交易。如果你单独坦白杀人的罪行，我只判你1年的监禁，但你的同伙要被判10年刑。如果你拒不坦白，而被同伙检举，那么你就将被判10年刑，他只判1年的监禁。但是，如果你们两人都坦白交代，那么，你们都要被判5年刑。”

6 囚徒困境 个人利益的最大化不一定会导致团体利益的最大化

7 纳什均衡 在博弈G=﹛S1,…,Sn：u1,…，un﹜中，如果由各个博弈方的各一个策略组成的某个策论组合（s1*,…，sn*）中，任一博弈方i的策论si*，都是对其余博弈方策略的组合（s1*,…s*i-1,s*i+1,…，sn*）的最佳对策，也即ui（s1*,…s*i-1,si*,s*i+1,…，sn*）≥ui（s1*,…s*i-1,sij*,s*i+1,…，sn*）对任意sij∈Si都成立，则称（s1*,…，sn*）为G的一个纳什均衡。 如果某情况下无一参与者可以独自行动而增加收益，则此策略组合被称为纳什均衡点。

8 多次囚徒困境博弈 双方均保持沉默，即会建立互信的关系，最终导致，二人同服刑半年。
如果假设，两个囚徒均欲利用此策略，并将局数推演为十次，那么就会出现如下的情况：在第一局到第九局的过程中双方均会保持沉默，以期望建立互信关系，并在第十局指控对方，这将最终导致，二人同服刑5年。 再一次假设，双方都明确对方会使用与自己同样的策略，即知道对方会在第十局中指控自己，这样，在第九局时两者间的信任关系的建立即是没有意义的，如此类推，第八局到第一局中信任关系的建立也是没有意义的，即是十局都会互相背叛，也就是纳什均衡。也可推论，在如此的情况下，只有在囚徒困境的局数在不肯定的情况下（即双方均不知道进行的局数），才会出现互相保持沉默以获得信任关系的现象。

9 现实中的囚徒困境 贸易壁垒 军备竞赛 价格大战 囚徒困境的解决之道 多次博弈； 设立规章制度，惩罚违规者； 思想教育（效果待定）。

10

11 设对手选择A的概率为p，则 自己选择A的支付的期望为y=5p 选择B的支付的期望为y=4-3p 选择C的支付的期望为y=2+2p

12

13 其他的非合作博弈问题 每位学生从1-100中选择一个数字。选择到最接近全班平均数的2/3的学生为胜利者。在所有学生都理性的情况下，他们会选择哪一个数字?

14 由于平均数不可能大于100，因而无人会选择大于66的数
在剔除了66以上的数后，所有人的平均数不可能会大于44 以此类推，所有人最后选择的数字都会是数字1 前提：所有人都是理性的

15 两个政治候选人，为了选举须确定自己的政治立场。共有10个立场：
1、2、3、4、5、6、7、8、9、10。 第个立场都有10%选票。两个候选人要在一系列的政治主张中选择一个，已知每个立场的选民会把自己的票投给与自己立场最接近的候选人，问如果你是其中一个候选人，且想要最大化地获得选票，应当选择哪一个立场

16 当2号候选人选择1号策略S1时 U1(1、1)[表示2号候选人选择S1，1号候选人选择S1]为50% < U1(2、1)[表示2号候选人选择S1，1号候选人选择S1]为90% 当2号候选人选择2号策略S2时 U1(1,2)=10% < U1(2,2)=50% 当2号候选人选择3号策略S3时 U1(1,3)=15% < U1(2,3)=20% 当2号候选人选择4号策略S4时 U1(1,4)=20% < U1(2,4)=25%

17 剔除劣势策略S1，S10 U1(2,2)=50% < U1(3,2)=80% 当2号候选人选择3号策略S3时

18 5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。
他们决定这么分： 1、抽签决定自己的号码（1，2，3，4，5） 　2、首先，由1号提出分配方案，然后大家5人进行表决，当且仅当半数和超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。 　3、如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当半数和超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。 　4。以次类推...... 条件：每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。 问题：第一个海盗提出怎样的分配方案才能够使自己的收益最大化