Braess paradoks

Braess -paradokset er en illustration af det faktum, at en ekstra handlingsmulighed under forudsætning af rationelle individuelle beslutninger kan føre til en forværring af situationen for alle. Paradokset blev udgivet i 1968 af den tyske matematiker Dietrich Braess .

Braess 'originale arbejde viser en paradoksal situation, hvor anlæg af en ekstra vej (dvs. en forøgelse af kapaciteten) fører til, at rejsetiden for alle chauffører stiger (dvs. netets kapacitet reduceres), mens trafikmængden forbliver det samme. Dette er baseret på den antagelse, at hver trafikant vælger sin rute på en sådan måde, at han ikke har anden mulighed med en kortere rejsetid. Den situation, der opstår efter anlæg af den nye vej, kan i spilteorien tolkes som et fange-dilemma for flere personer og dermed forklare dette paradoks.

Indimellem diskuteres paradokset også med egoistiske routere . Derudover er Braess -paradokset et eksempel på, at den rationelle optimering af individuelle interesser i forbindelse med et offentligt ydet godt kan føre til en forværret tilstand for hver enkelt.

eksempel

Et vejnet vælges her som et eksempel på forekomsten af Braess -paradokset. Hvis dette vejnet udvides med en anden vej, øges køretiden for hver chauffør. Eksemplet er taget fra Braess 'originale værk Über ein Paradoxon fra 1968 i trafikplanlægning .

indledende situation

Fig. 1: Skitse af den oprindelige situation

Figur 2: Trafiktæthed med 6000 chauffører i timen

De fire byer A, B, C og D er forbundet med fire veje. En motorvej kører både fra A til C og fra B til D. Motorvejene er veludviklede, så rejsetiden ikke afhænger meget af trafiktætheden. Motorvejene skal dog overvinde en forhindring og er derfor ret lange. Når der er trafik $x$ ${\ displaystyle x}$ $x$ (i tusinder af biler i timen) er den tilsvarende rejsetid pr. chauffør

t_{\mathrm {AC} }(x)=t_{\mathrm {BD} }(x)=(50+x)\,\mathrm {min}

{\ displaystyle t _ {\ mathrm {AC}} (x) = t _ {\ mathrm {BD}} (x) = (50 + x) \, \ mathrm {min}}

{\ displaystyle t _ {\ mathrm {AC}} (x) = t _ {\ mathrm {BD}} (x) = (50 + x) \, \ mathrm {min}}

Byer A og B er ligesom byerne C og D forbundet med en landevej. Selvom disse veje er kortere end motorvejene, er de meget dårligere udviklet. Rejsetiden pr. Chauffør afhænger derfor i det væsentlige kun af trafikmængden:

t_{\mathrm {AB} }(x)=t_{\mathrm {CD} }(x)=(0+10\cdot x)\,\mathrm {min}

{\ displaystyle t _ {\ mathrm {AB}} (x) = t _ {\ mathrm {CD}} (x) = (0 + 10 \ cdot x) \, \ mathrm {min}}

{\ displaystyle t _ {\ mathrm {AB}} (x) = t _ {\ mathrm {CD}} (x) = (0 + 10 \ cdot x) \, \ mathrm {min}}

Alle chauffører vil køre fra A til D, og hver chauffør vælger den hurtigste rute for dem. Der etableres en såkaldt Nash-ligevægt , hvor halvdelen af chaufførerne bruger ruten via by B og den anden halvdel kører via by C. Med 6.000 chauffører i timen kører 3.000 biler hver rute, og alle chauffører har en køretid på 83 minutter.

Scenarie efter anlæg af den ekstra vej

Fig. 3: Skitse af scenariet efter anlæg af den ekstra vej

Fig. 4: Ligevægtssituation med den nye linje. Strømmene (i 1000 biler i timen) er angivet på ruterne

Efter et stykke tid beslutter de ansvarlige politikere at bygge en tunnel gennem bjerget mellem byerne B og C, som vist i figur 3. Denne nye linje kan kun køres i retning B → C - dette forenkler overvejelsen, men er ikke relevant for forekomsten af paradokset.

På denne ekstra rute gælder rejsen

t_{\mathrm {BC} }(x)=(10+x)\,\mathrm {min}

{\ displaystyle t _ {\ mathrm {BC}} (x) = (10 + x) \, \ mathrm {min}}

{\ displaystyle t _ {\ mathrm {BC}} (x) = (10 + x) \, \ mathrm {min}}

.

Så denne rute er kort og har en høj kapacitet .

Også her er der en balance (fig. 4), hvor rejsetiderne er ens på alle ruter:

2000 chauffører vælger ABD -ruten
2000 chauffører vælger ACD -ruten
2000 chauffører vælger ABCD -ruten
Således er der en strøm på 4.000 køretøjer i timen på landevejene, og en strøm på 2.000 køretøjer i timen på motorvejene og den nye anlægslinje.

I dette tilfælde er rejsetiden for alle chauffører 92 minutter og dermed 9 minutter længere end uden den nye rute.

illustration

Betragtet klart har chauffører, der bruger en af motorvejene, en uundgåelig vej til at bruge landevejsafsnittet som en flaskehals. Der afhænger hastigheden af trafikstrømmen stærkt af antallet af trafikanter eller reduceres af dem. Det nye vejbyggeri betyder dog nu, at nogle bilister bruger landevejens fulde længde og dermed også tilstopper det - udover den nye rute bruger de nu både landevejsstrækninger og ikke kun en som motorvejsbrugerne. Nu er flaskehalssituationen blevet tydeligere, da motorvejsbrugerne også har brug for betydeligt længere tid til deres uundgåeligt brugte vejstrækning på landet. I eksemplet kan den tilsvarende reduktion i trafikken på motorvejene med høj kapacitet ikke medføre en kompenserende tidsfordel.

diskussion

Man kunne nu antage, at et andet rutevalg af nogle bilister ville skabe en bedre situation. Dette er imidlertid ikke tilfældet. En chauffør, der - hvis den beskrevne balance eksisterer - beslutter andet dagen efter, har den virkning, at rejsetiden på den rute, han har valgt - og dermed for ham selv - forlænges. Denne tilstand svarer til en Nash -ligevægt . På den foregående dags rute reduceres rejsetiden dog for alle andre. Dette er naturligvis ikke et kriterium, der får en chauffør til at ændre sin rute. For nemheds skyld ændrer 1000 chauffører i det følgende numeriske eksempel hver deres rute i forhold til ligevægten. Hvis en individuel chaufførs adfærd ændrede sig, ville ændringerne være mindre, men altid gå i samme retning på grund af den monotone (lineære) afhængighed af rejsetiden på floden.

Fig. 5: Gennemsnitlig rejsetid, hvis N = 6000 chauffører kører p via BD og k via BC. Det vil sige N - p - k drev på AC, N - p CD, p + k AB, k BC, p BD. Minimumet er p = 3000, k = 0 (rødt område).

3000 chauffører vælger ABD -ruten og tager 93 minutter. 2000 chauffører vælger ACD -ruten og tager 82 minutter. 1000 chauffører vælger ABCD -ruten og tager 81 minutter.
3000 chauffører vælger ABD -ruten og tager 103 minutter. 1000 chauffører vælger ACD -ruten og tager 81 minutter. 2000 chauffører vælger ABCD -ruten og tager 92 minutter.
2000 chauffører vælger ABD -ruten og tager 82 minutter. 3000 chauffører vælger ACD -ruten og tager 93 minutter. 1000 chauffører vælger ABCD -ruten og tager 81 minutter.
1000 chauffører vælger ABD -ruten og tager 81 minutter. 3000 chauffører vælger ACD -ruten og tager 103 minutter. 2000 chauffører vælger ABCD -ruten og tager 92 minutter.
1000 chauffører vælger ABD -ruten og tager 91 minutter. 2000 chauffører vælger ACD -ruten og har brug for 102 minutter. 3000 chauffører vælger ABCD -ruten og tager 103 minutter.
2000 chauffører vælger ABD -ruten og har brug for 102 minutter. 1000 chauffører vælger ACD -ruten og tager 91 minutter. 3000 chauffører vælger ABCD -ruten og tager 103 minutter.

Bemærk, at på alle ruter med 3000 chauffører i timen er rejsetiden længere end 92 minutter.

Hvis alle bilister accepterede at ignorere den nye rute og opføre sig, som de gjorde, da den ikke eksisterede, ville rejsetiden for alle trafikanter være 83 minutter igen. Fristelsen ville dog være stor til at være den eneste, der skulle bruge den gratis nye linje og dermed reducere din egen rejsetid fra 83 minutter til 70 minutter. Den sædvanlige menneskelige adfærd er derefter at efterligne misligholdelsen af kontrakten. Systemet har således en tendens til at vende tilbage til ligevægten beskrevet ovenfor. Som en løsning på dette dilemma er der ingen anden mulighed end at rive den nye linje, der er planlagt centralt, eller at fordoble kapaciteten på linjer AB og CD.

I sin originale publikation klassificerede Braess ikke situationen som et fangenes dilemma , men det er en variant af et flerpersoners fange-dilemma med tre beslutningsalternativer. ^[1]

Forekomsten af Braess -paradokser i den virkelige verden

Der er eksempler på, at Braess -paradokset ikke bare er en teoretisk konstruktion. I 1969 betød åbningen af en ny gade i Stuttgart , at trafikstrømmen i nærheden af Schlossplatz forværredes. ^[2] I 1990 blev det omvendte fænomen observeret i New York . Blokering af 42nd Street reducerede mængden af trafikpropper i området. ^[3] På samme måde blev trafikstrømmen og rejsetiden forbedret i den sydkoreanske hovedstad Seoul i 2005, efter at en firefelts krydsfri bymotorvej blev revet ned. ^[4] ^[5] Der er mere empiriske rapporter om forekomsten af paradokset fra Winnipegs gader. ^[6] I Neckarsulm blev trafikstrømmen forbedret, efter at en ofte lukket overkørsel blev lukket helt ned. Effekten blev vist, da den midlertidigt skulle lukkes på grund af en byggeplads. Teoretiske overvejelser tyder også på, at Braess -paradokset ofte forekommer i tilfældige netværk. ^[7] Mange netværk i den virkelige verden er tilfældige netværk.

Mekanisk analog

Mekanisk analog: en vægt hænger på to bløde fjedre (gul) og tre hårde fjedre (blå og rød)

Der er en analog - selv om det ikke er i den snævre betydning af en matematisk fremstilling - til Braess -paradokset i mekanik : ^[8]

En vægt (vægtkraft 6 N) suspenderes fra to fjedertråde. Den første består af en svag gul fjer øverst (mellem punkterne A og B) og en stærk blå fjer i bunden (mellem B og D), den anden streng øverst på en stærk blå fjer (mellem A og C) og en i bunden svag gul fjer (mellem C og D). De gule fjer har en funktion af den kraft, der virker på dem $F.$ ${\ displaystyle F}$ $F.$ længden $l_{\mathrm {g} }(F)=10\,\mathrm {\tfrac {cm}{N}} \cdot F$ ${\ displaystyle l _ {\ mathrm {g}} (F) = 10 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ ${\ displaystyle l _ {\ mathrm {g}} (F) = 10 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ der har foretrukket blå fjer i længden $l_{\mathrm {b} }(F)=50\,\mathrm {cm} +1\,\mathrm {\tfrac {cm}{N}} \cdot F$ ${\ displaystyle l _ {\ mathrm {b}} (F) = 50 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ ${\ displaystyle l _ {\ mathrm {b}} (F) = 50 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ . Vægten fordeles ligeligt mellem suspensionerne ABD og ACD, således at en kraft på 3 N virker på begge suspensioner. Fjedrenes længde er derefter

{\begin{matrix}l_{\mathrm {AB} }(3\,\mathrm {N} )=30\,\mathrm {cm} \\l_{\mathrm {BD} }(3\,\mathrm {N} )=53\,\mathrm {cm} \\l_{\mathrm {AC} }(3\,\mathrm {N} )=53\,\mathrm {cm} \\l_{\mathrm {CD} }(3\,\mathrm {N} )=30\,\mathrm {cm} \end{matrix}}

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \ end {matrix}}}

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \ end {matrix}}}

Hele affjedringen er 83 cm lang.

Hvis nu punkterne B og C er forbundet med en anden fjeder (rød i skitsen), hvis længde $l_{\mathrm {r} }(F)=10\,\mathrm {cm} +1\,\mathrm {\tfrac {cm}{N}} \cdot F$ ${\ displaystyle l _ {\ mathrm {r}} (F) = 10 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ ${\ displaystyle l _ {\ mathrm {r}} (F) = 10 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ man kunne antage, at denne fjeder absorberer en del af kraften og derved aflaster de andre fjedre, så vægten løftes. Faktisk er kun de blå fjer lettet, og de gule fjer er tungere belastet. Da de gule fjer er svagere, udvider de sig mere, end de blå forkorter. Dette fører til, at vægten falder. I ligevægtstilstand virker kræfter på 2 N hver på de blå fjedre og den røde fjeder og kræfter på 4 N hver på de gule fjedre, hvilket resulterer i følgende længder:

{\begin{matrix}l_{\mathrm {AB} }(4\,\mathrm {N} )=40\,\mathrm {cm} \\l_{\mathrm {BD} }(2\,\mathrm {N} )=52\,\mathrm {cm} \\l_{\mathrm {AC} }(2\,\mathrm {N} )=52\,\mathrm {cm} \\l_{\mathrm {CD} }(4\,\mathrm {N} )=40\,\mathrm {cm} \\l_{\mathrm {BC} }(2\,\mathrm {N} )=12\,\mathrm {cm} \end{matrix}}

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BC}} (2 \, \ mathrm {N}) = 12 \, \ mathrm {cm} \ end {matrix}}}

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BC}} (2 \, \ mathrm {N}) = 12 \, \ mathrm {cm} \ end {matrix}}}

Længden af hele affjedringen stiger til 92 cm.

Bemærk: For at finde ligevægten skal følgende ligningssystem løses for kræfterne:

{\begin{matrix}F_{\mathrm {AB} }=F_{\mathrm {BD} }+F_{\mathrm {BC} }\\F_{\mathrm {CD} }=F_{\mathrm {BC} }+F_{\mathrm {AC} }\\F_{\mathrm {AB} }+F_{\mathrm {AC} }=6\,\mathrm {N} \\F_{\mathrm {AB} }=F_{\mathrm {CD} }\\l_{\mathrm {AB} }(F_{\mathrm {AB} })+l_{\mathrm {BC} }(F_{\mathrm {BC} })=l_{\mathrm {AC} }(F_{\mathrm {AC} })\end{matrix}}

{\ displaystyle {\ begin {matrix} F _ {\ mathrm {AB}} = F _ {\ mathrm {BD}} + F _ {\ mathrm {BC}} \\ F _ {\ mathrm {CD}} = F _ {\ mathrm {BC}} + F _ {\ mathrm {AC}} \\ F _ {\ mathrm {AB}} + F _ {\ mathrm {AC}} = 6 \, \ mathrm {N} \ \ F _ {\ mathrm {AB}} = F _ {\ mathrm {CD}} \\ l _ {\ mathrm {AB}} (F _ {\ mathrm {AB}}) + l _ {\ mathrm {BC }} (F _ {\ mathrm {BC}}) = l _ {\ mathrm {AC}} (F _ {\ mathrm {AC}}) \ end {matrix}}}

{\ displaystyle {\ begin {matrix} F _ {\ mathrm {AB}} = F _ {\ mathrm {BD}} + F _ {\ mathrm {BC}} \\ F _ {\ mathrm {CD}} = F _ {\ mathrm {BC}} + F _ {\ mathrm {AC}} \\ F _ {\ mathrm {AB}} + F _ {\ mathrm {AC}} = 6 \, \ mathrm {N} \ \ F _ {\ mathrm {AB}} = F _ {\ mathrm {CD}} \\ l _ {\ mathrm {AB}} (F _ {\ mathrm {AB}}) + l _ {\ mathrm {BC }} (F _ {\ mathrm {BC}}) = l _ {\ mathrm {AC}} (F _ {\ mathrm {AC}}) \ end {matrix}}}

Slægtskab med andre problemer

En variant af Newcombs problem kan løses ved hjælp af Braess -paradokset. ^[9]
Braess -paradokset er en variant af minoritetsspillet , når minoritet forstås at betyde, at en chauffør "kører godt", hvis han vælger en vej, der er mindre tilbagelagt, end ligevægtsløsningen giver. Hvis man generaliserer til omkostningsfunktioner , der ikke længere er monotone , gælder denne erklæring ikke længere.
Braess-paradokset ligner noget af is-sælger-på-stranden-problemet . Der beskrives også en situation, hvordan det teoretisk er muligt, at et systemoptimum kan gå glip af, hvis aktørerne hverken koordinerer eller organiserer centralt.

Se også

Downs-Thomson Paradox

litteratur

Dietrich Braess: Om et paradoks fra trafikplanlægning . (PDF; 841 kB) I: Unternehmensforschung . 12, s. 258-268.
Katharina Belaga-Werbitzky: The Braess Paradox i udvidede Wheatstone-netværk med M / M / 1-operatører . ISBN 3-89959-123-2 (afhandling).
Jörg Esser: Simulering af bytrafik på basis af mobilautomater . Duisburg 1997, DNB 953736350 , kapitel 8 (afhandling, University of Duisburg).

Weblinks

Dietrich Braess 'arbejdsside med en bibliografi om emnet
Jane Hagstrom: Braess's Paradox -eksempler - Single Origin -Destination Pair
Jane Hagstrom: Braess's Paradox -eksempler - Flere oprindelses -destinationpar

Individuelle beviser

^ Andreas Diekmann: Spelteori. Rowohlt Taschenbuch Verlag, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9 , s. 113-122.
↑ Wolfgang Blum: Motorvejen lokker for evigt. I: Süddeutsche Zeitung . 24. januar 2006.
^ G. Kolata: Hvad hvis de lukkede 42nd Street, og ingen lagde mærke til det? I: New York Times . 25. december 1990, s.38.
^ J. Vidal: Byens hjerte og sjæl I: The Guardian . 1. november 2006.
↑ K. Schön: Trafikprop? Nedriv byens motorvej! I: urbanistisk magasin . 7. februar 2014.
↑ C. Fisk, S. Pallotion: empiriske beviser for Equilibrium Paradokser med implikationer for optimal planlægning strategier. I: Transportforskning. Bind 15A, 1981, nr. 3, s. 245-248.
^ Greg Valiant, Tim Roughgarden: Braess paradoks i store tilfældige grafer. I: Proceedings of the 7. ACM -konference om elektronisk handel. Ann Arbor MI 2006.
↑ Joel E. Cohen, Paul Horowitz: Paradoksal opførsel af mekaniske og elektriske netværk . I: Naturen . 352, 22. august 1991, s. 699-701, doi: 10.1038 / 352699a0 .
^ AD Irvine: Hvordan Braess 'paradoks løser Newcombs problem. I: Internationale studier i videnskabens filosofi . Bind 7, 1993, nr. 2, s. 145-164.

[Diekmann2009-1] Andreas Diekmann: Spelteori. Rowohlt Taschenbuch Verlag, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9 , s. 113-122.

[BLUM-2] Wolfgang Blum: Motorvejen lokker for evigt. I: Süddeutsche Zeitung . 24. januar 2006.

[NYT-3] G. Kolata: Hvad hvis de lukkede 42nd Street, og ingen lagde mærke til det? I: New York Times . 25. december 1990, s.38.

[Guardian-4] J. Vidal: Byens hjerte og sjæl I: The Guardian . 1. november 2006.

[urbanist-5] K. Schön: Trafikprop? Nedriv byens motorvej! I: urbanistisk magasin . 7. februar 2014.

[Fisk-6] C. Fisk, S. Pallotion: empiriske beviser for Equilibrium Paradokser med implikationer for optimal planlægning strategier. I: Transportforskning. Bind 15A, 1981, nr. 3, s. 245-248.

[Valiant-7] Greg Valiant, Tim Roughgarden: Braess paradoks i store tilfældige grafer. I: Proceedings of the 7. ACM -konference om elektronisk handel. Ann Arbor MI 2006.

[8] Joel E. Cohen, Paul Horowitz: Paradoksal opførsel af mekaniske og elektriske netværk . I: Naturen . 352, 22. august 1991, s. 699-701, doi: 10.1038 / 352699a0 .

[Irvine-9] AD Irvine: Hvordan Braess 'paradoks løser Newcombs problem. I: Internationale studier i videnskabens filosofi . Bind 7, 1993, nr. 2, s. 145-164.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]