Repeated Selfish Routing with Incomplete Information - Yu, He (My University, 2013)
Selﬁsh routing is frequently discussed. The general framework of a system of non-cooperative users can be used to model many diﬀerent optimization problems such as network routing, traﬃc or transportation problems.
It is well known that the Wardrop user equilibria (i.e. the user optima) generally do not optimize the overall system cost in a traﬃc routing problem.
In order to induce the equilibrium ﬂow to be as close to the optimal ﬂow as possible, the term “toll” is introduced. With the addition of tolls, a traﬃc system does not show the actual cost to the users but the displayed cost of users, which is the summation of the actual cost and the toll. A common behavioral assumption in traﬃc network modeling is that every user chooses a path which is perceived as the shortest path, then the whole system achieves the equilibrium of the displayed cost. It is proved that there exists an optimal toll which can induce the equilibrium ﬂow under displayed cost to be the optimal ﬂow in reality.
However, this conclusion holds only if the selﬁsh routing executes only once. If the game is played repeatedly, the users will detect the diﬀerence between the actual and displayed costs. Then, they will not completely trust the information given by the system and calculate the cost. The purpose of this thesis is to ﬁnd out the optimal strategy given by the system–how to set tolls in order to maintain the ﬂow as close to the optimal ﬂow as possible.
Keywords: Selfish Routing; Repeated Game; Toll; Digital Communications and Networking; Other Computer Engineering; Digital Communications and Networking