Modeling the traffic flow in a congestion game using Evolutionary Game Theory

This thesis analyses a traffic model evolutionary game, where cars and trucks must choose between two different routes in order to travel from a point A to a point B. The model is built on the replicator equation, which is an essential concept of the Evolutionary Game Theory (EGT). EGT has grown into a field that combines the principles of game theory and dynamical systems to interpret the interactions between the agents. In chapter two, a small introduction in game theory is provided, presenting some basic, but fundamental, notions such as the one of strategy and Nash equilibrium. In the third chapter, the key definitions of Evolutionary Stable Strategy (ESS) and replicator dynamics are introduced. A point is an ESS if it is a better strategy than a mutant strategy, and it fares better against the mutation than the mutation does against itself. The main result is that in a symmetric game an evolutionary stable strategy is always a symmetric Nash equilibrium, but the converse is not true. The replicator equation is an Ordinary Differential Equation (ODE), which models the change in the composition of the population over time. Some properties regarding the replicator equation are presented, without entering in the details of the theory. The core of this thesis, the traffic model, is introduced in chapter four. Two populations of vehicles, cars and trucks, must choose between two different routes in order to travel from a common starting point to a common destination. At first the general traffic model is introduced, then the population dynamics are studied in a specific real case scenario, the journey from Rovato to Politecnico di Milano. The equilibrium points of the system and their stability are studied not only considering the actual tolls of the two highways connecting Rovato and Milano (A4 and A35), but also by altering the price of the tolls. In the fifth chapter the time of travel is analysed. The time spent on a path is directly proportional to the length of the route and the number of vehicles that drives over the same route. The objective is to find an optimal distribution of the time of travel over the two different highways.

Questa tesi analizza un modello di traffico in chiave evolutiva, in cui auto e camion devono scegliere un percorso fra due possibili, con l'obiettivo di arrivare ad un punto B partendo da un punto A. Il modello è costruito sulle equazioni della replicazione, che sono un concetto chiave nella Teoria Evolutiva dei Giochi (EGT). EGT è una materia che combina i principi della teoria dei giochi e dei sistemi dinamici al fine di analizzare le interazioni tra i giocatori. Nel capitolo due viene proposta una breve introduzione riguardo la teoria dei giochi e vengono presentati alcuni concetti fondamentali, come quello di strategia o di equilibrio di Nash. Nel terzo capitolo vengono definite le nozioni di Strategia Evolutivamente Stabile (ESS) e di equazione della replicazione. Una strategia è una ESS se non può essere invasa da una strategia 'mutante'. Uno dei teoremi più importanti è il seguente: in un gioco simmetrico una ESS è sempre un equilibrio di Nash simmetrico, mentre il viceversa non è garantito. L'equazione della replicazione è un ODE che modella il cambiamento nel tempo nella composizione della popolazione. Saranno presentate alcune proprietà riguardanti la dinamica delle popolazioni, ma senza entrare nei dettagli della teoria. Il focus principale di questa tesi, il modello di traffico, viene introdotto nel capitolo quattro. Due popolazioni di veicoli, auto e camion, devono viaggiare dallo stesso punto di partenza verso la stessa destinazione, scegliendo tra due percorsi possibili. Dopo aver presentato il modello generale, questo viene applicato in uno scenario reale: il viaggio da Rovato al Politecnico di Milano. La dinamica del sistema verrà analizzata sia usando valori reali per il pedaggio delle autostrade (A4 e A35), sia considerando i pedaggi come dei parametri del sistema. Nel quinto capitolo viene analizzato il tempo di percorrenza sulle due autostrade del modello di traffico. Il tempo di percorrenza è proporzionale sia alla lunghezza del percorso, sia al numero di veicoli presenti sulla tratta. L'obiettivo è quello di trovare per quale valore dei pedaggi si ottiene una distribuzione ottimale del tempo di percorrenza.