Imagine que la autoridad de transporte de una metrópoli invierte miles de millones de dólares en construir un puente exprés sin demoras para aliviar los atascos matutinos. El sentido común sugiere que añadir una carretera nueva solo puede mejorar el tráfico: la capacidad total de la red aumenta, no se elimina ninguna vía existente y quien no quiera usar el nuevo puente puede seguir tomando su ruta habitual. ¿Cómo podría perjudicar a todos el hecho de ampliar las opciones disponibles?

En 1968, el matemático alemán Dietrich Braess publicó un artículo histórico (“Über ein Paradoxon aus der Verkehrsplanung”) que demolió esta intuición. Braess demostró matemáticamente que cuando cada conductor elige su ruta de forma egoísta para minimizar su propio tiempo de viaje (enrutamiento egoísta / Selfish Routing), añadir un atajo de latencia cero puede hacer que el tiempo de viaje en equilibrio del 100 % de los conductores sea estrictamente mayor. Este fenómeno contraintuitivo se conoce como la paradoja de Braess.

Más sorprendente aún es que la paradoja de Braess no se debe a información imperfecta ni a irracionalidad humana: surge inevitablemente como el único equilibrio de Nash (equilibrio de Wardrop) de un juego de congestión no cooperativo. Además, dado que los sistemas físicos pasivos minimizan funciones de energía potencial convexas matemáticamente isomorfas al potencial de tráfico de Beckmann, la paradoja de Braess se manifiesta de forma idéntica en el enrutamiento de paquetes de Internet (OSPF/BGP), en redes eléctricas de corriente alterna, en anillos cuánticos mesoscópicos y en la mecánica clásica: como demostraron Joel E. Cohen y Paul Horowitz en Nature (1991), en una red de muelles y cuerdas que sostiene un peso pesado, ¡cortar con unas tijeras una cuerda central tensa hace que el peso suba hacia arriba en contra de la gravedad!

1. El artículo de Dietrich Braess (1968) y la red diamante de 4 nodos

1.1 Topología de la red y funciones de latencia

Supongamos que un flujo total de $F = 4.000\text{ vehículos/hora}$ (o $F = 1$ en unidades normalizadas) viaja desde el origen $S$ hasta el destino $T$ pasando por dos nodos intermedios $A$ y $B$. El tiempo de viaje (función de latencia) $\ell_e(f_e)$ de cada arco dirigido $e \in E$ en función de su flujo $f_e$ viene dado por:

1. Arco $S \to A$ (Puente estrecho congestionable): Su tiempo de recorrido crece linealmente con el flujo $f_{SA}$: $$\ell_{SA}(f_{SA}) = \frac{f_{SA}}{100}\text{ minutos}$$
2. Arco $A \to T$ (Autopista amplia de circunvalación): Inmune a la congestión, tiempo constante: $$\ell_{AT}(f_{AT}) = 45\text{ minutos}$$
3. Arco $S \to B$ (Autopista amplia de circunvalación): Simétrica a $A \to T$, tiempo constante: $$\ell_{SB}(f_{SB}) = 45\text{ minutos}$$
4. Arco $B \to T$ (Puente estrecho congestionable): Idéntico a $S \to A$, tiempo lineal: $$\ell_{BT}(f_{BT}) = \frac{f_{BT}}{100}\text{ minutos}$$

  flowchart TD
    subgraph Before["Estado 1: Antes de la nueva vía (Flujo total F = 4.000 veh/h, todos tardan 65 min)"]
        S1["Origen S (4.000 veh)"] -->|"S→A: f/100 min (2.000 veh → 20 min)"| A1["Nodo A"]
        S1 -->|"S→B: 45 min (2.000 veh → 45 min)"| B1["Nodo B"]
        A1 -->|"A→T: 45 min (2.000 veh → 45 min)"| T1["Destino T (65 min total)"]
        B1 -->|"B→T: f/100 min (2.000 veh → 20 min)"| T1
    end

1.2 Estado 1: Equilibrio antes de construir el atajo ($65$ minutos)

Este reparto coincide además con el óptimo social ($f^*$).

1.3 Estado 2: Apertura del atajo de latencia cero $A \to B$ (¡$80$ minutos!)

Se inaugura una vía ultrarrápida desde $A$ hasta $B$ con tiempo de viaje $\ell_{AB}(f_{AB}) = 0$ minutos.

  flowchart TD
    subgraph After["Estado 2: Tras abrir el atajo A→B (0 min) — Los 4.000 vehículos colapsan la ruta en zigzag (¡80 min!)"]
        S2["Origen S (4.000 veh)"] ==>|"S→A: f/100 min (4.000 veh → 40 min)"| A2["Nodo A"]
        S2 -.->|"S→B: 45 min (0 veh — abandonada)"| B2["Nodo B"]
        A2 ==>|"Nuevo atajo A→B: 0 min (4.000 veh → 0 min)"| B2
        A2 -.->|"A→T: 45 min (0 veh — abandonada)"| T2["Destino T (¡Todos tardan 80 min!)"]
        B2 ==>|"B→T: f/100 min (4.000 veh → 40 min)"| T2
    end

Aparece una tercera ruta: el camino en zigzag $P_{\text{zig}} = (S \to A \to B \to T)$. Mediante el análisis de estrategias estrictamente dominantes:

1. Decisión en el origen $S$ ($S \to A \to B$ frente a $S \to B$): Incluso si los $4.000$ coches toman el puente estrecho $S \to A$, su demora máxima es $\frac{4000}{100} = 40$ minutos. Como cruzar $A \to B$ toma $0$ minutos, llegar a $B$ vía $S \to A \to B$ tarda como máximo $40$ minutos, frente a los $45$ minutos fijos de la autopista $S \to B$. Por tanto, tomar $S \to A$ es una estrategia estrictamente dominante y el $100\,\%$ de los conductores abandona $S \to B$ ($f_{SB} = 0$).
2. Decisión en el nodo $A$ ($A \to B \to T$ frente a $A \to T$): Análogamente, ir de $A$ a $T$ vía $A \to B \to T$ tarda a lo sumo $0 + \frac{4000}{100} = 40$ minutos $< 45$ minutos, dominando estrictamente a la autopista $A \to T$ ($f_{AT} = 0$).
3. Nuevo equilibrio único ($80$ minutos): Los $4.000$ vehículos se agolpan en la ruta en zigzag $S \to A \to B \to T$, cruzando ambos puentes estrechos: $$T_{\text{después}} = \frac{4000}{100} + 0 + \frac{4000}{100} = 40 + 0 + 40 = 80\text{ minutos!}$$ Cualquier conductor que intente volver unilateralmente a $S \to A \to T$ o $S \to B \to T$ tardará $40 + 45 = 85$ minutos. Todos quedan atrapados en un dilema del prisionero (+15 minutos o $+23,1\,\%$ más lento para todos).

2. Los dos principios de Wardrop (1952) y la función de potencial de Beckmann (1956)

Sea $G = (V, E)$ un grafo dirigido con demanda total $F$, politopo de flujos factibles $\mathcal{F} = \{f \ge 0 : \sum_{P \in \mathcal{P}} f_P = F\}$ y latencias crecientes y diferenciables $\ell_e(f_e)$.

2.1 Primer principio de Wardrop (Equilibrio del usuario $f^{\text{EQ}}$)

2.2 Segundo principio de Wardrop (Óptimo social $f^*$) y externalidades de Pigou

2.3 Función de potencial convexo de Beckmann-McGuire-Winsten (1956)

Para latencias lineales $\ell_e(u) = a_e u + b_e$, comparando $\Phi(f) = \sum_e (\frac{1}{2}a_e f_e^2 + b_e f_e)$ con $C(f) = \sum_e (a_e f_e^2 + b_e f_e)$, vemos que el enrutamiento egoísta descuenta exactamente a la mitad ($\frac{1}{2}$) la penalización cuadrática por congestión.

3. Teorema de Roughgarden y Tardos (2002): Demostración de $\text{PoA} \le 4/3$

El Precio de la Anarquía ($\text{PoA}$) (Koutsoupias & Papadimitriou, 1999) se define como $\text{PoA} = \frac{C(f^{\text{EQ}})}{C(f^*)}$. En la red de 2 enlaces de Pigou (1920) ($\ell_1(x)=1, \ell_2(x)=x, F=1$), $C(f^{\text{EQ}}) = 1$ y $C(f^*) = \frac{3}{4}$ (en $x^* = \frac{1}{2}$), dando $\text{PoA} = \frac{4}{3}$.

$$\text{PoA}_{\text{lineal}} = \frac{C(f^{\text{EQ}})}{C(f^*)} \le \frac{4}{3}$$

【Demostración completa】

1. Desigualdad variacional: Como $\sum_{e \in E} \ell_e(f_e^{\text{EQ}})(f_e^* - f_e^{\text{EQ}}) \ge 0$, tenemos: $$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. Completar el cuadrado en cada arco: Sean $x = f_e^{\text{EQ}} \ge 0$ e $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. Suma sobre todos los arcos: Sumando para todo $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$$

Para polinomios de grado $d$ (como la función cuártica BPR $\ell_e(f_e) = t_e^0[1 + 0,15(f_e/c_e)^4]$ con $d=4$), la cota exacta es $\text{PoA}_d = \frac{(d+1)\sqrt[d]{d+1}}{(d+1)\sqrt[d]{d+1} - d}$ (siendo $\text{PoA}_4 \approx 2,1505$).

4. Realizaciones físicas: La paradoja de muelles y cuerdas de Cohen y Horowitz (1991)

En 1991, Joel E. Cohen y Paul Horowitz (Nature) demostraron que un sistema mecánico con dos muelles idénticos (constante $k$, longitud natural $L_0$), dos cuerdas de seguridad inextensibles de longitud $L_s$ y una cuerda central corta $A \to B$ (longitud $\approx 0$) que sostiene un peso $F = Mg$ exhibe la paradoja de Braess:

• Antes de cortar la cuerda central (Muelles en serie): Ambos muelles soportan toda la fuerza $F$ y se estiran $\frac{F}{k}$ cada uno. Si $L_s > L_0 + \frac{F}{k}$, las cuerdas laterales cuelgan flojas y la profundidad del peso es: $$Y_{\text{antes}} = 2L_0 + \frac{2F}{k}$$
• Tras cortar la cuerda central con tijeras (Muelles en paralelo): Las cuerdas de seguridad se tensan y los dos muelles pasan a trabajar en paralelo, soportando solo $\frac{F}{2}$ cada uno y estirándose $\frac{F}{2k}$. La nueva profundidad de equilibrio es: $$Y_{\text{después}} = L_0 + \frac{F}{2k} + L_s$$
• Si $L_0 + \frac{F}{k} < L_s < L_0 + \frac{3F}{2k}$ (por ejemplo $L_s = L_0 + \frac{5F}{4k}$), entonces: $$\Delta Y = Y_{\text{después}} - Y_{\text{antes}} = -\frac{F}{4k} < 0$$ ¡Cortar la cuerda tensa que sostiene el peso hace que la masa suba en contra de la gravedad una distancia $\frac{F}{4k}$!

5. Urbanismo real y peajes de congestión pigouvianos

1. Stuttgart (1969) y Nueva York — Calle 42 (1990) y Broadway en Times Square (2009): La clausura al tráfico de Broadway (que cortaba diagonalmente la cuadrícula de Manhattan exactamente igual que el atajo $A \to B$ de Braess) agilizó el tráfico de Midtown hasta en un $17\,\%$.
2. Seúl — Demolición de la autopista elevada de Cheonggyecheon (2003–2005): Demoler una autopista de 6 carriles con $168.000$ vehículos diarios para restaurar el río Cheonggyecheon eliminó los cuellos de botella de sus rampas, incrementó la velocidad media vehicular en el centro de Seúl y redujo la temperatura estival en $3,6^\circ\text{C}$.
3. Impuesto de Pigou: Aplicando un peaje $\tau_e = f_e^* \ell_e'(f_e^*)$ igual a la externalidad marginal de congestión en cada vía, el equilibrio de Wardrop coincide exactamente con el óptimo social ($\text{PoA} = 1$).