Congested network笔记(1)

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

——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是博弈论中众多均衡的一种,它是一种非合作博弈均衡,即这种均衡假设了竞争者之间不存在合作,都采用“自私自利”的策略时,系统最终等达到的平衡状态。

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

transport-1

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\),如果小于的话,那么肯定有用户会向花费少的路径走,而这种情况显然还没有平衡。

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

transport-2

已知给定的需求\(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

声明: 本文为0xBBC原创, 转载注明出处喵~

《Congested network笔记(1)》有5个想法

    1. 应该是遇到了少见的MathJax加载问题吧?或者我这边的PHP缓存的问题……多刷新几次试试ww

    2. 好吧,我发现是之前升级时把MathJax的Config给覆盖掉了_(: 」∠)_
      现在应该可以了,如果没有别的坑了的话……

发表评论

电子邮件地址不会被公开。 必填项已用*标注