拥塞博弈

形式陈述 ​

有限无权原子拥塞博弈是有限策略式博弈公理库有限策略式博弈Strategic-form game · Normal-form game · 标准式博弈用玩家、有限策略集和收益函数描述相互影响的选择，并以固定他人策略后的单方偏离定义最佳回应。的一种资源模型。玩家集为 $N=\{1,\dots ,n\}$，资源集 $E$ 有限，每位玩家有非空策略集 $S_i\subseteq 2^E$。一次选择 $s_i\in S_i$ 就是同时使用其中的全部资源。每位玩家的权重都是 $1$；资源 $e$ 有所有玩家共享的成本函数 ${\ell }_e:\{1,\dots ,n\}\to \mathbb{R}$。对剖面 $s$ 定义负载与个人成本

$$x_e(s)=|\{i:e\in s_i\}|,c_i(s)=\sum _{e\in s_i}{\ell }_e(x_e(s)).$$

本页最小化成本，与收益约定的对应为 $u_i=-c_i$。纯策略 Nash 均衡公理库Nash 均衡Nash equilibrium · 纳什均衡 · 混合策略纳什均衡每位玩家都无法在其他人策略固定时通过单方偏离增加期望收益；有限博弈总存在这样的混合策略剖面。满足：对每位玩家及其每个可选资源集合 $t_i\in S_i$，都有 $c_i(s)\le c_i(t_i,s_{-i})$。这里一位玩家可以同时更换多个资源，但其他人的选择固定。

Rosenthal 势函数定理。 定义

$$\mathrm{\Phi }(s)=\sum _{e\in E}\sum _{k=1}^{x_e(s)}{\ell }_e(k),$$

其中零负载的内层和为零。任意单方偏离都满足

$$\mathrm{\Phi }(t_i,s_{-i})-\mathrm{\Phi }(s)=c_i(t_i,s_{-i})-c_i(s).$$

因此该有限博弈至少有一个纯 Nash 均衡，而且任何只允许严格降低自身成本的单方改进序列都有限终止。这个存在性结论不要求成本非负或随负载单调；它依赖有限策略空间、单位权重与共享成本函数。

精确变化为什么成立 ​

固定玩家 $i$，把资源分成离开的 $s_i\setminus t_i$、新进入的 $t_i\setminus s_i$、前后都使用的 $s_i\cap t_i$，以及前后都不使用的资源。离开资源 $e$ 时，其负载从 $x_e$ 降至 $x_e-1$，势函数恰删去最后一项 ${\ell }_e(x_e)$；进入资源时，负载从 $x_e$ 增至 $x_e+1$，势函数恰添上 ${\ell }_e(x_e+1)$。其余资源负载不变。因此

$$\mathrm{\Delta }\mathrm{\Phi }=\sum _{e\in t_i\setminus s_i}{\ell }_e(x_e+1)-\sum _{e\in s_i\setminus t_i}{\ell }_e(x_e).$$

玩家的新旧成本作差时，交集资源的成本相同并抵消，余下恰是右式。这证明的是每次变化完全相等，比仅要求两者同号更强，故称精确势函数。

从势函数得到存在与终止 ​

策略剖面总数有限，所以 $\mathrm{\Phi }$ 取得全局最小值。若最小点允许某位玩家严格降成本，精确变化式就会让 $\mathrm{\Phi }$ 更小，矛盾。因此每个全局最小点都是纯均衡。更准确地说，纯均衡恰是关于所有单方换策略操作的非严格局部最小点；它不必是全局最小点。

沿严格改进序列，$\mathrm{\Phi }$ 每步严格下降，故不可能再次访问同一个剖面。序列最多经过 $\prod _i|S_i|$ 个不同剖面。若算法在存在严格改进时就继续执行一个这样的偏离，终点一定是纯均衡。这个状态数界可能很大，并不自动给出多项式时间算法。

直觉

一条资源被 $x$ 人使用时，势函数依次记下第一位、第二位、直到第 $x$ 位使用者的成本。当前最后一项正是一个人离开时省下的成本，下一项正是一个人加入时要支付的成本。这里的“先后”只是记账顺序，不要求玩家真的依次到达。

个人成本还会随别人的加入而改变，但单次偏离的势函数只需与偏离者自己的变化对齐。这样，不同玩家轮流改进也都在降低同一标量，避免出现彼此改善却绕回原处的严格改进环。

例子与边界

两条资源上的一次完整改进 ​

两位玩家各选资源 $A$ 或 $B$，成本为 ${\ell }_A(k)=k$、${\ell }_B(k)=3/2$。若双方都选 $A$，每人成本为 $2$，而

$$\mathrm{\Phi }(A,A)=1+2=3.$$

让第一位玩家改选 $B$，新成本为 $3/2$，另一位玩家留在 $A$ 的成本为 $1$。新势函数为

$$\mathrm{\Phi }(B,A)=\frac{3}{2}+1=\frac{5}{2},\mathrm{\Delta }\mathrm{\Phi }=-\frac{1}{2}=\mathrm{\Delta }{c}_1.$$

这是纯均衡：选 $B$ 的人回到 $A$ 要付 $2>3/2$，选 $A$ 的人去 $B$ 要付 $3/2>1$。社会总成本却从 $4$ 变为 $5/2$，下降 $3/2$，并不等于势函数下降的 $1/2$。原因是第一人的离开也让第二人的成本下降了 $1$。

允许平局移动就不保证终止 ​

若两条资源对任意负载都收取成本 $1$，则每个剖面都是纯均衡。一位玩家仍可以在 $A,B$ 之间无限交替，每次都是最佳回应，却没有严格改进，势函数也不下降。因此“不断执行最佳回应”必须说明如何处理平局；只在当前策略不是最佳回应时才改选最佳回应，才属于上面的严格改进过程。

若让一个权重为 $w_i$ 的玩家一次改变 $w_i$ 单位负载，或者让同一资源对不同玩家使用不同的成本函数，前面的逐项抵消就不能直接套用。这样的模型需要另行寻找势函数或存在性条件，本页没有对它们给出结论。

推论与应用

路径选择是一个直接实例：有向边是资源，玩家的一条允许路径是资源子集，边成本由通过它的玩家数决定。玩家也可以选择机器集合、时间段组合等；证明只使用资源集合结构，不要求策略一定是路径。

势函数保证稳定状态存在，却没有保证社会成本最小。社会目标通常是

$$C(s)=\sum _i{c}_i(s)=\sum _{e\in E}{x}_e(s){\ell }_e(x_e(s)),$$

其中零负载资源的贡献约定为零。它把每位当前使用者的成本都计入，与 $\mathrm{\Phi }$ 的逐层记账不同。无政府价格公理库无政府价格Price of anarchy · PoA · 无序代价 · Smoothness bound比较最坏均衡与社会最优的总成本，并证明有限无权原子拥塞博弈在非负仿射成本下具有紧的 5/2 界。据此比较最坏均衡与社会最优：在非负仿射成本下，最坏纯均衡的总成本恰可达到最优的 $5/2$ 倍。

参考资料

• Robert W. Rosenthal，A Class of Games Possessing Pure-Strategy Nash Equilibria，International Journal of Game Theory 2，1973，pp. 65–67，§1–2；有限资源模型与势函数存在性证明。
• Tim Roughgarden，Routing Games，载 Algorithmic Game Theory，2007，作者章节，§18.2.2、§18.3.2；原子路径选择模型与 Theorem 18.12 的纯均衡存在性。