Представьте себе, что транспортное управление мегаполиса тратит миллиарды долларов на строительство нового бессветофорного моста с нулевой задержкой, чтобы разгрузить утренние пробки. Здравый смысл подсказывает, что новая дорога может только помочь: общая пропускная способность дорожной сети строго выросла, ни одна старая дорога не была закрыта, и любой водитель, которому не нравится новый мост, может продолжать ездить по прежнему маршруту. Как расширение свободы выбора может ухудшить положение абсолютно всех?

В 1968 году немецкий математик Дитрих Браес (Dietrich Braess) опубликовал в журнале Unternehmensforschung фундаментальную работу “Über ein Paradoxon aus der Verkehrsplanung”, которая навсегда разрушила эту интуицию. Браес математически строго доказал, что когда каждый водитель выбирает маршрут эгоистично, стремясь минимизировать собственное время в пути (эгоистичная маршрутизация / Selfish Routing), добавление новой сверхбыстрой дороги может привести к тому, что в новом равновесии время в пути строго увеличится для 100 % водителей! Это контринтуитивное явление получило название парадокса Браеса (Braess’s Paradox).

Ещё более поразительно то, что парадокс Браеса не связан с нехваткой информации или человеческой иррациональностью: он неизбежно возникает как единственное равновесие Нэша (равновесие Уордропа) в некооперативной игре перегрузки. Более того, поскольку пассивные физические системы минимизируют выпуклую потенциальную энергию, математически изоморфную потенциалу Бекмана для транспортных потоков, парадокс Браеса проявляется в маршрутизации пакетов в Интернете (OSPF/BGP), в высоковольтных электросетях, в мезоскопических квантовых кольцах и в классической механике: как показали Джоэл Коэн и Пол Хоровиц в журнале Nature (1991), в системе из пружин и нитей, удерживающей тяжёлый груз, разрезание ножницами натянутой центральной несущей нити заставляет груз подняться вверх против силы тяжести!

1. Статья Дитриха Браеса (1968) и 4-узловая ромбовидная сеть

1.1 Топология сети и функции задержки (Latency Functions)

Пусть общий поток \(F = 4\,000\text{ автомобилей/час}\) (или \(F = 1\) в нормированных единицах) движется из начального узла \(S\) в конечный узел \(T\) через два промежуточных узла \(A\) и \(B\). Время проезда (функция задержки) \(\ell_e(f_e)\) каждого ориентированного ребра \(e \in E\) зависит от потока \(f_e\):

1. Ребро \(S \to A\) (Узкий мост): Время проезда линейно растёт с потоком \(f_{SA}\): \(\ell_{SA}(f_{SA}) = \frac{f_{SA}}{100}\text{ минут}\)
2. Ребро \(A \to T\) (Широкое обходное шоссе): Не подвержено заторам, время постоянно: \(\ell_{AT}(f_{AT}) = 45\text{ минут}\)
3. Ребро \(S \to B\) (Широкое обходное шоссе): Симметрично \(A \to T\), время постоянно: \(\ell_{SB}(f_{SB}) = 45\text{ минут}\)
4. Ребро \(B \to T\) (Узкий мост): Идентично \(S \to A\), время линейно зависит от потока \(f_{BT}\): \(\ell_{BT}(f_{BT}) = \frac{f_{BT}}{100}\text{ минут}\)

  flowchart TD
    subgraph Before["Состояние 1: До постройки новой дороги (Поток F = 4 000 авто/ч, у всех 65 мин)"]
        S1["Старт S (4 000 авто)"] -->|"S→A: f/100 мин (2 000 авто → 20 мин)"| A1["Узел A"]
        S1 -->|"S→B: 45 мин (2 000 авто → 45 мин)"| B1["Узел B"]
        A1 -->|"A→T: 45 мин (2 000 авто → 45 мин)"| T1["Финиш T (65 мин у всех)"]
        B1 -->|"B→T: f/100 мин (2 000 авто → 20 мин)"| T1
    end

1.2 Состояние 1: Равновесие до постройки перемычки (\(65\) минут)

Это распределение одновременно является общественным оптимумом (\(f^*\)).

1.3 Состояние 2: Открытие мгновенной перемычки \(A \to B\) (\(80\) минут!)

Между узлами \(A\) и \(B\) открывается сверхскоростная односторонняя магистраль \(A \to B\) с нулевым временем проезда \(\ell_{AB}(f_{AB}) = 0\) минут.

  flowchart TD
    subgraph After["Состояние 2: После открытия перемычки A→B (0 мин) — Все 4 000 авто едут зигзагом (80 мин!)"]
        S2["Старт S (4 000 авто)"] ==>|"S→A: f/100 мин (4 000 авто → 40 мин)"| A2["Узел A"]
        S2 -.->|"S→B: 45 мин (0 авто — заброшено)"| B2["Узел B"]
        A2 ==>|"Новая дорога A→B: 0 мин (4 000 авто → 0 мин)"| B2
        A2 -.->|"A→T: 45 мин (0 авто — заброшено)"| T2["Финиш T (Все едут 80 мин!)"]
        B2 ==>|"B→T: f/100 мин (4 000 авто → 40 мин)"| T2
    end

Появляется третий маршрут — зигзагообразный путь \(P_{\text{зиг}} = (S \to A \to B \to T)\). Анализ строго доминирующих стратегий показывает:

1. Выбор в узле \(S\) (\(S \to A \to B\) против \(S \to B\)): Даже если все \(4\,000\) машин поедут через узкий мост \(S \to A\), время на нём составит максимум \(\frac{4000}{100} = 40\) минут. Так как переезд \(A \to B\) занимает \(0\) минут, путь до \(B\) через \(S \to A \to B\) занимает не более \(40\) минут, тогда как шоссе \(S \to B\) всегда требует \(45\) минут! Следовательно, выбор \(S \to A\) — строго доминирующая стратегия, и \(100\,\%\) водителей отказываются от \(S \to B\) (\(f_{SB} = 0\)).
2. Выбор в узле \(A\) (\(A \to B \to T\) против \(A \to T\)): Аналогично, путь из \(A\) в \(T\) через \(A \to B \to T\) занимает максимум \(0 + \frac{4000}{100} = 40\) минут \(< 45\) минут, строго доминируя над шоссе \(A \to T\) (\(f_{AT} = 0\)).
3. Новое единственное равновесие (\(80\) минут): Все \(4\,000\) автомобилей устремляются по зигзагу \(S \to A \to B \to T\), дважды проезжая по перегруженным узким мостам: \(T_{\text{после}} = \frac{4000}{100} + 0 + \frac{4000}{100} = 40 + 0 + 40 = 80\text{ минут!}\) Любой водитель, решивший в одиночку вернуться на старый маршрут \(S \to A \to T\) или \(S \to B \to T\), потратит \(40 + 45 = 85\) минут. Все участники оказываются заперты в многопользовательской дилемме заключённого (+15 минут или \(+23{,}1\,\%\) для каждого!).

2. Два принципа Уордропа (1952) и выпуклый потенциал Бекмана (1956)

Пусть \(G = (V, E)\) — ориентированный граф с общим спросом \(F\), множеством допустимых потоков \(\mathcal{F} = \{f \ge 0 : \sum_{P \in \mathcal{P}} f_P = F\}\) и неубывающими дифференцируемыми задержками рёбер \(\ell_e(f_e)\).

2.1 Первый принцип Уордропа (Пользовательское равновесие \(f^{\text{EQ}}\))

2.2 Второй принцип Уордропа (Общественный оптимум \(f^*\)) и экстерналии Пигу

2.3 Выпуклая потенциальная функция Бекмана–Макгуайра–Уинстена (1956)

Для линейных задержек \(\ell_e(u) = a_e u + b_e\) сравнение \(\Phi(f) = \sum_e (\frac{1}{2}a_e f_e^2 + b_e f_e)\) и \(C(f) = \sum_e (a_e f_e^2 + b_e f_e)\) показывает, что эгоистичные водители учитывают квадратичный штраф за заторы \(a_e f_e^2\) ровно вполовинную силу (множитель \(\frac{1}{2}\)).

3. Теорема Рафгардена и Тардош (2002): Доказательство оценки \(\text{PoA} \le 4/3\)

Цена анархии (\(\text{PoA}\)) (Koutsoupias & Papadimitriou, 1999) определяется как \(\text{PoA} = \frac{C(f^{\text{EQ}})}{C(f^*)}\). На 2-звенной сети Пигу (1920) (\(\ell_1(x)=1, \ell_2(x)=x, F=1\)) имеем \(C(f^{\text{EQ}}) = 1\) и \(C(f^*) = \frac{3}{4}\) (при \(x^* = \frac{1}{2}\)), откуда \(\text{PoA} = \frac{4}{3}\).

\[\text{PoA}_{\text{linear}} = \frac{C(f^{\text{EQ}})}{C(f^*)} \le \frac{4}{3}\]

【Полное доказательство】

1. Вариационное неравенство: Из \(\sum_{e \in E} \ell_e(f_e^{\text{EQ}})(f_e^* - f_e^{\text{EQ}}) \ge 0\) следует: \(C(f^{\text{EQ}}) = \sum_{e \in E} f_e^{\text{EQ}} \ell_e(f_e^{\text{EQ}}) \le \sum_{e \in E} f_e^* \ell_e(f_e^{\text{EQ}})\)
2. Выделение полного квадрата на каждом ребре: Обозначим \(x = f_e^{\text{EQ}} \ge 0\) и \(y = f_e^* \ge 0\): \(y \ell_e(x) = y(a_e x + b_e) = y(a_e y + b_e) + a_e(xy - y^2) = y \ell_e(y) + a_e\left[\frac{1}{4}x^2 - \left(y - \frac{x}{2}\right)^2\right] \le y \ell_e(y) + \frac{1}{4}a_e x^2 \le y \ell_e(y) + \frac{1}{4} x \ell_e(x)\)
3. Суммирование по всем рёбрам: Суммируя по \(e \in E\), получаем: \(C(f^{\text{EQ}}) \le \sum_{e \in E} f_e^* \ell_e(f_e^{\text{EQ}}) \le C(f^*) + \frac{1}{4}C(f^{\text{EQ}}) \implies \frac{3}{4}C(f^{\text{EQ}}) \le C(f^*) \implies \text{PoA} \le \frac{4}{3} \quad \blacksquare\)

Для полиномиальных задержек степени \(d\) (включая квартическую функцию BPR \(\ell_e(f_e) = t_e^0[1 + 0{,}15(f_e/c_e)^4]\) при \(d=4\)) точная граница равна \(\text{PoA}_d = \frac{(d+1)\sqrt[d]{d+1}}{(d+1)\sqrt[d]{d+1} - d}\) (при \(d=4\) имеем \(\text{PoA}_4 \approx 2{,}1505\)).

4. Физические реализации: Пружинно-нитевой парадокс Коэна и Хоровица (1991)

В 1991 году Джоэл Коэн и Пол Хоровиц (Nature) показали, что механическая система из двух одинаковых пружин (жёсткость \(k\), длина в ненагруженном состоянии \(L_0\)), двух нерастяжимых страховочных нитей длины \(L_s\) и короткой центральной соединительной нити \(A \to B\) (длина \(\approx 0\)), удерживающая груз \(F = Mg\), демонстрирует парадокс Браеса:

• До разрезания центральной нити (Последовательное соединение): Обе пружины несут полную нагрузку \(F\) и растягиваются на \(\frac{F}{k}\) каждая. При \(L_s > L_0 + \frac{F}{k}\) боковые страховочные нити провисают, и глубина подвеса груза равна: \(Y_{\text{до}} = 2L_0 + \frac{2F}{k}\)
• После разрезания центральной нити ножницами (Параллельное соединение): Страховочные нити натягиваются, и две пружины начинают работать параллельно, неся лишь половину веса \(\frac{F}{2}\) каждая и растягиваясь только на \(\frac{F}{2k}\). Новая равновесная глубина: \(Y_{\text{после}} = L_0 + \frac{F}{2k} + L_s\)
• Если \(L_0 + \frac{F}{k} < L_s < L_0 + \frac{3F}{2k}\) (например, \(L_s = L_0 + \frac{5F}{4k}\)), то: \(\Delta Y = Y_{\text{после}} - Y_{\text{до}} = -\frac{F}{4k} < 0\) Разрезание натянутой несущей нити заставляет тяжёлый груз подняться вверх против силы тяжести на величину \(\frac{F}{4k}\)!

5. Реальное градостроительство и плата за перегрузку Пигу (Congestion Pricing)

1. Штутгарт (1969) и Нью-Йорк — 42-я улица (1990) и Бродвей на Таймс-сквер (2009): Закрытие для автомобилей Бродвея (который пересекал прямоугольную сетку Манхэттена по диагонали, в точности как перемычка \(A \to B\) у Браеса) ускорило движение такси в Мидтауне на \(17\,\%\).
2. Сеул — Снос эстакадного шоссе Чхонгечхон (2003–2005): Демонтаж 6-полосной эстакады с потоком \(168\,000\) машин в сутки ради восстановления реки Чхонгечхон устранил бутылочные горлышки съездов, повысил среднюю скорость движения в центре Сеула и снизил летнюю температуру воздуха на \(3{,}6^\circ\text{C}\).
3. Налог Пигу: Введение дорожного сбора \(\tau_e = f_e^* \ell_e'(f_e^*)\), равного предельной экстерналии затора на каждом участке, совмещает равновесие Уордропа с общественным оптимумом (\(\text{PoA} = 1\)).