# 零和博弈的近似 Nash 均衡：Multiplicative Weights 与 Dynamic Gibbs Sampling

给 $m\times n$ payoff matrix $A$，零和博弈的 equilibrium 是一个 convex--concave saddle point。经典 multiplicative weights 每轮维护两组 exponential weights；若显式归一化/采样，成本随 $m+n$ 线性。量子算法为缓慢变化的 Gibbs 分布设计动态采样数据结构，把维数依赖降到平方根，同时输出可直接使用的稀疏经典混合策略。

## 1. Minimax 与 saddle gap

Row player 选

$$
p\in\Delta_m,
$$

最大化 payoff；column player 选

$$
q\in\Delta_n
$$

最小化。Von Neumann minimax：

$$
v=\max_{p\in\Delta_m}\min_{q\in\Delta_n}p^TAq
=\min_q\max_pp^TAq.
$$

定义 saddle gap

$$
\operatorname{Gap}(p,q)
=\max_i(Aq)_i-min_j(p^TA)_j.
$$

若 gap $\le\epsilon$，$(p,q)$ 是 $\epsilon$-approximate Nash equilibrium；任何单边 best response 最多改善 $\epsilon$。

## 2. Multiplicative weights dynamics

假设 $A_{ij}\in[-1,1]$。初始权重全 1。第 $t$ 轮按

$$
p_t(i)=
\frac{\exp(\eta\sum_{\tau<t}A_{i,j_\tau})}
{\sum_{i'}\exp(\eta\sum_{\tau<t}A_{i',j_\tau})},
$$

$$
q_t(j)=
\frac{\exp(-\eta\sum_{\tau<t}A_{i_\tau,j})}
{\sum_{j'}\exp(-\eta\sum_{\tau<t}A_{i_\tau,j'})}.
$$

采样 $i_t\sim p_t,j_t\sim q_t$，查询 $A_{i_t,j}$ / $A_{i,j_t}$ 对相应 loss vectors 更新。Regret bound：

$$
\frac1T\sum_t e_{i_t}^TAq
\ge\max_i e_i^TA\bar q
-O\!\left(\eta+\frac{\log m}{\eta T}\right)
$$

及 column 对称式。取

$$
\eta=\Theta(\epsilon),
\qquad
T=\widetilde O(1/\epsilon^2)
$$

得到 empirical strategies

$$
\bar p=\frac1T\sum_te_{i_t},\qquad
\bar q=\frac1T\sum_te_{j_t}
$$

的 saddle gap $O(\epsilon)$。

## 3. Classical 维数瓶颈

每轮 energy vector

$$
u_t(i)=\eta\sum_{\tau<t}A_{i,j_\tau}
$$

只增加一列贡献，但若重新计算 partition function

$$
Z_t=\sum_i e^{u_t(i)}
$$

并采样，需 $O(m)$；另一方 $O(n)$。数据结构/随机化后的经典总时间约

$$
\widetilde O((m+n)/\epsilon^2)
$$

在相应 oracle 模型下。

## 4. Quantum dynamic Gibbs sampler

目标 state

$$
|p_t\rangle
=Z_t^{-1/2}\sum_i e^{u_t(i)/2}|i\rangle.
$$

若从均匀叠加计算 $u_t(i)$ 并受控旋转，直接 postselection 成本取决于最大权重/normalization。动态算法利用相邻 $u_t,u_{t+1}$ 只差一个 bounded payoff vector：

1. 保留分层估计的权重范围与重元素；
2. 复用上一轮 sampler/reference state；
3. 用 rejection sampling/amplitude amplification 修正权重比
   $$
   e^{(u_{t+1}(i)-u_t(i))/2};
   $$
4. 低方差 amplitude/mean estimation 更新 normalization，而不每轮从零开始。

这把一次从 $m$ weights 采样的维数成本降到约 $\sqrt m$（另一方 $\sqrt n$），并控制 $T$ 轮累计误差与 state disturbance。

## 5. 总复杂度与输出

改进算法运行时间

$$
\widetilde O\!\left(
\sqrt{m+n}\,\epsilon^{-5/2}
+\epsilon^{-3}
\right).
$$

相对早期 quantum $\widetilde O(\sqrt{m+n}\epsilon^{-3})$ 改善精度。与 classical 维数线性式比较，在

$$
\epsilon=\Omega((m+n)^{-1})
$$

等广泛区域有 polynomial speedup；非常高精度时额外 $\epsilon$ 幂可能主导。

输出不是 amplitude-encoded hidden strategy，而是 sample history 给出的 classical sparse distributions：最多 $T$ 个非零支持及频数。长度

$$
O(T\log(m+n))
$$

，可直接采样/计算 payoff；避免对 $m+n$ 维 quantum state tomography。

## 6. 验证与 payoff oracle

Oracle

$$
O_A|i,j,z\rangle
=|i,j,z\oplus A_{ij}\rangle
$$

需给足够 fixed-point 精度。验证 saddle gap 要估计

$$
\max_i(A\bar q)_i,\qquad
\min_j(\bar p^TA)_j,
$$

可用 quantum min/max finding + sparse support sum；失败率需在 $T$ 轮 union bound 下放大。

算法只针对 two-player zero-sum/bilinear game。一般和 Nash equilibrium 是 PPAD 型 fixed point 问题，不能由 minimax/MWU 结果直接解决。

## 7. 小例子：Matching Pennies

$$
A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.
$$

均衡

$$
p=q=(1/2,1/2),\qquad v=0.
$$

若 $q=(1/2+\delta,1/2-\delta)$，row best payoff $2|\delta|$；若 $p$ 均匀，column 最小 payoff 0，所以 gap $2|\delta|$。这直接给 strategy estimation error 与 $\epsilon$ 的关系。

## 8. 小结与习题

- 零和 equilibrium 等价 convex--concave minimax saddle point。
- MWU 的 empirical action distributions 在 $O(1/\epsilon^2)$ 轮达到小 regret/gap。
- Quantum dynamic Gibbs sampling 利用相邻权重缓慢变化，把 $m+n$ 降到平方根维数依赖。
- 稀疏经典输出避免 tomography；结果不推广到一般和 Nash。

1. 由两方 regret bounds 推导 saddle gap。
2. 对 Matching Pennies 计算任意 $p,q$ 的 gap。
3. 比较维数项与 $\epsilon$ 项，求 quantum/classical crossover。
4. 解释为何 empirical distribution 支持至多 $T$。

## 参考文献

- Zoo 编号 485：Bouland、Getachew、Jin、Sidford 与 Tian, [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://arxiv.org/abs/2301.03763).
- Zoo 编号 486：van Apeldoorn 与 Gilyén, [Quantum Algorithms for Zero-Sum Games](https://arxiv.org/abs/1904.03180).