On the characterization and computation of Nash equilibria on parallel networks with horizontal queues

TitleOn the characterization and computation of Nash equilibria on parallel networks with horizontal queues
Publication TypeConference Paper
Year of Publication2012
AuthorsKrichene, W.., J.. Reilly, S.. Amin, and A.. Bayen
Conference Name2012 IEEE 51st IEEE Conference on Decision and Control (CDC)
Date PublishedDec
KeywordsComputational modeling, congestion mitigation strategies, game theory, Games, horizontal queues, latency function, Manganese, minimisation, Nash equilibrium, Nash equilibrium computation, network theory (graphs), parallel algorithms, parallel-link networks, queueing theory, Roads, Routing, routing games, selfish behavior, social optima, stability, static analysis, total cost minimization, transportation networks, two-link networks, Vectors
Abstract

We study inefficiencies in parallel networks with horizontal queues due to the selfish behavior of players, by comparing social optima to Nash equilibria. The article expands studies on routing games which traditionally model congestion with latency functions that increase with the flow on a particular link. This type of latency function cannot capture congestion effects on horizontal queues. Latencies on horizontal queues increase as a function of density, and flow can decrease with increasing latencies. This class of latency functions arises in transportation networks. For static analysis of horizontal queues on parallel-link networks, we show that there may exist multiple Nash equilibria with different total costs, which contrasts with results for increasing latency functions. We present a novel algorithm, quadratic in the number of links, for computing the Nash equilibrium that minimizes total cost (best Nash equilibrium). The relative inefficiencies of best Nash equilibria are evaluated through analysis of the price of stability, and analytical results are presented for two-link networks. Price of stability is shown to be sensitive to changes in demand when links are near capacity, and congestion mitigation strategies are discussed, motivated by our results.

DOI10.1109/CDC.2012.6426543