8 贝叶斯均衡 - Lecture notes 13-14 PDF

Preview

Summary

Notes for Beysian Game...

Description

贝叶斯均衡 Xi December 9, 2019

不完全信息静态博弈中, 每个参与者不确定其对手的某些能影响双方收益的特性.

1

不完全信息静态博弈的扩展表达 John C. Harsanyi 最先发现, 不完全信息静态博弈可以转化成一个完全信息动态博弈, 并由

此找到了解决这类问题的办法. 基本的想法是, 引入一个特殊的参与者“自然”(Nature), 这个参与者没有收益, 不做最大化, 只按照预先设计的概率去选择所有参与者的特性, 然后每个参与者了解自己的特性之后做出选 择. 以一个例子来介绍这种想法. 例1

两个动物竞争某个生存资源. 他们可以选择放弃 (C) 或者竞争 (D). 只要放弃, 获得的收

益是 0. 如果对方选择放弃自己选择竞争, 那么获得收益 R. 如果两方都选择竞争, 那么他们平 分收益, 并各自遭受损失 ki . 假设只有两种动物, 一种从冲突中遭到的损失是 H, 另一种从冲突 中遭到的损失是 L, H > L. 双方只知道自己属于哪一种, 并不知道对方的种类; 但是双方认为 对方是 H 的概率都是 1/2. 这样, 用博弈矩阵表示就是 c C D

d

0, 0

0, R R 2

R, 0

− k, R2 − k

我们知道可能出现的两人的类型组合是 LL, LH, HL 和 HH. 不难计算每种可能性出现的概率 都是 1/4. 我们假设自然以固定的行为策略 41 ◦ LL +

1 4

◦ LH + 41 ◦ HL +

1 4

◦ HH 选择策略, 又

因为每个人不能观察对方的策略和类型, 信息集就如图所示. 收益的填写也不难. Nature 的每一个子节点都引导着一个特定信息情况下的静态博弈, 譬 如 LL 下的博弈是两者的损失都是 L 的情形, 此时如果两人都选 D, 收益是 0.5R − L. 余类似.

1

这里的 Nature 和一般的参与者不同: 他没有收益, 因此不需要最大化, 只行使给定的行为 策略. 这样, 分析均衡的时候便不需要考虑他. 我们注意到 1 和 2 各自有两个信息集, 每个信息 集对应自己的一个类型. 这样, 每个人就有四个纯策略: CC, CD, DC 和 DD. 我们对任意一个 策略组合, 可以写出收益. 注意到这里 Nature 行使的是混合策略, 因此我们需要对各个可能的 结果求期望. 以策略组合 (DC, dc) 为例:

因此得到二者的收益为 ( ) 1 1 3 1 1 1 1 v1 (DC, dc) = R + R−L + ·0+ ·0= R− L 4 4 4 8 4 2 4 ( ) 1 1 1 1 3 1 1 v2 (DC, dc) = · 0 + R−H + ·0+ R = R− H 4 4 4 8 4 2 4 类似地可以得到所有策略组合下的收益表达, 从而求出纳什均衡.

2

2

贝叶斯博弈的描述

定义 1

一个贝叶斯博弈 (或不完全信息静态博弈) 的正则表达是 n (N, {Ai }i=1 , {Θi }ni=1 , {vi }ni=1 , P)

其中, N = {1, 2, · · · , n} 是参与者的集合, 和完全信息的一致. Ai 是参与者 i 的行为空间. 我们这里称行为, 是因为对策略有别的定义. 具体的思想后述. Θi 是参与者 i 的类型空间 (Type Space), θi ∈ Θi 为参与者 i 的一个类型. vi : A × Θ → R 是收益函数. 它表明收益不仅和行为有关, 也和类型有关. P 是 Θ 上的一个概率分布, 称作先验概率 (Common Prior), 它是所有参与者的共识. 注 1. 不完全信息的核心思想就在这个定义的收益函数 vi : A × Θ → R 中. 收益不仅和行为有 关, 也和类型有关, 而对手的类型是不确定的, 这就体现为信息不对称. 注 2. 先验概率是一个类型组合概率分布, 即是 P(θ1 θ2 · · · θn ). 这个概率是共识, 就是自然的行 为策略的概率, 可以解释为人一开始 (知道自己的类型前) 对世界的认识都是相同的; 知 道自己的类型后, 也即知道 θi ∈ Θi 后, 他对世界的认识发生了变化: 按照贝叶斯公式, 对 手的类型 θ−i ∈ Θ−i 发生的概率就是

φ(θ−i |θi ) =

P(θi , θ−i ) P(θ−i )

其中 P(θi ) 是 θi 的边际分布, 满足 ∑

P (θi ) =

′ θ−i ∈Θ−i

( ′ ) P θi , θ−i

这个被称为后验概率 (Posterior Belief ). 定义 2

在一个贝叶斯博弈中, 一个纯策略是函数 si : Θi → Ai , 即每个参与者为他的每个可

能出现的类型 θi 安排一个行为 ai = si (θi ). 定义 3

在一个贝叶斯博弈中, 一个混合策略是函数 σi : Θi → ∆(Ai ), 即每个参与者为他每个

可能出现的类型 θi 安排一个混合行为 σi (θi ). 定义 4

给定对手的策略 s−i , 那么对某个人而言, 他在类型 θi 时选择行为 ai 的期望回报是 ∑

φi (θ−i |θi )vi (ai , s−i (θ−i ); θi , θ−i )

θ−i ∈Θ−i

注 3. 在这个表达式中, 不确定的是对方的类型, 因此对方的策略也不确定. 期望收益就是给定 自己的类型, 对方每个类型的可能性乘上相应可能下的的收益.

3

纯策略的贝叶斯均衡 (Pure Strategy Bayesian Nash Equilibrium)

对任意一个参与者 i, 如

果对他每个可能的类型 θi ∈ Θi , 且 ∀ai ∈ Ai , 满足

∑

θ−i ∈Θ−i

( ) φi (θ−i |θi ) vi si∗ (θi ) , s∗−i (θ−i ) ; θi , θ−i ≥

∑

θ−i ∈Θ−i

( ) ∗ φi (θ−i |θi ) vi ai , s−i (θ−i ) ; θi , θ−i

注 4. 这个定义仍旧是在说没有人有动力偏离. 如此复杂只不过是因为效用的因素比较多. 总 结而言, 逻辑如下: 行驶任意的行为 ai ∈ Ai , 不论自己是哪一个类型 θi ∈ Θi , 都有对方 所有类型 θ−i 的期望回报不比行使策略 si∗ 高.

3

贝叶斯均衡和纳什均衡的一致性 事实上, 我们定义贝叶斯博弈和贝叶斯均衡正是从清晰但很麻烦的等价的扩展表达中获

得的灵感. 但是, 要说明贝叶斯均衡的正确性, 我们需要说明这二者等价.

定理 1

一个策略组合是贝叶斯均衡当且仅当它是原博弈等价的扩展表达中的纳什均衡.

证明 为了证明贝叶斯均衡一定是扩展表达中的纳什均衡, 先研究一下扩展表达能不能抽象成 贝叶斯均衡的定义. 注意到两个情况下的策略实际上是一样的: 在扩展表达中, 每个信息 集恰对应着一个类型. 二者之间唯一的差异是在扩展表达中的纳什是在自然做出选择之 前找期望收益, 因此比贝叶斯定义中多出一个对参与者 i 的类型求期望的过程. ”=⇒” 设 s∗ 是贝叶斯均衡. 我们考虑一个特定的偏离 si ∈ Si , 按贝叶斯均衡定义,

∑

θ−i ∈Θ−i

( ) φi (θ−i |θi ) vi si∗ (θi ) , s∗−i (θ−i ) ; θi , θ−i ≥

∑

θ−i ∈Θ−i

( ) ∗ φi (θ−i |θi ) vi si (θi ) , s−i (θ−i ) ; θi , θ−i

在两边同乘 P(θi ) 再对 θi ∈ Θ 累加, 也就是说, 对 i 的类型求期望. 这样, 得到 ∑

θi ∈Θi

P(θi )

∑

θ−i ∈Θ−i

) ( ∗ (θ ) ; θ , θ φi (θ−i |θi ) vi si∗ (θi ) , s−i −i i −i

≥

∑

θi ∈Θi

P(θi )

∑

θ−i ∈Θ−i

) ( ∗ (θ φi (θ−i |θi ) vi si (θi ) , s−i −i ) ; θi , θ−i

注意 P(θi ) 与 θ−i 无关, 因此它能拿到后一个求和号之中去, 进而由于 4

P (θi ) · φi (θ−i |θi ) = P (θi θ−i ) 又因为离散和可以换序, 因此得到 ∑

θ∈Θ

( ( ) ) ∑ ∗ P(θ)vi s∗i (θi ) , s∗−i (θ−i ) ; θi , θ−i ≥ P(θ)vi si (θi ) , s−i (θ−i ) ; θi , θ−i θ∈Θ

左边就是 i 在扩展表达形式中从策略组合 达形式中从策略组合

∗ (si , s−i )

(si∗, s∗−i )

中得到的期望回报, 右边是在扩展表

中得到的期望回报. 这就证明了贝叶斯均衡 s∗ 是扩展表达

形式的一个纳什均衡. ”⇐=” 用反证法. 假设 s∗ 不是贝叶斯均衡, 对某个 θˆi ∈ Θi , 存在 a ˆi 使得 ∑

θ−i ∈Θ−i

那么我们令策略

 ) ( ( )  φi θ−i  θˆi vi a ˆi , s∗−i ... >

∑

θ−i ∈Θ−i

 )( ( )  φi θ−i  ˆθi s∗i (θˆi ), s∗−i ...

 a ˆ ˆi , if θi = θi, si (θi ) = s∗ (θ ), if θ = ˆ θi, i i

也就是说, 策略 si 和 si∗ 仅在 θˆi 上不同. 这样, 我们在两边乘上 P(θi ) 再对 θi ∈ Θ 累加, 就 得到

∑

θ∈Θ

∑ ( ) P(θ)vi si , s∗−i .. =

∑

∗ P(θ˜i , θ−i )vi (si∗( θ˜i ), s−i ...) +

˜ θi = θˆi θ−i ∈Θ−i

>

∑

θ∈Θ

∑

∗ ai , s−i ...) P(θˆ, θ−i )vi (ˆ

θ−i ∈Θ−i

) P(θ)vi si∗, s∗−i .. (

∗ 的最优反应, 因此这也不是扩展形式中的纳什均衡. 这就说明 s∗i 并不是扩展形式当中 s−i

综上所述, 定理得证. 注 5. 我们注意到在贝叶斯均衡的定义中并没有涉及 P, 但是在证明它和扩展表达形式等价 的时候用到了 P. 这说明 P 实际上是将不对称信息变成不完美信息的一个媒介: 虽然不 知道对方的类型, 但是知道对方类型和自己类型的关系. 有的时候我们也直接通过定义 {φi } 来描述贝叶斯博弈, 这样的一组后验概率不一定存在一个 P, 但是贝叶斯均衡定义 仍然适用. 此时, 不存在等价的扩展表达.

5...