Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?
Abstract
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 NP=Σ2p, 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.
Related
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems
- Stability of ideal Nash equilibrium points in generalized multi-criteria games, interval-valued games, and existence in single-leader--multi-follower problems
- A true single-level reformulation for pessimistic bilevel optimization
- A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
BibTeX
@misc{aussel2026singleleadermultifollower,
title = {{Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?}},
author = {Didier Aussel and David Salas and Martin Schmidt},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23458},
eprint = {2610.23458},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23458},
}
RIS
TY - UNPB
TI - Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?
AU - Didier Aussel
AU - David Salas
AU - Martin Schmidt
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23458
UR - https://arxiv.org/abs/2610.23458
AB - 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 NP=Σ_2^p, 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.
ER -