A matematikában és pontosabban a játékelméletben a Braess-paradoxon kijelenti, hogy egy új útvonal hozzáadása az úthálózathoz csökkentheti az általános teljesítményt, amikor a mozgó entitások egyenként választják meg az útvonalukat. Ennek oka , hogy egy ilyen rendszer Nash-egyensúlya nem feltétlenül optimális . Ezt a paradoxont Dietrich Braess matematikus emelte ki 1968-ban .
A paradoxont a következőképpen fogalmazzák meg:
Tekintettel az úthálózat egyes pontjairól induló járművek számára és rendeltetési helyére, megpróbáljuk megbecsülni a forgalom áramlásának megoszlását . Az, hogy az egyik csatorna előnyösebb-e a másiknál, nemcsak a csatorna minőségétől, hanem az áramlás sűrűségétől is függ. Ha minden sofőr a számára legkedvezőbbnek tűnő utat választja, az ebből adódó menetidő nem feltétlenül a legrövidebb. Ezenkívül (ezt egy példa mutatja) az úthálózat kiterjesztése a hálózat újraelosztásához vezethet, ami hosszabb menetidőt eredményez.
Ennek oka, hogy Nash-egyensúlyi helyzetben a sofőröknek nem érdeke a sávváltás. Ha a rendszer nincs Nash-egyensúlyban, a járművezetőknek képesnek kell lenniük arra, hogy más útvonalak segítségével egyénileg javítsák utazási idejüket. A Braess Paradox esetében a sofőrök az általános teljesítmény csökkenése ellenére továbbra is ringatnak, amíg el nem érik a Nash-egyensúlyt. Összehasonlíthatjuk Nash egyensúlyának ezen nem optimális jellegét a híres fogoly dilemmájával : a hálózat élének hozzáadása új játékot hoz létre, amely egy fogoly dilemma.
Ha a késleltetési függvények lineárisak, akkor egy csatorna hozzáadása legfeljebb 4/3-szorosával hosszabbíthatja meg a teljes utazási időt az egyensúlyig.
Tekintsük a hálózat le a szemközti diagram, amelyen 4000 járművezetők akar menni a Indítás pontot a Vége pontot . A Start - A sáv és a B-End sávon az utazási idő megegyezik az utazók számával (T) elosztva 100-mal, a Start - B sávon és az A-End sávon pedig állandóan 45 perc. Ha a pontozott sáv nem létezik (a hálózat, akkor a 4 sáv), az idő, hogy végre a Start - A - Vége a járművek legyen . És az idő, hogy végre a Start - B - Vége a járművek legyen . Ha az egyik útvonal rövidebb lenne, akkor nem lenne Nash-egyensúly: egy racionális sofőr a rövidebb utat választaná. Mivel 4000 vezető van, az a tény, amellyel arra lehet következtetni, hogy amikor a rendszer egyensúlyban van. Ezért minden út percekig tart .
Most tegyük hozzá a szaggatott vonallal ábrázolt tengelyt olyan rövid utazási idővel, hogy elhanyagolható, vagyis 0-t számít. Ebben a helyzetben az összes járművezető a Start - A helyett a Start - B lehetőséget választja , mert a Start - A legrosszabb esetben csak perceket vesz igénybe, míg a Start - B bizonyosan 45 percet vesz igénybe. Egyszer pont, minden racionális sofőr fogja kiválasztani a „szabad” utat B , és onnan tovább End , mert megint egy - End biztos, hogy 45 perc alatt, míg egy - B - Vége lesz legfeljebb percig. Ezért minden vezető menetideje perc, több mint a szükséges 65 perc, ha az A - B expressz vonal nem létezik. Egyetlen sofőrnek sem érdeke a változtatás, mivel a két kezdeti útvonal ( Start - A - Vég és Start - B - Vég ) most mindkettő 85 percet vesz igénybe. Ha az összes sofőr beleegyezik abba, hogy nem használja az A - B összeköttetést , mindenki számára előnyös lehet, ha 15 perccel lerövidíti útját. Mivel azonban az egyéni sofőrnek mindig érdeke lesz az A - B út választása , a társadalmilag optimális eloszlás nem stabil, és bekövetkezik a Braess-paradoxon.
Legyen az e sáv utazási ideje egy járművel, ha ezen a sávon x jármű van.
Vegyünk egy grafikont az e vágány vezetőivel . Adjuk energia , szerint:
(Igen , kérdezzük ). Nevezzük „a gráf teljes energiájának” a gráf összes élének energiáinak E összegét .
Ha a grafikon eloszlása nincs egyensúlyban, akkor legalább egy sofőrnek kell lennie, aki megváltoztathatja az útvonalat az utazási idő javítása érdekében. Jegyezze fel a kezdeti és az új útvonalat. Fontolja meg, mi történik az útvonal törlésével. Az egyes élek energiája csökken, és ezért csökken . Vegye figyelembe, hogy ez egyszerűen a teljes út szükséges a régi úton. Felveszi az új útvonalat , növeli a teljes utazási idő az új útvonalat. Mivel az új útvonal rövidebb, mint a régi, csökkentenie kell. Ha megismételjük ezt a folyamatot, akkor tovább csökken, amíg ki nem áll az egyensúly, mivel csak véges számú értéket vehet fel.
A fenti bizonyítás egy " legjobb válasz " néven ismert eljárást generál , amely egyensúlyt eredményez egy lineáris forgalmi gráfnál, és véges számú lépés után ér véget. Az algoritmust azért hívják "legjobb válasznak", mert az algoritmus minden egyes lépésénél, ha a grafikon nincs egyensúlyban, akkor van legalább egy olyan illesztőprogram, aki jobban reagál az összes többi meghajtó stratégiájára, és ezért ezt választja válasz.
Álkód a legjobb dinamikus válasz érdekében:
Soit P un graphe de trafic. tant que P n'est pas à l'équilibre : calculer l'énergie potentielle e de P pour chaque conducteur c de P: pour chaque chemin alternatif p possible pour c: calculer l'énergie potentielle n du graphe lorsque c utilise p si n < e: modifier P de telle sorte que c utilise p continuer la boucle tant queMinden lépésnél, ha egy adott járművezető jobban teljesíthet más útvonal kiválasztásával (a "legjobb válasz"), ez szigorúan csökkenti a grafikon energiáját. ha egyetlen illesztőprogram sem reagál jobban, a grafikon egyensúlyban van. Mivel a grafikon energiája szigorúan csökken minden lépésnél, a legjobb dinamikus válasz algoritmus szükségszerűen leáll.
Ha az utazási idő függvénye affin , azaz ha létezik olyan, hogy akkor a legrosszabb esetben az egyensúlyi forgalom kétszer olyan rossz, mint a társadalmi optimális
DemonstrációAz x járművek által megtett e él energiája az aritmetikai progresszióban szereplő x számok összege :
.Az összes vezető ezen az élen eltöltött teljes ideje egyenlő:
.Egyrészt, mivel :
.Másrészről :
.Összefoglalva :
.Ha Z a járművek eloszlása a forgalmi grafikonon, a grafikon összes szélének összeadásával megkapjuk:
Vagyis társadalmilag optimális eloszlás és egyensúlyi eloszlás esetén (ugyanarra a grafikonra):
ezért .
1983-ban Steinberg és Zangwill ésszerű feltételezések mellett szükséges és elégséges feltételeket adott ahhoz, hogy a Braess-paradoxon új útvonal hozzáadásakor beavatkozhasson egy úthálózatba. (Ne feledje, hogy eredményük bármilyen új út hozzáadására vonatkozik , nem csak egyetlen link hozzáadásával.) Következményként arra a következtetésre jutottak, hogy Braess paradoxonának körülbelül annyi esélye van, mint megtörténni; eredményeik véletlenszerű helyzetekre vonatkoznak, nem pedig a tervezett hálózatokra és kiegészítésekre.