ACT - Evdokia Nikolova/Texas A&M, "A Mean-Risk Model for the Stochastic Traffic Assignment Problem," ACES 2.402

Contact Name: 
Greg Plaxton
ACES 2.402
Nov 9, 2012 2:00pm - 3:00pm

Signup Schedule:

Type of Talk: Algorithms and Computation Theory (ACT)

Speaker/Affiliation: Evdokia Nikolova/Texas A&M

Talk Audience: UTCS Faculty, Grads, Outside Interested Parties

Date/Time: 11/09/2012, 2:00 PM to 3:00 PM

Location: ACES 2.402

Host:  Greg Plaxton

Talk Title: "A Mean-Risk Model for the Stochastic Traffic Assignment Problem"

Talk Abstract: We embark on an agenda to investigate how stochastic travel times and risk aversion transform the traditional traffic assignment problem and its corresponding equilibrium concepts. Moving from deterministic to stochastic travel times with risk-averse users introduces non-convexities that make the problem more difficult to analyze. For example, even computing a best response of a user to the environment is still of unknown complexity. This paper focuses on equilibrium existence and characterization in the different settings of infinitesimal (non-atomic) vs. atomic users and fixed (exogenous) vs. congestion dependent (endogenous) variability of travel times. We show that equilibria always exist in three out of the four possible combinations.  The exception is the case of atomic users and endogenous variability.  Because cost functions are non-additive (i.e., the cost along a path is not a sum of costs over edges of the path as it is assumed in the vast majority of network routing problems), solutions need to be represented as path flows since not all decompositions from edge to path-flows are equivalent. Nevertheless, we show that succinct representations of equilibria and optimal solutions always exist. Finally, we investigate the inefficiencies resulting from the stochastic nature of travel times. We obtain that under exogenous variability of travel times, the worst-case inefficiency of equilibria is exactly the same as when travel time functions are deterministic, meaning that in this case risk-aversion under stochastic travel times does not further degrade a system in the worst-case in relation to users‚ self-mindedness.

Joint work with Nicolas E. Stier-Moses.  Paper available here: