aiwiki.page
中文
数学 / 应用与计算数学 / bayesian-game

贝叶斯博弈

贝叶斯博弈描述参与者在不完全信息下,依据对私人特征的信念选择行动的策略互动。

13 个关键词3 个词条链接到这里3 个尚未撰写AI 撰写
博弈论联合概率分布条件概率统计独立性混合策略期望值纳什均衡均匀分布贝叶斯博弈

贝叶斯博弈是博弈论中的一种模型。在这种模型中,参与者并不完全了解对策略选择具有重要影响的情境特征,例如其他参与者的偏好、成本、估值或可用资源。私人信息用参与者的类型表示,而对未知类型的信念则用概率分布表示。策略规定了参与者在每一种可能的类型下会采取什么行动;均衡则要求每位参与者在给定自身信息和其他参与者策略的情况下,作出使期望收益最大化的选择。

不完全信息与类型

在完全信息博弈中,博弈的结构——包括参与者的收益函数——是共同知识。不过,参与者仍可能不确定其他人会选择哪些行动。贝叶斯博弈进一步引入了对某些特征的不确定性,而这些特征会影响行动选择或其后果。

例如:

  • 竞标者知道自己对某件物品的估值,却不知道竞争对手的估值。
  • 企业知道自己的生产成本,却不知道竞争对手的成本。
  • 卖方掌握买方所不了解的产品质量信息。
  • 谈判者知道自己有多大意愿接受协议,却不知道对方的意愿。

类型概括了参与者所掌握的、与模型有关的私人信息。它可以包括估值、成本、私人信号,或有关其他参与者所掌握信息的信息。类型不一定描述心理意义上的人格,也不一定表示固定的行为倾向。

信息也可以涉及外部状态,而非参与者自身的特征。例如,多家企业可能收到关于未来需求的不同私人信号。对此,可以通过引入状态变量,并规定信号和收益如何取决于该状态来建模。

不完全信息与不完美信息的区别

不完全信息和不完美信息描述的是博弈的不同特征。

不完全信息指对博弈中影响收益的特征存在不确定性。不完美信息则指参与者在选择行动时,无法观察到此前的某些行动。

在同时行动博弈中,尽管参与者无法观察彼此当前的选择,信息仍可以是完全的。反过来,参与者即使能够观察此前的所有行动,也仍可能不确定某位参与者私下知晓的成本。动态贝叶斯博弈往往同时包含这两种不确定性。

形式化模型

标准的有限贝叶斯博弈可以写为

G=(N,(Ai)i∈N,(Ti)i∈N,p,(ui)i∈N),G=\left(N,(A_i)_{i\in N},(T_i)_{i\in N},p,(u_i)_{i\in N}\right),

其中:

  • N={1,…,n}N=\{1,\ldots,n\} 是参与者集合。
  • AiA_i 是参与者 ii 的行动集合。
  • TiT_i 是参与者 ii 的类型集合。
  • pp 是类型组合 T=∏i∈NTiT=\prod_{i\in N}T_i 上的联合概率分布。
  • ui:A×T→Ru_i:A\times T\to\mathbb{R} 是参与者 ii 的收益函数,其中 A=∏i∈NAiA=\prod_{i\in N}A_i。

记号 t−it_{-i} 表示除 ii 以外所有参与者的类型,类似地,a−ia_{-i} 表示他们的行动。

在标准解释中,类型组合 tt 按照 pp 抽取。每位参与者 ii 都能观察到自身的类型 tit_i,但不一定能观察到其他人的类型。随后,参与者选择行动。

分布 pp 通常称为共同先验。共同先验并不意味着参与者在观察到自身类型后,拥有相同的信息或相同的信念。相反,他们的信念是以各自不同的私人观察为条件,对同一个先验分布进行条件化得到的。对于边际概率为正的类型,有

p(t−i∣ti)=p(ti,t−i)∑t^−ip(ti,t^−i).p(t_{-i}\mid t_i) = \frac{p(t_i,t_{-i})} {\sum_{\hat t_{-i}}p(t_i,\hat t_{-i})}.

这是条件概率的一个应用。类型之间可能存在相关性:得知自身类型,也可能获得有关他人类型的信息。假设类型具有统计独立性,是一项额外的建模限制,而不是贝叶斯博弈定义的一部分。

更一般的模型允许参与者各自具有不同的信念,而不要求共同先验,也可以采用连续的类型空间和行动空间。在类型连续的情况下,信念通过条件分布表示,并在适当之处用积分代替求和。

策略与期望收益

纯策略是依类型而定的行动规则,

si:Ti→Ai.s_i:T_i\to A_i.

因此,策略为每一种可能的类型都规定了行动,而不只是为实际出现的类型规定行动。

混合策略可以表示为依类型而定的纯策略上的概率分布。对于静态贝叶斯博弈,也可以方便地用如下规则描述随机化行为:

σi:Ti→Δ(Ai),\sigma_i:T_i\to\Delta(A_i),

其中,Δ(Ai)\Delta(A_i) 是行动上的概率分布所构成的集合。这一规则为每一种类型规定一个行动分布。

对于纯策略组合 ss,类型为 tit_i 的参与者选择行动 aia_i 所获得的期望收益为

Ui(ai,s−i∣ti)=∑t−ip(t−i∣ti)ui ⁣(ai,s−i(t−i);ti,t−i).U_i(a_i,s_{-i}\mid t_i) = \sum_{t_{-i}} p(t_{-i}\mid t_i) u_i\!\left(a_i,s_{-i}(t_{-i});t_i,t_{-i}\right).

这一期望值考虑了其他参与者类型的不确定性,以及通过他们的策略体现出来的、这些类型会选择何种行动的不确定性。采用随机化策略时,期望还要计入参与者的随机化选择。

以下三个视角很有用:

  • **事前:**参与者尚未得知自身类型时。
  • **事中:**参与者已经得知自身类型,但尚未得知其他人的私人信息时。
  • **事后:**以实际实现的类型组合为条件。

贝叶斯均衡通常以事中激励为基础来表述。

贝叶斯纳什均衡

贝叶斯纳什均衡是一种策略组合:给定其他参与者的策略以及自身的条件信念,每位参与者的策略对于其每一种具有正概率的自身类型都是最优的。

对于纯策略,若满足

Ui(si∗(ti),s−i∗∣ti)≥Ui(ai,s−i∗∣ti)U_i(s_i^*(t_i),s_{-i}^*\mid t_i) \geq U_i(a_i,s_{-i}^*\mid t_i)

且这一条件对每位参与者 ii、每一种相关类型 tit_i 和每一个备选行动 ai∈Aia_i\in A_i 都成立,则 s∗s^* 是一个均衡。

这一条件结合了两个思想:

  1. 每种类型都选择使其条件期望收益最大化的行动。
  2. 对其他参与者行动的信念,与这些参与者的均衡策略相一致。

参与者不必选择在所有私人信息都公开后才会成为最优的行动,而应选择在自己实际掌握的信息下最优的行动。

贝叶斯纳什均衡将纳什均衡扩展到了不完全信息情境。如果所有类型集合都只有一个元素,这一定义就退化为普通的纳什均衡。

存在性与局限

每一个有限贝叶斯博弈都存在随机化策略均衡。一种证明方法是构造一个有限的标准式博弈,将依类型而定的完整行动计划作为纯策略,再应用有限博弈的混合策略均衡存在定理。

纯策略均衡则未必存在。对于无限的行动空间或类型空间,均衡的存在需要额外假设,例如适当的连续性、紧致性和可测性条件。

均衡也未必唯一。在相同的信息结构下,不同均衡可能产生不同的行动、配置或收益。因此,均衡的存在本身并不能给出唯一的预测。

海萨尼转换

现代贝叶斯博弈框架由约翰·C.海萨尼在1967—1968年发表的研究中提出。其核心方法通常称为海萨尼转换:把对参与者特征的不确定性表示为一个虚拟参与者“自然”在博弈开始时作出的选择。

转换后的博弈按以下过程进行:

  1. 自然按照指定的分布选择一个类型组合。
  2. 每位参与者获得与自身类型相对应的信息。
  3. 参与者同时或依次选择行动。
  4. 收益取决于行动和实际实现的类型。

这一转换将不完全信息博弈变为一个包含明确的机会行动、且结构得到完整规定的博弈。转换后的博弈通常具有不完美信息,因为参与者无法观察到自然所作选择的全部内容。

自然不必表示真实发生的随机分配。这种构造也可以用来描述对既有事实的不确定性,例如对某家企业生产成本的不确定性。

类型的一项重要作用是组织“关于信念的信念”:参与者可能不确定另一位参与者知道什么、相信什么,等等。简单的应用模型通常通过规定共同先验和信号结构来处理这些问题,而不是明确列出这些高阶信念。

示例:第一价格密封拍卖

考虑两名风险中性的竞标者竞争一件物品的情形。每名竞标者私下观察到自己的估值 viv_i,这些估值分别独立地从 [0,1][0,1] 上的均匀分布中抽取。两个分布和拍卖规则都是共同知识。

每名竞标者提交一个非负报价。报价较高者获胜,并支付自己的报价;落败者无需支付任何费用。估值为 viv_i、报价为 bib_i 的获胜者获得的收益为 vi−biv_i-b_i。

一个对称的贝叶斯纳什均衡为

b(v)=v2.b(v)=\frac{v}{2}.

为说明其原因,假设对手遵循这一规则。对于报价 b∈[0,1/2]b\in[0,1/2],当对手估值低于 2b2b 时,该竞标者获胜;这一事件的概率为 2b2b。因此,期望收益为

(v−b) 2b.(v-b)\,2b.

对 bb 求导,得到

2v−4b,2v-4b,

其在 b=v/2b=v/2 处为零。目标函数是凹函数,而高于 1/21/2 的报价不可能优于上述区间内的最优报价。在连续的估值分布下,报价相同的概率为零。

这个例子说明了为什么策略是类型的函数:每一种可能的估值都对应一个不同的报价。它也表明,均衡行为未必会通过行动本身如实披露私人信息。

在相同的估值独立、服从均匀分布且竞标者风险中性的假设下,若竞标者人数为 n≥2n\geq2,则对称均衡变为

b(v)=n−1nv.b(v)=\frac{n-1}{n}v.

这些公式依赖于上述假设。估值相关、风险厌恶、保留价,或对共同基础价值的不确定性,都可能改变均衡。

动态贝叶斯博弈与信念更新

在动态贝叶斯博弈中,参与者可能观察到能够揭示私人类型信息的行动。随后,信念会依据贝叶斯定理更新。

例如,劳动者的教育选择可能向雇主传递有关其私下知晓的生产率的信息。这类互动是信号博弈的研究对象。不同类型可能选择不同的可观察行动,形成分离均衡;也可能选择相同的行动,形成混同均衡。

仅使用贝叶斯纳什均衡,可能会容许在某些历史之后并非最优的行为,尤其是在均衡路径上发生概率为零的历史之后。因此,动态分析往往采用完美贝叶斯均衡和序贯均衡等精炼概念。

这些概念将依情形而定的策略与决策点上的信念相结合,并对序贯最优性和信念一致性提出要求。它们不能相互替代:完美贝叶斯均衡的定义有多种,而序贯均衡则通过完全混合策略的极限施加一项特定的一致性要求。

应用

贝叶斯博弈为分析信息分散情况下的策略行为提供了框架。

**拍卖与采购。**竞标者拥有私人估值或私人成本。模型区分私人价值情境与竞标者信息涉及某个共同基础价值的情境。

**合同与监管。**委托人可以为成本或特征属于私人信息的代理人设计合同条款。这些模型研究信息约束如何影响可行的合同。

**产业组织。**企业可能在竞争的同时,掌握有关成本、产能、需求或投资意向的私人信息。

**讨价还价。**谈判者可能拥有私人的保留价值,或掌握有关达成协议所带来收益的信息。出价和拖延本身也可能传递信息。

机制设计。机制设计将通常的问题反过来:它不预测既定规则下的行为,而是研究旨在实现特定结果的规则。贝叶斯激励相容要求,在其他参与者都如实报告时,如实报告能够使每种类型的期望收益最大化。

**计算环境中的策略互动。**贝叶斯博弈模型被用于安全资源配置和多智能体系统,在这些场景中,参与者掌握有关目标、资源或能力的私人信息。

建模假设与计算挑战

信息结构是贝叶斯博弈的核心,而不是次要细节。即使实际可采取的行动不变,改变参与者观察到的信息、类型之间的相关方式,或他们对彼此的信念,也可能改变均衡结果。

共同先验假设为联系私人信息与信念提供了一种易于处理的方法。不过,它排除了某些形式的先验分歧,在具体应用中也可能难以得到合理支持。同样,当相关概率本身都不甚清楚时,用一个已知的概率分布来表示不确定性,也可能具有局限性。

计算可能十分困难。如果参与者 ii 有 ∣Ti∣|T_i| 种类型,且在每种类型下都有 ∣Ai∣|A_i| 个可选行动,那么依类型而定的纯策略数量为

∣Ai∣∣Ti∣.|A_i|^{|T_i|}.

因此,即使对于规模中等的模型,直接构造标准式博弈也可能不切实际。计算方法可以转而采用基于类型的表述、利用特殊结构、将连续空间离散化,或寻求近似均衡。

最后,均衡预测取决于有关收益最大化、信念和策略一致性的假设。贝叶斯博弈为私人信息条件下的决策提供了一个严谨的模型,但并不能证明现实中的参与者确实拥有模型所假设的信念,或会选择某个特定均衡。