Near-optimal Robust Bilevel Optimization
Bilevel optimization studies problems where the optimal response to a second mathematical
optimization problem is integrated in the constraints. Such structure arises in a variety of decision-making
problems in areas such as market equilibria, policy design, product pricing or network protection. We
introduce the concept of near-optimal robustness for bilevel problems, protecting the upper-level decision-
maker from limited deviations of the lower level, related to a bounded rationality assumption. We show it
is a restriction of the corresponding so-called pessimistic bilevel problem. Essential properties are derived
in generic and specific problem settings. This model finds an intuitive interpretation in various situations
cast as bilevel optimization problems. We develop a duality-based solution method for cases where the lower
level is convex, leveraging the methodology from robust and bilevel literature. In the case of linear-linear
bilevel problems, an extended formulation can be derived, replacing the non-convex quadratic terms with
disjunctions over linear constraints. The models obtained are tested numerically using different solvers and
formulations, showing the successful implementation of the near-optimal robust bilevel problem.