Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation
This work addresses a theoretical gap in game theory for scenarios with nonconvex constraints, which is incremental but important for modeling complex interactions.
The paper tackles the problem of proving existence and computing Nash equilibria in games with playerwise concave coupling constraints, where prior methods fail due to strong convexity assumptions, and demonstrates a method that converges to an approximate equilibrium in O(ε^{-3}) iterations.
We study the existence and computation of Nash equilibria in continuous static games where the players' admissible strategies are subject to shared coupling constraints, i.e., constraints that depend on their \emph{joint} strategies. Specifically, we focus on a class of games characterized by playerwise concave utilities and playerwise concave constraints. Prior results on the existence of Nash equilibria are not applicable to this class, as they rely on strong assumptions such as joint convexity of the feasible set. By leveraging topological fixed point theory and novel structural insights into the contractibility of feasible sets under playerwise concave constraints, we give an existence proof for Nash equilibria under weaker conditions. Having established existence, we then focus on the computation of Nash equilibria via independent gradient methods under the additional assumption that the utilities admit a potential function. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $ε$-approximate constrained Nash equilibrium within $\mathcal{O}(ε^{-3})$ iterations.