扩展形式的博弈

✍ dations ◷ 2025-04-25 18:14:13 #扩展形式的博弈

博弈论中,与正则形式相应,扩展形式(英语:Extensive-form game)通过树来描述博弈。每个节点(称作决策节点)表示博弈进行中的每一个可能的状态。博弈从唯一的初始节点开始,通过由参与者决定的路径到达终端节点,此时博弈结束,参与者得到相应的收益。每个非终端节点只属于一个参与者;参与者在该节点选择其可能的行动,每个可能的行动通过边从该节点到达另一个节点。

和正则形式不同,扩展形式允许互动的显式模型(explicit modeling of interactions),互动中,一个参与者可以在博弈中多次行动,并且在不同的状态中可以做出不同的行为。

完整的扩展形式表述包括:

右图是一个双人博弈:1和2。每个非终端节点上的数字表示该节点所属的参与者。终端节点上的数字表示参与者的收益(例如:2,1表示参与者1得到2,参与者2得到1)。图片里每个边上的符号是这个边所代表的行动的名字。

初始节点属于参与者1,表示该参与者先动。博弈顺序如下:参与者1选择或者;参与者2观察到参与者1的选择,然后选择或者,最后得到最终收益。四个终端节点代表四个结果:(U,U'),(U,D'),(D,U')和(D,D')。每个结果得到的收益分别是(0,0),(2,1),(1,2)和(3,1)。

如果参与者1选择,参与者2为了最大化收益,会选择,最后参与者1只能得到1。但是如果参与者1选择,参与者2为了最大化收益,会选择,此时参与者1得到2。所以参与者1会选择,参与者2选择。即是子博弈完美均衡

参与者在一个特定的决策节点上可能有无数种可能的行动可以选择。其表示方法是用弧形来连接从该决策节点延伸出的两条边。如果行动空间是在两个数字之间的闭联集(continuum),那么把这两个表示上下界限的数字分别放在弧的上方和下方,并用一个变量来表示其支付。此时无数个决策节点可以用一个在弧中心的节点所代替。这种表示方式同样可以用在一个有限的行动空间中,只要该行动空间足够大,此时不可能用边来表示每个行动。

左侧的树表示这样一个博弈:该博弈或者有一个无限行动空间(任何0到5000的实数),或者有一个很大的行动空间(可能是任何在0到5000的整数)。如果我们在这里假设它表示两个参与Stackelberg竞争的企业。公司的支付表示在左边,其中q1和q2表示先行者公司以及追随者公司分别采用的策略,c1和c2是常数(表示公司的机会成本)。该博弈的子博弈完美纳什均衡可以通过对支付函数求追随者策略变量(q2)的一阶偏导数表示其利润最大化,并求出其最优反应函数, q 2 ( q 1 ) = ( 5000 q 1 c 2 ) / 2 {\displaystyle q2(q1)=(5000-q1-c2)/2} 。用同样的方法计算先行者的最优反应函数,并假定先行者知道追随者会选择上述的行动,通过一阶偏导数来解出 q 1 = ( 5000 + c 2 2 c 1 ) / 2 {\displaystyle q1*=(5000+c2-2c1)/2} 。在将q1*代入到追随者的最优反应函数中, q 2 = ( 5000 + 2 c 1 3 c 2 ) / 4 {\displaystyle q2*=(5000+2c1-3c2)/4} ,此时(q1*,q2*)就是子博弈完美纳什均衡。如果假设 c1=c2=1000,那幺子博弈完美纳什均衡的解就是(2000,1000)。

树图清楚地表示了参与者1先动,参与者2观察到参与者1的行动。然而,一些博弈并不是这样。参与者并不是一直能观察到另一个人的选择(例如,同时行动或者行动被隐藏)。信息集是决策节点的组合:

完美信息的博弈是指在博弈的任何阶段,每个参与者都清楚博弈之前发生的所有行动,也即每个信息集都是一个单元素集合。没有完美信息的博弈具有不完美信息。

左图中的博弈中,参与者2行动时不知道参与者1的选择,除此之外和第一个博弈相同。第一个博弈具有完美信息;而左图中的没有。如果两个参与者都是理性的,并且都知道对方也是理性人,对方知道的信息,自己也能获得(即参与者1知道参与者2知道参与者1是理性的,参与者2同样也知道,如此循环下去),

博弈论是一种数学理论,所以上述的博弈树结构可以转化为公式表达。

扩展形式的有限树是这样一个结构 Γ = K , H , , { A ( H ) } H H ] , a , ρ , u {\displaystyle \Gamma =\langle {\mathcal {K}},\mathbf {H} ,,\{A(H)\}_{H\in \mathbf {H} }],a,\rho ,u\rangle } 其中:

相关

  • 病程人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学病程,是指一个疾病或者其治疗的持续时
  • 西伯利亚坐标:60°0′N 105°0′E / 60.000°N 105.000°E / 60.000; 105.000地理上的西伯利亚西伯利亚(俄语:Сибирь,罗马化:Sibir)是乌拉山脉以东的广大地区的总称,占北亚的大部分,面
  • 掌骨掌骨是手部骨骼中间的部分,连接在近端手指及腕骨之间,而腕骨再与前臂连结。掌骨由五个圆柱状的骨头组成,由桡骨到尺骨侧依序命名(I-V)。每个由一块主体及两个极端组成。人体手部
  • 丁奎岭丁奎岭(1966年3月15日-),河南永城人,中国化学家。1985年毕业于郑州大学化学系,1990年获南京大学化学系博士学位。2013年当选为中国科学院院士。曾任中国科学院上海有机化学研究所
  • 宏(英语:Macro),是一种批量处理的称谓。计算机科学里的宏是一种抽象(Abstraction),它根据一系列预定义的规则替换一定的文本模式。解释器或编译器在遇到宏时会自动进行这一模式替换
  • 暗之末裔《暗之末裔》(日语:闇の末裔)是日本漫画家松下容子在花与梦(白泉社)杂志上连载的少女漫画,2000年改编为电视动画。于2006年6月号开始长期休载,后来传出2011年10月1日号继续连载的消
  • 克劳黛·考尔白克劳黛·考尔白(英语:Claudette Colbert,1903年9月13日-1996年7月30日),美国电影及舞台剧演员,好莱坞三、四十年代的知名影星。她出生于法国巴黎,幼时举家移民美国,原名克劳黛·莉莉
  • 宫古群岛宫古群岛(日语:宮古列島/みやこれっとう Miyako Rettō)为琉球列岛西部的岛屿群,位于钓鱼台群岛和八重山群岛的东方。在日本的划分中和八重山群岛、钓鱼台群岛合称为先岛群岛。
  • 世界篮球锦标赛国际篮联篮球世界杯(简称世界杯男篮)是国际篮球联合会主办的一项国际性男子篮球赛事,自1950年起每四年举办一次。冠军将获得奥运男篮参赛资格。2012年1月国际篮联宣布男篮世锦
  • 玛丽·碧克馥玛丽·毕克馥(英语:Mary Pickford,1892年4月8日-1979年5月29日),加拿大电影演员,曾获得过奥斯卡最佳女主角奖和奥斯卡终身成就奖。她有很多昵称,如"美国甜心"("America's Sweetheart"