Braess-paradox: ‘verbeteringen’ in het netwerk

January 5, 2016

Share this article:

Het veroorzaakte veel opschudding in de stad New York toen de burgemeester in 1990 besloot om 42nd street voor een dag te sluiten. Hij deed dit naar aanleiding van Earth Day, een jaarlijks terugkerende dag waarbij wordt stilgestaan bij het consumptiegedrag van de mensheid. Waar iedereen dacht dat dit besluit voor een enorme chaos zou zorgen, gebeurde het tegenovergestelde: de verkeersstroom in de stad verliep alleen maar vlotter.

In 1968 was de Duitser Dietrich Braess de eerste die een dergelijk fenomeen ontdekte en onderzocht. Hij ondervond dat het toevoegen van een extra route aan een wegennetwerk niet per se hoefde te leiden tot een reductie in de doorstroming van dat netwerk. Daarom wordt het ook wel Braess-paradox genoemd: hoe kan het dat het een lijkende verbetering tot een vermindering in prestaties kan leiden? Ook komt de paradox volgens experts voor op andere gebieden, zoals sport en biologie.

Het schoolvoorbeeld

Laten we beginnen met een klassiek voorbeeld: een verkeersnetwerk. Stel dat we de situatie hebben zoals hieronder weergegeven. Er zijn vier plaatsen (A, B, C en D) verbonden met elkaar. De reistijden in minuten staan aangegeven onder het betreffende pad. De reistijden van B naar D en van A naar C hangen af van het aantal voertuigen dat daar per uur langsgaat, respectievelijk Y en X. Ook nemen we aan dat de bestuurders van de voertuigen van elkaar weten wat hun uitgangspunten zijn. Met andere woorden: alle bestuurders zijn rationeel. Een bestuurder heeft als doel om zo snel mogelijk van A naar D te reizen.
schoolvoorbeeld1
Wat zal de evenwichtssituatie zijn in dit voorbeeld? Stel dat alle bestuurders (2000) ervoor kiezen om via B naar D te reizen. Voor een reguliere bestuurder betekent dit dat de reistijd 25 + 2000/100 = 45 minuten bedraagt. Echter, alle bestuurders zijn rationeel. Dit betekent dus dat iedere bestuurder zich zal realiseren dat hij zijn reistijd kan optimaliseren door de andere route te kiezen. Uiteindelijk zullen de bestuurders zich verdelen over de beide routes totdat iedere bestuurder zich realiseert dat hij zijn situatie niet meer kan verbeteren door de andere route te kiezen. Dit resulteert in een reistijd van 25 + 1000/100 = 35 minuten voor elke bestuurder. Er ontstaat een Nash evenwicht: niemand kan zijn reistijd verkleinen, er vanuit gaande dat anderen hun strategie niet veranderen aangezien dat geen verbeteringen oplevert.
Stel nu dat het mogelijk wordt om van B naar C te gaan en vice versa met een reistijd van 0 minuten. Deze situatie wordt hieronder weergegeven. Op zich zou je nu denken dat het systeem zal worden verbeterd. Er wordt een extra mogelijkheid toegevoegd om de plaats van bestemming te bereiken. Het tegendeel is echter waar. Iedere bestuurder zal ervoor kiezen om eerst van A naar C te reizen, dan de switch te maken van C naar B en vervolgens naar D te reizen. Vanaf A kiest iedereen ervoor om naar C te reizen aangezien je nooit slechter af kunt zijn dan een tijd van 20 minuten. Dat gebeurt als iedereen voor deze route kiest.  Dit kost uiteindelijk 2000/100 + 2000/100 = 40 minuten. De toevoeging zorgt dus voor een extra reistijd van 5 minuten. Ondanks dat dit een theoretisch concept lijkt, wordt het toch waargenomen in de praktijk zoals in New York in 1990. Daar gebeurde eigenlijk het tegenovergestelde als in dit voorbeeld. In plaats van de toevoeging van een pad, besloot de burgemeester om er een weg te halen.
schoolvoorbeeld2

Ewing Theory

Niet alleen op het gebied van verkeer doet de paradox zich voor. De sportwereld heeft zijn eigen versie. In 2009 kwam de Amerikaanse sportjournalist Bill Simmons met zijn invulling van wat hij de Ewing Theory noemde. Hij stelde dat Patrick Ewing’s basketbalteams, Georgetown en New York, beter presteerden als Ewing, door velen bestempeld als beste speler, plaatsnam op de reservebank of geblesseerd was. Zijn theorie was dat als Ewing speelde zijn teamgenoten hem zoveel mogelijk in scoringspositie probeerden te brengen. Hierdoor zouden zijn teamgenoten ‘vergeten’ om zelf de weg naar de ring te vinden. Met andere woorden: er zou te veel ‘verkeer’ naar de ring via Ewing gaan. Als er wordt aangenomen, en dat doet Simmons, dat de efficiëntie van een speler afneemt naarmate er meer doelpogingen worden ondernomen, heeft dit tot uitwerking dat het team uiteindelijk minder presteert.

American Football

Een zelfde verschijnsel onderzochten Skinner en Carlin (2012) [1] van de Universiteit van Minnesota in American Football. Ze nemen als voorbeeld een team met een zeer getalenteerde quarterback, een soort spelverdeler. Omdat verondersteld wordt dat de quarterback een goede speler is, zal geprobeerd worden om daar zo vaak mogelijk gebruik van te maken. In dit onderzoek wordt de vergelijking getrokken tussen de paradox in het verkeer en bij American Football. In het verkeer hebben de bestuurders het doel om zo snel mogelijk van A naar B te gaan. In het onderzoek wordt aangenomen dat het doel bij American Football het winnen van meters is.
In het onderzoek representeren de mogelijke passes de routes uit het verkeersprobleem. Daarbij komt dat de keus voor de ene pass meer kan opleveren dan een andere, maar ook dat sommige keuzes risicovoller zijn. Daar waar in het verkeer een bepaalde route wordt vertraagd naarmate die meer gebruikt wordt, is het bij American Football zo dat passes ook minder effectief kunnen worden naarmate die intensiever gebruikt worden. Stel bijvoorbeeld dat een speler zo vaak de bal krijgt en loopacties moet maken dat hij vermoeid wordt. Ook kan het zo zijn dat de verdediging van de tegenstander anticipeert op het feit dat een bepaald pass frequent gegeven wordt. Dit resulteert in een minder efficiënt gebruik van de ‘routes’.
Skinner en Carlin gebruiken in hun onderzoek een van de beste quarterbacks van de NFL: Peyton Manning. Het aantal passes in zijn dertien jaar durende loopbaan wordt per seizoen bekeken. Het blijkt dat Manning efficiënter wordt, lees meer meters wint, als hij minder passes per wedstrijd verzorgt. Skinner en Carlin vinden een verband tussen het aantal passes en de efficiëntie van die passes.
Aan dit model zitten nogal wat haken en ogen; er wordt bijvoorbeeld geen rekening gehouden met de kracht van Manning’s team. De vraag die Skinner en Carlin zichzelf stellen is echter wel een interessante: kunnen we bepalen hoe vaak een speler als Manning een pass moet versturen om zo veel meters te winnen? Daarom wordt ervoor gekozen om het onderzoek nog wat uit te breiden.
Skinner en Carlin gaan er vanuit dat een team twee keuzes heeft bij het opzetten van een aanval; er kan gekozen worden voor een pass van de quarterback of er kan een loopactie ingezet worden. Aan een loopactie wordt gemiddeld 4,5 yards toegekend, terwijl de yard-winst van een pass afhangt van de hoeveelheid passes.
De onderzoekers merken op dat het zou lonen om zoveel passes te versturen totdat die gemiddeld 4,5 yards opleveren, evenveel als een loopactie. Als er wordt uitgegaan van de eerdere functie y = a + bx, berekenen Skinner en Carlin dat dit neerkomt op 57 passes van Manning per wedstrijd. Dat is bijna het totale aantal passes van Mannings team per wedstrijd! Dit evenwicht is vergelijkbaar met het voorbeeld van Braess-paradox in het verkeer. In het voorbeeld van het verkeer kiest iedere bestuurder voor zijn persoonlijk meest voordelige route waardoor vervolgens de doorstroming vermindert. Bij American Football geeft Manning zo veel passes dat de bijbehorende efficiëntie afneemt totdat die net zo veel oplevert als een loopactie.
Vervolgens wordt het volgende model opgesteld:

    \[Y = x \times y(x) + x_{run} \times y_{run}(x_{run})\]

Het totaal aantal plays wordt beperkt tot een aantal van 61, het gemiddeld aantal plays in een American Football wedstrijd: x + x_{run} = 61. Er wordt vervolgens berekend dat een x = 29 en x_{run} = 32 de meest voordelige strategie is. Dit resulteert in 8,3 yards per pass van Manning. Het tegenstrijdige hiervan is dat Manning maar 29 passes verstuurt. Je zou denken dat, gezien zijn exceptionele kwaliteiten, Manning meer passes zou moeten geven. In de praktijk gebeurt het laatste vaak: Manning wordt vaker gezocht in het veld om veel in het spel te worden betrokken. Wat er vervolgens gebeurt is dat de efficiëntie van zijn passes naar beneden gaat en de strategie verschuift naar een Nash Equilibrium waar Manning 94% van de passes op zich neemt. Dit is het punt dat een pass van Manning evenveel oplevert als een gewone loopactie met de bal: 4,5 yards zoals in het vorige voorbeeld. Als je op een statistische manier als deze redeneert, zou de coach van het team van Manning de keuze moeten maken om Manning in het verloop van de wedstrijd te wisselen zodat het rendement, lees de meterwinst per pass, niet naar beneden gaat. Het zou goed kunnen zijn dat de quarterback die op de bank zit, efficiënter is dan Manning als hij al zoveel passes heeft gegeven. Het frappante hieraan is: welke coach in het American Football haalt zijn beste quarterback naar de kant, omdat een paar statistici menen dat het verstandiger is om Manning niet de gehele wedstrijd op te stellen?
Het is opvallend om te zien dat het principe van Braess-paradox tegenwoordig in meer gebieden dan alleen het verkeersnetwerk opgemerkt wordt, ook in de sport, waar statistieken een steeds prominentere rol spelen. De aannames die in het onderzoek van Skinner en Carlin worden gedaan zijn nogal extreem: een team zou slechts twee keuzes hebben bij een aanval, een pass en een loopactie, en ook wordt er geen rekening gehouden met de kracht van het team van Manning als er wordt gekeken naar de efficiëntie van zijn passing. Toch is het een interessant onderzoek dat eens te meer aantoont dat statistieken in de sport een steeds groter aandeel in de professionele sport krijgt zoals het feit dat veel sportclubs tegenwoordig statistici in dienst hebben om het spel te analyseren. Het blijft daarentegen wachten op de coach die Peter Manning op basis van deze statistieken naar de kant haalt.
[1] ‘The Price of Anarchy of Football’, B. Skinner and B.P. Carlin, 2012


Dit artikel is geschreven door Jorrit Visser

jorritvisser

Read more

The Seven Bridges of Königsberg

The Seven Bridges of Königsberg

Imagine you are taking a stroll around the 18th century Prussian city of Königsberg (currently Kaliningrad, Russia). The river Pregel runs through Königsberg and there are two large islands in this river. The islands are connected to each other and to the mainland by...

Mr. Pity vs. Nature

Mr. Pity vs. Nature

Mr. Pity was a very, very unlucky man. As a kid he had once accidentally stepped on a butterfly in the forest. But this was no ordinary butterfly! It was the most beautiful butterfly Nature had ever produced. Out of revenge, Nature cursed young Mr. Pity: "Whatever you...