Analyzing the Braess paradox: non-cooperative, cooperative and evolutionary perspectives

This thesis investigates the Braess paradox and its implications in network routing games by integrating non-cooperative, cooperative, and evolutionary game-theoretic frameworks. The paradox, which reveals that adding a new route to a network may paradoxically worsen overall performance due to selfish optimization, serves as the central motivation of the study. The analysis covers both the classical Braess network and a more complex topology in which the paradox-inducing arc is replaced by an embedded Braess subsystem with adjusted cost parameters. In both cases, explicit analytical and dynamical modeling demonstrate how the paradox arises within specific demand intervals. At low demand, the newly added routes improve travel times; as demand increases, overuse of these links leads to longer travel times—characteristic of the paradox—until flows eventually redistribute onto the original paths at high demand. Evolutionary analysis confirms that only asymptotically stable equilibria persist in the long run, corresponding to Nash equilibria of the underlying game, while cooperative optimization ensures non-negative marginal contributions for all network arcs and minimization of total travel time. Overall, the results clarify the mechanisms driving the Braess paradox in both simple and complex networks, highlighting how individual rationality can conflict with collective efficiency and how cooperation is a way to improve global performances of the system.

La presente tesi esamina il paradosso di Braess e le sue implicazioni nei giochi di instradamento su reti, integrando approcci di teoria dei giochi non cooperativa, cooperativa ed evolutiva. Il paradosso evidenzia come l’aggiunta di una nuova strada a una rete possa paradossalmente peggiorarne le prestazioni complessive a causa del comportamento egoistico degli utenti. L’analisi prende in considerazione sia la classica rete di Braess sia una topologia più complessa, in cui l’arco coinvolto nel paradosso è sostituito da un sottosistema di Braess con opportuni parametri. In entrambi i casi, lo studio mostra come il paradosso emerga in specifici intervalli della domanda: per bassi livelli di traffico, le nuove strade migliorano i tempi di percorrenza, mentre all’aumentare della domanda il loro eccessivo utilizzo porta a un peggioramento delle prestazioni complessive; per valori elevati della domanda, il flusso si ridistribuisce sui percorsi originari. L’analisi evolutiva conferma che, nel lungo periodo, persistono solo gli equilibri asintoticamente stabili, corrispondenti agli equilibri di Nash del gioco di riferimento, mentre l’approccio cooperativo garantisce contributi marginali non negativi per tutti gli archi della rete e la minimizzazione del tempo di percorrenza complessivo. Nel complesso, i risultati chiariscono i meccanismi alla base del paradosso di Braess nelle reti semplici e complesse, mettendo in luce come il principio di razionalità individuale possa entrare in conflitto con l’efficienza collettiva e come la cooperazione rappresenti una via per il miglioramento delle prestazioni globali del sistema.