Eitan Altman
Institut national de recherche en informatique et en automatique (INRIA, Sophia Antipolis)
Analysis of routing in a competitive context is already 100 years old. It has become central in road traffic engineering and only in the last 25 years it started to penetrate into computer networks. Key differences between road traffic and road traffic models are 1. in road traffic a player (driver) is not expected to be lost where as in computer networks there are losses due to queueing overflow, to collision in the access to the network, to interference and to noise. 2. in road traffic, the decisions of a single player (a driver) have a negligible impact on the performance of other players which implies modeling the drivers as continuum flows. In computer networks the action taken by a decision maker may have a non-negligible impact on other players. In some cases this creates further difficulties in handling a discrete action space rather than a compact convex one. We shall present some examples that illustrate these two modelling issues in routing games and present novel tools from discrete convex analysis to study the properties of equilibria in such games.