随机博弈

✍ dations ◷ 2025-04-26 13:54:27 #随机博弈

随机博弈(英语:stochastic game),或称随机赛局、随机对局,在博弈论中是一类由一个或多个参与者所进行的、具有状态概率转移的动态博弈,由劳埃德·夏普利(Lloyd Shapley)于20世纪50年代初期提出。

这类博弈由一系列阶段组成。在博弈中每一阶段的起始,博弈处于某种特定状态。每一参与者选择某种行动,然后会获得取决于当前状态和所选择行动的收益。之后,博弈发展到下一阶段,处于一个新的随机状态,这一随机状态的分布取决于先前状态和各位参与者选择的行动。在新状态中重复上述过程,然后博弈继续进行有限或无限个数的阶段。一个参与者得到的总收益常用各阶段收益的贴现和,或是各阶段收益平均值的下极限来计算。

随机博弈的组成部分有:有限参与者集 I {\displaystyle I} ;状态空间 M {\displaystyle M} (可以是有限集,也可以是可测空间 ( M , A ) {\displaystyle (M,{\mathcal {A}})} );对于每一参与者 i I {\displaystyle i\in I} ,存在行动集 S i {\displaystyle S^{i}\,} (可以是有限集,也可以是可测空间 ( S i , S i ) {\displaystyle (S^{i},{\mathcal {S}}^{i})} ); P {\displaystyle P} M × S {\displaystyle M\times S} M {\displaystyle M} 的转移概率,其中 S = × i I S i {\displaystyle S=\times _{i\in I}S^{i}} 是行动组合, P ( A m , s ) {\displaystyle P(A\mid m,s)} 是下一状态处于 A {\displaystyle A} 中的概率,而 A {\displaystyle A} 给定了当前状态 m {\displaystyle m} 和当前行动组合 s {\displaystyle s} ;从 M × S {\displaystyle M\times S} R I {\displaystyle R^{I}\,} 的收益函数 g {\displaystyle g} ,其中 g {\displaystyle g} 的第 i {\displaystyle i} 个坐标 g i {\displaystyle g^{i}\,} 是参与者 i {\displaystyle i} 的收益,而 g i {\displaystyle g^{i}\,} 是状态 m {\displaystyle m} 和行动组合 s {\displaystyle s} 的函数。

博弈以某个初始状态 m 1 {\displaystyle m_{1}} 开始。在阶段 t {\displaystyle t} 中,参与者最先观测到 m t {\displaystyle m_{t}} ,同时选择行动 s t i S i {\displaystyle s_{t}^{i}\in S^{i}} ,然后观测到行动组合 s t = ( s t i ) i {\displaystyle s_{t}=(s_{t}^{i})_{i}} ,然后以概率 P ( m t , s t ) {\displaystyle P(\cdot \mid m_{t},s_{t})} 自然选择 m t + 1 {\displaystyle m_{t+1}} 。一次随机博弈 m 1 , s 1 , , m t , s t , {\displaystyle m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots } 定义了一个收益流 g 1 , g 2 , {\displaystyle g_{1},g_{2},\ldots } ,其中 g t = g ( m t , s t ) {\displaystyle g_{t}=g(m_{t},s_{t})\,}

下面给出随机博弈的一个例子:

当前有任意个装着球的桶,每个桶中球的数目也是任意的,两位参与者轮流从中取出球,且需要遵守如下规则:

贴现因子为 λ {\displaystyle \lambda } 0 < λ 1 {\displaystyle 0<\lambda \leq 1} )的贴现博弈 Γ λ {\displaystyle \Gamma _{\lambda }} 中,参与者 i {\displaystyle i} 的收益是 λ t = 1 ( 1 λ ) t 1 g t i {\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}} n {\displaystyle n} 阶段博弈中,参与者 i {\displaystyle i} 的收益是 g ¯ n i := 1 n t = 1 n g t i {\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}

若存在有限多个状态和行动的二人零和博弈 Γ n {\displaystyle \Gamma _{n}} (各自是 Γ λ {\displaystyle \Gamma _{\lambda }} )的值为 v n ( m 1 ) {\displaystyle v_{n}(m_{1})} (各自是 v λ ( m 1 ) {\displaystyle v_{\lambda }(m_{1})} ),则 v n ( m 1 ) {\displaystyle v_{n}(m_{1})} n {\displaystyle n} 趋于无穷时收敛到一个极限,且 v λ ( m 1 ) {\displaystyle v_{\lambda }(m_{1})} λ {\displaystyle \lambda } 趋于 0 {\displaystyle 0} 时收敛到相同的极限。这一结论已被杜鲁门·彪利(Truman Bewley)和艾朗·克尔伯格(Elon Kohlberg)于1976年证明。

非贴现博弈 Γ {\displaystyle \Gamma _{\infty }} 中,参与者 i {\displaystyle i} 的收益是各阶段收益平均值的极限。在定义二人零和博弈 Γ {\displaystyle \Gamma _{\infty }} 的值与非零和博弈 Γ {\displaystyle \Gamma _{\infty }} 的均衡收益之前需要注意一些事情:若对于每一 ε > 0 {\displaystyle \varepsilon >0} 都有正整数 N {\displaystyle N} 、参与者1的策略 σ ε {\displaystyle \sigma _{\varepsilon }} 和参与者2的策略 τ ε {\displaystyle \tau _{\varepsilon }} ,二人零和随机博弈 Γ {\displaystyle \Gamma _{\infty }} 的一致值(uniform value) v {\displaystyle v_{\infty }} 存在,这样对于每一 σ {\displaystyle \sigma } τ {\displaystyle \tau } 和每一 n N {\displaystyle n\geq N} ,博弈中由 σ ε {\displaystyle \sigma _{\varepsilon }} τ {\displaystyle \tau } 定义的概率的 g ¯ n i {\displaystyle {\bar {g}}_{n}^{i}} 期望至少为 v ε {\displaystyle v_{\infty }-\varepsilon } ,由 σ {\displaystyle \sigma } τ ε {\displaystyle \tau _{\varepsilon }} 定义的概率的 g ¯ n i {\displaystyle {\bar {g}}_{n}^{i}} 期望至多为 v + ε {\displaystyle v_{\infty }+\varepsilon } 。让·弗朗索瓦·梅顿斯(Jean Francois Mertens)和亚伯拉罕·奈曼(Abraham Neyman)于1981年证明二人零和随机博弈具有一致值。

若参与者数量有限且行动集和状态集有限,则有限阶段随机博弈总有纳什均衡,对于总收益是贴现和的无限多阶段随机博弈也是如此。尼古拉斯·维勒(Nicolas Vieille)已经证明当总收益是各阶段收益平均值的下极限时,所有具有有限状态和行动空间的二人随机博弈都有近似纳什均衡。不过,当参与者多于2名时,随机博弈是否存在这类均衡仍是一个极具挑战性的开放性问题。

随机博弈在经济学、演化生物学和计算机网络中都有应用。事实上,随机博弈是重复博弈这类每一阶段都处于相同状态的博弈的一般化形式。

有关随机博弈的最全面的参考书籍是奈曼和索林编著的文集。菲拉尔和乌瑞兹所著的书籍更为基础,书中提供了马尔可夫决策过程(MDP)和二人随机博弈理论的严密的统一处理方法。他们创造了Competitive MDPs这一术语来概括一人和二人随机博弈。

相关

  • 头孢克肟头孢克肟(Cefixime)是一种口服的第三代头孢菌素抗生素,通常用于治疗淋病、扁桃腺炎和咽炎。常用剂量为400毫克。头孢克肟在美国以“Suprax”的名称发售,直到2003年,当它的专利失
  • 葡萄球菌黄素葡萄球菌黄素(英语:Staphyloxanthin)是一种由一些金黄色葡萄球菌菌种制造的类胡萝卜素。这种色素给了金黄色葡萄球菌它的颜色。葡萄球菌黄素在金黄色葡萄球菌的感染中扮演了重
  • 酥油酥油是以驯养的犛牛(学名:Bos grunniens)之产乳制成的奶油。它是中亚南部和青藏高原的放牧人家最重要的主食和贸易食品之一。酥油脂质含量是牛奶的两倍,口感近似起司甚于奶油。
  • 船蛆船蛆(学名:Teredo navalis),又名凿船虫、船食虫、船喰虫,是双壳纲的一种海洋动物,属于海螂目蛀船蛤科蛀船蛤属。本物种分布于韩国、中国大陆、台湾及南中国海,常栖息在温带及热带,尤
  • 果冻果冻(又称啫喱、明胶点心、吉利丁点心,英语gelatin dessert,jelly)是一种西方甜食,呈半固体状,由食用明胶加水、糖、果汁制成。市面出售的果冻有已经凝固成形的,也有需要食用者自行
  • 乙酰-smallL/small-肉碱乙酰左式肉碱(英语:Acetyl-L-carnitine,简写为ALCAR)是左式肉碱的一种酯化物,也是一种常见的食品添加剂。广泛存在于植物和动物组织中。(声明:一般人将“左式 L-form”“右式 D-for
  • 男欢女爱《一个男人和一个女人》(法语:Un homme et une femme)是一部1966年的浪漫爱情法国电影,克劳德·勒鲁什担任影片的导演、制片人,而且还是编剧之一,尚-路易·特罕狄酿和阿努克·艾梅
  • 管中闵管中闵(1956年8月15日-),台湾中研院院士、计量经济学学者,生于台北市,现任国立台湾大学校长暨财务金融学系讲座教授、经济学系合聘教授、中央研究院经济研究所合聘研究员。台北市
  • 政治工作局中国人民解放军军徽中国共产党中央军事委员会办公厅政治工作局,位于北京市,是中央军委办公厅下属局,负责该办公厅的政治工作。2016年改革前,中央军委办公厅设有中央军委办公厅政
  • 约克夏猪大白猪(Large White),也称为英国大白,是起源于约克郡(Yorkshire)的一个家猪品种,因此也称约克夏猪。这一品种在1868年首次得到认可,是北美的美国约克夏猪的品种来源。大白是世界上最