Abstract
Many combinatorial and network problems that motivate the study of algorithms and algorithmic game theory (AGT) are traditionally modeled as deterministic. In practice, noise and uncertainty can preclude the use of traditional analysis for such problems, when one seeks reliable or risk-averse solutions. Risk has been at the forefront of research and practice in finance and economics. However, there is still a need for computational approaches, as well as new risk models specific to networked systems.
In this talk, I will give a brief overview of different approaches to risk and examples of how core algorithmic and AGT problems such as routing and congestion games are transformed in the presence of uncertainty and risk-averse users. I will conclude with a mix of concrete and high-level research directions that aim at developing a systematic understanding of risk in networks and their motivation/ applications to real world problems from transportation, telecommunications and energy.