pipette
ESEspañol

Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?

Didier Aussel, David Salas, Martin Schmidt

Preprint

In the authors' words

For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case the answer is positive: We derive an equivalent bilevel problem by representing the followers' equilibria as fixed points of the solution mapping of a single optimization problem. For pessimistic problems, the situation is different. We show that every optimistic trilevel problem admits an equivalent pessimistic SLMF formulation with two followers. Conversely, for every pessimistic SLMF problem verifying a mild attainability assumption we establish an equivalent optimistic trilevel reformulation. The reformulations are easy, readily tractable, and they preserve convex and linear data. Thus, unless , we deduce as byproduct that multiple followers induce an unexpected complexity gap between optimistic and pessimistic approaches, which is not the case when considering one follower alone.

Main resultLimitation the authors admit

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.