Braess paradoxona

Braess paradoxona az a megfigyelés, hogy egy vagy több út hozzáadása az úthálózathoz lelassíthatja a teljes forgalom áramlását. A paradoxont először Arthur Pigou írta le 1920-ban, majd 1968-ban Dietrich Braess német matematikusról kapta a nevét.

A paradoxonnak lehetnek analógiái az elektromos hálózatokban és a biológiai rendszerekben. Egyes hibásan működő hálózatok javítása megvalósítható bizonyos részeinek eltávolításával.

Felfedezés

Dietrich Braess, a németországi Ruhr Egyetem matematikusa észrevette, hogy az úthálózat áramlását akadályozhatja egy új út építése, amikor a forgalommodellezésen dolgozott. Az volt az elképzelése, hogy ha minden sofőr saját érdekből az optimális döntést hozza meg arról, hogy melyik útvonal a leggyorsabb, akkor túl gyakran választanak az autóvezetők rövid utakat a lehető legrövidebb menetidő érdekében. Formálisabban Braess felfedezésének gondolata az, hogy a Nash-egyensúly nem feltétlenül valósítja meg a hálózaton keresztüli legjobb általános áramlást. A hálózatbővítés új játékstruktúrát indukál, ami egy (többszereplős) fogolydilemmához vezet.

Definíció

Egy úthálózat minden pontjára adott az onnan induló autók száma, és az autók úti céljai. A cél az adott körülményekre megbecsülni a forgalom eloszlását. Az, hogy az egyik utca előnyösebb-e a másiknál, nemcsak az út minőségétől függ, hanem az áramlás sűrűségétől is. Ha minden járművezető a számára legkedvezőbb utat választja, az ebből eredő menetidőknek nem kell minimálisnak lenniük. Továbbá az úthálózat meghosszabbítása a forgalom újraeloszlását idézheti elő, ami hosszabb egyéni menetidőket eredményez.

Ha a késleltetési függvények lineárisak, egy él hozzáadása soha nem ronthatja a teljes menetidőt egyensúlyban 4/3-nál nagyobb mértékben.

Példák

Gyakoriság

1983-ban Steinberg és Zangwill észszerű feltételezések mellett megadta a szükséges és elégséges feltételeket ahhoz, hogy Braess paradoxona egy általános közlekedési hálózatban egy új útvonal hozzáadásával létrejöhessen. (Az eredmény minden új útvonal hozzáadására vonatkozik, nem csak egyetlen új összekötésre.) Azt a következtetést vonták le, hogy a Braess-féle paradoxon körülbelül 50% eséllyel következik be véletlenszerű új útvonalak hozzáadása esetén.

Forgalom

A dél-koreai Szöulban felgyorsult a forgalom a város körül, amikor a Cheonggyecheon helyreállítási projekt részeként eltávolítottak egy autópályát. A németországi Stuttgartban az 1969-es úthálózati beruházások után a forgalmi helyzet addig nem javult, amíg az újonnan épített útszakaszt ismét le nem zárták a forgalom elől. 1990-ben New Yorkban a 42. utcát a Föld napja alkalmából ideiglenesen lezárták, ami csökkentette a torlódást a környéken. 2008-ban Youn, Gastner és Jeong konkrét útvonalakat mutatott be Bostonban, New Yorkban és Londonban, ahol ez ténylegesen előfordulhat, és rámutatott azokra az utakra, amelyeket le lehet zárni az előre jelzett menetidők csökkentése érdekében. 2009-ben New York kísérletezett a Broadway bezárásával a Times Square-en és a Herald Square-en, ami jobb forgalomhoz és állandó sétálóutcákhoz vezetett.

2012-ben Paul Lecroart, az Île-de-France tervezési és fejlesztési intézetének munkatársa azt írta, hogy „A kezdeti félelmek ellenére a főutak eltávolítása a kezdeti kiigazításokon túl nem okoz forgalmi romlásokat. A forgalom korlátozott marad, és a várakozásokat alulmúlja." Azt is megjegyzi, hogy egyes magánjellegű utazások (és a kapcsolódó gazdasági tevékenységek) nem kerülnek át a tömegközlekedésbe, és egyszerűen eltűnnek („elpárolognak”).

Ugyanez a jelenség volt megfigyelhető akkor is, amikor az útlezárás nem városi projekt része volt, hanem baleset következménye. 2012-ben Rouenben egy hidat tűz pusztított el. A következő két évben más hidakat gyakrabban használtak, de csökkent a hidakon áthaladó autók száma.

Elektromosság

2012-ben a Max Planck Institute for Dynamics and Self-Organization tudósai számítási modellezéssel kimutatták, hogy a jelenség előfordulhat olyan villamos hálózatokban, ahol az energiatermelés decentralizált.

2012-ben az Institut Néel (CNRS, Franciaország), INP (Franciaország), az IEMN (CNRS, Franciaország) és a UCL (Belgium) kutatóiból álló nemzetközi csapat a Physical Review Letters című folyóiratban publikált egy tanulmányt, amely bemutatja, hogy a Braess-féle paradoxon előfordulhat mezoszkópikus elektronrendszerekben. Az eredményeik szerint további elektronútvonalak hozzáadása egy nanoszkópikus hálózatban paradox módon csökkenti a rendszer vezetőképességét. Ezt mind szimulációkkal, mind alacsony hőmérsékleten végzett pásztázókapu-mikroszkóppal végzett kísérletekkel kimutatták.

Rugók

Két rugó rövid kötéllel sorba kapcsolva. Ha a B és C összekötő rövid kötelet hozzáadjuk, a súly lejjebb lóg.

Rugók és kötelek modellje megmutatja, hogy a felakasztott súly a függőrendszerben lévő feszült kötél elvágása ellenére is megemelkedhet. Ez ugyanabból a matematikai struktúrából következik, mint az eredeti Braess-paradoxon.

Két azonos, rövid kötéllel sorba kapcsolt rugó esetén az eredő rugóállandó minden egyes rugóállandók fele, ami hosszabb nyúlást eredményez egy bizonyos súly felakasztása esetén. Ez így marad akkor is, ha két hosszabb kötél lazán köti össze a felső rugó alsó végét a függő nehezékkel (az alsó rugó alsó vége), és az alsó rugó felső végét pedig a felfüggesztési ponttal (az alsó rugó felső vége). A rövid kötél elvágásakor azonban a hosszabb kötelek megfeszülnek, és a két rugó párhuzamos lesz egymással. Az eredő rugóállandó minden az egyes rugók kétszerese, és ha a hosszú kötelek nem túl hosszúak, a felakasztott súly ténylegesen megemelkedik a rövid kötél elvágása előtti magassághoz képest.

Az a tény, hogy a felakasztott súly megemelkedik annak ellenére, hogy egy feszes kötélt (a rövid kötélt) levágtak a rendszerből, meglepő, de Hooke törvényének, és a rugók soros és párhuzamos működésének egyenes következménye.

Biológia

Adilson E. Motter és munkatársai bebizonyították, hogy Braess-paradoxon következményei gyakran előfordulhatnak biológiai és ökológiai rendszerekben. Kimutatták, hogy a veszélyeztetett fajok táplálékhálózatainak erőforrás-gazdálkodása érdekében — ahol sok faj kihalása következhet egymás után — egy halálra ítélt faj szelektív eltávolítása a hálózatból elvileg megakadályozhatja a további kihalások sorozatát.

Csapatsport-stratégia

Felmerült, hogy a kosárlabdában a csapatot a kosárszerzéshez vezető útvonal lehetőségeinek a hálózataként tekinthetjük. Minden egyes útvonalon eltérő hatékonyságú, és egy sztárjátékos csökkentheti a csapat általános hatékonyságát. A túlzottan kihasznált rövid úthoz hasonlóan a sztárjátékos megnövelheti a labdának teljes menetidejét az úthálózatban. A maximális hatékonyság érdekében az ekkor javasolt megoldás az, hogy egy sztárjátékos körülbelül ugyanannyiszor jusson labdához, mint a többi csapattag. Ezt a megközelítést jelenleg azonban nem támasztják alá szilárd statisztikai bizonyítékok, amint azt az eredeti dokumentum is megjegyezte.

Matematikai megközelítés

Példa

Tekintsünk egy olyan úthálózatot, amely a mellékelt ábrán látható, és amelyen 4000 járművezető szeretne utazni a kezdőponttól (START) a végpontba (END). Az utazási idő percekben:

• START–A útvonalon utazók száma (T) osztva 100-zal
• START–B útvonalon állandó 45 perc
• B-END esetén útvonalon utazók száma (T) osztva 100-zal
• A-END állandó 45 perc

Ha a szaggatott út A és B között nem létezik (tehát a forgalmi hálózatnak összesen 4 útja van), akkor a START–A–END útvonal megtételéhez szükséges idő $a$ számú sofőr esetén ${\tfrac {a}{100}}+45$, míg a START–B–END útvonal megtételéhez szükséges idő $b$ számú sofőr esetén ${\tfrac {b}{100}}+45$.

Mivel 4000 sofőr van ( $a+b=4000$ ), levezethető, hogy $a=b=2000$, amikor a rendszer egyensúlyban van. Ezért mindkét útvonalon ${\tfrac {2000}{100}}+45=65$ perc a menetidő. Ha bármelyik útvonal kevesebb időt venne igénybe, az nem lenne Nash-egyensúlyban: a racionális vezető a hosszabb útvonalról a rövidebbre váltana.

Ezután tegyük fel, hogy létezik az A–B szaggatott vonal, ami egy olyan út, amelynek a menetideje elhanyagolható (0 perc). Tegyük fel, hogy az A-B út megnyílik, és az egyik vezető megpróbálja a START–A–B–END útvonalat. Azt veszi észre, hogy a menetideje ${\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01$ perc, ami majdnem 25 perc időspórolást jelent. Hamarosan a 4000 sofőr közül többen próbálkoznak ezzel az új útvonallal. Az eltelt idő 40.01-ről folyamatosan emelkedik a növekvő forgalom miatt. Amikor az új útvonalat kipróbálók száma eléri a 2500-at, akkor 1500-an még a START–B–END útvonalon vannak, az új útvonalon közlekedők menetideje ekkor már ${\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65$ perc, ami nem jobb az eredeti útvonalhoz képest. Ekkor már az 1500 maradó sofőrt lelassították $45+{\tfrac {4000}{100}}=85$ perces menetidőre. Az 1500 maradó sofőr ekkor már kénytelen A-n keresztül áttérni az új útvonalra, ami ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ perces menetidőt eredményez. Senkinek sem érdeke az A-END vagy a START-B útvonal követése, mert ekkor már 85 percessé válnak ezek az útvonalak. Így a keresztút megnyitása mindenkinek 80 percre növeli a menetidőt az eredeti 65 helyett. Ha a járművezetők megegyeznének, hogy nem használják az A–B útvonalat, vagy ha ez az útvonal lezárásra kerül, akkor minden járművezető 15 perccel csökkentené a menetidejét.

Egyensúly

Ha egy élen haladó minden egyes személy menetidejét egyenlőnek tételezzük fel, akkor egyensúlyi állapot mindig létezik.

$L_{e}(x)$ legyen a képlet az egyes személyek menetidejére, $e$ él és $x$ résztvevő esetén. Tegyük fel, hogy van egy forgalmi gráf $x_{e}$ darab sofőrrel az $e$ élen. Legyen $e$ él energiája $E(e)$, amit a következőképpen definiálunk:

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

(Ha $x_{e}=0$,akkor $E(e)=0$ ). Legyen a forgalmi gráf teljes energiája a gráf minden élének az energiáinak összege.

Keressük meg teljes energia minimumát. Egy ilyen eloszlásnak léteznie kell, mert véges sok útvonal választható. Ez a minimális energiájú eloszlás lesz az egyensúlyi állapot.

Tegyük fel, hogy a fenti állítás hamis. Ebben az esetben energiaminimum esetén legalább egy sofőr meg tudja úgy változtatni az útvonalát, hogy javítja a menetidejét. Tegyük fel, hogy az eredeti útvonala $e_{0},e_{1},\ldots ,e_{n}$, míg az új útvonala $e'_{0},e'_{1},\ldots ,e'_{m}$. Legyen $E$ a forgalmi gráf teljes energiája, és fontolja meg, mi történik az útvonalon $e_{0},e_{1},...e_{n}$ eltávolításra kerül. Az egyes $e_{i}$ élek energiája csökkenni fog ekkor $L_{e_{i}}(x_{e_{i}})$-vel,lés így a $E$ csökkenni fog ${\textstyle \sum _{i=0}^{n}L_{e_{i}}(x_{e_{i}})}$ mértékben. Ez utóbbi érték egyszerűen az eredeti útvonal megtételéhez szükséges teljes menetidő. Ha ezután hozzáadja az új útvonalat, $e'_{0},e'_{1},\ldots ,e'_{m}$, a teljes energia, $E$ megnövekszik az új útvonal megtételéhez szükséges teljes menetidővel. Mivel az új útvonal rövidebb, mint az eredeti, $E$-nek csökkennie kell az eredeti konfigurációhoz képest, ami ellentmond annak a feltételezésnek, hogy az eredeti útvonalkészlet minimálisra csökkentette a teljes energiát.

Ezért a teljes energiát minimalizáló útvonalak kiválasztása egyensúlyt jelent.

Fordítás

• Ez a szócikk részben vagy egészben a Braess's paradox című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További irodalom

• Braess (1969). „Über ein Paradoxon aus der Verkehrsplanung” (német nyelven). Unternehmensforschung 12, 258–268. o.  (translation by Nagurney & Wakolbinger)
• Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN 3-89959-123-2
• Translation of the Braess 1968 article from German to English appears as the article "On a paradox of traffic planning," by D. Braess, A. Nagurney, and T. Wakolbinger in the journal Transportation Science, volume 39, 2005, pp. 446–450. More information Archiválva 2011. szeptember 27-i dátummal a Wayback Machine-ben
• Irvine (1993). „How Braess' paradox solves Newcomb's problem”. International Studies in the Philosophy of Science 7 (2), 141–160. o. DOI:10.1080/02698599308573460. 
• Steinberg (1983). „The Prevalence of Braess' Paradox”. Transportation Science 17 (3), 301. o. DOI:10.1287/trsc.17.3.301. 
• Rapoport (2009). „Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox”. Games and Economic Behavior 65 (2), 538–571. o. DOI:10.1016/j.geb.2008.02.007. 
• T. Roughgarden. "The Price of Anarchy." MIT Press, Cambridge, MA, 2005.

Külső linkek

A Wikimédia Commons tartalmaz Braess paradoxona témájú médiaállományokat.

• Szoftvertesztelési paradoxonok (2005. december) Közvetlen kapcsolat
• Dietrich Braess honlapja
• Az úthálózat paradoxona
• Rövid videó, amely a Braess Paradoxot illusztrálja Lego minifigurákkal
• A tavaszi paradoxon, Steve Mold YouTube -videója, amely elmagyarázza Braess paradoxonját, valamint egy szorosan kapcsolódó tavaszi paradoxont