最坏均衡与最佳解比

最坏均衡与最佳解比（英语：Price of Anarchy，PoA），是赛局理论中的一个概念，目的是为了衡量在一个赛局中，由于参与者的自私所导致整个系统的效能降低。在这个概念中，所谓的系统和效率可以指很多方面。例如在一个城市里交通中，有A和B两个地点，有一群人开车从A前往B，而在这两个地点之间有不止一条道路可以选择。在这个模型里，效率指的是这群人到达目的地所需要的平均时间，这些参与者可以通过集中决策从而达成最佳效率，也可以基于自私的立场而决定自己的决策，从而达成一个或多个纳什均衡。在这些纳什均衡中，最差的效率比上最佳效率就是最坏均衡与最佳解比。

数学定义

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

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

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

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

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

囚徒困境

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

	出卖	抗供
出卖	1, 1	7, 0
抗供	0, 7	5, 5

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

工作排程问题

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

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

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

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

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

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

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

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

宣称：对于每个工作排程的赛局，纯PoA最多为$M$。

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

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

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

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

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

自私路线问题

布雷斯悖论

主条目：布雷斯悖论

布雷斯悖论的例子

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

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

另见

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

外部链接

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