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

We study the existence and computation of Nash equilibria in concave games where the players' admissible strategies are subject to shared coupling constraints. Under playerwise concavity of constraints, we prove existence of Nash equilibria. Our proof leverages topological fixed point theory and novel structural insights into the contractibility of feasible sets, and relaxes strong assumptions for existence in prior work. Having established existence, we address the question of whether in the presence of coupling constraints, playerwise independent learning dynamics have convergence guarantees. We address this positively for the class of potential games by designing a convergent algorithm. 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 $\epsilon$-approximate constrained Nash equilibrium within $\mathcal{O}(\epsilon^{-3})$ iterations.

Many real-world systems involve multiple decision-makers whose actions interact and must satisfy shared constraints, such as self-driving cars avoiding collisions or mobile devices competing for limited network bandwidth. Game theory studies such settings and asks whether a stable outcome exists: one in which no participant can improve their objective by changing their decision alone. However, when players are coupled through constraints, classical existence results rely on strong assumptions that often fail in practice, leaving it unclear whether stable outcomes exist at all, let alone whether they can be computed efficiently. We study a broad class of constrained games in which each player's feasible decisions are well-behaved once the others' strategies are fixed, while the overall set of jointly feasible decisions may have a complicated non-convex shape. Using tools from topology, we prove that a stable outcome always exists in this setting. We also develop a decentralized learning algorithm in which players update their strategies independently using only local information, and we prove that these updates converge reliably to a stable outcome. Our results broaden the class of multi-agent systems for which equilibrium existence and computability can be guaranteed, with potential applications in safe robotics, traffic and communication networks, and modern machine learning systems involving competing or interacting models.