טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentWong Wafung
SubjectNash Equilibria and Efficiency in Routing Games
DepartmentDepartment of Applied Mathematics
Supervisor Professor Rann Smorodinsky


Abstract

We study a model of traffic routing in a network, where N players need to move a certain amount of traffic between given source and target nodes, while minimizing latency. Our model consists of a finite set of non-negligible players and we consider two variants. In the first variant each player must choose one route for all of his traffic (the non-splitable case) while in the other player may split their traffic among several routes. We define the efficiency of a flow as the maximal latency incurred by the players and the efficiency of the network the efficiency of the best Nash equilibrium. A network complies with the well know Braess paradox if the deletion of arcs increases efficiency. We study the connection between the network topology, efficiency and compliance with Breass paradox.