Monte Carlo Optimization for Solving Multilevel Stackelberg Games

Pravesh Koirala, Forrest LainearXiv 2023 · DOI · arXiv

Abstract

Multilevel Stackelberg games represent a class of hierarchical optimization problems where a sequence of players (leaders and followers) make decisions in a nested fashion. These problems are notoriously difficult to solve due to their NP-hard nature, non-convexity, and the requirement for rational reactions at every level. This paper introduces Monte Carlo Multilevel Optimization (MCMO), a gradient-free, sampling-based algorithm designed to find local equilibria in these complex hierarchies. MCMO distinguishes itself by handling unbounded variables and strict constraints without requiring cooperation between players. Experimental results demonstrate that MCMO significantly outperforms existing meta-heuristics in accuracy, achieving errors as low as 0.025% in economic modeling benchmarks and proving robust in adversarial robotic path planning scenarios.

Introduction

In game theory, a Stackelberg game describes a scenario where a "leader" makes a move, and a "follower" responds optimally. When extended to multiple layers—such as a leader, a middle-manager, and a front-line worker—it becomes a Multilevel Stackelberg game. Mathematically, this is a Bilevel (or Multilevel) Optimization problem where each level's objective is constrained by the optimal solutions of the levels below it.

Traditional solvers for these problems often rely on restrictive assumptions, such as strictly bounded decision variables or player cooperation. Furthermore, the search space is frequently non-smooth and "jagged," making gradient-based methods difficult to apply. MCMO addresses these challenges by employing a recursive sampling strategy that respects the hierarchical "rational reaction" requirement of Stackelberg games.

Methodology

MCMO is a recursive, sampling-based approach that operates through the following stages:

  1. Recursive Sampling: Starting at the top level, the algorithm generates candidate moves (samples) within the neighborhood of the current best estimate.
  2. Hierarchical Propagation: These candidates are passed down to the subsequent level, which generates its own responses and continues the chain until the bottom level is reached.
  3. The Anchor Level: The final follower level is solved to completion using a high-performance standard solver, such as IPopt, to ensure a precise baseline for the hierarchy.
  4. Bottom-Up Evaluation: Results are propagated back up the hierarchy. Each level evaluates the responses based on its specific objective function, selecting the optimal response to return to its respective leader.
  5. Smoothing: To mitigate the noise inherent in stochastic sampling, a "Best Objective Smoothing Scheme" is applied to identify the most stable optimal point across final iterations.

This gradient-free structure allows MCMO to navigate nested layers without calculating complex derivatives, a primary bottleneck in traditional multilevel optimization.

Experimental Validation

The algorithm was evaluated against several benchmarks, including trilevel linear problems from literature and a novel Adversarial Initial Condition (AIC) robotics problem. In the AIC scenario, an adversary attempts to find a starting point for a robot's path that forces it to either collide with an obstacle or follow a highly inefficient route.

Figure 1: Trajectory optimization in the Adversarial Initial Condition (AIC) problem. The algorithm identifies worst-case starting points that challenge the robot's ability to navigate obstacles while remaining within feasible regions.

In economic modeling, specifically a Nested Toll-Setting problem, MCMO achieved a remarkable error rate of 0.025%. In comparison, existing state-of-the-art meta-heuristics produced errors ranging from 18% to 191%, largely because they failed to accurately model the rational reactions of lower-level players.

Key Insights and Results

  • Rational Reaction Integrity: Unlike solvers that default to Nash Equilibrium (simultaneous reaction), MCMO strictly adheres to the Stackelberg hierarchy, ensuring leaders account for the mandatory optimal responses of followers.
  • Handling Unbounded Spaces: By utilizing local neighborhood sampling, MCMO effectively explores infinite search spaces in $\mathbb{R}^n$, a task where traditional genetic algorithms often fail.
  • Anytime Accuracy: The algorithm allows for a trade-off between computation time and precision by adjusting the number of samples ($N$) or iterations ($M$).

Limitations and Future Work

While powerful, MCMO faces the "curse of dimensionality," as the required sample size grows with the number of decision variables. Additionally, as a sampling-based method, it identifies local rather than global equilibria. Future research will focus on parallelizing the algorithm for GPU execution—since samples at each level are independent—and extending the framework to handle multilevel decentralized problems with multiple competing players at each level.

Summary updated

Abstract

Stackelberg games originate where there are market leaders and followers, and the actions of leaders influence the behavior of the followers. Mathematical modelling of such games results in what's called a Bilevel Optimization problem. There is an entire area of research dedicated to analyzing and solving Bilevel Optimization problems which are often complex, and finding solutions for such problems is known to be NP-Hard. A generalization of Stackelberg games is a Multilevel Stackelberg game where we may have nested leaders and followers, such that a follower is, in turn, a leader for all lower-level players. These problems are much more difficult to solve, and existing solution approaches typically require extensive cooperation between the players (which generally can't be assumed) or make restrictive assumptions about the structure of the problem. In this paper, we present a stochastic algorithm to approximate the local equilibrium solutions for these Multilevel games. We then construct a few examples of such Multilevel problems, including: a) a nested toll-setting problem; and b) an adversarial initial condition determination problem for Robust Trajectory Optimization. We test our algorithm on our constructed problems as well as some trilevel problems from the literature, and show that it is able to approximate the optimum solutions for these problems within a reasonable error margin. We also provide an asymptotic proof for the convergence of the algorithm and empirically analyze its accuracy and convergence speed for different parameters. Lastly, we compare it with existing solution strategies from the literature and demonstrate that it outperforms them.
BibTeX
@misc{koirala2023monte,
  author = {Pravesh Koirala and Forrest Laine},
  title = {{Monte Carlo Optimization for Solving Multilevel Stackelberg Games}},
  year = {2023},
  eprint = {2312.03282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.03282},
}
Figure