无名氏定理:修订间差异
WhitePhosphorus(留言 | 贡献) 内容扩充 |
WhitePhosphorus(留言 | 贡献) 内容扩充 |
||
第1行: | 第1行: | ||
在[[博弈论]]中,'''无名氏定理'''({{lang-en|folk theorems}})是一类描述重复博弈[[纳什均衡]]的定理。<ref name="Friedman1971">{{citation|last=Friedman|first=J.|year=1971|title=A non-cooperative equilibrium for supergames|journal=Review of Economic Studies|volume=38|pages=1–12|doi=10.2307/2296617|jstor=2296617|issue=1}}</ref>{{noteTag|1=数学中,“无名氏定理”一词通常表示人们普遍同意,且已经经过讨论却未曾发表的定理。为了让名字更直白一些,Roger Myerson推荐把这类定理叫做“一般可行性定理”({{lang-en|general feasibility theorem}}),参见Myerson, Roger B. ''Game Theory, Analysis of conflict'', Cambridge, Harvard University Press (1991)}}起初,无名氏定理仅关注无穷博弈的纳什均衡。在20世纪50年代,这类定理已经广受博弈论学者知晓,但并没有人发表它,所以称为无名氏定理。1971年发表的Friedman定理考虑了无穷博弈的一系列{{tsl|en|Subgame perfect equilibrium|子博弈完美均衡|子博弈精炼纳什均衡}}(SPE),把定理的初始版本推广到了更强的均衡概念上。<ref>{{cite book |title= A Primer in Game Theory |authors= R. Gibbons |publisher=[[Harvester Wheatsheaf]] |isbn= 0-7450-1160-8 |year=1992|pages=89}}</ref> |
在[[博弈论]]中,'''无名氏定理'''({{lang-en|folk theorems}})是一类描述重复博弈[[纳什均衡]]的定理。<ref name="Friedman1971">{{citation|last=Friedman|first=J.|year=1971|title=A non-cooperative equilibrium for supergames|journal=Review of Economic Studies|volume=38|pages=1–12|doi=10.2307/2296617|jstor=2296617|issue=1}}</ref>{{noteTag|1=数学中,“无名氏定理”一词通常表示人们普遍同意,且已经经过讨论却未曾发表的定理。为了让名字更直白一些,Roger Myerson推荐把这类定理叫做“一般可行性定理”({{lang-en|general feasibility theorem}}),参见Myerson, Roger B. ''Game Theory, Analysis of conflict'', Cambridge, Harvard University Press (1991)}}起初,无名氏定理仅关注无穷博弈的纳什均衡。在20世纪50年代,这类定理已经广受博弈论学者知晓,但并没有人发表它,所以称为无名氏定理。1971年发表的Friedman定理考虑了无穷博弈的一系列{{tsl|en|Subgame perfect equilibrium|子博弈完美均衡|子博弈精炼纳什均衡}}(SPE),把定理的初始版本推广到了更强的均衡概念上。<ref>{{cite book |title= A Primer in Game Theory |authors= R. Gibbons |publisher=[[Harvester Wheatsheaf]] |isbn= 0-7450-1160-8 |year=1992|pages=89}}</ref> |
||
无名氏定理指出,如果参与者对未来足够有耐心(也即贴现因子<math> \delta \to 1 </math>),对于任意可行、满足个人理性假设的一组收益<math>v=(v_1, \cdots, v_n)</math>,都存在着一个子博弈精炼纳什均衡,使得第<math>i</math>个参与者的平均收益就是<math>v_i</math>。<ref>{{cite web|url = http://web.stanford.edu/~jdlevin/Econ%20203/RepeatedGames.pdf |title= Bargaining and Repeated Games|author=Jonathan Levin| year = 2002}}</ref>换言之,任何程度的合作都可以通过一个子博弈精炼纳什均衡来达成。 |
无名氏定理指出,如果参与者对未来足够有耐心(也即贴现因子<math> \delta \to 1 </math>),对于任意可行、满足个人理性假设的一组收益<math>v=(v_1, \cdots, v_n)</math>,都存在着一个子博弈精炼纳什均衡,使得第<math>i</math>个参与者的平均收益就是<math>v_i</math>。<ref>{{cite web|url = http://web.stanford.edu/~jdlevin/Econ%20203/RepeatedGames.pdf |title= Bargaining and Repeated Games|author=Jonathan Levin| year = 2002}}</ref>换言之,任何程度的合作(只要是可行的且满足个人理性)都可以通过一个子博弈精炼纳什均衡来达成。 |
||
例如,在只有一期的[[囚徒困境]]中,两个参与者都选择合作并非纳什均衡,唯一的纳什均衡就是两个人都选择背叛。根据无名氏定理,如果囚徒困境重复无穷多次,并且参与者足够有耐心,就会存在两个参与者都合作的纳什均衡。但在有限期囚徒困境中,最后一期一定会双方都背叛,从而倒数第二期双方也会背叛,以此类推,唯一的子博弈精炼纳什均衡就是双方一直背叛,不会有合作出现。 |
例如,在只有一期的[[囚徒困境]]中,两个参与者都选择合作并非纳什均衡,唯一的纳什均衡就是两个人都选择背叛。根据无名氏定理,如果囚徒困境重复无穷多次,并且参与者足够有耐心,就会存在两个参与者都合作的纳什均衡。但在有限期囚徒困境中,最后一期一定会双方都背叛,从而倒数第二期双方也会背叛,以此类推,唯一的子博弈精炼纳什均衡就是双方一直背叛,不会有合作出现。 |
||
第7行: | 第7行: | ||
== 前提 == |
== 前提 == |
||
重复博弈中的纳什均衡应该满足以下两个性质: |
重复博弈中的纳什均衡应该满足以下两个性质: |
||
* 个人理性:最终支付至少要大弱占优于参与者能得到的最大收益的最小值 |
* 个人理性:最终支付至少要大弱占优于参与者能得到的最大收益的最小值(即最小最大收益),否则他还不如选择最小最大化策略。 |
||
* 可行性:最终支付必须是一系列可能策略的[[凸组合]],因为重复博弈中参与者的最终支付就是单个博弈中收益的加权平均。 |
* 可行性:最终支付必须是一系列可能策略的[[凸组合]],因为重复博弈中参与者的最终支付就是单个博弈中收益的加权平均。 |
||
无名氏定理有若干种,有些考虑有限重复博弈,有些考虑无限重复博弈。<ref name=ZMS>{{cite book |title=Game Theory |authors=Michael Maschler, Eilon Solan & Shmuel Zamir |publisher=[[Cambridge University Press]] |isbn=978-1-107-00548-8 |year=2013 |pages=176–180}}</ref> |
无名氏定理有若干种,有些考虑有限重复博弈,有些考虑无限重复博弈。<ref name=ZMS>{{cite book |title=Game Theory |authors=Michael Maschler, Eilon Solan & Shmuel Zamir |publisher=[[Cambridge University Press]] |isbn=978-1-107-00548-8 |year=2013 |pages=176–180}}</ref> |
||
== 不考虑贴现的无穷博弈 == |
|||
在不考虑贴现的无穷博弈中,参与者都是有耐心的。在任何时间点,相同的效用带来的收益都是相同的。所以在无穷博弈中,每个参与者的收益就等于每一期博弈获取效用的总和。 |
|||
就无穷博弈而言,总收益的计算通常是平均效用取极限以后的[[下确界]]。假设第<math>t</math>期参与者<math>i</math>选择的行动是<math>x_t</math>,那么他的总收益就是: |
|||
::<math>U_i = \lim_{T\to \infty} \inf \frac{1}{T} \sum_{t=0}^{T} u_i(x_t),</math> |
|||
其中<math>u_i</math>表示每个阶段博弈中,参与者<math>i</math>的效用函数。 |
|||
这种情况下,无名氏定理指出:阶段博弈中满足个人理性且可行的行动在无穷博弈中都是纳什均衡。 |
|||
考虑{{tsl|en|Grim trigger||冷酷战略}}。所有参与者都按照预定的策略进行每一期博弈。如果在某一期中有人没有使用预定策略,从下一期开始所有人永远选择让这个人只能拿到最小最大收益的策略。这样,出偏差的人的总收益也只能是最小最大收益,所以所有人都愿意按照预定策略行事。<ref name=AumannShapley94>{{cite book|doi=10.1007/978-1-4612-2648-2_1|chapter=Long-Term Competition—A Game-Theoretic Analysis|title=Essays in Game Theory|pages=1|year=1994|last1=Aumann|first1=Robert J.|last2=Shapley|first2=Lloyd S.|isbn=978-1-4612-7621-0}}</ref><ref name="Rubinstein79" /> |
|||
=== 子博弈精炼均衡 === |
|||
上述纳什均衡不一定是一个子博弈精炼均衡。如果实施惩罚对其他人的收益影响也很大,那么惩罚就是不可信的。 |
|||
要想达到子博弈精炼均衡,每次有人偏离预定策略时,惩罚不应该一直实施下去,而只应持续到出偏差的人在那一期博弈带来的额外收益得到抵消为止。之后,大家依旧按照预定策略继续博弈。<ref name=AumannShapley94 /><ref name=OR>{{cite book|isbn=0-262-15041-7| ol=1084491M |lccn=94008308}}</ref>{{rp|146–149}} |
|||
因为计算总收益的方法是平均收益取极限,所以有限期的惩罚并不会影响总收益。这样,这就是一个子博弈精炼纳什均衡。 |
|||
== 注释 == |
== 注释 == |
2018年5月6日 (日) 05:24的版本
在博弈论中,无名氏定理(英語:folk theorems)是一类描述重复博弈纳什均衡的定理。[1][註 1]起初,无名氏定理仅关注无穷博弈的纳什均衡。在20世纪50年代,这类定理已经广受博弈论学者知晓,但并没有人发表它,所以称为无名氏定理。1971年发表的Friedman定理考虑了无穷博弈的一系列子博弈精炼纳什均衡(SPE),把定理的初始版本推广到了更强的均衡概念上。[2]
无名氏定理指出,如果参与者对未来足够有耐心(也即贴现因子),对于任意可行、满足个人理性假设的一组收益,都存在着一个子博弈精炼纳什均衡,使得第个参与者的平均收益就是。[3]换言之,任何程度的合作(只要是可行的且满足个人理性)都可以通过一个子博弈精炼纳什均衡来达成。
例如,在只有一期的囚徒困境中,两个参与者都选择合作并非纳什均衡,唯一的纳什均衡就是两个人都选择背叛。根据无名氏定理,如果囚徒困境重复无穷多次,并且参与者足够有耐心,就会存在两个参与者都合作的纳什均衡。但在有限期囚徒困境中,最后一期一定会双方都背叛,从而倒数第二期双方也会背叛,以此类推,唯一的子博弈精炼纳什均衡就是双方一直背叛,不会有合作出现。
前提
重复博弈中的纳什均衡应该满足以下两个性质:
- 个人理性:最终支付至少要大弱占优于参与者能得到的最大收益的最小值(即最小最大收益),否则他还不如选择最小最大化策略。
- 可行性:最终支付必须是一系列可能策略的凸组合,因为重复博弈中参与者的最终支付就是单个博弈中收益的加权平均。
无名氏定理有若干种,有些考虑有限重复博弈,有些考虑无限重复博弈。[4]
不考虑贴现的无穷博弈
在不考虑贴现的无穷博弈中,参与者都是有耐心的。在任何时间点,相同的效用带来的收益都是相同的。所以在无穷博弈中,每个参与者的收益就等于每一期博弈获取效用的总和。
就无穷博弈而言,总收益的计算通常是平均效用取极限以后的下确界。假设第期参与者选择的行动是,那么他的总收益就是:
其中表示每个阶段博弈中,参与者的效用函数。
这种情况下,无名氏定理指出:阶段博弈中满足个人理性且可行的行动在无穷博弈中都是纳什均衡。
考虑冷酷战略。所有参与者都按照预定的策略进行每一期博弈。如果在某一期中有人没有使用预定策略,从下一期开始所有人永远选择让这个人只能拿到最小最大收益的策略。这样,出偏差的人的总收益也只能是最小最大收益,所以所有人都愿意按照预定策略行事。[5][6]
子博弈精炼均衡
上述纳什均衡不一定是一个子博弈精炼均衡。如果实施惩罚对其他人的收益影响也很大,那么惩罚就是不可信的。
要想达到子博弈精炼均衡,每次有人偏离预定策略时,惩罚不应该一直实施下去,而只应持续到出偏差的人在那一期博弈带来的额外收益得到抵消为止。之后,大家依旧按照预定策略继续博弈。[5][7]:146–149
因为计算总收益的方法是平均收益取极限,所以有限期的惩罚并不会影响总收益。这样,这就是一个子博弈精炼纳什均衡。
注释
- ^ 数学中,“无名氏定理”一词通常表示人们普遍同意,且已经经过讨论却未曾发表的定理。为了让名字更直白一些,Roger Myerson推荐把这类定理叫做“一般可行性定理”(英語:general feasibility theorem),参见Myerson, Roger B. Game Theory, Analysis of conflict, Cambridge, Harvard University Press (1991)
参考文献
- ^ Friedman, J., A non-cooperative equilibrium for supergames, Review of Economic Studies, 1971, 38 (1): 1–12, JSTOR 2296617, doi:10.2307/2296617
- ^ R. Gibbons. A Primer in Game Theory. Harvester Wheatsheaf. 1992: 89. ISBN 0-7450-1160-8.
- ^ Jonathan Levin. Bargaining and Repeated Games (PDF). 2002.
- ^ Michael Maschler, Eilon Solan & Shmuel Zamir. Game Theory. Cambridge University Press. 2013: 176–180. ISBN 978-1-107-00548-8.
- ^ 5.0 5.1 Aumann, Robert J.; Shapley, Lloyd S. Long-Term Competition—A Game-Theoretic Analysis. Essays in Game Theory. 1994: 1. ISBN 978-1-4612-7621-0. doi:10.1007/978-1-4612-2648-2_1.
- ^ 引用错误:没有为名为
Rubinstein79
的参考文献提供内容 - ^ . ISBN 0-262-15041-7. LCCN 94008308. OL 1084491M. 缺少或
|title=
为空 (帮助)
|