No-Regret Learning in Stackelberg Games with an Application to Electric Ride-Hailing
Anna Maddux *, Marko Maljkovic *, Nikolas Geroliminis, Maryam Kamgarpour · 2025
Read No-Regret Learning in Stackelberg Games with an Application to Electric Ride-Hailing by Anna Maddux *, Marko Maljkovic *, Nikolas Geroliminis, Maryam Kamgarpour (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-2504-03745.txt.
Introduction
Anna Maddux and co-authors design a learning rule in 2025 for a leader who must steer followers without seeing their private goals. Such stacked games model taxi fleets well: a city sets charging prices, and firms then place cars and plugs by their own aims. Past methods needed followers to hand over private payoff data, which real firms will not do.
Their rule treats the follower game as a black box and only watches the leader's own cost after each round. Under smooth-shape assumptions, the rule's regret vanishes at a square-root pace and lands near the best stacked outcome, they prove. A numeric case on electric ride-hailing prices checks the idea. Privacy-safe steering could help cities shape fleets without owning them.
Catalog record
| CREATOR | Anna Maddux *, Marko Maljkovic *, Nikolas Geroliminis, Maryam Kamgarpour |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-03745
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
No-Regret Learning in Stackelberg Games with an Application to Electric Ride-Hailing Anna Maddux *, Marko Maljkovic *, Nikolas Geroliminis, Maryam Kamgarpour Abstract We consider the problem of efficiently learning to play single-leader multi-follower Stackelberg games when the leader lacks knowledge of the lower-level game. Such games arise in hierarchical decision-making problems involving self-interested agents. For example, in electric ride-hailing markets, a central authority aims to learn optimal charging prices to shape fleet distributions and charging patterns of ride-hailing companies. Existing works typically apply gradient-based methods to find the leader’s optimal strategy. Such methods are impractical as they require that the followers share private utility information with the leader. Instead, we treat the lower-level game as a black box, assuming only that the followers’ interactions approximate a Nash equilibrium while the leader observes the realized cost of the resulting approximation. Under kernel-based regularity assumptions on the leader’s cost function, we develop a no-regret algorithm that converges to an ϵ \epsilon -Stackelberg equilibrium in 𝒪 ( T ) \mathcal{O}(\sqrt{T}) rounds. Finally, we validate our approach through a numerical case study on optimal pricing in electric ride-hailing markets. I Introduction Many real-world systems, including traffic networks, communication systems, and smart grids, involve multiple self-interested agents that interact repeatedly. Such independent and self-interested decision-making may result in inefficient and socially undesirable outcomes due to misaligned objectives and a lack of coordination among the agents [ 1 ] . Therefore, from a global perspective, it is important to design intervention mechanisms such as tolls, pricing schemes, and subsidies that can steer agents towards a socially desirable and efficient behavior. A prominent example of inefficient decision-making arises in ride-hailing markets, where service providers may flock to regions of high demand in search of passengers, leaving other customer locations underserved [ 2 ] . Interestingly, the growing integration of electric vehicles (EVs) into ride-hailing fleets of companies such as Uber, Lyft, and Curb, introduces a lever for external intervention via electricity pricing [ 3 , 4 , 5 ] . A central authority, such as the government or power providers, may set spatially varying prices to shape fleet distribution and charging patterns to match demand and supply across regions. Introducing a central authority to design intervention mechanisms imposes a bi-level structure that naturally fits into the framework of a single-leader, multi-follower Stackelberg game [ 6 ] . In this setting, the incentive designer assumes the role of the leader, while the self-interested agents act as followers. In the context of ride-hailing, the government or the power provider would act as the leader, while the competing ride-hailing fleets would serve as the followers. At the upper level, the leader selects incentives to minimize a societal cost, anticipating the followers’ best responses. At the lower level, the followers are considered rational agents that play a non-cooperative game, the outcome of which forms a Nash equilibrium. This paper investigates whether the leader can efficiently learn to solve Stackelberg games solely from observations of the societal cost to tackle the incentive design problem described above. Existing approaches usually rely on first-order methods [ 7 , 8 , 9 , 10 , 11 ] or problem-specific solutions [ 12 ] . First-order methods typically estimate the gradient of the leader’s objective, i.e., the so-called hypergradient, but this estimation requires the leader to have access to estimates of both the lower-level Nash equilibrium and the gradient of the followers’ utility functions [ 7 ] . While these methods may be suitable for bilevel optimization problems [ 13 ] , they become impractical when the lower-level involves self-interested agents that are unwilling to share their private information. In particular, this is evident in electric ride-hailing markets, where agents behave strategically and are unlikely to disclose sensitive information, such as the gradient of their utility functions. As a result, the lower-level problem effectively becomes a black box to the leader, making traditional approaches difficult to apply. Several past works [ 14 , 15 , 16 ] allow the leader to probe the followers with different incentives and observe the realized societal cost. The work of [ 14 ] focuses on a single-leader, single-follower setup, where the leader observes the follower’s noisy best response. Assuming that the follower’s response function lies in a reproducing kernel Hilbert space (RKHS), they propose a no-regret algorithm that converges to an approximately optimal incentive in \mathcal{O}(\sqrt{T}) . In contrast, [ 15 ] considers a different approach to tackle multi-follower Stackelberg games based on zeroth-order estimation of the leader’s hypergradient. While their algorithm converges to an approximately stationary point in \mathcal{O}(\sqrt{T}) , to ensure that it is an approximate Stackelberg equilibrium, they require a hard-to-verify assumption on the Hessian of the leader’s cost function. Moreover, their method estimates the hypergradient by probing followers with an incentive and a perturbed version thereof, which may be impractical when a central authority cannot evaluate multiple incentives simultaneously. In this paper, we consider a class of multi-follower Stackelberg games for which our contributions are threefold: • We propose a novel no-regret algorithm for the leader to learn in Stackelberg games that leverages Gaussian process regression, assuming that the leader’s cost function satisfies the RKHS assumption. • We show that with high probability our algorithm converges in \mathcal{O}(\sqrt{T}) to an \epsilon -Stackelberg equilibrium. Our method requires no prior knowledge of the lower-level game and only assumes that the followers can approximate a Nash equilibrium within a number of rounds polynomial in T . • We demonstrate the applicability of our setup to electric ride-hailing markets and validate our algorithm through a numerical case study in this domain. Notation: Let \mathds{R} and \mathbb{Z}_{(+)} denote the sets of real and (non-negative) integer numbers. For any T\in\mathbb{Z}_{+} , we let [T]=\{1,2,...,T\} . Let \mathds{1} be the vector of all ones. If \mathcal{A} is a finite index, we let x=(x_{i})_{i\in\mathcal{A}} be the concatenation of vectors x_{i} . For a real-valued function f:\mathds{R}^{d}\rightarrow\mathds{R} , we let \nabla_{x}f=(\frac{\partial f}{\partial x_{i}})_{i=1}^{d} be its gradient. II Problem setup We consider a Stackelberg game with N+1 agents consisting of a leader L and a set of followers denoted by \mathcal{N} . In a Stackelberg game, the leader first chooses an action \pi\in\Pi from its action set \Pi\subseteq\mathds{R}^{p} . The followers then simultaneously respond to the leader’s action \pi by choosing an action x_{i}\in\mathcal{X}_{i}\subseteq\mathds{R}^{d} , where \mathcal{X}_{i} denotes the action set of follower i\in\mathcal{N} . Furthermore, the leader has a cost function given by J:\Pi\times\mathcal{X}\rightarrow\mathds{R} and each follower has a utility function given by U_{i}:\mathcal{X}\times\Pi\rightarrow\mathds{R} , where \mathcal{X}=\Pi_{i=1}^{N}\mathcal{X}_{i} denotes the action space of the joint action profile x\coloneqq(x_{i})_{i\in\mathcal{N}} . II-A Lower-level game Given the leader’s action \pi , at the lower level, the followers decision-making problem can be cast as a game \Gamma(\mathcal{N},\{\mathcal{X}_{i}\}_{i=1}^{N},\{U_{i}\}_{i=1}^{N};\pi) . Each agent aims to maximize its utility given the actions of the other agents and the action of the leader. A popular solution concept in such games is the Nash equilibrium at which no agent has an incentive to unilaterally deviate from its action. Definition 1 For a given \pi , the joint action profile x^{*}\in\mathcal{X} is an \epsilon -Nash equilibrium if U_{i}(x_{i},x_{-i}^{*};\pi)\leq U_{i}(x_{i}^{*},x_{-i}^{*};\pi)+\epsilon holds for all i\in\mathcal{N} , where x_{-i}\coloneqq(x_{j})_{j\in\mathcal{N}\setminus\{i\}} denotes the joint action of all agents except i .