Paradoxul lui Braess

Paradoxul lui Braess este observația că adăugarea unuia sau mai multor drumuri la o rețea de drumuri poate încetini fluxul general de trafic prin aceasta. Paradoxul a fost descoperit pentru prima dată de Arthur Pigou în 1920, și ulterior numit după matematicianul german Dietrich Braess^⁠(d) în 1968.

Paradoxul poate avea analogii în rețelele electrice și sistemele biologice. S-a sugerat că, în teorie, îmbunătățirea unei rețele defectuoase ar putea fi realizată prin eliminarea anumitor părți ale acesteia. Paradoxul a fost folosit pentru a explica de ce se îmbunătățește fluxului de trafic^⁠(d) atunci când se închid drumuri importante existente.

Descoperire și definiție

Dietrich Braess, un matematician la Universitatea Ruhrului^⁠(d) din Germania, a observat că fluxul într-o rețea de drumuri ar putea fi împiedicat prin adăugarea unui drum nou, când lucra la modelarea traficului^⁠(d). Ideea lui a fost că, dacă fiecare șofer ia decizia optimă și interesată cu privire la ruta care este cea mai rapidă, o scurtătură ar putea alege prea mulți o scurtătură pentru ca șoferii să aibă cei mai scurti timpi de călătorie posibili. Mai formal, ideea din spatele descoperirii lui Braess este că echilibrul Nash ar putea să nu echivaleze cu cel mai bun flux global printr-o rețea.

Paradoxul este formulat după cum urmează:

„Pentru fiecare punct al unei rețele rutiere, fie dat numărul de mașini care pleacă de la acesta și destinația mașinilor. În aceste condiții, se dorește să se estimeze distribuția fluxului de trafic. Dacă o stradă este preferabilă alteia depinde nu numai de calitatea drumului, ci și de densitatea fluxului. Dacă fiecare șofer ia calea care îi pare cea mai favorabilă, timpul de rulare rezultat nu este neapărat cel minim. Mai mult, se indică printr-un exemplu că o extindere a rețelei rutiere poate determina o redistribuire a traficului care are ca rezultat timpi de rulare individuală mai mari.”

Adăugarea de capacitate suplimentară la o rețea atunci când entitățile în mișcare își aleg în mod egoist ruta poate reduce, în unele cazuri, performanța generală. Aceasta pentru că echilibrul Nash al unui astfel de sistem nu este neapărat optim. Schimbarea rețelei induce o nouă structură de joc care duce la dilema prizonierului (cu mai mulți jucători). La echilibru Nash, șoferii nu au niciun stimulent să-și schimbe rutele. Câtă vreme sistemul nu este în echilibru Nash, șoferii individuali își pot îmbunătăți durata de călătorie schimbând rutele pe care le parcurg. În cazul paradoxului lui Braess, șoferii vor continua să schimbe până când vor ajunge la echilibrul Nash, în ciuda reducerii performanței generale.

Dacă funcțiile de latență sunt liniare, adăugarea unei muchii nu poate înrăutăți niciodată timpul total de călătorie la echilibru cu un factor mai mare de 4/3.

Exemple posibile ale paradoxului în acțiune

Prevalența

În 1983, Steinberg și Zangwill au furnizat, în baza unor ipoteze rezonabile, condițiile necesare și suficiente pentru ca paradoxul lui Braess să apară într-o rețea generală de transport atunci când se adaugă o nouă rută. Rezultatul lor se aplică pentru adăugarea oricărei rute noi, nu doar pentru cazul adăugării unei singure legături. Ca corolar, ei constată că, atunci când se adaugă o nouă rută aleatorie, paradoxul lui Braess are șanse peste 50% să se manifeste.

Trafic

Paradoxul lui Braess are o contrapartidă în cazul reducerii rețelei de drumuri (care poate determina o reducere a timpului individual de tranzit).

În Seul, Coreea de Sud, viteza de circulație în jurul orașului a crescut după ce a fost demolată o autostradă ca parte a proiectului de restaurare Cheonggyecheon^⁠(d). În Stuttgart, Germania, după investițiile în rețeaua de drumuri în 1969, situația traficului nu s-a îmbunătățit până când o porțiune de drum nou construit a fost din nou închisă circulației. În 1990, închiderea temporară a străzii 42^⁠(d) din Manhattan, New York City, pentru Ziua Pământului a redus aglomerația din zonă. În 2008, Youn, Gastner și Jeong au demonstrat că există anumite rute din Boston, New York și Londra unde acest fenomen ar putea avea loc, și au indicat ce drumuri care ar putea fi închise pentru a reduce timpul estimat de călătorie. În 2009, New Yorkul a testat închiderea Broadway-ului la Times Square și Herald Square^⁠(d), ceea ce a dus la îmbunătățirea fluxului de trafic și la a creat piețe pietonale permanente.

În 2012, Paul Lecroart, de la Institutul de planificare și dezvoltare din Île-de-France, a scris că „În ciuda temerilor inițiale, înlăturarea de drumuri principale nu provoacă deteriorarea condițiilor de trafic după o perioadă inițială de adaptare. Transferurile de trafic sunt limitate și sub așteptări”. El observa și că unele călătorii cu vehicule private (și activitatea economică aferentă) nu se transferă în transportul public și pur și simplu dispar („se evaporă”).

Același fenomen a fost observat și atunci când închiderea drumurilor nu făcea parte dintr-un proiect urban, ci ca urmare a unui accident. În 2012, în Rouen, un pod a fost distrus de un incendiu. În următorii doi ani, alte poduri au fost folosite mai intens, dar numărul total de mașini care traversau podurile s-a redus.

Electricitate

În 2012, cercetătorii de la Institutul Max Planck pentru Dinamică și Auto-Organizare^⁠(d) au demonstrat, prin modelare computațională^⁠(d), potențialul acestui fenomen de a se manifesta și în rețelele de transport a energiei unde generarea de energie este descentralizată.

În 2012, o echipă internațională de cercetători de la Institut Néel (CNRS, Franța), INP (Franța), IEMN (CNRS, Franța) și UCL (Belgia) a publicat în Physical Review Letters o lucrare care arată că paradoxul lui Braess poate apărea în sisteme electronice mezoscopice^⁠(d). Anume, ei au arătat că adăugarea unei căi pentru electroni într-o rețea nanoscopică reduce în mod paradoxal conductanța acesteia. Acest lucru a fost demonstrat atât de simulări, cât și de experimente la temperatură scăzută, folosind microscopia cu poartă de scanare^⁠(d).

Resorturi

Două resorturi legate în serie printr-o frânghie scurtă. Când se adaugă frânghia scurtă care conectează B și C, greutatea atârnă mai jos.

Un model cu resorturi și frânghii poate arăta că o greutate atârnată se poate ridica în înălțime, chiar dacă o frânghie întinsă în sistemul de agățare este tăiată. Fenomenul derivă din aceeași structură matematică din care provine și paradoxul Braess originar.

Pentru două resorturi identice legate în serie printr-o frânghie scurtă, constanta lor elastică totală este jumătate din constanta fiecărui resort individual, rezultând o elongație mare atunci când se atârnă o anumită greutate. Situația se menține dacă se adaugă două frânghii mai care leagă capătul inferior al resortului superior de greutatea suspendată (capătul inferior al resortului inferior), și capătul superior al resortului inferior de punctul de agățare (capătul superior al resortului superior). Cu toate acestea, atunci când se taie frânghia scurtă, frânghiile mai lungi se întind, iar cele două resorturi devin paralele unul cu celălalt; Constanta elastică totală este de dublul față de cea a fiecărui resort individual, și, dacă lungimea frânghiilor lungi nu este prea mare, atunci greutatea atârnată se va ridica față de poziția dinainte de tăierea frânghiei scurte.

Faptul că greutatea atârnată se ridică în ciuda tăierii unei frânghii întinse (coarda scurtă) din sistemul de agățare este contraintuitiv, dar derivă din legea lui Hooke și din modul în care resorturile funcționează în serie și în paralel.

Biologie

Adilson E. Motter^⁠(d) și colaboratorii au demonstrat că rezultatele paradoxului lui Braess pot apărea adesea în sistemele biologice și ecologice. Motter sugerează că o rețea perturbată ar putea fi salvată prin eliminarea unei părți a ei. Pentru gestionarea resurselor rețelelor trofice ale speciilor pe cale de dispariție, în care extincția multor specii ar putea urma secvențial, îndepărtarea selectivă a unei specii condamnate din rețea ar putea avea, în principiu, rezultatul pozitiv al prevenirii unei serii de extincții ulterioare.

Strategia în sporturile de echipă

S-a sugerat că în baschet, o echipă poate fi văzută ca o rețea de posibilități pentru un traseu de a marca un coș, cu o eficiență diferită pentru fiecare cale, iar un jucător vedetă ar putea reduce eficiența generală a echipei, analog unei scurtături suprautilizate care mărește timpul total de deplasare printr-o rețea de drumuri. O soluție propusă pentru o eficiență maximă de marcare a coșurilor este ca un jucător vedetă să efectueze aproximativ același număr de aruncări ca și colegii de echipă. Cu toate acestea, această abordare nu este susținută de dovezi statistice solide, după cum menționează lucrarea inițială.

Abordare matematică

Exemplu

Fie rețeaua de drumuri ilustrată în diagrama alăturată, pe care 4000 de șoferi doresc să călătorească de la punctul START până la END. Timpul de călătorie în minute pe drumul START–A este numărul de călători (T) împărțit la 100, iar pe START–B este o constantă de 45 de minute (la fel și cu drumurile de vizavi de ei). Dacă drumul întrerupt nu există (deci rețeaua de trafic are 4 drumuri în total), timpul necesar pentru a parcurge traseul START–A–END cu $a$ șoferi ar fi ${\tfrac {a}{100}}+45$. Timpul necesar pentru a parcurge traseul START–B–END cu $b$ șoferi ar fi ${\tfrac {b}{100}}+45$ . Deoarece sunt 4000 de șoferi, faptul că $a+b=4000$ poate fi folosit pentru a deduce faptul că $a=b=2000$ când sistemul este în echilibru. Prin urmare, fiecare traseu ia ${\tfrac {2000}{100}}+45=65$ minute. Dacă oricare dintre rute ar lua mai puțin timp, nu ar fi echilibru Nash: un șofer rațional ar trece de la ruta mai lungă la ruta mai scurtă.

Acum să presupunem că linia întreruptă A–B este un drum cu un timp de călătorie extrem de scurt de aproximativ 0 minute. Să presupunem că drumul este deschis și un șofer încearcă START–A–B–END. Spre surprinderea lui, el descoperă că timpul lui este ${\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01$ minute, o economie de aproape 25 de minute. În curând, mai mulți dintre cei 4000 de șoferi încearcă această nouă rută. Durata de parcurgere crește de la 40.01 și continuă să urce. Când numărul șoferilor care încearcă noul traseu ajunge la 2500, cu 1500 încă pe ruta START–B–END, timpul lor va fi ${\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65$ minute, ceea ce nu reprezintă nicio îmbunătățire față de ruta inițială. Între timp, cei 1500 de șoferi rămași au fost încetiniți la $45+{\tfrac {4000}{100}}=85$ minute, o creștere de 20 de minute. Ei sunt obligați să treacă și ei pe noua rută prin A, așa că acum au nevoie de ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ minute. Nimeni nu are niciun stimulent să călătorească A-END sau START-B, deoarece orice șofer care le încearcă va pierde 85 de minute. Astfel, deschiderea traseului transversal declanșează o trecerea ireversibilă a tuturor pe acesta, pe toată lumea pierzând 80 de minute în loc de cele 65 inițiale. Dacă fiecare șofer ar accepta să nu folosească traseul A–B sau dacă acea rută ar fi închisă, fiecare șofer ar beneficia de o reducere de 15 minute a timpului de călătorie.

Existența unui echilibru

Dacă se presupune că timpul de călătorie pentru fiecare persoană care conduce pe o muchie este egal, va exista întotdeauna un echilibru.

Fie $L_{e}(x)$ formula pentru timpul de călătorie al fiecărei persoane care călătorește de-a lungul muchiei $e$ când $x$ oamenii merg pe această muchie. Să presupunem că există un graf de trafic cu $x_{e}$ oameni care conduc de-a lungul muchiei $e$. Fie energia lui $e$, $E(e)$

$\sum _{i=1}^{x_{e}}L_{e}(i)=L_{e}(1)+L_{e}(2)+\cdots +L_{e}(x_{e})$

(Dacă $x_{e}=0$ fie $E(e)=0$ ). Fie energia totală a grafului de trafic egală cu suma energiilor fiecărei muchii din graf.

Se aleg unele rute care minimizează energia totală. O astfel de alegere trebuie să existe, deoarece există un număr limitat de opțiuni de rute. Acesta va fi un echilibru.

Să presupunem, prin absurd, că nu este cazul. Există, atunci, cel puțin un șofer care poate schimba ruta și poate îmbunătăți timpul de călătorie. Să presupunem că ruta inițială este $e_{0},e_{1},\ldots ,e_{n}$ în timp ce noua rută este $e'_{0},e'_{1},\ldots ,e'_{m}$ . Fie $E$ energia totală a grafului de trafic și să vedem ce se întâmplă atunci când traseul $e_{0},e_{1},...e_{n}$ este eliminat. Energia fiecărei muchii $e_{i}$ va fi redusă cu $L_{e_{i}}(x_{e_{i}})$ și astfel $E$ va fi redus cu ${\textstyle \sum _{i=0}^{n}L_{e_{i}}(x_{e_{i}})}$. Acesta este pur și simplu timpul total de călătorie necesar pentru a parcurge traseul inițial. Dacă se adaugă atunci noua rută, $e'_{0},e'_{1},\ldots ,e'_{m}$, energia totală $E$ va crește cu timpul total de călătorie necesar pentru a parcurge noua rută. Deoarece noua rută este mai scurtă decât cea inițială, $E$ trebuie să scadă în raport cu configurația originară, contrazicând ipoteza că mulțimea originară de rute minimizează energia totală.

Prin urmare, alegerea de rute care minimizează energia totală este un echilibru.

Găsirea unui echilibru

Demonstrația de mai sus conturează o procedură cunoscută sub numele de dinamica Best response^⁠(d), care găsește un echilibru pentru un graf de trafic liniar și se termină într-un număr finit de pași. Algoritmul se numește „best response” („cel mai bun răspuns”) deoarece la fiecare pas al algoritmului, dacă graful nu este la echilibru, atunci un șofer găsește un cel mai bun răspuns la strategiile tuturor celorlalți conducători și trece la acel răspuns.

Pseudocod pentru dinamica best response:

Fie P un model de trafic.
while P nu este la echilibru:
  se calculează energia potențială e a lui P
  for each șofer d din P :
    for each cale alternativă p disponibilă pentru d :
      se calculează energia potențială n a modelului atunci când d urmează ruta p
      if n < e :
        se modifică P astfel încât d să urmeze ruta p
continue while

La fiecare pas, dacă un anumit șofer ar putea face mai bine urmând o rută alternativă (un „best response”), acest lucru scade strict energia grafului. Dacă niciun șofer nu are un best response , atunci graful este la echilibru. Deoarece energia grafului scade strict la fiecare pas, algoritmul de dinamică best responsece trebuie să se oprească la un moment dat.

Cât de departe de optim este traficul la echilibru?

Dacă funcțiile de timp de călătorie sunt liniare, adică $L_{e}(x)=a_{e}x+b_{e}$ pentru $a_{e},b_{e}\geq 0$, atunci, în cel mai rău caz, traficul în starea de echilibru cu minimizarea energiei este de două ori mai rea decât optimul social.

Demonstrație: fie $Z$ o configurație de trafic, cu energia asociată $E(Z)$ și timpul total de călătorie $T(Z)$. Pentru fiecare muchie, energia este suma unei progresii aritmetice și, folosind formula pentru suma progresiei aritmetice, se poate arăta că $E(Z)\leq T(Z)\leq 2E(Z)$. Dacă $Z_{o}$ este fluxul de trafic optim social și $Z_{e}$ este fluxul de trafic care minimizează energia, inegalitatea înseamnă că $T(Z_{e})\leq 2E(Z_{e})\leq 2E(Z_{o})\leq 2T(Z_{o})$ .

Astfel, timpul total de călătorie pentru echilibrul cu minimizarea energiei este de cel mult două ori mai slab decât pentru fluxul optim.

Analiza dinamică a paradoxului lui Braess

În 2013, Dal Forno și Merlone au interpretat paradoxul lui Braess ca pe o problemă de alegere ternară dinamică. Analiza arată cum noua rută modifică problema. Înainte ca noua rută să fie disponibilă, dinamica rămâne aceeași ca în alegerile binare cu externalități, dar noua rută o transformă într-o problemă de alegere ternară. Adăugarea unei resurse suplimentare îmbogățește complexitatea dinamicii. De fapt, poate exista chiar și coexistență de cicluri, iar efectele paradoxului asupra dinamicii pot fi văzute atât din perspectivă geometrică, cât și din perspectivă analitică.

Efectul topologiei rețelei

Mlichtaich a demonstrat că paradoxul lui Braess poate apărea dacă și numai dacă rețeaua nu este un graf serie-paralel^⁠(d).

Vezi și

• Paradoxul Downs–Thomson^⁠(d) – paradox din ingineria traficului, legat de îmbunătățiri ale rețelei de drumuri
• Paradoxul Jevons^⁠(d) – eficiența conduce la creșterea cererii
• Constanta lui Marchetti^⁠(d) – timpul mediu petrecut de o persoană pentru transport în fiecare zi
• Poziția Lewis–Mogridge^⁠(d)
• Prețul anarhiei în jocurile de congestie^⁠(d) — o analiză cantitativă a pierderii de eficiență cauzată de externalități de congestie

Lectură suplimentară

• Braess, D. (1969). „Über ein Paradoxon aus der Verkehrsplanung” [Despre un paradox al planificării traficului] (PDF). Unternehmensforschung (în germană). 12: 258–268.  (traducere în engleză de Nagurney & Wakolbinger)
• Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN: 3-89959-123-2
• Traducere în engleză a articolului lui Braess (originar în germană) din 1968, apărută ca articolul „On a paradox of traffic planning” de D. Braess, A. Nagurney, și T. Wakolbinger în revista științifică Transportation Science, volumul 39, 2005, pp. 446–450. Mai multe informații Arhivat în 27 septembrie 2011, la Wayback Machine.
• Irvine, A. D. (1993). „How Braess' paradox solves Newcomb's problem” [Despre cum paradoxul lui Braess rezolvă problema lui Newcomb]. International Studies in the Philosophy of Science. 7 (2): 141–160. doi:10.1080/02698599308573460. 
• Steinberg, R.; Zangwill, W. I. (1983). „The Prevalence of Braess' Paradox” [Prevalența paradoxului lui Braess]. Transportation Science. 17 (3): 301. doi:10.1287/trsc.17.3.301. 
• Rapoport, A.; Kugler, T.; Dugar, S.; Gisches, E. J. (2009). „Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox” (PDF). Games and Economic Behavior. 65 (2): 538–571. doi:10.1016/j.geb.2008.02.007. 
• T. Roughgarden. „The Price of Anarchy”. MIT Press, Cambridge, MA, 2005.

Legături externe

• Paradoxuri din testarea software-ului (decembrie 2005) Legătură directă
• Pagina lui Dietrich Braess
• Paradoxul rețelei de drumuri
• Scurt videoclip care ilustrează paradoxul Braess cu minifigurine Lego
• The Spring Paradox, videoclip YouTube de Steve Mould^⁠(d) care explică paradoxul lui Braess, precum și un alt paradox strâns legat de resorturi