Risk-Averse Equilibria for Vehicle Navigation in Stochastic Congestion Games

Ali Yekkehkhany, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review

Abstract

The fast-growing market of autonomous vehicles, unmanned aerial vehicles, and fleets in general necessitates the design of smart and automatic navigation systems considering the stochastic latency along different paths in the traffic network. The longstanding shortest path problem in a deterministic network, whose counterpart in a congestion game setting is Wardrop equilibrium, has been studied extensively, but it is well known that finding the notion of an optimal path is challenging in a traffic network with stochastic arc delays. In this work, we propose three classes of risk-averse equilibria for an atomic stochastic congestion game in its general form where the arc delay distributions are load dependent and not necessarily independent of each other. The three classes are risk-averse equilibrium (RAE), mean-variance equilibrium (MVE), and conditional value at risk level α equilibrium (CVaRαE) whose notions of risk-averse best responses are based on maximizing the probability of taking the shortest path, minimizing a linear combination of mean and variance of path delay, and minimizing the expected delay at a specified risky quantile of the delay distributions, respectively. We prove that for any finite stochastic atomic congestion game, the risk-averse, mean-variance, and CVaRα equilibria exist. We show that for risk-averse travelers, the Braess paradox may not occur to the extent presented originally since players do not necessarily travel along the shortest path in expectation, but they take the uncertainty of travel time into consideration as well. We show through some examples that the price of anarchy can be improved when players are risk-averse and travel according to one of the three classes of risk-averse equilibria rather than the Wardrop equilibrium.

Original languageEnglish (US)
Pages (from-to)18719-18735
Number of pages17
JournalIEEE Transactions on Intelligent Transportation Systems
Volume23
Issue number10
DOIs
StatePublished - Oct 1 2022

Keywords

  • Stochastic congestion games
  • risk-averse equilibrium
  • risk-aversion
  • vehicle navigation

ASJC Scopus subject areas

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Risk-Averse Equilibria for Vehicle Navigation in Stochastic Congestion Games'. Together they form a unique fingerprint.

Cite this