Stochastic selfish routing

摘要: We embark on an agenda to investigate how stochastic delays and risk aversion transform traditional models of routing games the corresponding equilibrium concepts. Moving from deterministic with risk-averse players introduces nonconvexities that make network game more difficult analyze even if one assumes variability is exogenous. (For example, computing players' best responses has unknown complexity [24].) This paper focuses existence characterization in different settings atomic vs. nonatomic exogenous endogenous factors causing edge delays. also show succinct representations equilibria always exist though non-additive, i.e., cost along a path not sum costs over edges as typically assumed selfish problems. Finally, we inefficiencies resulting nature prove under delays, price anarchy exactly same implies do further degrade system worst-case than selfishness players.