请考虑以下方案。大量的独立Agent希望遍历一个网络，从某个起始点到某个终结点。他们旅行的每个边缘都需要一些时间，这通常取决于沿着边缘旅行的特工数量。为简单起见，我们将标准化，以便\(x\)表示一定比例的代理(即\(x\)范围从0到1)。下面，我们将用\(\mathcal{E}\)表示边的集合，并\(c_e：[0，1]\to\mathbb{R}\)表示与边\(e\)相关的代价函数。一个非常简单的示例如下所示，其中\(s\)是起点，\(d\)是目的地，边已经用它们的成本进行了标记。
总结所选的整组路径的一种方式是通过流\(f\)，它为每条边分配选择沿着它旅行的代理的归一化比例。例如，如果所有代理都选择上述网络中的顶层路由，则我们将有\(f_{su}=1，f_{ud}=1\)和\(f_{sv}=0，f_{vd}=0\)。当然，还有其他可能的流；可以考虑将所有代理沿着底部路径放置的流，或者以某种方式混合顶部和底部路径的流。1个。
对于一般流程\(f\)，代理在网络导航中承担的总成本为。
在上面的示例中，沿顶部路径(或相当于底部路径)路由所有流量的总成本为\(2\)。但是，如果拆分流量，一半沿着顶部路径，一半沿着底部路径，那么总成本仅为\(0.5c_{su}(0.5)+0.5\cot c_{ud}+0.5\cot c_{sv}(0.5)+0.5\cot_{vd}(0.5)=1.5\)。在本例中，这是最小成本流。可以想象，如果我们是仁慈的独裁者，控制着代理人的选择，我们可能会选择这一结果。
看待此路由问题的另一种方式是从座席的角度来看。假设对于每条路径\(P\)，一定比例的代理选择\(P\)进行遍历。换句话说，我们可以想象我们有一个分布\(g\)，其中\(g_P\geq0\)和\(\sum_{P\in\mathcal{P}}g_P=1\)，其中\(\mathcal{P}\)表示通过网络的\(s-d)条路径的集合。因此，(g_P\)是主体选择路径\(P\)的比例。由于没有更好的名称，我们将这种\(g\)称为路径分布。
考虑路径分布而不是流不会有任何损失。实际上，给定路径分布\(g\)，我们可以通过使\(f_e=\sum_{P：e\in P}g_P\)恢复流，其中和是包含边\(e\)的所有路径上的和。不难证明，这是一个诚实的流程。2个。
那么，从这个角度来看：代理会选择哪条道路？一般来说，一条边的成本取决于它得到多少流量，所以答案实际上取决于其他代理选择的路径。
为了澄清这一点，让我们引入一个关于行为的假设：只有在没有更便宜的替代方案时，代理才会选择一条路径。这既是一个薄弱的假设，从很难与基本原理争辩的意义上说，也是一个强有力的假设，因为我们向每个代理提供了关于手头问题的相当多的信息(例如，网络拓扑、其他代理的行为等等)。
考虑到这一点，请注意，相对于固定流量\(f\)，路径\(P\)的成本为。
形式上，路径分布\(g\)称为(纯Nash)平衡分布，如果。
\[G_P>；0\text{仅当}P\text{最小化}C(P；f)，\]。
换句话说，在均衡分布中，每个代理走的路径相对于其他代理诱导的流是最小的。
这是值得仔细考虑一下的。在均衡分布的情况下，任何特定的代理都没有切换路径的动机。每个代理都认为它周围的社会世界基本上是固定的；其他代理已经诱导了一些流量\(f\)，一个代理所能做的最好的事情就是选择相对于这条路径最便宜的路径。
在我们的简单网络中，只有一个均衡分布：一半的代理采取顶部的路径，另一半采取底部的路径。这种均衡分布的成本是\(1.5)，和以前一样。
简单回顾一下，我们挑出了两种特殊的流。
如果我们扮演一个仁慈的独裁者的角色，我们会选择成本最小化的流程。
平衡流(即由均衡路径分布引起的流)是我们可以想象一群独立的代理满足的流。
有点巧合的是，在我们的玩具网络中，这两个人最终是一样的。但他们不一定非得如此。
那么，如果我们开始向网络添加边缘，会发生什么呢？天真的是，它似乎只会让事情变得更好。当然，添加边不会增加以前任何流的成本(因为它们根本不使用新的边)，而且实际上，它可能会提供一个新的、更便宜的流。因此，作为仁慈的独裁者，不会有太多损失。
但是，当我们从代理人的角度思考时，会发生什么呢？令人惊讶的是，增加一条边可以将平衡流转移到成本更高的地方！举个极端的例子，考虑给我们以前的网络增加一条自由边。
有了这个加法，均衡分布3将所有代理放在路径\(suvd\)上，总成本为2！这就是布雷斯悖论：增加网络容量实际上会增加均衡流量的成本。
我不打算证明这种流是均衡的，但让我来看一下激励因素：以前的分配，把一半的代理放在上半个代理上，把一半的代理放在底部，从旅行者的角度来看，现在是没有吸引力的：相对于那个流，代理切换到(Suvd)的影响是减少他们的路径成本\(0.5\)。诸若此类。
根据定义，均衡流至少与成本最小化的流一样昂贵。比率。
有时被称为无政府状态的代价。对于我们的原始网络，它是\(1\)。添加边后，它是\(4/3\)。
一般而言，流是函数\(f：E\to\mathbb{R}\)(其中\(E\)是边的集合)，满足三个条件：i)离开\(s\)的边上的\(f\)之和是1，ii)进入\(d\)的边上的\(f\)之和是1，以及iii)对于任何其他顶点，传入边上的\(f\)之和等于传出边上的\(f\)之和(即流是‘守恒的’)。↩。
另一方面，在一般网络中，可能有几个路径分布导致相同的流量。↩。
一般来说，像这样的路由博弈可能有几个均衡分布。然而，在本例中，只有一个。↩