Algorithms for Risk Mitigation in Networks

on YouTube ↗58m

" summary

Uncertainty forces new algorithms: minimizing a mean+standard-deviation objective is nonadditive so optimal substructure fails, but projecting paths to the mean–variance plane reduces the search to extreme points and yields an exact enumeration algorithm with a worst-case n^{log n} extreme-point bound. Smoothed analysis and an MIT Kartel implementation report about 10 extreme points in Boston (Kartel), and a black-box reduction to deterministic shortest-path solvers gives practical (1+ε) approximations. Game-theoretically, the price of risk aversion can grow like 1+R·K (times a topology factor up to V/2).

AI-written summary · about

" chapters (27)

1. 0:00Intro
2. 0:27Motivation
3. 2:10Talk outline
4. 2:40What is risk?
5. 4:32Risk l: Expected Utility Theory
6. 5:57Risk Il: Mean-variance framework
7. 9:31Risk III: Coherent risk measures
8. 12:37Computational implications
9. 16:19Algorithmic challenges
10. 18:57Algorithmic insights
11. 31:57Risk-averse combinatorial framework
12. 34:17General utility functions
13. 35:26Traffic routing
14. 36:45Risk sensitivity of price of anarchy
15. 37:54Related work on routing games
16. 38:06Goal
17. 39:29Routing games with stochastic delays
18. 41:57Risk-averse vs Risk-neutral Wardrop Equilibrium
19. 42:59Equilibrium characterization for mean-stdev risk
20. 43:31Succinct Solution Representation
21. 44:35Effect of Risk vs Selfish Behavior?
22. 46:56Risk-averse vs Risk-neutral equilibria
23. 49:09Price of Risk Aversion for mean-var risk
24. 51:14Dynamic (adaptive) problems
25. 51:33Summary
26. 52:58Open/Future research directions
27. 57:28Heterogeneous risk-averse players