Game Theoretical Study on Selfish Routing with User Preferences

Abstract

<p>We study selfish routing with user-specific preferences. The selfish routing model captures the selfish behaviour of users in a transportation system. Each user tries to minimize her own travel latency by choosing the shortest route, i.e. the route with the smallest latency, without taking other users' welfare into consideration. In this model, users are assumed infinitesimal, in the sense that the impact of the behaviour of any single user to the network is negligible. Under certain constraints, a steady state is known to exist, where no user has the incentive to deviate from her current route. This state is referred to as a traffic equilibrium.</p> <p>We extend the traditional selfish routing model by incorporating user preferences. In traditional selfish routing, one assumes that users make their routing decisions merely based on path latencies, and furthermore all users perceive the same latency on any single edge. We observe that in reality users may have their personal preferences on the routes to travel on, e.g., some may be accustomed to certain routes and feel unwilling to try out new ones; some may enjoy the wonderful views available on some routes more than their care for the slightly longer travel time; some may be limited to certain rules because they prefer public transportations, and so on. This observation motivates our work. We introduce to the model a set of edgewise userspecific preferences which come as inherent properties of each user. The disutility of using each edge, which is the basis of a user's routing decision, is now a function of latency and user preference.</p> <p>In this work several equilibria related aspects of the extended model are studied. Since we are working with infinitesimal users, the distinct combinations of edge preferences among all users might be either finite or infinite. There is qualitative difference between these two cases in terms of analysis, and both cases are discussed. We show existence and uniqueness of equilibria, give an upper bound on the price of anarchy, and study how taxation can help in this setting.</p>