Invited Talks

Motivated by transportation systems control problems, this talk discusses multi-scale dynamical network flow models whereby the dynamics of traffic flows are intertwined with those of the drivers’ route choices. The latter are influenced by the current congestion through the network as well as decentralized congestion-dependent tolls set by the system planner. Our main result proves that a class of decentralized monotone congestion-dependent tolls allow for globally stabilising the transportation network around a generalized Wardrop equilibrium. In particular, our results imply that using decentralized marginal cost tolls, stability of the dynamic transportation network is guaranteed to be around the social optimum traffic assignment. This is particularly remarkable as such feedback tolls can be computed in a fully local way without the need for any global information about the network structure, its state, or the exogenous network loads.

Finally, the impact of heterogeneities in the drivers’ behaviours is addressed by considering a model where different classes of users perceive different congestion costs (which may correspond to different available information). In this case, the game is no longer potential. Results on existence and uniqueness of user equilibria and convergence of (noisy) best response dynamics are presented for certain classes of network topologies.

In this presentation, we present and analyze distributed best re- sponse dynamics to compute Nash equilibria in potential games. This algorithm uses local Poisson clocks for each player, and does not rely on the usual but un- realistic assumption that players take no time to compute their best response. If this time (d) is taken into account, distributed best response dynamics may suffer from overlaps: one player starts to play while another player has not changed its strategy yet. Overlaps may lead to drops of the potential but we can show that they do not jeopardize eventual convergence to a Nash equilibrium. We show that the average execution time of the algorithm can be bounded from above by C d n log n (1 + o(1)) and from below by C’ n log n (1 + o(1)), where C and C’ are constants, n is the number of players and d is the time taken by one player to compute its best response. These bounds are obtained by using an asymptotically optimal playing rate. Our analytic bounds show that this rate is high (order of log log n). This induces a large probability of overlap (p = 1 log log n/ log n). In practice, numerical simulations also show that using high playing rates is efficient, with an optimal probability of overlap equal to 0.78 for any number of players smaller than 250. This implies that best response dynamics are unexpectedly efficient to compute Nash equilibria, even in a distributed setting.

The problem of finding optimal routes in networks that adapt to the state of the network has been addressed in several contexts including transportation networks, roads, communication networks (wired and wireless) as well as electric networks. The most celebrated results in this area pertain to algorithmic graph theory with the celebrated max-flow, min-cut theorem of Fulkerson and to algorithmic game theory with the work of Tardos and Roughgarden. A noteworthy class of routing algorithms bases its routing decisions on dynamic properties of the network, including real time link load and end-to-end latency. This class of strategies is known as adaptive routing. Such solutions are attractive because they typically enable more efficient usage of network resources. In contrast, traditional load-oblivious routing algorithm may blindly over-utilize some links, leading to congestion, while other links have unused capacity. In this work, we present a novel algorithm for adaptive routing in sta- tionary packet-switched networks, mapping source-destination flows to paths. We find that it provides a viable and stable solution to adapt to traffic condi- tions. Our algorithm is based on game theory and is endowed with the following desirable properties that make it a good candidate for efficient implementation in real-world networks:

– It is fully distributed: only local information is needed, and it requires no explicit coordination between routers;
– It is oblivious to the network topology: it will work in all networks provided that paths are available for all flows (source- destination);

– It is based on a bandit information model: The delay over each link is only available under a black box function: only the delay over the utilized links can be estimated, up to some un-biased noise.
– It scales with the number of flows and with the size of the network (conver- gence to optimal solutions takes a polynomial time in the size of the network and in the number of flows).