Finding a Multiple Follower Stackelberg Equilibrium: A Fully First-Order Method

April Niu, Kai Wang, Juba Ziani · 2025

Read Finding a Multiple Follower Stackelberg Equilibrium: A Fully First-Order Method by April Niu, Kai Wang, Juba Ziani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-08161.txt.

Introduction

April Niu and 2 co-authors compute game equilibria with gradients alone in a 2025 paper. The games have a leader and many followers. Followers first settle their own best replies to the leader. The leader's best move depends on that reply. Past methods need second-order data, which is costly or missing.

The new method uses only first-order steps. The whole game is recast as one constrained problem. A Lagrangian then tracks how the leader's goal shifts as the followers settle. The steps swap between the two sides and settle near a valid equilibrium, with proof. Markets, security games, and platform rules all have this shape. Cheap equilibrium maths serves them all.

Catalog record

CREATORApril Niu, Kai Wang, Juba Ziani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-08161

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Finding a Multiple Follower Stackelberg Equilibrium: A Fully First-Order Method April Niu, Kai Wang, Juba Ziani Abstract This paper studies Stackelberg games with multiple followers and continuous strategy spaces, where a single leader first commits to a strategy, then k k followers ( k > 1 k>1 ) play a simultaneous game in response to the leader’s decision. We study the complexity of finding ϵ \epsilon -stationary Stackelberg equilibria , where neither the leader nor the followers want to deviate from the current strategies with gradient norm greater than ϵ \epsilon . In this work, we propose the first fully first - order method to compute a ϵ \epsilon -stationary Stackelberg equilibrium with convergence guarantees. To achieve this, we first reframe the leader–follower interaction as single - level constrained optimization. Second, we define the Lagrangian and show that it can approximate the leader’s gradient in response to the equilibrium reached by followers with only first-order gradient evaluations. These findings suggest a fully first-order algorithm that alternates between (i) approximating followers’ best responses through gradient descent and (ii) updating the leader’s strategy via approximating the gradient using Lagrangian. Under standard smoothness and strong monotonicity assumptions on the followers’ sub-game, we prove that the algorithm converges to an ϵ \epsilon - stationary Stackelberg equilibrium in O ⁡ ( k 2 ​ ϵ − 6 − α ) O(k^{2}\epsilon^{-6-\alpha}) gradient evaluations, where α > 0 \alpha>0 is arbitrarily small. Our method dispenses with any Hessian or matrix-inverse computations, is scalable to high - dimensional settings, and provides the first fully first - order convergence guarantees for multi - follower Stackelberg games. 1 Introduction Stackelberg games model hierarchical interactions where a leader first commits to a decision, anticipating how one or more followers will respond optimally. This structure captures a wide range of real-world systems, including pricing in markets, security resource allocation, and multi-agent learning in strategic settings ( An et al. 2017 ; Gerstgrasser and Parkes 2023 ; Li and Sethi 2017 ) . In Stackelberg games, one agent influences the outcome by acting first, in contrast to simultaneous games where every player chooses their strategy simultaneously. The game’s equilibrium, known as a Stackelberg equilibrium Bazin et al. 2020 , formalizes this anticipatory behavior and has become a fundamental concept in game theory and optimization. In recent years, there has been a surge of interest in computational methods for Stackelberg games, especially in continuous action spaces ( Fiez et al. 2019 ; Mertikopoulos and Zhou 2019 ) , due to their relevance in learning, control, and multi-agent reinforcement learning ( Groot et al. 2017 ; Zhang et al. 2021 ) . A common formulation of the Stackelberg equilibrium problem is through bilevel optimization Bazin et al. 2020 : the leader’s objective depends on the followers’ equilibrium outcome of a lower-level game played among the followers. This nested structure poses significant computational challenges: the leader must optimize over a followers’ equilibrium set that is often not available in closed form and may be sensitive to perturbations. To address this, recent works have proposed alternative formulations such as penalized or regularized versions (e.g., ( Ji et al. 2021 ; Kwon et al. 2023 ) ) that render the problem more tractable by transforming it into a single-level problem. Our work builds on this line of research by introducing a novel Lagrangian-based reformulation for multiple followers, enabling fully first-order optimization without requiring exact best-response computations from the followers. Despite recent advances, existing approaches for computing Stackelberg equilibria often suffer from key limitations that hinder scalability. Many ( Amos and Kolter 2017 ; Agrawal et al. 2019 ; Wang et al. 2022 ) rely on implicit differentiation through the followers’ equilibrium map, which requires computing or inverting large Hessian matrices—a process that is computationally expensive and memory-intensive, especially in high dimensions. Other ( Bai et al. 2021 ) assume access to the exact best responses from the followers, which may not be realistic in practice when the lower-level game is non-trivial to solve. These limitations have made prior methods either infeasible for large-scale problems in the multi-follower setting. Our approach circumvents both issues by leveraging a Lagrangian-based reformulation and using only first-order gradient methods throughout, enabling efficient and scalable computation even in complex multi-follower settings. 1.1 Our Contributions This work addresses the problem of computing Stackelberg equilibria in multi-follower games by leveraging a bilevel optimization framework. Our contributions are as follows: • First, we reformulate the Stackelberg game with multiple followers as a bilevel program and then reduce it to a single-level constrained optimization problem via a Lagrangian penalty formulation. This avoids differentiating through the equilibrium map while retaining the hierarchical structure. • Second, we propose a fully first-order algorithm that alternates between approximating the followers’ equilibrium and updating the leader’s strategy. Importantly, the method relies only on first-order gradients and avoids second-order computations, making it scalable. To the best of our knowledge, we are the first to apply this framework to the multi-follower case. • Third, we establish convergence guarantees under smoothness and monotonicity assumptions. Our algorithm converges to an \epsilon -stationary point of the Stackelberg equilibrium at a rate of O(k^{2}\epsilon^{-6-\alpha}) with precise bounds on both the outer and inner iterations. 1.2 Related Work We summarize the related work in: (i) Stackelberg games with single and multiple followers, (ii) bilevel optimization methods, and (iii) first-order algorithms for smooth and monotone games. Smooth Monotone Games The smoothness and monotonicity of followers’ games ensure existence, uniqueness, and stability of Nash equilibria, enabling analysis via variational inequalities. Lin et al. 2020 establish the first finite-time guarantees for last-iterate convergence, showing that no-regret dynamics converge (rather than just average) to Nash equilibria in monotone games; Golowich et al. 2020 sharpen the result and provide a tight O(1/\sqrt{T}) last-iterate rates. Recent work has advanced learning dynamics in this setting: Gao and Pavel 2022 establish exponential convergence for continuous-time dynamics; and Tatarenko and Kamgarpour 2019 design distributed algorithms that converge under general monotonicity without cost-function knowledge. The most recent result that we are aware is from Cai and Zheng 2023 , where they propose an optimistic accelerated gradient method that achieves O(1/T) last-iterate convergence. We use the result from Cai and Zheng 2023 as a black-box for smooth monotone games. Stackelberg Games Stackelberg games capture hierarchical leader–follower interactions, with single-follower cases well studied in zero-sum settings Goktas et al. 2022 ; Goktas et al. 2023 . Gradient-based methods ( Fiez et al. 2020 ; Jain et al. 2011 ) use implicit optimality conditions, but complexity grows in multi-follower games requiring Nash equilibria at the lower level. Li et al. 2022 extend to structured hierarchical games with multiple followers, solving approximate equilibria via back-propagation, while Wang et al. 2022 similarly apply gradient descent with KKT-based differentiation. Both approaches rely on second-order information, whereas other works ( Başar and Srikant 2002 ; Xu et al. 2018 ) study discrete strategy spaces. Bilevel Optimization Bilevel optimization refers to problems where one optimization task (the upper level) is constrained by the solution set of another optimization task (the lower level), making it a natural lens for modeling Stackelberg-type interactions ( ) . The bilevel perspective has become central in understanding and solving Stackelberg-type problems. Zhang

Read the complete text