博弈论课程在线辅导找专注留学生课程辅导的考而思,博弈论专业老师在线一对一辅导,确保你的博弈论作业,博弈论考试顺利通过。
Doval, Laura, and Vasiliki Skreta. "Mechanism design with limited commitment."arXiv preprint arXiv:1811.03579 (2018). ECMA R&R
把mechanism定义成一个tuple
R为input message (agent的report)
S为output message (principal观测到的结果)
b为communication device,把R映射到S
a为assignment rule,把S映射到allocation A上
agent的private information 为
full commitment下
根据revelation principle我们有SP的optimal direct mechanism
===========
假设现在limited commitment
动态环境里principal每期选择一个mechanism
s.t
带星号表示finite support的概率
然后这种环境下的类似revelation principle的机制被叫做canonical mechanism
timline
t期开始时,收到公共信号
principal选择当期的机制Mt
agent选择策略p :加入 (1)或者不加入 (0) (不加入则获得一个null allocation)
加入则释放私人input
根据r生成分布
释放公共output
根据s生成分布
释放allocation ( 表示t期时可能的allocation)
公共历史(=principal知道的)为
私人历史(=agent知道的)为
agent在t期的策略为一个pair 分别是参加不参加和参加的话input什么message
这里下标表示agent的type v
principal在t期的策略为根据历史随机选择一个机制 ,其中M为所有机制的集合
principal额外还有一个belief,关于两点:agent的type和agent的私人历史
这里 为所有可能的私人历史集合(consistent w.r.t. 公共历史)
两个player的payoff只关于type v和allocation
这样一个动态博弈被叫做mechanism selection game。而如果只考虑选择canonical mechanism, 其reduced form被叫做 canonical (mechanism selection )game
其solution concept为PBE: 所有人的策略满足sequential rationality,belief满足贝叶斯法则(on path)
Main THM (revelation principle的变种)
对mechanism selection game的任何PBE而言 ,存在一个payoff equivalent的PBE满足
1) 每期选择的机制都是一个canonical mechanism
2) IR: 此PBE下
3) SP:
4) belief Bayes plausible (recommended beliefs coincide with realized beliefs)
又有
Prop: Any equilibrium payoff of the canonical game can be attained in an equilibrium
of the mechanism selection game.
PS:定理的第四点最有趣,因为它将问题转换成了一个information design的Bayes game (当然这是一个带了IR和SP的constrained information design):
principal在t期当sender发一个belief给t+1期的principal,t+1期的principal作为receiver根据这个updated belief去选择机制 (这个部分主要在文章的第五章,通过构造dual problem)
计算出来的结果是这个discount要大于1/3才有理由先采取合作策略,由于案例中概率是0.75,符合条件,所以应该采取恐怖扳机策略。不过老师在计算what of reward的时候用的是2(a+a^2+a^3+……),有些疑惑为什么不用乘以1-a,因为比如就继续了两次,应该是a^2*(1-a)才是这个事件的概率吧,如果是这种计算方式,计算出来概率要大于1/2才行。
对于任意M 1,N(或M,N 1)的矩阵,假设存在后手必胜策略
先手必定可以在第一步采用策略使得矩阵M 1,N转变为M,N矩阵
由于对于M 1,N矩阵后手存在必胜策略
那么对于一个任意M,N的矩阵,存在先手必胜策略
令M’=M 1,则对于M,N存在先手必胜策略
这与假设矛盾,所以假设不成立
因此对于M,N=1的情况下,M 1,N矩阵不存在后手必胜策略
即当且仅当M=N=1时,有矩阵1x1存在后手必胜策略
1,不要选择劣势策略。2、理性选择导致次优结果。3、学会换位思考。4、将欲取之,必先知之。5、大部分人都是自私的。
不够严谨
1.劣势策略是指严格下策吗?严格下策在博弈中自然会被排除,但如果你所指的是纳什均衡相对的帕累托上策,那相对劣势的纳什均衡可能还真是选择的必然
2.理性选择不一定是次优结果,在重复博弈中完全有机会通过实施触发策略实现最优结果
3.对于完全但不完美信息动态博弈,不完美信息一方没有能力换位思考,因为两者信息严重不对称
4.同样是对于不完美信息动态博弈,对于不完美信息一方者,你都不知道,怎么取之?
5.博弈论的前提是理性人,有限理性等,而不是大部分是自私的,自私这个东西人人都有,但自私更深层次的是利益最大化,成本最小化,效用最大化等动机,并且这种自私并非是单独的自私,也可能是群体性自私,比如说国际卡特尔,关税同盟等关于MxN取石子问题:该问题一般被称为Chomp游戏。
可以证明除了1x1的情况外,先手有必胜策略。其他网友的评论已经有给出证明方法了,用反证法结合一个小技巧即可证明。一般也称该小技巧为strategy stealing argument。原始证明由 David Gale给出。
然而,该证明方法只给出了结论,并未能给出具体的必胜策略。我目前查到的资料显示该问题的具体必胜策略目前仍未解决。只有一些特例的必胜策略被给出,比如M=N的情况,或者2xN的情况,以及3xN的情况在2002年被解决。
此外,当M和N的规模较小时,计算机编程可以给出具体的必胜策略(应该也是用SG函数)。N和M规模较大时,目前无法解决。关于MxN取石子问题:该问题一般被称为Chomp游戏。
可以证明除了1x1的情况外,先手有必胜策略。其他网友的评论已经有给出证明方法了,用反证法结合一个小技巧即可证明。一般也称该小技巧为strategy stealing argument。原始证明由 David Gale给出。
然而,该证明方法只给出了结论,并未能给出具体的必胜策略。我目前查到的资料显示该问题的具体必胜策略目前仍未解决。只有一些特例的必胜策略被给出,比如M=N的情况,或者2xN的情况,以及3xN的情况在2002年被解决。
此外,当M和N的规模较小时,计算机编程可以给出具体的必胜策略(应该也是用SG函数)。N和M规模较大时,目前无法解决。
目前只有反证法的那位网友是对的,其他的构造性证明方法都为问题。谁能给个靠谱的构造性证明吗?
这是个典型的impartial combinatorial game,我反向推导可以得到几个P-position,比如呈L型且竖直方向的点数和水平方向的点数相同时是一个P-position,仅有两行且第2行比第1行少1个点时也是P-position,总共N行:最底下两行为N 1个点,上面的N-2行为2个点时也是个P-position。。。
但是NxM完整布局的情况实在过于复杂,我研究了很多天也没有找到一个玩法可以保证先手必胜(但是我们知道先手是必胜的)。
凡来源标注“考而思”均为考而思原创文章,版权均属考而思教育所以,任何媒体、网站或个人不得转载,否则追究法律责任。
kaoersi03