近似纳什均衡

纳什均衡要求所有人都没有偏离当前策略的动机。 纳什证明了n个人的有限博弈一定存在纳什均衡, 但是即使对于两个人的情形, 如果每个人的策略空间很大, 均衡的求解还是会很困难。 如果放松求解的条件, 寻求一个策略使得每个人偏离增加的收益不超过一个常数, 则这个策略叫做一个近似纳什均衡(Approximate Nash Equilibria)。 考虑两个人的双矩阵博弈(bimatrix game), 寻找 PPAD-complete 的均衡求解还是很困难, 但是TS方法给出了在多项式时间内求得一个 0.3393 近似的均衡的算法。

收益的矩阵写法与近似均衡

对于两个人的策略, 可以表示成矩阵的形式. 以一个人的纯策略作为列索引, 另一个人的纯策略作为行索引, 两个矩阵中元素 (i,j)(i,j) 分别对应的是行动 (ai,bj)(a_i,b_j) 对两个人产生的收益。 给定两人的混合策略, 则矩阵中每一项被实现的概率就可以确定, 分别乘上对应的收益后加和就得到了这种策略下的期望收益。 记 R,CR, C 分别是行玩家和列玩家的收益矩阵, (x1,x2,⋯ ,xm)(x_1,x_2,\cdots,x_m) 和 (y1,y2,⋯ ,yn)(y_1,y_2, \cdots, y_n) 是两人在纯策略上的概率分布, 则玩家 11 的期望收益可以写作 xtRyx^tRy, 玩家 22 的期望收益可以写作 xtCyx^tCy.

对于一个纳什均衡 (xˉ,yˉ)(\bar{x},\bar{y}), 两人都没有偏离的动机, 即

xtRyˉ≤xˉRyˉ∀x∈Δmx^t R \bar{y} \le \bar{x} R \bar{y}\quad \forall x \in \Delta_m

且

xˉtCy≤xˉCyˉ∀y∈Δn.\bar{x}^t C y \le \bar{x} C \bar{y}\quad \forall y \in \Delta_n.

玩家 11 没有偏离的动机也可以表述成 supp(x)⊂argmax(Ryˉ)\text{supp}(x) \subset \text{argmax} (R \bar{y}).

** ϵ\epsilon-近似纳什均衡：** 将 R,CR,C 标准化到 [0,1][0,1] 上之后, 给定 ϵ\epsilon, 寻找一组 (xˉ,yˉ)(\bar{x},\bar{y}) 使得以下两式同时成立：

xtRyˉ≤xˉRyˉ+ϵ∀x∈Δm(1)x^t R \bar{y} \le \bar{x} R \bar{y} + \epsilon\quad \forall x \in \Delta_m \tag{1}

xˉtCy≤xˉCyˉ+ϵ∀y∈Δn(2)\bar{x}^t C y \le \bar{x} C \bar{y} + \epsilon\quad \forall y \in \Delta_n\tag{2}

从经济学的角度来看, 如果引入改变策略的交易成本 ϵ\epsilon, 则对于上述的策略 (xˉ,yˉ)(\bar{x},\bar{y}), 两人都不会有偏离的动机。

TS方法的思路

构造一个连续函数 f(x,y)f(x,y) 来衡量两人单独偏离时能获得的最大收益, 并用梯度下降的方法尽量最小化目标函数, 达到一定条件后就可以获得满足条件的近似均衡。

f(x,y)=max⁡{max⁡(Ry)−xtRy,max⁡(Ctx)−xtCy}f(x,y) = \max \{\max(Ry) - x^tRy,\max(C^tx) - x^tCy\}

由定义知 f(x,y)≥0f(x,y) \ge 0 恒成立, 取等当且仅当 (x,y)(x,y) 是纳什均衡点。 ϵ\epsilon近似均衡对应了 f(x,y)≤ϵf(x,y) \le \epsilon. 给定 xx 或 yy, 函数关于另一个变量是凸的。

定义 fR(x,y)=max⁡(Ry)−xtRyf_R(x,y) = \max(Ry)-x^tRy, fC(x,y)=max⁡(Ctx)−xtCyf_C(x,y) = \max(C^tx) - x^tCy, 则 f(x,y)=max⁡{fR,fC}f(x,y) = \max\{f_R,f_C\}.

对于任何一个定义域内的点 (x,y)(x,y), 考虑其在任一可行方向 (x′,y′)(x',y') 移动到 (1−ϵ)(x,y)+ϵ(x′,y′)(1 - \epsilon)(x,y) + \epsilon(x',y') 时目标函数的变化:

Df(x,y,x′,y′,ϵ)=f(x+ϵ(x′−x),y+ϵ(y′−y))−f(x,y)D f(x,y,x',y',\epsilon) = f(x + \epsilon(x'-x), y + \epsilon(y' - y)) - f(x,y)

此函数化简后是关于 ϵ\epsilon 的分段二次函数, 且存在 ϵ∗\epsilon^*, ∀0<ϵ≤ϵ∗\forall 0 < \epsilon \le \epsilon^* ϵ\epsilon 的线性部分系数和如下定义的梯度相同：

Df(x,y,x′,y′)=lim⁡ϵ→01ϵDf(x,y,x′,y′,ϵ).Df(x,y,x',y') = \lim_{\epsilon \rightarrow 0} \frac 1 \epsilon Df(x,y,x',y',\epsilon).

也就是目标函数的变化对 ϵ\epsilon 的梯度. 对于给定的 (x,y)(x,y), Df(x,y,x′,y′)Df(x,y,x',y') 关于 (x′,y′)(x',y') 是一个凸多面体泛函。 优化的思路是寻找最陡峭的下降方向进行下降。

比较 fRf_R 和 fCf_C 的关系, 如果二者不一样大（不妨设fR>fCf_R>f_C ）, 在保持不等式的约束下仅改变 xx 来最小化 fRf_R. 直观来说, 总存在改进的方向可以让 fRf_R 减小, 直到达到 fR=fCf_R=f_C 时停止.

当 fR=fCf_R=f_C 时,

Df(x,y,x′,y′)=max⁡(T1(x,y,x′,y′),T2(x,y,x′,y′))−f(x,y)Df(x,y,x',y') = \max(T_1(x,y,x',y'),T_2(x,y,x',y')) - f(x,y)

其中

m1(y′)m_1(y') 是玩家 11 在对 yy 的最优反应集合中取得的最大化 Ry′Ry' 的值,

m2(x′)m_2(x') 是玩家 22 在对 xx 的最优反应集合中取得的最大化 CTx′C^Tx' 的值,

T1(x,y,x′,y′)=m1(y′)−xtRy′−(x′)tRy+xtRyT_1(x,y,x',y') = m_1(y') - x^tRy' - (x')^tRy + x^tRy,

T2(x,y,x′,y′)=m2(yx′)−xtCy′−(x′)tCy+xtCyT_2(x,y,x',y') = m_2(yx') - x^tCy' - (x')^tCy + x^tCy.

于是问题可以被转化为一个 minmax 问题：

V(x,y)= ⁣=defmin⁡x′,y′max⁡w,z,ρ[ρwt,(1−ρ)zt]G(x,y)(y,x)′V(x,y) \overset{\text{def}}{=\!=} \min_{x',y'} \max_{w,z,\rho} [\rho w^t,(1 - \rho)z^t]G(x,y)(y,x)'

其中 w,zw, z 是两人各自对 (x,y)(x,y) 的最优反应的组合, ρ∈[0,1]\rho \in [0,1].

G(x,y)=[R−emxtR−emytRt+ememtxtRy−enxtC+enentxtCyCt−enytCt].G(x,y) = \begin{bmatrix} R - e_mx^tR & -e_my^tR^t + e_me_m^tx^tRy \\ -e_nx^tC + e_ne_n^tx^tCy & C^t - e_ny^tC^t \end{bmatrix}.

然后求解优化问题得到梯度下降的方向 (x′,y′)(x',y')

梯度下降的操作步骤

  • 任意选择一点 (x,y)=(x0,y0)∈Δm×Δn(x,y) = (x_0,y_0) \in \Delta_m \times \Delta_n

  • 如果 fR(x,y)≠fC(x,y)f_R(x,y) \neq f_C(x,y), 按照上述方法优化使得两值相等

  • 求解上述优化问题, 计算 (x~,y~)(\tilde{x}, \tilde{y}) (之后补上这一段)

  • 如果以下条件之一满足, 算法停止, 已经找到 bb-近似均衡：

    • V(x,y)−f(x,y)≥0V(x,y) - f(x,y) \ge 0, 说明已经下降到了一个稳定点

    • f(x,y)≤bf(x,y) \le b

    • (x~,y~)≤b(\tilde{x}, \tilde{y}) \le b

    • f(x′,y′)≤bf(x',y') \le b

    • f(x′,y)≤bf(x',y) \le b

    • f(x,y′)≤bf(x,y') \le b

  • 如果以上条件都不满足, 计算最优的步长 ϵ\epsilon 并更新 (x,y)(x,y), 然后回到第二步