Sari la conținut

Paradoxul lui Braess

De la Wikipedia, enciclopedia liberă

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,[1] și ulterior numit după matematicianul german Dietrich Braess⁠(d) în 1968.[2]

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

[modificare | modificare sursă]

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.[3]

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.[4]

Exemple posibile ale paradoxului în acțiune

[modificare | modificare sursă]

Î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.[5]

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

Î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).[7] Î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.[8] Î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ă.[9] Î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.[10] Î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”.[6] 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ă”).[6]

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.[6]

Electricitate

[modificare | modificare sursă]

Î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ă.[11]

Î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[12] 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).

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.[13]

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.

Adilson E. Motter⁠(d) și colaboratorii au demonstrat că rezultatele paradoxului lui Braess pot apărea adesea în sistemele biologice și ecologice.[14] 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.[15]

Strategia în sporturile de echipă

[modificare | modificare sursă]

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ă.[16]

Abordare matematică

[modificare | modificare sursă]

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 șoferi ar fi . Timpul necesar pentru a parcurge traseul START–B–END cu șoferi ar fi . Deoarece sunt 4000 de șoferi, faptul că poate fi folosit pentru a deduce faptul că când sistemul este în echilibru. Prin urmare, fiecare traseu ia 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 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 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 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 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

[modificare | modificare sursă]

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 formula pentru timpul de călătorie al fiecărei persoane care călătorește de-a lungul muchiei când oamenii merg pe această muchie. Să presupunem că există un graf de trafic cu oameni care conduc de-a lungul muchiei . Fie energia lui ,

(Dacă fie ). 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 în timp ce noua rută este . Fie energia totală a grafului de trafic și să vedem ce se întâmplă atunci când traseul este eliminat. Energia fiecărei muchii va fi redusă cu și astfel va fi redus cu . Acesta este pur și simplu timpul total de călătorie necesar pentru a parcurge traseul inițial. Dacă se adaugă atunci noua rută, , energia totală 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ă, 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

[modificare | modificare sursă]

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?

[modificare | modificare sursă]

Dacă funcțiile de timp de călătorie sunt liniare, adică pentru , 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.[17]

Demonstrație: fie o configurație de trafic, cu energia asociată și timpul total de călătorie . Pentru fiecare muchie, energia este suma unei progresii aritmetice și, folosind formula pentru suma progresiei aritmetice, se poate arăta că . Dacă este fluxul de trafic optim social și este fluxul de trafic care minimizează energia, inegalitatea înseamnă că .

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

[modificare | modificare sursă]

În 2013, Dal Forno și Merlone[18] 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

[modificare | modificare sursă]

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

  1. ^ Pigou, Arthur Cecil (), „Welfare and Economic Welfare”, The Economics of Welfare, Routledge, pp. 3–22, doi:10.4324/9781351304368-1, ISBN 978-1-351-30436-8, accesat în  
  2. ^ Braess, D. (decembrie 1968). „Über ein Paradoxon aus der Verkehrsplanung”. Unternehmensforschung Operations Research - Recherche Opérationnelle. 12 (1): 258–268. doi:10.1007/bf01918335. ISSN 0340-9422. 
  3. ^ New Scientist, 42nd St Paradox: Cull the best to make things better, 16 January 2014 by Justin Mullins
  4. ^ Roughgarden, Tim; Tardos, Éva. „How Bad is Selfish Routing?” (PDF). Journal of the ACM. Arhivat din original (PDF) la . Accesat în . 
  5. ^ Steinberg, R.; Zangwill, W. I. (). „The Prevalence of Braess' Paradox”. Transportation Science. 17 (3): 301. doi:10.1287/trsc.17.3.301. 
  6. ^ a b c d Olivier Razemon (). „Quand les voitures s'évaporent” (în franceză). Le Monde. p. 5. Accesat în . 
  7. ^ Easley, D.; Kleinberg, J. (). Networks. Cornell Store Press. p. 71. 
  8. ^ Knödel, W. (). Graphentheoretische Methoden Und Ihre Anwendungen. Springer-Verlag. pp. 57–59. ISBN 978-3-540-04668-4. 
  9. ^ Kolata, Gina (). „What if They Closed 42d Street and Nobody Noticed?”. New York Times. Accesat în . 
  10. ^ Youn, Hyejin; Gastner, Michael; Jeong, Hawoong (). „Price of Anarchy in Transportation Networks: Efficiency and Optimality Control”. Physical Review Letters. 101 (12): 128701. Bibcode:2008PhRvL.101l8701Y. doi:10.1103/PhysRevLett.101.128701. ISSN 0031-9007. PMID 18851419. 
  11. ^ Staff (Max Planck Institute) (), „Study: Solar and wind energy may stabilize the power grid”, R&D Magazine⁠(d), rdmag.com, accesat în  
  12. ^ Pala, M. G.; Baltazar, S.; Liu, P.; Sellier, H.; Hackens, B.; Martins, F.; Bayot, V.; Wallart, X.; Desplanque, L. (). „Transport Inefficiency in Branched-Out Mesoscopic Networks: An Analog of the Braess Paradox”. Physical Review Letters. 108 (7): 076802. Bibcode:2012PhRvL.108g6802P. doi:10.1103/PhysRevLett.108.076802. ISSN 0031-9007. PMID 22401236. 
  13. ^ Mould, Steve. „The Spring Paradox”. YouTube (în engleză). Accesat în . 
  14. ^ Motter, Adilson E. (). „Improved network performance via antagonism: From synthetic rescues to multi-drug combinations”. BioEssays. 32 (3): 236–245. doi:10.1002/bies.200900128. PMC 2841822Accesibil gratuit. PMID 20127700. 
  15. ^ Sahasrabudhe S., Motter A. E., Rescuing ecosystems from extinction cascades through compensatory perturbations, Nature Communications 2, 170 (2011)
  16. ^ Skinner, Brian; Gastner, Michael T; Jeong, Hawoong (). „The price of anarchy in basketball”. Journal of Quantitative Analysis in Sports. 6 (1). Bibcode:2009arXiv0908.1801S. doi:10.2202/1559-0410.1217. 
  17. ^ Easley, David; Kleinberg, Jon. „Networks, Crowds, and Markets: Reasoning about a Highly Connected World (8.3 Advanced Material: The Social Cost of Traffic at Equilibrium)” (PDF). Jon Kleinberg's Homepage. Jon Kleinberg. Arhivat din original (PDF) la . Accesat în .  – This is the preprint of ISBN: 9780521195331
  18. ^ Dal Forno, Arianna; Merlone, Ugo (). „Border-collision bifurcations in a model of Braess paradox”. Mathematics and Computers in Simulation. 87: 1–18. doi:10.1016/j.matcom.2012.12.001. ISSN 0378-4754. 
  19. ^ Milchtaich, Igal (). „Network topology and the efficiency of equilibrium”. Games and Economic Behavior (în engleză). 57 (2): 321–346. doi:10.1016/j.geb.2005.09.005. ISSN 0899-8256. 

Lectură suplimentară

[modificare | modificare sursă]

Legături externe

[modificare | modificare sursă]