Aggregative games with bilevel structures: Distributed algorithms and convergence analysis

Technical Summary: Aggregative Games with Bilevel Structures: Distributed Algorithms and Convergence Analysis

Problem Formulation
This paper addresses the problem of distributively seeking the Nash equilibrium (NE) in aggregative games (AGs) characterized by bilevel structures. Unlike traditional AGs where the aggregation term is a direct sum or average of local player actions, the aggregation in this framework is determined by the minimizer of a virtual leader's objective function in an inner level. Specifically, the game $\Gamma(V, \Omega, J)$ involves $n$ players in an outer level, each minimizing a cost function $J_i(x_i, \sigma(x))$ dependent on their local action $x_i$ and a global aggregation variable $\sigma(x)$. The variable $\sigma(x)$ is defined as the solution to an inner-level optimization problem:
$$\sigma(x) = \arg \min_{y} \sum_{i=1}^n g_i(x_i, y)$$
where $g_i$ represents a local function of player $i$ and the aggregation variable $y$. The global objective of the virtual leader is the sum of these local functions, which are assumed to be strongly convex with respect to $y$.

A critical challenge identified is that players in the outer level possess only local information: their own cost function $J_i$, a local part of the virtual leader's objective function $g_i$, and their local action set. They cannot access the full information of the inner-level objective function or the global aggregation term directly. Consequently, the gradient of a player's cost function in the outer level depends on $\nabla_{x_i}\sigma(x)$, which involves the inverse of the sum of Hessian matrices of the inner-level functions—a term not directly accessible to individual players.

Methodology
To solve this problem under a connected communication graph, the authors propose two distributed algorithms:

1. Second-Order Gradient-Based Distributed (SOGD) Algorithm:
   This algorithm assumes players have access to second-order gradient information (Hessian matrices). It integrates three components:

   • Primal-Dual Strategy: Used to estimate the aggregation $\sigma(x)$ by cooperatively minimizing the inner-level global objective function.
   • Distributed Average Tracking: Employed to track the average of the Hessian matrices associated with the inner-level objective functions.
   • Gradient Descent with Projection: Players update their actions in the outer level using a projected gradient strategy involving the Krasnoselskii-Mann iterative method. This strategy utilizes the tracked Hessian information to compute the necessary gradient terms for the outer-level cost functions.

2. First-Order Gradient-Based Distributed (FOGD) Algorithm:
   Recognizing that computing Hessian matrices can be expensive or impossible in high-dimensional applications (e.g., meta-learning), the authors propose a first-order method.

   • Distributed Estimate Strategy: Instead of computing Hessians, this algorithm introduces an auxiliary variable and a perturbation parameter $\delta_i$. It estimates the product of the aggregation's gradient and the cost function's gradient with respect to the second argument.
   • Auxiliary Optimization: Players solve an auxiliary optimization problem to estimate the necessary gradient terms, avoiding the direct use of second-order information.

Key Contributions
The paper claims the following novelties and contributions:

• Generalized Framework: The proposed bilevel structure generalizes existing single-level AGs and distributed optimization problems with strongly convex objectives. It differs from prior Stackelberg game formulations where players typically have access to full gradient information; here, the aggregation relies on an inner-level solution that is not fully observable.
• SOGD Algorithm Design: The authors develop a new algorithm combining primal-dual methods, distributed average tracking, and gradient descent. They prove that under mild assumptions, player actions asymptotically converge to the NE with a convergence rate of $O(\sqrt{\ln t}/t)$.
• FOGD Algorithm and Error Analysis: For cases where Hessian matrices are unavailable, the FOGD algorithm is introduced. The authors establish a linear relationship between the convergence error and the estimate parameter $\delta_i$, proving that the error is linear with respect to these parameters.

Results and Convergence Analysis

• SOGD Convergence: Under assumptions of graph connectivity, convexity, strong convexity of inner functions, and Lipschitz continuity, the SOGD algorithm ensures that player actions $x_t$ and aggregation estimates $y_{i,t}$ converge to the NE $x^*$ and $\sigma(x^*)$ respectively. The convergence rate is shown to be $O(\sqrt{\ln t}/t)$, which the authors note is faster than the common $O(\ln t/\sqrt{t})$ rate for distributed optimization with decaying step-sizes.
• FOGD Convergence: The FOGD algorithm achieves convergence to an approximate NE. Theoretical analysis demonstrates that the convergence errors are bounded by terms involving the estimate parameters $\delta_i$. Specifically, the error bound includes a term proportional to $\sqrt{\delta_i} + \delta_i$, indicating that smaller $\delta_i$ yields higher accuracy, though practical constraints prevent $\delta_i$ from being arbitrarily small.
• Numerical Simulation: The algorithms were tested on a distributed power allocation problem in a small-cell network consisting of 20 base stations. The simulations confirmed that both algorithms drive the system toward the theoretical equilibrium, with trajectories of error metrics decaying over time as predicted.

Significance and Claims
The paper positions itself as the first to study distributed aggregative games with bilevel structures where the aggregation is determined by a virtual leader's inner-level minimization problem, and players lack full information regarding this inner level. The authors emphasize that their work unifies the research frameworks for traditional AGs and distributed optimization.

The significance lies in providing a theoretical foundation and practical algorithms for scenarios where the "price" or "aggregation" is an emergent property of a complex, distributed optimization process (e.g., network pricing in small-cell networks) rather than a simple sum of actions. The paper modestly acknowledges that while the FOGD algorithm achieves approximate convergence, achieving accurate convergence using only first-order information remains a difficult problem for future investigation. Future work is suggested to address network-induced time delays, packet loss, and communication bandwidth constraints.