Bayangkan otoritas transportasi sebuah kota metropolitan menghabiskan милиaran dolar untuk membangun jembatan pintas baru tanpa hambatan guna mengurai kemacetan jam sibuk pagi hari. Akal sehat menyimpulkan bahwa penambahan jalan baru pasti mempercepat lalu lintas: kapasitas total jaringan jalan meningkat, tidak ada jalan lama yang ditutup, dan siapa pun yang tidak menyukai jembatan baru bebas tetap melewati rute lama mereka. Bagaimana mungkin memperluas pilihan justru merugikan semua orang?

Pada tahun 1968, matematikawan Jerman Dietrich Braess menerbitkan makalah bersejarah (“Über ein Paradoxon aus der Verkehrsplanung”) yang meruntuhkan intuisi tersebut. Braess membuktikan secara matematis bahwa ketika setiap pengendara memilih rute secara egois demi meminimalkan waktu tempuh pribadinya (perutean egois / Selfish Routing), menambahkan jalan pintas berlatensi nol justru dapat membuat waktu tempuh ekuilibrium bagi 100% pengendara menjadi lebih lama secara ketat! Fenomena kontradiktif ini dikenal sebagai Paradoks Braess (Braess’s Paradox).

Lebih mengejutkan lagi, Paradoks Braess bukan disebabkan oleh kurangnya informasi atau perilaku irasional manusia, melainkan muncul secara niscaya sebagai satu-satunya ekuilibrium Nash (ekuilibrium Wardrop) dalam permainan kemacetan non-kooperatif. Karena sistem fisik pasif juga meminimalkan energi potensial konveks yang isomorfik secara matematis dengan fungsi potensial Beckmann pada lalu lintas, Paradoks Braess muncul secara identik dalam perutean paket Internet (OSPF/BGP), jaringan listrik arus bolak-balik, cincin kuantum mesoskopik, hingga mekanika klasik — sebagaimana dibuktikan oleh Joel E. Cohen dan Paul Horowitz di jurnal Nature (1991): pada rangkaian pegas dan tali yang menahan beban berat, memotong tali tengah yang tegang dengan gunting justru membuat beban tersebut naik ke atas melawan gravitasi!

1. Makalah Dietrich Braess (1968) dan Jaringan Berlian 4-Simpul

1.1 Topologi Jaringan dan Fungsi Latensi

Misalkan arus lalu lintas total sebesar $F = 4.000\text{ mobil/jam}$ (atau $F = 1$ dalam satuan ternormalisasi) bergerak dari titik asal $S$ menuju tujuan $T$ melalui dua simpul perantara $A$ dan $B$. Waktu tempuh (fungsi latensi) $\ell_e(f_e)$ pada setiap sisi berarah $e \in E$ bergantung pada arus $f_e$:

1. Sisi $S \to A$ (Jembatan sempit rawan macet): Waktu tempuh meningkat secara linear terhadap arus $f_{SA}$: $$\ell_{SA}(f_{SA}) = \frac{f_{SA}}{100}\text{ menit}$$
2. Sisi $A \to T$ (Jalan raya lingkar lebar): Kebal terhadap kemacetan, waktu tempuh konstan: $$\ell_{AT}(f_{AT}) = 45\text{ menit}$$
3. Sisi $S \to B$ (Jalan raya lingkar lebar): Simetris dengan $A \to T$, waktu tempuh konstan: $$\ell_{SB}(f_{SB}) = 45\text{ menit}$$
4. Sisi $B \to T$ (Jembatan sempit rawan macet): Identik dengan $S \to A$, waktu tempuh linear: $$\ell_{BT}(f_{BT}) = \frac{f_{BT}}{100}\text{ menit}$$

  flowchart TD
    subgraph Before["Kondisi 1: Sebelum Jalan Baru (Total Arus F = 4.000 mobil/jam, Semua 65 menit)"]
        S1["Asal S (4.000 mobil)"] -->|"S→A: f/100 mnt (2.000 mobil → 20 mnt)"| A1["Simpul A"]
        S1 -->|"S→B: 45 mnt (2.000 mobil → 45 mnt)"| B1["Simpul B"]
        A1 -->|"A→T: 45 mnt (2.000 mobil → 45 mnt)"| T1["Tujuan T (Total 65 mnt)"]
        B1 -->|"B→T: f/100 mnt (2.000 mobil → 20 mnt)"| T1
    end

1.2 Kondisi 1: Ekuilibrium Sebelum Pembangunan Jalan Pintas ($65$ Menit)

Pembagian ini sekaligus merupakan optimum sosial ($f^*$).

1.3 Kondisi 2: Pembukaan Jalan Pintas Tanpa Latensi $A \to B$ ($80$ Menit!)

Pemerintah membuka jalan pintas satu arah super cepat dari $A$ ke $B$ dengan waktu tempuh $\ell_{AB}(f_{AB}) = 0$ menit.

  flowchart TD
    subgraph After["Kondisi 2: Setelah Jalan Pintas A→B (0 mnt) Dibuka — Semua 4.000 Mobil Menumpuk di Rute Zigzag (80 mnt!)"]
        S2["Asal S (4.000 mobil)"] ==>|"S→A: f/100 mnt (4.000 mobil → 40 mnt)"| A2["Simpul A"]
        S2 -.->|"S→B: 45 mnt (0 mobil — ditinggalkan)"| B2["Simpul B"]
        A2 ==>|"Jalan Pintas A→B: 0 mnt (4.000 mobil → 0 mnt)"| B2
        A2 -.->|"A→T: 45 mnt (0 mobil — ditinggalkan)"| T2["Tujuan T (Semua 80 mnt!)"]
        B2 ==>|"B→T: f/100 mnt (4.000 mobil → 40 mnt)"| T2
    end

Kini muncul rute ketiga: rute zigzag $P_{\text{zig}} = (S \to A \to B \to T)$. Melalui analisis strategi dominan ketat (Strictly Dominant Strategy):

1. Keputusan di titik asal $S$ ($S \to A \to B$ vs. $S \to B$): Sekalipun seluruh $4.000$ mobil melewati jembatan sempit $S \to A$, waktu tempuhnya paling lama $\frac{4000}{100} = 40$ menit. Karena melintasi $A \to B$ memakan $0$ menit, mencapai $B$ lewat $S \to A \to B$ memakan waktu paling lama $40$ menit, lebih cepat dibandingkan jalan raya $S \to B$ yang selalu $45$ menit. Maka memilih $S \to A$ adalah strategi dominan ketat, dan $100\%$ pengendara meninggalkan $S \to B$ ($f_{SB} = 0$).
2. Keputusan di simpul $A$ ($A \to B \to T$ vs. $A \to T$): Demikian pula, dari $A$ ke $T$ lewat $A \to B \to T$ memakan waktu paling lama $0 + \frac{4000}{100} = 40$ menit $< 45$ menit, mendominasi secara ketat jalan raya $A \to T$ ($f_{AT} = 0$).
3. Ekuilibrium Baru yang Unik ($80$ Menit): Seluruh $4.000$ kendaraan menumpuk di jalur zigzag $S \to A \to B \to T$, melewati kedua jembatan sempit: $$T_{\text{sesudah}} = \frac{4000}{100} + 0 + \frac{4000}{100} = 40 + 0 + 40 = 80\text{ menit!}$$ Pengendara mana pun yang mencoba kembali sendirian ke rute lama $S \to A \to T$ atau $S \to B \to T$ akan membutuhkan $40 + 45 = 85$ menit. Semua orang terjebak dalam Dilema Tahanan (Prisoner’s Dilemma) (+15 menit atau $+23,1\%$ lebih buruk bagi semua orang).

2. Dua Prinsip Wardrop (1952) dan Fungsi Potensial Konveks Beckmann (1956)

Pada graf berarah $G = (V, E)$ dengan total permintaan $F$, politop arus layak $\mathcal{F} = \{f \ge 0 : \sum_{P \in \mathcal{P}} f_P = F\}$, dan fungsi latensi monoton naik $\ell_e(f_e)$:

2.1 Prinsip Pertama Wardrop (Ekuilibrium Pengguna $f^{\text{EQ}}$)

2.2 Prinsip Kedua Wardrop (Optimum Sosial $f^*$) dan Eksternalitas Pigou

2.3 Fungsi Potensial Konveks Beckmann-McGuire-Winsten (1956)

Untuk latensi linear $\ell_e(u) = a_e u + b_e$, membandingkan $\Phi(f) = \sum_e (\frac{1}{2}a_e f_e^2 + b_e f_e)$ dengan $C(f) = \sum_e (a_e f_e^2 + b_e f_e)$ menunjukkan bahwa perutean egois mendiskon penalti kemacetan kuadratik sebesar tepat setengahnya ($\frac{1}{2}$).

3. Teorema Roughgarden & Tardos (2002): Bukti Batas $\text{PoA} \le 4/3$

Harga Anarki ($\text{PoA}$) (Koutsoupias & Papadimitriou, 1999) didefinisikan sebagai $\text{PoA} = \frac{C(f^{\text{EQ}})}{C(f^*)}$. Pada jaringan 2-tautan Pigou (1920) ($\ell_1(x)=1, \ell_2(x)=x, F=1$), $C(f^{\text{EQ}}) = 1$ dan $C(f^*) = \frac{3}{4}$ (pada $x^* = \frac{1}{2}$), menghasilkan $\text{PoA} = \frac{4}{3}$.

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

【Bukti Lengkap】

1. Pertidaksamaan variasional: Karena $\sum_{e \in E} \ell_e(f_e^{\text{EQ}})(f_e^* - f_e^{\text{EQ}}) \ge 0$, diperoleh: $$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. Melengkapkan kuadrat sempurna pada tiap sisi: Misalkan $x = f_e^{\text{EQ}} \ge 0$ dan $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. Penjumlahan pada seluruh sisi: Menjumlahkan untuk seluruh $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$$

Untuk fungsi latensi polinomial berderajat $d$ (seperti fungsi kuartik BPR $\ell_e(f_e) = t_e^0[1 + 0,15(f_e/c_e)^4]$ dengan $d=4$), batas eksaknya adalah $\text{PoA}_d = \frac{(d+1)\sqrt[d]{d+1}}{(d+1)\sqrt[d]{d+1} - d}$ (untuk $d=4$, $\text{PoA}_4 \approx 2,1505$).

4. Realisasi Fisik: Paradoks Pegas-dan-Tali Cohen & Horowitz (1991)

Pada tahun 1991, Joel E. Cohen dan Paul Horowitz (Nature) membuktikan bahwa sistem mekanis dengan dua pegas identik (konstanta $k$, panjang alami $L_0$), dua tali pengaman tak-melar sepanjang $L_s$, dan seutas tali penghubung tengah yang pendek $A \to B$ (panjang $\approx 0$) yang menahan beban $F = Mg$ memperlihatkan Paradoks Braess:

• Sebelum tali tengah dipotong (Pegas seri): Kedua pegas menahan beban penuh $F$ dan masing-masing memanjang sebesar $\frac{F}{k}$. Jika $L_s > L_0 + \frac{F}{k}$, kedua tali pengaman mengendur dan kedalaman beban adalah: $$Y_{\text{sebelum}} = 2L_0 + \frac{2F}{k}$$
• Setelah tali tengah digunting (Pegas paralel): Tali pengaman menegang dan kedua pegas berbagi beban secara paralel ($\frac{F}{2}$ masing-masing), sehingga hanya memanjang $\frac{F}{2k}$. Kedalaman ekuilibrium baru menjadi: $$Y_{\text{sesudah}} = L_0 + \frac{F}{2k} + L_s$$
• Jika $L_0 + \frac{F}{k} < L_s < L_0 + \frac{3F}{2k}$ (misalnya $L_s = L_0 + \frac{5F}{4k}$), maka: $$\Delta Y = Y_{\text{sesudah}} - Y_{\text{sebelum}} = -\frac{F}{4k} < 0$$ Menggunting tali penahan beban justru membuat beban berat tersebut naik ke atas melawan gravitasi sejauh $\frac{F}{4k}$!

5. Perencanaan Kota Nyata dan Tarif Kemacetan Pigou (Congestion Pricing)

1. Stuttgart (1969) dan New York City — 42nd Street (1990) & Broadway di Times Square (2009): Penutupan permanen Broadway bagi kendaraan bermotor di Times Square (yang memotong diagonal jaringan jalan Manhattan persis seperti jalan pintas $A \to B$ pada jaringan Braess) mempercepat waktu tempuh taksi di Midtown hingga $17\%$.
2. Seoul — Pembongkaran Jalan Layang Cheonggyecheon (2003–2005): Membongkar jalan raya layang 6-lajur sepanjang $5,8\text{ km}$ yang dilewati $168.000$ kendaraan per hari demi merestorasi sungai alami Cheonggyecheon terbukti menghilangkan kemacetan di jalur masuk/keluar, meningkatkan kecepatan rata-rata lalu lintas di pusat kota Seoul, serta menurunkan suhu musim panas sebesar $3,6^\circ\text{C}$.
3. Pajak Pigou: Dengan menerapkan tarif kemacetan $\tau_e = f_e^* \ell_e'(f_e^*)$ yang setara dengan eksternalitas marginal pada setiap ruas jalan, ekuilibrium Wardrop menyatu sempurna dengan optimum sosial ($\text{PoA} = 1$).