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:
- Reformulation: For a specific class of quadratic games, the follower’s best response is explicitly reformulated as a
maxfunction. - Smoothing (NEP($\epsilon$)): The nonsmooth
maxfunction is replaced with a smooth approximation controlled by a parameter $\epsilon$. This transforms the difficult MLFG into a "Smooth Nash Equilibrium Problem." - 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
medianfunction, 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