Jag kom hem från jobbet och började bläddra i Ny Teknik. Jag kom till spalten för veckans problem, miniproblemet, och började genast med en lösning. Veckans problem handlar om trafikstockning och lyder:
En graf över problemet
Ett mycket stort antal bilar skall efter ett evenemang i A köra till D. Vägarna AC, BC och BD har hög kapacitet. Där är körtiden alltid densamma, 2 h, 0,25 h respektive 2 h. Vägen AB har begränsad kapacitet, och körtiden är (1 + p) timmar, där 0 < p < 1 är andelen av bilarna som kör AB. Analogt gäller för vägen CD, med 0 < q < 1.
Man får först höra att vägen BC är avstängd. Då planerar ungefär hälften av förarna att köra ABD och resten ACD. I båda fallen tar det 3,5 h. Men just innan evenemanget är slut får man veta att BC har öppnats, och man får också kontinuerligt rapporter om trafikflödet på vägarna.
Denna nya möjlighet leder till att alla resorna tar en kvart längre. Hur kan det komma sig?
Eftersom alla bilar kontinuerligt har information om hur de andra bilarna agerar kommer samtliga bilar att ta lika lång tid på sig ute på vägen. Detta innebär att alla tänkbara vägsträckor kommer att gå lika fort att åka, så:
1+p + 2 = 2 + 1+q = 1+p + 0,25 + 1+q (1)
<=> 3+p = 3+q <=> q = p
=> 3+p = 2,25 + 2p => p = q = 0,75
Stoppas detta in i (1) blir den totala åktiden 3,75 timmar, dvs 15 minuter längre än om inte en extra väg hade öppnats! En extra väg, som intiutivt borde innebär mer utrymme och kortare tid, ger istället motsatt resultat. Detta kallas för ett Nash-jämviktsläge som uppstår om alla individer försöker optimera för sig själva.
Exempel: Antag att det finns två aktörer som väljer mellan två alternativ; att ta den kortaste vägen för sig själva eller att tillsammans optimera med avseende på båda aktörerna samtidigt. I ruta (1) optimerar individerna med avseende på kollektivet, i ruta (4) med avseende på sig själva. I ruta (2) och (3) optimerar någon individ med avseende på sig själv och den andra med avseende på kollektivet. Eftersom utfallet i dessa rutor är sämre än när båda optimerar med avseende på sig själva så kommer ett jämviktsläge uppstå i (4).
i : ACD, ii : ABD => 3,5h för båda | i : ABCD, ii : ACD => 3.25h < i < 3.5h, ii > 3,5h |
ii : ABCD, i : ACD => 3.25h < ii < 3.5h, i > 3,5h | Jämviktsläge då både i och ii tar 3,75h |
Ett annat exempel på Nash-jämviktsläge är då två aktörer plockar svamp innan den är mogen (eftersom någon annan kan komma att ta den innan dess). Detta är ett exempel på ett så kallat prisoners dilemma, som uppstår när det går att dra fördel av att agera direkt jämfört med att vänta.