人类天性是自私的，而经济行为植根于此"事实"之上。博弈论看似也反映了此种假设。在博弈论最初的形式中，博弈论数学描述"理性的"行为，本质上是将"理性"和"自私"当作同义词。但按照今天的解释，博弈论并非假设人类总是表现得自私——或理性。博弈论告诉你如果人类确实表现得自私或理性，会是怎么样的情形。

——A BEAUTIFUL MATH
John Nash, Game Theory
AND THE MODERN QUEST FOR A CODE OF NATURE

首先需要说明这里“Congested network”中的"network"并非专指计算机网络，它也可以是交通网络，人口迁移网络。或者我们可以将这里的网络理解为「图」，用\(\mathcal{G}\)表示。既然是图的话，那么必定少不了顶点、边，在这里，图\(\mathcal{G}\)是由这些因素定义的：一组共有\(n_\mathcal{L}\)条有向线段(link)的集合，\(\mathcal{L}\)，一组共有\(n_\mathcal{W}\)个源点/终点对(O/D Pair)的集合，\(\mathcal{W}\)。

Nash equilibrium是博弈论中众多均衡的一种，它是一种非合作博弈均衡，即这种均衡假设了竞争者之间不存在合作，都采用“自私自利”的策略时，系统最终等达到的平衡状态。

假设有如下图所示的交通网络

O 为起点(origin)，D 为终点(destination)，并且对每条边分别进行编号。假设这个网络（或可称为系统）总的需求(demand)是\(d\)，并且对于第\(i\)条线段上的流量记为\(x_i\)。在交通网络中，假设从 O 点到 D 点共有n条路径，将第i条记为\(\mathcal{P}_i\)。在这个例子中，一共有4条可能的路径(path)

$$\left\{\begin{align}&\mathcal{P}_{1=(1,4)}\\
&\mathcal{P}_{2=(1,3,5)}\\
&\mathcal{P}_{3=(2,5)}\\
&\mathcal{P}_{4=(2,3,4)}\end{align}\right.$$

那么我们有共计\(n_p\)条无环路径组成的集合\(\mathcal{P}\)，这里要求路径中不包含环应该是容易理解的，如果允许环存在的话，我们就可以有无数多路径了，而那样是没有意义的，也不符合“自私自利”的原则——你的花费是增函数，如果有环的话，那么你的选择必然不是最优。我们使用\(x_p\)来代表路径\(p\)上的流量(flow)

$$x_p=\mathcal{P}_p$$

除此之外，我们还要求对于每个源点/终点对(O/D Pair)\(w\in \mathcal{W}\)来说，都要有

$$\sum_{p\in \mathcal{P}_w}{x_p}=d_w$$

即给定一个源点/终点对(O/D Pair)\(w\)，共有\(n_p\)条无环路径组成的集合\(\mathcal{P}_w\)，如果我们把集合\(\mathcal{P}_w\)中所有的流量\(x_p\)加起来，必须要等于这个源点/终点对(O/D Pair)\(w\)的需求\(d\)

接下来，我们为第\(i\)条线段计算它的流量(flow)

$$f_i=\sum_{p\in \mathcal{P}}{x_p\delta_{ap}}$$

其中，如果路径\(p\)包含了线段\(i\)，那么\(\delta_{ap}=1\)，否则\(\delta_{ap}=0\)。即对于\(f_i\)来讲，只要某条路径\(p\)使用了\(i\)这条线段，则都算入\(f_i\)中(\(f_i\)代表第i条线段上的流量)。那么对于上图则有

$$\left\{\begin{align}f_1=\mathcal{P}_1+\mathcal{P}_2\\
f_2=\mathcal{P}_3+\mathcal{P}_4\\
f_3=\mathcal{P}_2+\mathcal{P}_4\\
f_4=\mathcal{P}_2+\mathcal{P}_3\\
f_5=\mathcal{P}_1+\mathcal{P}_4\end{align}\right.$$

我们通过凹函数\(\mathcal{c}_a(\mathcal{f_a})\)表示在线段\(a\)上，当有\(f_a\)流量时，单个流量的花费(cost)。为什么要这么定义呢，假如我们把流量想成用户，当新的用户想用线段\(a\)时，他不能把原来的花费函数用来计算自己加入以后的花费，因为他的加入实际上也影响了这个系统，这个系统要为他服务，所以花费增加了。这和现实世界中是一样的，想想一下城市交通，如果在路上的车越多，大家的出行时间就会越长；或者在计算机网络中，当同一个网络，使用的人越多，它整体的服务就越慢。

接着我们定义在路径\(p\)上的总花费\(\mathcal{C}_p(x_p)\)，显然，它是关于路径\(p\)上的流量\(x_p\)的函数。

在使用 Nash equilibrium 时，若要求均衡解，有如下定义

$$\left\{\begin{align}\mathcal{C}_P(x^*)&=\lambda_w &\text{ if } x^{*}_p&\gt 0\\
\mathcal{C}_P(x^*)&\geq\lambda_w &\text{ if } x^{*}_p&= 0\end{align}\right.$$

即对于给定的源点/终点对(O/D Pair)\(w\)，有流量模式\(x^*\)，\(x^*\)是一个向量，其每一个分量代表连接了这个给定源点/终点对(O/D Pair)\(w\)的路径\(p\)上的流量。这些路径\(p\)上的花费\(\lambda_w\)都相等且最小。换种说法则是，在给定源点/终点对(O/D Pair)\(w\)时，如果路径\(\mathcal{P}^{*}_j\)有被选择，那么均衡时，任意路径\(\mathcal{P}^{*}_j\)的花费\(\mathcal{C}_p{_j}\)都等于计算出的\(\lambda_w\)。如果\(P^{*}_j\)没有被选择，就说明该路径的花费\(\mathcal{C}_p{_j}\geq\lambda_w\)，如果小于的话，那么肯定有用户会向花费少的路径走，而这种情况显然还没有平衡。

对于一个简单一点的例子，如下图

已知给定的需求\(d\)和各线段的花费函数\(\mathcal{c}_a\)

$$d=100\\
\left\{\begin{align}\mathcal{c}_1&=f_1+5\\
\mathcal{c}_2&=2f_2+10\\
\mathcal{c}_3&=f_3+15\end{align}\right.$$

根据先前对\(f_i\)的定义，可以知道

$$\left\{\begin{align} f_1&=\mathcal{P}_{1=(1,3)}\\
f_2&=\mathcal{P}_{2=(2,3)}\\
f_3&=\mathcal{P}_1+\mathcal{P}_2\end{align}\right.$$

再根据对\(\mathcal{C}\)的定义，路径\(p\)上的花费是该路径所使用的线段\(i\)的花费\(c_i\)之和。

$$\left\{\begin{align}\mathcal{C}_p{^*_1}&=\mathcal{c}_1+\mathcal{c}_3\\
&=\mathcal{P}^*_1+5+(\mathcal{P}^*_1+\mathcal{P}^*_2)+15\\
&=\lambda\\
\mathcal{C}_p{^*_2}&=\mathcal{c}_2+\mathcal{c}_3\\
&=2\mathcal{P}^*_2+10+(\mathcal{P}^*_1+\mathcal{P}^*_2)+15\\
&=\lambda\end{align}\right.$$

并且我们的条件是

$$\left\{\begin{align}\mathcal{P}^*_1+\mathcal{P}^*_2&=d=100\\
\mathcal{P}^*_1,\mathcal{P}^*_2&\ge 0\end{align}\right.$$

于是化简联立方程

$$\left\{\begin{align}2\mathcal{P}^*_1+\mathcal{P}^*_2-\lambda&=-20\\
\mathcal{P}^*_1+3\mathcal{P}^*_2-\lambda&=-25\\
\mathcal{P}^*_1+\mathcal{P}^*_2&=100\end{align}\right.$$

求解线性方程可得

$$\left\{\begin{align}\mathcal{P}^*_1&=68.3\\
\mathcal{P}^*_2&=31.6\\
\lambda&=188.33\end{align}\right.$$

即该系统达到平衡时，选择\(\mathcal{P}_1\)的有68.3个单位，选择\(\mathcal{P}_2\)的有31.6个单位，并且选择\(\mathcal{P}_1\)与\(\mathcal{P}_2\)对每个单位的花费都是188.33

刚才计算出的是对每个单位来说的最优，但是每个单位最优，不一定是系统最优，要计算系统最优的话，需要计算如下方程。

$$\text{min}\, \mathcal{Z}=\sum_{i}(\mathcal{c}_i(f_i) f_i)$$

\(\mathcal{Z}\)代表一个和，这个和是由每条线段\(i\)上，单个流量的花费\(\mathcal{c}_i(f_i)\)乘上线段\(i\)上所有的流量\(f_i\)，这个乘积是线段\(i\)上有\(f_i\)流量时的总花费，将所有线段的总花费加在一起，则是整个系统的总花费\(\mathcal{Z}\)，我们的目标是要最小化它。将\(c_i\)与\(f_i\)带入\(\mathcal{Z}\)中得

$$\mathcal{Z}=(f^2_1+5f_1)+(2f^2_2+10f_2)+(f^2_3+15f_3)$$

因为现在想要求解的是\(\underline{\mathcal{P}_j}\)（我们使用\(\underline{\mathcal{P}_j}\)来代表最优解），即站在系统的角度来看，每条路径\(\mathcal{P}_j\)上的流量是多少时最为合适。于是使用\(\mathcal{P}_j\)替换\(f_i\)

$$\mathcal{Z}=(\mathcal{P}^2_1+5\mathcal{P}_1)+(2\mathcal{P}^2_2+10\mathcal{P}_2)+((\mathcal{P}_1+\mathcal{P}_2)^2+15(\mathcal{P}_1+\mathcal{P}_2))$$

此时\(\mathcal{Z}\)是两个自变量\(\mathcal{P}_1,\mathcal{P}_2\)的函数，并且我们有约束条件，

$$\left\{\begin{align}\text{min}\, \mathcal{Z}&=(\mathcal{P}^2_1+5\mathcal{P}_1)+(2\mathcal{P}^2_2+10\mathcal{P}_2)+((\mathcal{P}_1+\mathcal{P}_2)^2+15(\mathcal{P}_1+\mathcal{P}_2))\\
\text{s.t }\mathcal{P}_1+\mathcal{P}_2 &= 100\end{align}\right.$$

可以看出这是一个典型的在有等式约束的优化问题，一般具有如下形式

$$\left\{\begin{align}min\, \mathcal{Z}&=f(x,y)\\
\text{s.t }\varphi(x,y) &= 0\end{align}\right.$$

此时可通过Lagrange Multiplier（拉格朗日乘数法）求解，先构造函数

$$\mathcal{F}(x,y)=f(x,y)+\lambda\varphi(x,y)$$

在上式中的\(\lambda\)即为Lagrange Multiplier。然后求解方程组

$$\left\{\begin{align}\frac{\partial{\mathcal{F}}}{\partial{\mathcal{x}}}=f_x(x,y)+\lambda\varphi_x(x,y) &= 0\\
\frac{\partial{\mathcal{F}}}{\partial{\mathcal{y}}}=f_y(x,y)+\lambda\varphi_y(x,y) &= 0\\
\varphi(x,y) &= 0\end{align}\right.$$

解出\(x,y,\lambda\)，其中\((x,y)\)就是可能的极值点。

在这个例子中，

$$\mathcal{F}=(\underline{\mathcal{P}^2_1}+5\underline{\mathcal{P}_1})+(2\underline{\mathcal{P}^2_2}+10\underline{\mathcal{P}_2})+((\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2})^2+15(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}))-\lambda(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}-100)$$

$$\left\{\begin{align}\frac{\partial\mathcal{F}}{\partial\underline{\mathcal{P}_1}}&=(2\underline{\mathcal{P}_1}+5)+2(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2})+15-\lambda=0\\
\frac{\partial\mathcal{F}}{\partial\underline{\mathcal{P}_2}}&=(4\underline{\mathcal{P}_2}+10)+2(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2})+15-\lambda=0\\
\varphi(\underline{\mathcal{P}_1},\underline{\mathcal{P}_2}) &=\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}-100=0\end{align}\right.$$

化简(1), (2)式可得

$$\begin{align}\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_1}}-\frac{\partial\mathcal{Z}}{\partial\underline{\mathcal{P}_2}}&=(2\underline{\mathcal{P}_1}+5)-(4\underline{\mathcal{P}_2}+10)\\
&=2\underline{\mathcal{P}_1}-4\underline{\mathcal{P}_2}-5\\
&=\underline{\mathcal{P}_1}-2\underline{\mathcal{P}_2}-2.5\\
&=0\end{align}$$

联立给定的条件

$$\left\{\begin{align}\underline{\mathcal{P}_1}-2\underline{\mathcal{P}_2}-2.5&=0\\
\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}&=100\end{align}\right.$$

解得

$$\left\{\begin{align}\underline{\mathcal{P}_1}&=67.5\\
\underline{\mathcal{P}_2}&=32.5\\
\lambda&=355\end{align}\right.$$

对比均衡解和最优解的个体花费和系统花费，当使用均衡解时，个体花费\(\mathcal{C}_{\mathcal{P}^{*}_1}=\mathcal{C}_{\mathcal{P}^{*}_2}=188.33\)，系统花费为18833。

当使用最优解时，个体花费如下

$$\begin{align}\mathcal{C}_{\underline{\mathcal{P}_1}}&=\mathcal{c}_1+\mathcal{c}_3\\
&=(f_1+5)+(f_3+15)\\
&=(\underline{\mathcal{P}_1}+5)+(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}+15)\\
&=187.5\\
\mathcal{C}_{\underline{\mathcal{P}_2}}&=\mathcal{c}_2+\mathcal{c}_3\\
&=(2f_2+10)+(f_3+15)\\
&=(\underline{\mathcal{P}_2}+10)+(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2}+15)\\
&=190\end{align}$$

系统花费则为

$$\begin{align}\mathcal{Z}&=\sum_i(\mathcal{c}_i(f_i) f_i)\\
&=\mathcal{c}_1(f_1)f_1+\mathcal{c}_2(f_2)f_2+\mathcal{c}_3(f_3)f_3\\
&=(f^2_1+5f_1)+(2f^2_2+10f_2)+(f^2_3+15f_3)\\
&=(\underline{\mathcal{P}^2_1}+5\underline{\mathcal{P}_1})+(2\underline{\mathcal{P}^2_2}+10\underline{\mathcal{P}_2})+(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2})^2+15(\underline{\mathcal{P}_1}+\underline{\mathcal{P}_2})\\
&=18831.25
\end{align}$$

在这种情况下，系统花费18831.25低于18833，那么可以考虑让均衡解向最优解移动，在这个特定的例子中，可以考虑的方法有增加\(\mathcal{P}_1\)段的收费，让它与\(\mathcal{P}_2\)段相同；也可以把\(\mathcal{P}_2\)段的费用降到与\(\mathcal{P}_1\)段相同等等。

Reference:
[1]. A network efficiency measure for congested networks