最坏均衡与最佳解比

假设存在博弈${\displaystyle G=(N,S,u)}$ ，存在参与者集合${\displaystyle N}$ ，每个参与者又存在决策集合${\displaystyle S_{i}}$ 和效用函数${\displaystyle u_{i}:S\rightarrow \mathbb {R} }$ （其中${\displaystyle S=S_{1}\times ...\times S_{n}}$ 也被称为结果集）。对此，我们还可以定义一个衡量整体好坏的指标${\displaystyle Welf:S\rightarrow \mathbb {R} }$ ，通常可以是所有参与者效能的总和，即${\displaystyle Welf(s)=\sum _{i\in N}u_{i}(s),}$ ，或者是所有参与者效能的最小值，即${\displaystyle Welf(s)=\min _{i\in N}u_{i}(s),}$ ，当然也可以根据自身需要进行定义。

我们先定义一个决策集合${\displaystyle Equil\subseteq S}$ 满足均衡策略，那么最坏均衡与最佳解比数学定义如下：

${\displaystyle PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}}$ 

当然，对于收益函数，当然是多多益善，但是对于损失函数${\displaystyle Cost:S\rightarrow \mathbb {R} }$ ，则完全相反：

${\displaystyle PoA={\frac {\max _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}}$ 

在2x2的囚徒困境中，有如下的代价矩阵：

定义损失函数为${\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2})}$ 。在纳什均衡中，只有双方都选择招供，函数值为2.但是最好的结果是都不招供，函数值为10，故最坏均衡与最佳解比为${\displaystyle 10/2=5}$ 。

排程问题其实是最坏均衡与最佳解比的一个实例。有${\displaystyle N}$ 个参与者，每个参与者都有一个任务要完成，他们可以从${\displaystyle M}$ 台机器中选择一台来完成任务。在这一问题中最坏均衡与最佳解比对各行其是和集中安排机器进行了比较。

每一台机器都具有速度${\displaystyle s_{1},\ldots ,s_{M}>0.}$ ，每一项工作都具有权重${\displaystyle w_{1},\ldots ,w_{N}>0.}$ 。每名参与者都选择一台机器来完成工作，因此，每名参与者的决策为${\displaystyle A_{i}=\{1,2,\ldots ,M\}.}$ 。定义第${\displaystyle j}$ 台机器的负载为：

${\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.}$ 

参与者${\displaystyle i}$ 的成本函数为${\displaystyle c_{i}(a)=L_{a_{i}}(a),}$ ，也就是此人所选的机器负载。考虑到平均成本函数${\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)}$ ，我们称之为最大完工时间。

我们想到了纯策略和混合策略这两种策略，并且很容易知道混合策略时的最坏均衡与最佳解比肯定大于或等于纯策略时的最坏均衡与最佳解比。道理很简单，那是因为纯策略是一种特殊的混合策略，就好比正方形是一种特殊的矩形。首先我们要讨论是否存在纯纳什均衡。

宣称：在排程问题中，至少存在一个纳什均衡。

证明：我们想要全域最优解${\displaystyle a^{*}}$ 。这意味着按照这一种分配方式，我们能获得最小的最大完工时间。但是仅知道这些还不够，可能有多种分配方式有着共同的最大完工时间。因此，在这些分配方式里面再选出拥有着最小的第二大完工时间的分配方式，以此类推，直到第${\displaystyle M}$ 大时筛选出唯一的分配方式。

我们声称这是一个纯策略的纳什均衡。接下来可以运用反证法证明：假设某个参与者${\displaystyle i}$ 可以通过从机器${\displaystyle j}$ 移动到机器${\displaystyle k}$ 来改进自己的负载。这意味着移动后机器${\displaystyle k}$ 的负载依然小于移动前机器${\displaystyle j}$ 的负载。由于移动后机器${\displaystyle j}$ 的负载必须减少并且没有其他机器受到影响，这意味着新分配肯定减少了第 ${\displaystyle j}$ 大（或排名更高）的负载。但是这样一来就违背了之前选出的唯一的分配方式。 Q.E.D.

宣称：对于每个工作排程的博弈，纯PoA最多为${\displaystyle M}$ 。

证明：不难求出，在在任何混合策略纳什均衡${\displaystyle \sigma }$ 时所获得的收益上限为：

${\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.}$ 

为了清楚地说明情况，在纯策略${\displaystyle a}$ 时，不难看出：

${\displaystyle w(a)\geq {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geq {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.}$ 

由于上述情况也适用于社会最优，比较${\displaystyle w(\sigma )}$ 和${\displaystyle w(a)}$ 的比率证明了该宣称。 Q.E.D

布雷斯悖论

考虑右图中的交通网，有4000辆车打算在其中路上通行。通过的时间从起点到A点和从B点到终点均是路上车的数量除以100，而从起点到B点和从A点到终点均是固定的45分钟。如果近路不存在（即交通网上只有4条路），从起点到A点到终点需要的时间是 ${\displaystyle {\tfrac {A}{100}}+45}$ ，而从起点到B点到终点需要的时间是 ${\displaystyle {\tfrac {B}{100}}+45}$ 。如果其中一条路的通过时间较短，是不可以达到纳什均衡点的，因为理性的司机都会选择较短的路。因为有4000辆车，从 ${\displaystyle A+B=4000}$  可以解得平均 ${\displaystyle A=B=2000}$ ，这样每条路的平均通过时间都是 ${\displaystyle {\tfrac {2000}{100}}+45=65}$  分钟。

现在假设有了一条近路（如虚线所示），其通过时间接近于0，在这种情况下，所有的司机都会选择从起点到A点这条线路，因为就算所有的车都走这条路，通过时间也不过40分钟，小于起点到B点的45分钟。到达A点之后，所有的司机都会选择从用接近0的时间行驶到到B再到终点，因为就算所有的车都走这条路，通过时间也不过40分钟，小于A点到终点的45分钟。这样所有车的通过时间是${\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}$  分钟，比不存在近道的时候还多了15分钟。就算不走这条路，时间也不会缩短，因为原先的路线（起点→A→终点；起点→B→终点）的时间都变成了85分钟。如果大家都约定好不走近路，那么都可以节约15分钟的时间。但是，由于单个的司机总是能从抄近道上获益，所以这种约定是不稳定的，布雷斯悖论便出现了。

• 最好均衡与最佳解比
• 公地悲剧

• 多工玩家排程博弈中的随机本机政策 （页面存档备份，存于互联网档案馆）