On the Complexity of Robust Bilevel Optimization With Uncertain Follower's Objective

We investigate the complexity of bilevel combinatorial optimization with uncertainty in the follower's objective, in a robust optimization approach. In contrast to single-level optimization, we show that the introduction of interval uncertainty renders the bilevel problem significantly harder both in the optimistic and the pessimistic setting. More precisely, the robust counterpart of the uncertain bilevel problem can be $\Sigma^{\text P}_2$-hard in this case, even when the certain bilevel problem is NP-equivalent and the follower's problem is tractable. On the contrary, in the discrete uncertainty case, the robust bilevel problem is at most one level harder than the follower's problem. Moreover, we show that replacing an uncertainty set by its convex hull may increase the complexity of the robust counterpart in our setting, which again differs from the single-level case.