Stackelberg Routing on Parallel Networks With Horizontal Queues

TitleStackelberg Routing on Parallel Networks With Horizontal Queues
Publication TypeJournal Articles
Year of Publication2014
AuthorsKrichene, W., J. Reilly, S. Amin, and A. Bayen
JournalIEEE Transactions on Automatic Control
Date PublishedMarch
Keywordscentral authority, compliant drivers, compliant flow, computational complexity, congestion games literature, congestion relief, game theory, Games, horizontal queues, Indexes, latency functions, multiple Nash equilibria, Nash equilibrium, NCF strategy, network analysis and control, noncompliant first strategy, parallel networks, physical queues, polynomial-time algorithm, Polynomials, queueing theory, Routing, Stackelberg game, Stackelberg routing games, traffic management agency, transportation networks, vehicle routing, Vehicles

This paper presents a game theoretic framework for studying Stackelberg routing games on parallel networks with horizontal queues, such as transportation networks. First, we introduce a new class of latency functions that models congestion due to the formation of physical queues. For this new class, some results from the classical congestion games literature (in which latency is assumed to be a non-decreasing function of the flow) do not hold. In particular, we find that there may exist multiple Nash equilibria that have different total costs. We provide a simple polynomial-time algorithm for computing the best Nash equilibrium, i.e., the one which achieves minimal total cost. Then we study the Stackelberg routing game: assuming a central authority has control over a fraction of the flow on the network (compliant flow), and that the remaining flow (non-compliant) responds selfishly, what is the best way to route the compliant flow in order to minimize the total cost? We propose a simple Stackelberg strategy, the Non-Compliant First (NCF) strategy, that can be computed in polynomial time. We show that it is optimal for this new class of latency on parallel networks. This work is applied to modeling and simulating congestion relief on transportation networks, in which a coordinator (traffic management agency) can choose to route a fraction of compliant drivers, while the rest of the drivers choose their routes selfishly.