Probabilistic analyses in bi-level optimisation under uncertainty by Jakub Mareček

Many textbook examples of bilevel optimisation consider some decisions of transportation authorities at the upper level and route choices of individual drivers at the lower level. Clearly, there is a considerable amount of uncertainty involved, especially in modelling the behaviour of the drivers. One could consider a scenario expansion of bi-level optimisation under multi-stage uncertainty or use stochastic calculus on time scales to address the uncertainty. Neither option seems particularly promising computationally, though. Instead, we perform probabilistic analyses of a variety of newly-proposed policies for bi-level optimisation under uncertainty. Often, it is possible to show that the system is stable, under realistic assumptions. Both in principle and in simulations on transport engineering benchmarks, stable policies perform better than policies without such stability guarantees. Perhaps more importantly, the proposed policies use readily available data and are efficiently computable.

The first part of the tutorial covers applications in information provision and toll-setting, explains the results obtained there (e.g., distribution of drivers over the roads converges in distribution, under some assumptions), and the proof techniques involved. In the second part, this is generalised and suggestions are provided as to further applications.