# Learning in Stackelberg Conjectural Games

Francesco Morri, Hélène Le Cadre, Luce Brotcorne

► To cite this version:

Francesco Morri, Hélène Le Cadre, Luce Brotcorne. Learning in Stackelberg Conjectural Games. ROADEF 2025, Feb 2025, Champs-sur-Marne, France. hal-04969032

HAL Id: hal-04969032

https://inria.hal.science/hal-04969032v1

Submitted on 27 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Learning in Stackelberg Conjectural Games

Francesco Morri¹, Hélène Le Cadre¹, Luce Brotcorne¹

Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

Contact author: francesco.morri@inria.fr

**Keywords** : game theory, Stackelberg game, multi-agent learning.

# 1 Introduction

Game theory has been classically used to model and understand the outcomes of situations of conflict involving strategic agents in competition [1], in particular involving multi-agent decision making. Here we present a novel approach to combine conjectural and Stackelberg games, while introducing a procedure to learn equilibria in this class of games. Conjectural variations games are characterized by conjecture functions, which introduce the idea that each player explicitly tries to model its adversaries' reactions to its own action (see [3] for an exhaustive introduction). Stackelberg games are two-stage non-cooperative games, involving leaders at the upper level which compute their strategies based on their anticipation of the reactions of the follower, and a follower which reacts rationally to the leaders' strategies. The hierarchy introduced in Stackelberg games implicitly forces the leaders to form conjectures-like approximations of the follower's behavior. Thus, it makes sense to endogenize these conjectures and employ the theoretical results from conjectural variations games to learn Stackelberg Equilibria.

# 2 Conjectural Stackelberg Games Definition and Characterization

Consider a set $\mathcal{N}$ of leaders, each with decision variables $x_i \in \mathcal{X}_i$ and objective function $f_i(x_i, x_{-i}, y)$, where $x_{-i}$ are the decision variables of all leaders but $i$ and $y \in \mathcal{Y}$ is the decision variable of the follower; its objective function is $g(x, y)$. We introduce the conjecture functions $\gamma_i^j : \mathcal{X}_i \to \mathcal{X}_j$: this represents the conjecture that player $i$ forms about player $j$. These functions are then used to replace the actual decision variables for the leaders' problem in the conjectural Stackelberg game:

$$ \forall i \in \mathcal{N}, \min_{x_i \in \mathcal{X}_i} f_i(x_i, (\gamma_i^j(x_i))_{j \neq i}, \gamma_i^y(x_i)), \quad (1a) $$

$$ \min_{y \in \mathcal{Y}} g(x, y). \quad (1b) $$

We then define the equilibrium associated to the game in Eq. (1):

**Definition 1 (Conjectural Stackelberg Equilibrium)** Given a set of conjectures $\{(\gamma_i^j(x_i))_{j \neq i}, \gamma_i^y(x_i), \forall i \in \mathcal{N}\}$, a set of decision variables $(x^*, y^*)$, is a Conjectural Stackelberg Equilibrium (CSE) if it is a solution of Eqs. (1).

We then compare this equilibrium with the standard Stackelberg one. We obtain two important results:

**Proposition 1 (Objective Function Bound)** The difference between the objective function of a leader evaluated in a CSE and an SE is bounded by the distance ($L^2$-norm) between the strategy of the leaders in the two equilibria.
The second result is obtained using a specific version of CSE: we need to introduce the concept of *consistency*, obtaining a *consistent conjectural Stackelberg equilibrium* (CCSE). Intuitively, this forces the variation of the conjectures to be equal to the variation of the response function at equilibrium.

**Proposition 2 (Equivalence between SE and CCSE)** *Considering a differential definition of SE and CCSE, we obtain conditions for equivalence between the two equilibria. Of particular importance are the following cases:*

1. if the conjectures are exactly equal to the best-response functions, SE and CCSE coincide.

2. if the objective functions of the leaders are linear, SE and CCSE coincide.

3. if the objective functions are quadratic, the distance between SE and CCSE depends only on how close the conjectures are to the best responses.

# 3 The COSTAL Algorithm

We keep our formulation *conjecture agnostic*: indeed the only requirement for these functions is to be twice differentiable. This allows us to develop the **COSTAL** (COnjectural STAckelberg Learning) algorithm, which each player can use to first learn the conjectures functions, and then optimize its strategy. The first step consist in a *pre-game* between the players, where each player *i* uses noisy information about the other players to learn its conjecture. In the second step these conjectures are used in a gradient descent algorithm which is used to update dynamically the strategy of each player. We prove using stochastic approximation theory [2], that our algorithm converges to a *differential Conjectural Stackelberg equilibrium* (dCSE). As far as we know this is the first algorithm with provable convergence in this class of games. Furthermore, we provide numerical results showing out theoretical results and highlighting the usefulness of the new equilibrium concept, when compared with Nash and Stackelberg. The idea of the algorithm is based on gradient descent, exploiting the decoupled objective functions obtained using conjectures. On top of these results, the **COSTAL** algorithm could be run in parallel by each leader in the game, making it extremely efficient.

# 4 Conclusions and Further Developments

In this work we presented a new class of games, called Conjectural Stackelberg Games, aimed at bridging the gap between the use of conjectures and Stackelberg games. In particular we formalized how leaders may model opposite players’ behavior. To characterize the game we also propose a novel equilibrium definition, comparing it with the standard Stackelberg Equilibrium for multiple settings. Finally, we develop a multi agent learning algorithm (COSTAL) that can be used by the players of Conjectural Games to update their conjectures and their strategy. We also provide a proof of convergence for said algorithm.

# References

[1] Tamer Başar and Geert Jan Olsder. *Dynamic Noncooperative Game Theory, 2nd Edition*. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, January 1998.

[2] Vivek S. Borkar. *Stochastic Approximation*, volume 48 of *Texts and Readings in Mathematics*. Hindustan Book Agency, Gurgaon, 2008.

[3] Charles Figuières, Alain Jean-Marie, Nicolas Quérou, and Mabel Tidball. *Theory of Conjectural Variations*. WORLD SCIENTIFIC, February 2004.