Solving quadratic multi-leader-follower games by smoothing the follower's best response

Michaël Herty, Sonja Steffensen, Anna Thünen

Abstract

This paper analyzes the existence of Nash equilibria for a class of quadratic multi-leader-follower games (MLFGs) characterized by nonsmooth best response functions. To address the computational challenges posed by these "kinks," we employ a smoothing approach that reformulates the problem into a sequence of smooth Nash equilibrium problems (NEPs). We prove the existence and uniqueness of solutions for all smoothing parameters $\epsilon > 0$. Furthermore, we demonstrate that accumulation points of these solutions as $\epsilon \to 0$ satisfy the conditions of S-stationarity and constitute Nash equilibria for the original game. To enhance computational efficiency, we introduce a Taylor expansion update for leader variables and provide a numerical comparison between nonsmooth Newton and subgradient methods.

Introduction

Hierarchical games are essential for modeling complex interactions in fields such as electricity markets and supply chain management. In these Multi-Leader-Follower Games (MLFGs), multiple leaders compete while simultaneously accounting for the optimal reaction of a follower. Mathematically, these problems are notoriously difficult because the follower’s best response function often contains points of non-differentiability—or "kinks"—where standard calculus-based optimization tools fail.

This research provides a rigorous framework to smooth these nonsmooth responses, proving that a sequence of simplified, smooth problems can reliably converge to the true equilibrium of the complex hierarchical game.

Problem Formulation and Nonsmoothness

In a standard Nash game, players act simultaneously. However, in an MLFG, the hierarchy dictates that leaders move first, anticipating the follower's reaction. The mathematical difficulty arises because the follower’s best response function—the rule used to determine their optimal move—frequently involves max or min operators. For example, a follower might produce a certain quantity unless a price floor is reached, creating a piecewise linear response.

These kinks represent points where the function is not differentiable, breaking the assumptions required for most standard solvers. Previous research has often bypassed this by assuming smoothness (which lacks realism) or has struggled to guarantee the existence and uniqueness of solutions in the nonsmooth case.

The Smoothing Methodology

The authors propose a three-step strategy to resolve these issues:

  1. Reformulation: For a specific class of quadratic games, the follower’s best response is explicitly reformulated as a max function.
  2. Smoothing (NEP($\epsilon$)): The nonsmooth max function is replaced with a smooth approximation controlled by a parameter $\epsilon$. This transforms the difficult MLFG into a "Smooth Nash Equilibrium Problem."
  3. Path-Following & Taylor Updates: As $\epsilon$ approaches zero to recover the original game, the authors utilize a Taylor expansion update. Instead of restarting the solver at each step, this update predicts the shift in equilibrium, providing a high-quality "warm start" for the next iteration.

Theoretical Insights

Convergence and S-Stationarity

A primary contribution of this work is the proof that the limit of the smoothed solutions is a strongly stationary (S-stationary) point. This point is guaranteed to be a genuine Nash equilibrium of the original nonsmooth game, bridging the gap between numerical heuristics and rigorous game theory.

Potential Game Structure

The authors exploit the fact that the follower's problem can be viewed as a "potential game." This allows multiple followers to be collapsed into a single aggregate optimization problem without a loss of generality, simplifying the computational landscape.

Existence and Uniqueness

The paper proves that for any smoothing parameter $\epsilon > 0$, the smoothed game possesses a unique Nash equilibrium. This provides a stable foundation for numerical computation that is often missing in hierarchical game theory.

Numerical Results

The framework was validated using two synthetic benchmarks involving multiple leaders and linear constraints. The study compared two primary numerical approaches:

  • Nonsmooth Newton Method: This method exhibited quadratic convergence, typically reaching high precision within 10–15 iterations for a fixed $\epsilon$.
  • Subgradient Method: While capable of handling nonsmoothness, this method proved characteristically slow, requiring thousands of iterations to achieve comparable results.

The Taylor expansion update proved essential for robustness. Without it, solvers frequently failed to find the equilibrium as $\epsilon$ became very small and the problem became increasingly nonsmooth.

Limitations and Future Directions

While the framework is robust for quadratic games with linear constraints, several challenges remain:

  • Non-Convexity: The current proofs rely on the convexity of the follower's problem. If the follower has multiple local optima, the best response becomes a set rather than a function, complicating the smoothing process.
  • Upper Bounds: Adding upper bounds to the follower's strategy (e.g., $l(x) \le y \le u(x)$) transforms the best response into a median function, which may not be componentwise convex, potentially affecting existence proofs.
  • Scaling: Calculating the generalized Jacobian for large-scale systems with thousands of players remains a significant engineering challenge for the Newton method.

Reference: Herty, M., Steffensen, S., & Thünen, A. (2020). Solving quadratic multi-leader-follower games by smoothing the follower’s best response. arXiv:1808.07941v4.

Summary updated

Abstract

We analyse the existence of Nash equilibria for a class of quadratic multi-leader-follower games using the nonsmooth best response function. To overcome the challenge of nonsmoothness, we pursue a smoothing approach resulting in a reformulation as a smooth Nash equilibrium problem. The existence and uniqueness of solutions are proven for all smoothing parameters. Accumulation points of Nash equilibria exist for a decreasing sequence of these smoothing parameters and we show that these candidates fulfil the conditions of S-stationarity and are Nash equilibria to the multi-leader-follower game. Finally, we propose an update on the leader variables for efficient computation and numerically compare nonsmooth Newton and subgradient methods.
BibTeX
@inproceedings{herty2020solving,
  author = {Michaël Herty and Sonja Steffensen and Anna Thünen},
  title = {{Solving quadratic multi-leader-follower games by smoothing the follower's best response}},
  booktitle = {Optimization},
  year = {2020},
  doi = {10.1080/10556788.2020.1828412},
}
Figure