Quantal Response Equilibrium调研

Quantal Response Equilibrium

Notes of QRE Palgrave

历史

灵感：Harsanyi (1973) and McFadden (1976)，不完全信息博弈

提出：McKelvey and Palfrey (1995)

提出动机&直觉

1. 人类不是绝对理性的，有的时候确实可能犯错，因此应该在每个人的决策过程中增加概率因素
2. 人类在面对成本更高的选择时会更加谨慎（更少地犯错），但总是可能犯错
3. 由于每个人的选择都与其对其它参加博弈者的先验有关，因此也存在均衡

什么是QRE

1. 在博弈中对玩家增加一些概率噪声，其中选择模型基于Quantal Response Functions

让我们从一个例子：matching pennies博弈出发：

( 1 , − 1 ) ( − 1 , 1 ) ( − 1 , 1 ) ( 1 , − 1 ) (1,-1) \quad (-1,1)\\ (-1,1)\quad (1,-1) (1,−1)(−1,1)(−1,1)(1,−1)

那么，假如行玩家以p的概率选择策略1，则列玩家选择策略1的期望收益为1-2p，选择策略2的期望收益为2p-1，因此，他应该在p大于等于1/2的时候选择策略2，否则选择策略1；列玩家同理

那么，他们的反应函数图象如下：

这个博弈的Nash均衡即为两个人的反应曲线的交点：(1/2,1/2).

但是，如果我们考虑对两个人的反应做一个平滑，例如：(2p-1)^2/2+1/2，那么我们也可以得到两条曲线，而且QRE和NE是相同的：

但是，接下来，如果我们考虑在两个人都选择策略1的情况下，把支付变为(9,-1)，那么根据Nash均衡，寻找交点时应当出现的情况是行玩家以相同的概率选择策略（即图中虚线交点），但是我们做了平滑后的QRE则是以更高的概率选择策略1。

从理性的角度来看，行玩家确实应该这么做，但事实上没有人是真正理性的，人们在看到选择某个方案时收益更多的情况下总是会以更高的概率去选择。实验检验证明，人们总是会以更高的概率选择策略1。

严格定义

1. Regular Quantal-Response Function

令 G = ( N , { S 1 , . . . , S n } , π 1 , . . . , π n ) G=(N,\{S_1,...,S_n\},\pi_1,...,\pi_n) G=(N,{S1​,...,Sn​},π1​,...,πn​)为一个普通博弈，N={1,2,…,n}为玩家的集合， S i = { s i 1 , . . . , s i J ( i ) } S_i=\{s_{i1},...,s_{iJ(i)}\} Si​={si1​,...,siJ(i)​}​为第i个玩家的所有策略， S = S 1 × . . . × S n S=S_1\times...\times S_n S=S1​×...×Sn​为策略的集合， π i : S i → R \pi_i:S_i\rightarrow R πi​:Si​→R为第i个人的支付函数， Σ i = Δ J ( i ) \Sigma_i=\Delta^{J(i)} Σi​=ΔJ(i)为第i个玩家的策略集合上的概率分布， ∀ σ i ∈ Σ i \forall \sigma_i\in \Sigma_i ∀σi​∈Σi​为玩家的一个混合策略， σ i ( s i ) \sigma_i(s_i) σi​(si​)为玩家i选择战略 s i s_i si​的概率， R J ( i ) R^{J(i)} RJ(i)为第i个玩家在特定的策略分布下的收益分布， P i j P_{ij} Pij​​​表示玩家i选择策略j的概率。

回顾一下在QRE背后的主要思想：有更高期望收益的策略有更高的概率被选择。换句话说，QRE把玩家的绝对理性选择反应换成了平滑的反应，或者说quantal response.

P i : R J ( i ) → Δ J ( i ) P_i:R^{J(i)}\rightarrow \Delta^{J(i)} Pi​:RJ(i)→ΔJ(i)称为regular quantal-response function，如果它满足下列四条性质：

• 内部性(Interiority): P i j ( π i ) > 0 , ∀ j = 1 , 2 , . . . , J ( i ) , ∀ π i ∈ R J ( i ) P_{ij}(\pi_i)>0, \forall j=1,2,...,J(i), \forall \pi_i\in R^{J(i)} Pij​(πi​)>0,∀j=1,2,...,J(i),∀πi​∈RJ(i)​
• 连续性(Continuity)： ∀ π i ∈ R J ( i ) , P i j ( π i ) \forall \pi_i\in R^{J(i)}, P_{ij}(\pi_i) ∀πi​∈RJ(i),Pij​(πi​)关于 π i \pi_i πi​是一个连续可微函数
• 反应性(Responsiveness)： ∂ P i j ( π i ) ∂ π i j > 0 \frac{\partial P_{ij}(\pi_i)}{\partial \pi_{ij}}>0 ∂πij​∂Pij​(πi​)​>0（亦即如果一个策略的收益增加，那么选择这个策略的概率也相对地增加（偏导数，不绝对））
• 单调性(Monotonicity)：如果 π i j > π i k \pi_{ij}>\pi_{ik} πij​>πik​，那么 P i j ( π i ) > P i k ( π i ) P_{ij}(\pi_i)>P_{ik}(\pi_i) Pij​(πi​)>Pik​(πi​)

这些性质都是我们的直觉的直接反映。

考虑quantal-response function集合 P = { P 1 , . . . , P n } P=\{P_1,...,P_n\} P={P1​,...,Pn​}​​，我们称P为正则的，如果 P 1 , . . . , P n P_1,...,P_n P1​,...,Pn​​​都是正则的。那么，在给定的支付组合 π \pi π​​下， P ( π ) = { P 1 ( π 1 ) , . . . , P n ( π n ) } ∈ Σ P(\pi)=\{P_1(\pi_1),...,P_n(\pi_n)\}\in \Sigma P(π)={P1​(π1​),...,Pn​(πn​)}∈Σ​是支付组合到每个人的action的一个映射，而 σ \sigma σ又是在给定每个人action后的支付组合，因此 P ∘ σ P\circ \sigma P∘σ定义了 Σ \Sigma Σ到自身的变换​。

1. Regular Quantal Response Equilibrium

如果P是正则的，那么对于标准博弈G来说，其正则QRE就是使得 σ ∗ = P ( σ ∗ ) \sigma^*=P(\sigma^*) σ∗=P(σ∗)的不动策略 σ ∗ \sigma^* σ∗

亦即：QRE：假设所有人都使用Quantal Response进行反应的情况下，约定所有人都使用 σ ∗ \sigma^* σ∗时，每个人都有动机遵守约定。

类比：NE：假设所有人都使用绝对理性进行反应的情况下，约定所有人都使用 σ ∗ \sigma^* σ∗时，每个人都有动机遵守约定。

由于在我们的假设下，P是连续的，因此 P ∘ σ P\circ \sigma P∘σ是连续映射，从而由Brouwer定理知，QRE一定存在。

1. 概率观点（structural approach）

虽然理论上说每个人似乎都应该以绝对理性进行行动，但也有观点认为绝对理性只是对行动的无偏估计，而真实的行动是存在偏差的。如果行动完全不出现偏差的话，就会得到绝对理性的结果。

换句话说，QRF是对行动的偏差的一种模拟。例如，如果所有行动的偏差都是独立同分布的有界分布，那么QRF的形状就是一个正态分布；如果所有行动的偏差无界，那么QRF就会变成一个指数分布，也就是所谓的logitQRE.

事实上，从这种观点出发，可以证明，独立同分布造成的累计偏差对应的QRE总是满足连续性和单调性，随后就能得到一个正则的QRF，进而得到一个QRE。McKelvey and Palfrey, 1996证明了前述的概率直觉可以直接推导出logit QRE的形式。

1. QRE的应用

首先，QRE可以解释很多NE不能解释的实际现象，例如合作劳动问题：

如果n个人一起合作完成一个工作，每个人的努力是 x i x_i xi​，收益是 min ⁡ ( x 1 , . . . , x n ) − c ⋅ x i \min(x_1,...,x_n)-c\cdot x_i min(x1​,...,xn​)−c⋅xi​，那么，当c<1的时候，对任意a>0, x 1 = . . . = x n = a x_1=...=x_n=a x1​=...=xn​=a都是一个Nash均衡，但人们无法分辨到底哪一个才是NE。然而，如果假设所有人采用QRE的话，可以证明只有一个QRE，并且均衡a关于c单调递减。这与实际实验是吻合的，也符合常理：每个人的努力给自己带来的风险率c越低，每个人就越愿意努力。

除此之外，QRE还能用来解释很多博弈中的异常现象，例如信号博弈，过度出价等等。