Il Paradosso di Braess

Siete mai stati a Londra? Io, in quanto membro dell’NWO, ovviamente si (devo fare scalo per andare all’isola di Man). La cosa che colpisce più di Londra è la sua metropolitana, quando sono li ogni due per tre becco una fermata chiusa per sciopero. Sono sfigato io, ho sempre pensato, finché sono andato a cercarmi i dati e ho scoperto che dal 2000 al 2015 ci sono stati circa 50 scioperi.

C’è poco da ridere, gli scioperi sono una cosa pericolosa!

Nel febbraio del 2014 uno sciopero bloccò 171 stazioni della metro su 270, le autorità di Londra ne approfittarono per raccogliere dati tramite le Oyster Card (se siete stati a Londra probabilmente le odiavate ben prima di scoprire che fanno parte del complottone per controllarci tutti), trovandosi in mano i dati di circa 18.000 passeggeri che usano la metro tra le 7 e le 10 del mattino per andare a lavoro.

I tre quarti di questi passeggeri furono costretti a cambiare percorso a causa dello sciopero.

Quando lo sciopero finì e i dati vennero confrontati con quelli normali, venne fuori che il 5% di loro non era tornato al solito percorso. Stiamo parlando di quasi 700 persone!

Che fine hanno fatto? Sono rimaste sorprese dallo sciopero e sono state mangiate dai ghoul che infestano la metropolitana?

Per alcuni di loro sarà di sicuro stato così (fonte: fallout 3 e 4), ma molti altri sono stati vittima di un nemico ben più insidioso, ben più sconosciuto ma, soprattutto, ben più reale: la teoria dei giochi.

E in questa prima puntata de ma con questa roba ci vinco al Monopoli? Tutto quello che non volevo sapere sui giuochi parleremo del Paradosso di Braess e del perché il modo migliore per risolvere il traffico a Sim City non sia fare nuove strade, ma chiuderne.

 

 

Strade e Autostrade

Il paradosso di Braess dice questo:

For each point of a road network, let there be given the number of cars starting from it, and the destination of the cars. Under these conditions one wishes to estimate the distribution of traffic flow.

Whether one street is preferable to another depends not only on the quality of the road, but also on the density of the flow. If every driver takes the path that looks most favorable to him, the resultant running times need not be minimal.

Furthermore, it is indicated by an example that an extension of the road network may cause a redistribution of the traffic that results in longer individual running times.

 

Lo so bene perché spesso al mattino recito la sua versione ridotta (una serie di improperi) mentre vado a lavoro.

Il paradosso si basa sul presupposto che il flusso del traffico raggiunga un equilibrio di Nash che è lontano dall’ottimo che si potrebbe ottenere per quella rete stradale. In pratica ci dice che non siamo in un ottimo paretiano e noi odiamo non essere in un ottimo paretiano.

Prendiamo l’esempio più classico possibile (grazie Wiki): ci sono due punti: una partenza e un arrivo, un certo numero di persone deve guidare da un punto all’altro.

La gente ha a disposizione due strade, la prima viaggia dalla partenza a un punto A e poi da A all’arrivo. La seconda viaggia dalla partenza a un punto B e poi da B all’arrivo.

Ipotizziamo che i due percorsi siano simmetrici. Entrambi abbiano una parte che è influenzata dal numero degli automobilisti (ossia il tempo necessario a percorrerla dipende da quanto è congestionata) e una parte che invece è indipendente dal numero degli automobilisti.

Nel nostro esempio la parte congestionata ha un valore pari a t = auto/100, la parte non congestionabile invece ha un valore fisso di t = 45 minuti.

Sappiamo inoltre che ogni giorno il network autostradale è sfruttato da 4000 automobilisti.

Bene, forti dei nostri dati apriamo le strade e mettiamoci comodi a guardare cosa combinano gli automobilisti.

 

 

Equilibri

I nostri automobilisti non sono stupidi quindi inizialmente sceglieranno un percorso a caso.
Se tale percorso dovesse risultare troppo lungo il giorno dopo ne sceglieranno un altro facendo così decongestionare il primo.

Non sto a farvela troppo lunga ma alla fine gli automobilisti raggiungeranno un equilibrio facendo si che 2000 sceglieranno un percorso e 2000 l’altro.
Il tempo impiegato è identico: 2000/100 + 45 = 65 minuti.

 

 

Siamo in equilibrio, nessun automobilista è incentivato a cambiare percorso perché impiegherebbe più tempo, e il traffico fluisce allegro tra strombazzare di clacson e enunciazioni in forma ridotta del postulato di Braess.

Ipotizziamo ora di aprire una nuova strada per decongestionare il traffico.

Questa strada sarà fatta tra il punto A e il punto B, essa è una strada bellissima, ci si mette 0 minuti ad attraversarla ed è talmente larga da non subire congestioni (la immagino un po’ come saltare dal cavalcavia sulla strada sottostante).

Cosa faranno ora in nostri automobilisti. Beh, essendo che non sono scemi faranno i loro conti. Il gioco è passato da un sistema a 2 opzioni a uno a 4 opzioni.

Analizziamo la prima coppia: conviene fare Start – A o conviene fare Start – B?
Beh fare Start – A è ora una strategia dominante, alla peggio ci metterei 40 minuti (4000/100) contro i 45 di Start – B.

La gente si butta a mucchio sulla stradina congestionandola mentre l’autostrada rimane vuota come il mio portafoglio dopo i saldi Steam.

Arrivata a A la gente si interroga sulla seconda coppia di opzioni, è meglio fare A – End oppure fare A – B – End?

Beh la scelta A – B –End è di nuovo una strategia dominante, alla peggio ci metterei 40 minuti (0 + 4000/100) mentre nell’altro caso ce ne metterei 45. Cosi la gente salta a mucchio dal cavalcavia e va a congestionare la strada di sotto.

Risultato? Ora la gente ci mette 80 minuti ad andare a lavorare contro i 65 di prima, e la colpa è di aver migliorato il sistema stradale.

 

 

Conclusioni

A questo punto voi direte “ma amme che me ne frega amme? Io c’ho il diesel”. Assolutamente d’accordo.

O meglio “perché la gente non cambia strada?” il motivo è che non hanno incentivi a farlo.
Qualsiasi altra scelta è svantaggiosa rispetto a questa, questo è il significato di strategia dominante.

Le altre due scelte esistono ancora ma non c’è vantaggio a sceglierle e, come ci insegna la teoria di giochi, non siamo altro che un branco di avidi egoisti che se non vengono premiati non facciamo proprio nulla per cambiare le nostre abitudini.

Il problema quindi non è quanto sia buona la strada aggiunta (che in questo caso è l’ottimo assoluto) bensì che l’aggiunta di una strada ha trasformato il gioco in un gioco a mosse alterne dove esiste una strategia dominante, e l’equilibrio di Nash arriverà implacabile frutto delle nostre scelte.

Ma, alla fine, il paradosso di Braess funziona anche nella vita vera?

Ebbene si, perché la teoria dei giochi è basata sulla vita vera, la teoria dei giochi si appoggia a due pilastri, il primo è che la gente sia intelligente abbastanza da capire cosa è meglio per se stessi (assunzione forte se avete bazzicato i commenti del FQ) la seconda, molto più importante, è che la gente è avida e persegue il massimo risultato, anche se la somma dei “massimi risultati” singoli è inferiore al miglior risultato possibile che si potrebbe raggiungere.

Ma per raggiungere l’ottimo paretiano c’è bisogno di una forzatura esterna come ci ricorda il teorema di Sen.

 

 

Se noi prendessimo la situazione a 4 scelte e arbitrariamente chiudessimo la strada centrale il traffico diventerebbe più scorrevole. Wikipedia porta diversi esempi di dove il paradosso di Braess abbia funzionato per il traffico cittadino, e il paradosso di Braess spiega anche dove siano finiti i 700 londinesi, i quali, vistasi chiusa una strada, ne hanno trovata una più veloce e non sono tornati alle vecchie abitudini.

Ma la mia applicazione preferita rimane quella del basket: The price of anarchy in basketball (arxiv.org)

 

• Braess’s paradox (wikipedia.org)
• The silver line – How Tube strikes help Londoners (economist.com)