无政府价格 | Codeboy's Blog

形式陈述

在有限无权原子拥塞博弈中，玩家选择资源子集，每人对资源负载贡献 $1$ ，共享成本函数 $\ell_e$ ，个人成本为 $c_i(s)=\sum_{e\in s_i}\ell_e(x_e(s))$ 。以总成本为社会目标：

C(s)=\sum_i c_i(s)=\sum_e x_e(s)\ell_e(x_e(s)),\qquad s^*\in\operatorname*{arg\,min}_s C(s).

若 $C(s^*)>0$ ，该博弈的纯均衡无政府价格定义为

\operatorname{PoA}_{\mathrm{pure}}=\max_{s\in\operatorname{PNE}}\frac{C(s)}{C(s^*)}.

它考察最坏纯均衡。对一类博弈，则再对该类取上确界。本页证明的精确结论是：当所有资源都有非负仿射成本

\ell_e(k)=a_e k+b_e,\qquad a_e,b_e\ge0,

这类博弈的纯均衡 PoA 恰为 $5/2$ 。势函数保证纯均衡集合非空。若最优成本为零，则不取比值，而使用仍成立的结论 $C(s)\le(5/2)C(s^*)$ ；这时所有纯均衡的总成本也为零。

一个使用整数负载的不等式

证明的关键是：对所有非负整数 $y,z$ ，

3y(z+1)\le5y^2+z^2.

若 $y=0$ ，结论显然。若 $y=1$ ，右减左为 $(z-1)(z-2)$ ；整数 $z$ 不会落在 $1$ 与 $2$ 之间，所以它非负。若 $y\ge2$ ，则

5y^2+z^2-3y(z+1)=\left(z-\frac32y\right)^2+\frac{11}{4}y^2-3y\ge0,

因为 $y(11y/4-3)\ge0$ 。整数性不是装饰： $y=1,z=3/2$ 就会使原不等式失败。单位玩家产生整数负载，正是后面常数的来源。

从单人偏离拼出社会比较

固定任意两个剖面 $s,s^*$ ，写 $x_e=x_e(s)$ 、 $y_e=x_e(s^*)$ 。让玩家 $i$ 单独改选其最优方案中的策略 $s_i^*$ 。它在所用资源上面对的负载至多 $x_e+1$ ：若自己原本就在该资源上，负载实际上仍为 $x_e$ 。仿射成本非减，因此

\sum_i c_i(s_i^*,s_{-i})\le\sum_e y_e\ell_e(x_e+1).

这里把仿射公式延拓到 $n+1$ 仅用于上界；实际单人偏离的负载仍不超过 $n$ 。对每条资源，刚才的整数不等式以及 $y_e\le(5/3)y_e+(1/3)x_e$ 给出

\begin{aligned} y_e\ell_e(x_e+1) &=a_e y_e(x_e+1)+b_e y_e\\ &\le\frac53\bigl(a_e y_e^2+b_e y_e\bigr)+\frac13\bigl(a_e x_e^2+b_e x_e\bigr). \end{aligned}

求和得到对任意剖面成立的比较式

\boxed{\sum_i c_i(s_i^*,s_{-i})\le\frac53 C(s^*)+\frac13 C(s).}

若 $s$ 是纯均衡，每位玩家都有 $c_i(s)\le c_i(s_i^*,s_{-i})$ 。把这些不等式相加，再代入方框式：

C(s)\le\frac53C(s^*)+\frac13C(s),\qquad C(s)\le\frac52C(s^*).

直觉

社会最优要求所有玩家协同换到 $s^*$ ；均衡条件只能约束每个人单独换策略。证明先把这 $n$ 次互不同时发生的假想偏离加起来，再用资源负载控制它们的总成本。右端容许保留一部分当前成本，最终移项即可关闭估计。

一般地，若一个成本博弈对任意 $s,s^*$ 满足

\sum_i c_i(s_i^*,s_{-i})\le\lambda C(s^*)+\mu C(s),\qquad\mu<1,

就称它满足相应的光滑性（smoothness）比较式，并得到纯均衡界 $\lambda/(1-\mu)$ 。这里的“光滑”是跨剖面的成本不等式，不是可微性要求。本页构造的是 $(\lambda,\mu)=(5/3,1/3)$ ；关键优势是方框式本身没有要求 $s$ 已经是均衡。

例子与边界

四位玩家达到 5/2

取三个顶点 $u,v,w$ ，两个方向的边都存在。边 $u\to v,u\to w,v\to w,w\to v$ 的成本均为 $\ell(x)=x$ ；边 $v\to u,w\to u$ 的成本恒为零。四位单位玩家分别从 $u$ 到 $v$ 、从 $u$ 到 $w$ 、从 $v$ 到 $w$ 、从 $w$ 到 $v$ ，每人只可选直达路径或经第三个顶点的两跳简单路径。

玩家	直达路径	两跳路径	全部两跳时自身成本	独自改直达的成本
$1:(u,v)$	$u\to v$	$u\to w\to v$	$2+1=3$	$3$
$2:(u,w)$	$u\to w$	$u\to v\to w$	$2+1=3$	$3$
$3:(v,w)$	$v\to w$	$v\to u\to w$	$0+2=2$	$2$
$4:(w,v)$	$w\to v$	$w\to u\to v$	$0+2=2$	$2$

全部直达时，四条线性成本边负载都是 $1$ ，总成本为 $4$ 。每个人的每条可选路径都至少经过一条线性成本边，只要使用它，其负载就至少为 $1$ ；所以任何剖面的总成本都至少为 $4$ 。这证明全部直达确实社会最优，而不只是一个较好的比较方案。

全部两跳时，按 $(u\to v,u\to w,v\to w,w\to v)$ 的顺序，负载是 $(2,2,1,1)$ ，总成本为

C(s)=2^2+2^2+1^2+1^2=10.

每位玩家只有另一条直达路径可偏离。前两人独自改直达，会把目标边的负载从 $2$ 推到 $3$ ；后两人会把目标边负载从 $1$ 推到 $2$ 。表中逐一验证偏离成本都与当前相等，因而这是纯 Nash 均衡，虽然没有人严格偏好留下。于是 $10/4=5/2$ ，上界达到。

同一三角网络中，四人全选直达时线性边负载均为一，总成本四；全选两跳时负载为二、二、一、一，总成本十，且任一单人偏离只能打平 — 仿射原子拥塞博弈的紧例

图中实线边标注当前负载 $x_e$ ，成本函数均为 $\ell_e(x)=x$ ；虚线边的成本恒为零。两幅图表示两份不同的联合策略，边的成本函数完全相同。

常数依赖于哪个模型

这个 $5/2$ 结论同时使用单位权重、原子玩家、共享资源成本以及非负仿射形式。一般拥塞博弈即使存在纯均衡，也不能仅靠势函数推出相同的效率界。把玩家视为可无限细分的流量，或允许不同玩家具有不同权重，都会改变偏离与负载的计算；本页的整数不等式及紧例不能直接作为那些模型的结论。

推论与应用

同一个证明覆盖粗相关均衡

设 $\mu$ 是联合策略分布。用 $u_i=-c_i$ 改写粗相关均衡条件，任意事先固定的偏离 $b_i$ 满足

\mathbb E_{s\sim\mu}c_i(s)\le\mathbb E_{s\sim\mu}c_i(b_i,s_{-i}).

取固定动作 $b_i=s_i^*$ ，对玩家求和，再对逐剖面成立的方框式取期望，就得到

\mathbb E C(s)\le\frac53 C(s^*)+\frac13\mathbb E C(s),\qquad\mathbb E C(s)\le\frac52 C(s^*).

所以相同上界适用于 CCE，也适用于其内部的相关均衡与混合 Nash 均衡。这里比较的是联合分布的期望总成本；无需分布独立，也无需每个样本本身是纯均衡。纯均衡紧例是一份点质量 CCE，因此扩大到 CCE 后该类博弈的最坏比值仍恰为 $5/2$ 。

若采用每位玩家至多获得加性收益 $\varepsilon\ge0$ 的 $\varepsilon$ -CCE 定义，则求和时多出 $n\varepsilon$ ，移项后为

\mathbb E C(s)\le\frac52 C(s^*)+\frac32n\varepsilon.

这是加性误差，不能直接解释成乘法近似均衡的比值界。

无遗憾历史的平均成本

给定任意 $T$ 轮策略历史，令玩家的成本形式外部遗憾为

R_i(T)=\sum_{t=1}^T c_i(s^t)-\min_{b_i\in S_i}\sum_{t=1}^T c_i(b_i,s_{-i}^t).

固定最优动作 $s_i^*$ 的累计成本不小于右边的最小值，所以

\sum_t c_i(s^t)\le\sum_t c_i(s_i^*,s_{-i}^t)+R_i(T).

对玩家求和并逐轮使用方框式，得到逐条历史成立的保证

\frac1T\sum_{t=1}^T C(s^t)\le\frac52 C(s^*)+\frac{3}{2T}\sum_i R_i(T).

若每位玩家有次线性遗憾上界，平均总成本的渐近上界就是最优的 $5/2$ 倍。遗憾本身可以为负，公式无需截断；若算法只提供期望或高概率遗憾界，相应成本结论也保留同样限定。这个结果控制历史平均，不声称最后一轮会到达均衡或具有同样的成本保证。

参考资料

Tim Roughgarden，Intrinsic Robustness of the Price of Anarchy，作者完整期刊稿，§2.3.1 Example 2.5、式 (6)，以及 §3 Theorems 3.2–3.3；无权仿射资源的整数不等式、光滑性及无遗憾推广。部分早期会议版本的例子编号不同。
Tim Roughgarden，Routing Games，载 Algorithmic Game Theory，2007，作者章节，§18.2.2 Example 18.6；四玩家三角网络的紧例。

形式陈述 ​

一个使用整数负载的不等式 ​

从单人偏离拼出社会比较 ​

四位玩家达到 5/2 ​

常数依赖于哪个模型 ​

同一个证明覆盖粗相关均衡 ​

无遗憾历史的平均成本 ​

反向链接