Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation

Technical Summary: Nash Equilibria in Games with Playerwise Concave Coupling Constraints

Problem Statement
This paper addresses the existence and computation of Nash equilibria in static games with continuous strategy spaces where players face shared coupling constraints. Unlike standard game-theoretic frameworks where feasible action sets are decoupled, these games involve constraints that depend on the joint strategy profile of all players (e.g., resource limitations, safety requirements, or shared budgets). The central challenge is that coupling constraints destroy the separability of players' feasible response sets, complicating both the theoretical guarantee of equilibrium existence and the design of convergent learning algorithms.

The authors focus on a specific class of games characterized by:

1. Playerwise concave utilities: Each player's utility function is concave with respect to their own strategy, holding others' strategies fixed.
2. Playerwise concave constraints: Each constraint function is concave with respect to any single player's strategy, holding others fixed.
3. Shared constraints: All players are subject to the same set of constraints.

Crucially, the paper relaxes the "joint convexity" assumption (where the feasible region is convex in the joint strategy space) and the "nonempty feasible response" assumption (where a player always has a feasible response regardless of others' actions), both of which are common in prior literature but often violated in practical scenarios involving non-convex interactions.

Methodology

1. Existence Proof via Topological Fixed Point Theory
To prove the existence of a constrained Nash equilibrium without assuming joint convexity, the authors employ topological fixed point theory rather than standard convex analysis.

• Key Insight: They demonstrate that under the assumption of playerwise concave constraints and a specific regularity condition (a playerwise variant of the Mangasarian-Fromovitz Constraint Qualification, or MFCQ), the feasible region, while potentially non-convex and disconnected, possesses a well-behaved topological structure.
• Contractibility: The authors prove that every connected component of the feasible region is contractible (can be continuously deformed to a point). This allows the application of fixed point theorems (specifically Eilenberg & Montgomery, 1946; Begle, 1950) that extend beyond convex domains.
• Construction: They construct a best-response mapping that operates sequentially across players. By leveraging the playerwise concavity, they ensure the mapping is continuous and maps a connected component of the feasible set to itself, guaranteeing a fixed point which corresponds to a constrained Nash equilibrium.

2. Computation via Log Barrier Regularized Gradient Ascent
For the computation of equilibria, the paper focuses on potential games with shared coupling constraints. In this setting, players update strategies independently using only local gradient feedback.

• Algorithm: The authors propose an independent learning protocol using log barrier regularized gradient ascent. Each player maximizes a regularized objective function:
  $$B_i^\eta(x) = u_i(x) + \eta \sum_{j} \log(c_j(x) - \alpha_j)$$
  where $\eta$ is a regularization parameter and the log term acts as a barrier preventing the strategy from violating constraints.
• Adaptive Stepsizes: To handle the non-convexity of the feasible region and the singularity of the log barrier near the boundary, the algorithm employs adaptive stepsizes. These stepsizes are dynamically adjusted based on the current feasibility margin (distance to the constraint boundary) and local smoothness parameters.
• Feasibility Guarantee: Unlike methods that may require solving NP-hard feasibility subproblems or allow infeasible intermediate iterates, this approach ensures that if the algorithm starts from a strictly feasible point, all subsequent iterates remain strictly feasible.

Key Contributions

1. Existence under Weaker Conditions: The paper establishes the existence of constrained Nash equilibria for games with playerwise concave constraints without requiring the feasible response sets to be non-empty for all opponent strategies (relaxing Debreu, 1952) or the joint feasible region to be convex (relaxing Rosen, 1965).
2. Novel Topological Proof Technique: The authors introduce a proof technique analyzing the contractibility of the feasible region's connected components. This bridges the gap between playerwise concavity and the topological requirements for fixed point theorems.
3. Convergent Algorithm for Potential Games: They design a playerwise decoupled learning algorithm for potential games with shared coupling constraints. The algorithm requires no communication or coordination between players.
4. Convergence Rate: Under exact gradient feedback, the proposed method converges to an $\epsilon$-approximate constrained Nash equilibrium within $O(\epsilon^{-3})$ iterations. This is achieved by carefully balancing the regularization parameter and adaptive stepsizes to maintain feasibility and smoothness along the trajectory.

Results

• Theoretical: The paper proves that a constrained Nash equilibrium exists for the defined class of games. Furthermore, it proves that the proposed independent learning dynamics converge to an approximate equilibrium in potential games.
• Empirical: The authors validate their method through simulations on two continuous potential games:
  1. A cooperative game with a non-convex feasible region, demonstrating that the trajectory remains within the feasible set and converges to an equilibrium near the boundary.
  2. A network routing game with coupled link capacity constraints, showing convergence of the Nash gap to zero while respecting capacity limits.

Significance and Claims

The paper claims to resolve open questions regarding the existence and computation of equilibria in games with shared coupling constraints under weaker structural assumptions than previously possible. Specifically:

• It demonstrates that joint convexity is not necessary for equilibrium existence if playerwise concavity and appropriate constraint qualifications are met.
• It shows that independent learning can successfully converge to constrained equilibria in potential games, even when the feasible region is non-convex, provided a feasible starting point is available.
• The work extends the applicability of log barrier interior point methods from single-player optimization to multi-player game settings, offering a practical tool for scenarios where safety or resource constraints must be strictly maintained during the learning process.

The authors note that while their results are specific to potential games with playerwise concavity, they open avenues for future work in more general settings (e.g., Markov games, zero-sum games) and with stochastic feedback.