एक नई सड़क बनाने से हर किसी का यात्रा समय क्यों बढ़ जाता है: ब्रेयेस का विरोधाभास (Braess's Paradox) और स्वार्थी रूटिंग का गणित

कल्पना कीजिए कि किसी महानगर का परिवहन विभाग सुबह के भीषण ट्रैफिक जाम को खत्म करने के लिए अरबों रुपये खर्च करके शून्य-विलंब (zero-latency) वाला एक नया एक्सप्रेस पुल बनाता है। सामान्य बुद्धि यही कहती है कि नई सड़क बनने से लाभ ही होगा—आखिर सड़क नेटवर्क की कुल क्षमता बढ़ गई है, कोई पुरानी सड़क बंद नहीं की गई है, और जो लोग नए पुल का उपयोग नहीं करना चाहते वे अपने पुराने रास्ते से जा सकते हैं। विकल्पों के बढ़ने से भला हर किसी को नुकसान कैसे हो सकता है?

किंतु 1968 में जर्मन गणितज्ञ डीट्रिच ब्रेयेस (Dietrich Braess) ने अपना ऐतिहासिक शोध-पत्र (“Über ein Paradoxon aus der Verkehrsplanung”) प्रकाशित किया जिसने इस सहज ज्ञान को पूरी तरह ध्वस्त कर दिया। ब्रेयेस ने गणितीय रूप से सिद्ध किया कि जब प्रत्येक चालक केवल अपने व्यक्तिगत यात्रा समय को न्यूनतम करने के लिए स्वार्थपूर्ण ढंग से मार्ग चुनता है (स्वार्थी रूटिंग / Selfish Routing), तो नेटवर्क में एक शून्य-विलंब शॉर्टकट सड़क जोड़ने से नए संतुलन (Equilibrium) में 100% सभी चालकों का यात्रा समय पहले से अधिक लंबा हो सकता है! इस प्रति-सहज (counterintuitive) परिघटना को ब्रेयेस का विरोधाभास (Braess’s Paradox) कहा जाता है।

इससे भी अधिक आश्चर्यजनक बात यह है कि ब्रेयेस का विरोधाभास सूचना के अभाव या मानवीय अज्ञानता के कारण नहीं होता, बल्कि पूर्ण सूचना के अंतर्गत गैर-सहकारी भीड़ खेल (Congestion Game) के अद्वितीय नैश संतुलन (वार्ड्रॉप संतुलन / Wardrop Equilibrium) के रूप में अनिवार्य रूप से उत्पन्न होता है। चूंकि निर्जीव भौतिक प्रणालियां भी न्यूनतम स्थितिज ऊर्जा के सिद्धांत का पालन करती हैं जो गणितीय रूप से बेकमैन विभव फलन के समरूप है, इसलिए यह विरोधाभास इंटरनेट पैकेट रूटिंग (OSPF/BGP), एसी पावर ग्रिड, क्वांटम नैनो-संरचनाओं और शास्त्रीय यांत्रिकी में भी हूबहू प्रकट होता है—जैसा कि जोएल कोहेन और पॉल होरोविट्ज़ (Cohen & Horowitz, 1991) ने Nature पत्रिका में दिखाया: स्प्रिंग और धागों से लटके एक भारी द्रव्यमान के नेटवर्क में, भार संभाल रहे बीच के तने हुए धागे को कैंची से काटने पर लटका हुआ भार गुरुत्वाकर्षण के विरुद्ध ऊपर की ओर उठ जाता है!

1. डीट्रिच ब्रेयेस का 1968 का शोध-पत्र और 4-नोड डायमंड नेटवर्क

1.1 नेटवर्क संरचना और विलंब फलन (Latency Functions)

मान लीजिए कि सुबह के व्यस्त समय में कुल यातायात प्रवाह $F = 4,000\text{ कारें/घंटा}$ (या सामान्यीकृत इकाई में $F = 1$) प्रारंभिक बिंदु $S$ से गंतव्य $T$ की ओर दो मध्यवर्ती जंक्शनों $A$ और $B$ से होकर जाता है। प्रत्येक निर्देशित पथ (edge) $e \in E$ का यात्रा समय $\ell_e(f_e)$ उस पर चलने वाली कारों की संख्या $f_e$ पर निम्न प्रकार निर्भर करता है:

सड़क $S \to A$ (संकरा पुल): संकरा होने के कारण इसका यात्रा समय प्रवाह $f_{SA}$ के समानुपाती रूप से बढ़ता है: $$\ell_{SA}(f_{SA}) = \frac{f_{SA}}{100}\text{ मिनट}$$
सड़क $A \to T$ (चौड़ा बाईपास राजमार्ग): यह राजमार्ग बहुत चौड़ा है और कभी जाम नहीं होता, किंतु लंबा होने के कारण हमेशा नियत समय लेता है: $$\ell_{AT}(f_{AT}) = 45\text{ मिनट}$$
सड़क $S \to B$ (चौड़ा बाईपास राजमार्ग): $A \to T$ के सममित, नियत यात्रा समय: $$\ell_{SB}(f_{SB}) = 45\text{ मिनट}$$
सड़क $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$ मिनट)

$$T_{\text{before}} = \frac{2000}{100} + 45 = 20 + 45 = 65\text{ मिनट}$$

यह विभाजन समाज के कुल यात्रा समय को न्यूनतम करने वाला सामाजिक इष्टतम (Social Optimum $f^*$) भी है।

1.3 अवस्था 2: शून्य-विलंब शॉर्टकट सड़क $A \to B$ खुलने के बाद ($80$ मिनट!)

अब मान लीजिए कि जंक्शन $A$ से $B$ तक $\ell_{AB}(f_{AB}) = 0$ मिनट यात्रा समय वाली एक अति-तीव्र सड़क $A \to B$ खोल दी जाती है।

  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{zig}} = (S \to A \to B \to T)$। खेल सिद्धांत के कठोर प्रभावी रणनीति विश्लेषण (Strictly Dominant Strategy Analysis) से देखें:

प्रारंभ $S$ पर निर्णय ($S \to A \to B$ बनाम $S \to B$): भले ही सभी $4,000$ कारें संकरे पुल $S \to A$ पर चली जाएं, उसका अधिकतम समय $\frac{4000}{100} = 40$ मिनट होगा। चूंकि $A \to B$ में $0$ मिनट लगते हैं, इसलिए $S \to A \to B$ द्वारा $B$ तक पहुंचने में अधिकतम $40$ मिनट लगते हैं, जबकि राजमार्ग $S \to B$ में हमेशा $45$ मिनट लगते हैं! अतः $S \to A$ चुनना एक कठोर प्रभावी रणनीति है और $100\%$ चालक $S \to B$ को छोड़ देते हैं ($f_{SB} = 0$)।
जंक्शन $A$ पर निर्णय ($A \to B \to T$ बनाम $A \to T$): इसी प्रकार, $A$ से $T$ जाने के लिए $A \to B \to T$ में अधिकतम $0 + \frac{4000}{100} = 40$ मिनट लगते हैं जो $A \to T$ के $45$ मिनट से हमेशा कम है ($40 < 45$)। अतः सभी चालक $A \to T$ को भी छोड़ देते हैं ($f_{AT} = 0$)।
नया अद्वितीय नैश संतुलन ($80$ मिनट): परिणामस्वरूप, सभी $4,000$ कारें ज़िगज़ैग मार्ग $S \to A \to B \to T$ पर जमा हो जाती हैं और दोनों संकरे पुलों को पार करती हैं: $$T_{\text{after}} = \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$ मिनट लगेंगे। सभी चालक कैदी की दुविधा (Prisoner’s Dilemma) में फंस जाते हैं और हर किसी का समय $15$ मिनट ($+23.1\%$) बढ़ जाता है!

मापदंड	अवस्था 1: शॉर्टकट $A \to B$ से पूर्व (सामाजिक इष्टतम $f^*$)	अवस्था 2: शॉर्टकट $A \to B$ के बाद (वार्ड्रॉप संतुलन $f^{\text{EQ}}$)	विरोधाभासी प्रभाव
$S \to A \to T$ पर प्रवाह	$2,000\text{ कारें/घंटा}$ ($20 + 45 = 65\text{ मि.}$)	$0\text{ कारें/घंटा}$ (चलने पर $40 + 45 = 85\text{ मि.}$)	राजमार्ग $A \to T$ खाली
$S \to B \to T$ पर प्रवाह	$2,000\text{ कारें/घंटा}$ ($45 + 20 = 65\text{ मि.}$)	$0\text{ कारें/घंटा}$ (चलने पर $45 + 40 = 85\text{ मि.}$)	राजमार्ग $S \to B$ खाली
$S \to A \to B \to T$ पर प्रवाह	अनुपस्थित	$4,000\text{ कारें/घंटा}$ ($100\%$ यातायात केंद्रित)	दोनों संकरे पुलों पर दोहरा भार
प्रति चालक यात्रा समय	$65\text{ मिनट}$	$80\text{ मिनट}$	सभी के लिए $+15\text{ मि.}$ ($+23.1\%$) की वृद्धि
कुल सामाजिक लागत $C(f)$	$260,000\text{ कार-मिनट}$	$320,000\text{ कार-मिनट}$	$\text{PoA} = \frac{80}{65} = \frac{16}{13} \approx 1.231$

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}}$)

$$f_P^{\text{EQ}} > 0 \implies \ell_P(f^{\text{EQ}}) \le \ell_{P'}(f^{\text{EQ}}) \quad (\forall P' \in \mathcal{P})$$$$\sum_{e \in E} \ell_e\bigl(f_e^{\text{EQ}}\bigr)\bigl(f_e - f_e^{\text{EQ}}\bigr) \ge 0 \quad (\forall f \in \mathcal{F})$$

2.2 वार्ड्रॉप का द्वितीय सिद्धांत (सामाजिक इष्टतम $f^*$) और पिगू बाह्यता

$$\tilde{\ell}_e(f_e) = \frac{d}{df_e}\bigl[f_e \ell_e(f_e)\bigr] = \underbrace{\ell_e(f_e)}_{\text{निजी लागत}} + \underbrace{f_e \ell_e'(f_e)}_{\text{पिगू भीड़ बाह्यता (Pigouvian Externality)}}$$

2.3 बेकमैन-मैकग्वायर-विंस्टन उत्तल विभव फलन (1956)

$$\Phi(f) = \sum_{e \in E} \int_0^{f_e} \ell_e(u)\,du \qquad \left(\text{क्योंकि } \frac{\partial \Phi(f)}{\partial f_P} = \sum_{e \in P} \ell_e(f_e) = \ell_P(f)\right)$$

रैखिक विलंब $\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$) की उत्पत्ति

अराजकता की कीमत (Price of Anarchy, $\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}$$

【संपूर्ण उत्पत्ति (Proof)】

विचरणीय असमिका: चूंकि $\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}})$$
प्रत्येक भुजा के लिए पूर्ण वर्ग असमिका: $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)$$
सभी भुजाओं पर योग: समस्त $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$ की यांत्रिक प्रणाली ब्रेयेस के विरोधाभास का पालन करती है:

केंद्रीय धागा काटने से पहले (श्रेणीक्रम / Series): दोनों स्प्रिंग पूरा भार $F$ सहते हैं और प्रत्येक $\frac{F}{k}$ खिंचता है। जब $L_s > L_0 + \frac{F}{k}$, सुरक्षा डोरियां ढीली रहती हैं और भार की गहराई होती है: $$Y_{\text{before}} = 2L_0 + \frac{2F}{k}$$
कैंची से केंद्रीय धागा काटने के बाद (समांतर क्रम / Parallel): सुरक्षा डोरियां तन जाती हैं और दोनों स्प्रिंग समांतर क्रम में आधा-आधा भार ($\frac{F}{2}$) बांट लेते हैं, जिससे प्रत्येक का खिंचाव घटकर $\frac{F}{2k}$ रह जाता है! नई संतुलन गहराई होती है: $$Y_{\text{after}} = 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{after}} - Y_{\text{before}} = -\frac{F}{4k} < 0$$ अर्थात भार संभाल रहे तने हुए धागे को कैंची से काटने पर भारी द्रव्यमान गुरुत्वाकर्षण के विरुद्ध $\frac{F}{4k}$ ऊपर उठ जाता है!

5. वास्तविक शहरी नियोजन और पिगू भीड़ प्रभार (Congestion Pricing)

स्टटगार्ट (1969) और न्यूयॉर्क — 42वीं स्ट्रीट (1990) एवं टाइम्स स्क्वायर ब्रॉडवे (2009): मैनहट्टन के ग्रिड को तिरछा काटने वाले ब्रॉडवे (जो ब्रेयेस के शॉर्टकट $A \to B$ की तरह काम कर रहा था) को वाहनों के लिए बंद करने से मिडटाउन में यात्रा समय $17\%$ घट गया।
सियोल — चोंग्येचोन एलिवेटेड एक्सप्रेसवे को हटाना (2003–2005): प्रतिदिन $168,000$ वाहनों को ले जाने वाले $5.8\text{ किमी}$ लंबे 6-लेन राजमार्ग को तोड़कर चोंग्येचोन नदी को पुनर्जीवित करने से रैंप की बाधाएं समाप्त हो गईं, मध्य सियोल में वाहनों की औसत गति बढ़ गई और ग्रीष्मकालीन तापमान में $3.6^\circ\text{C}$ की कमी आई।
पिगू कर (Pigouvian Toll): प्रत्येक सड़क पर सीमांत भीड़ बाह्यता के बराबर शुल्क $\tau_e = f_e^* \ell_e'(f_e^*)$ लगाने से स्वार्थी संतुलन सीधे सामाजिक इष्टतम ($\text{PoA} = 1$) में परिवर्तित हो जाता है।