On the Analysis of Potential Games: From Constraints, Price of Anarchy and Reinforcement Learning to Contrastive Learning

Potential games provide a unified and tractable framework for analyzing multi-agent interactions in which individual incentives align with a common objective, the potential, making them central to understanding decentralized coordination in economics, engineering, and artificial intelligence. This thesis investigates how structure, learning, and computation interact within potential games, covering equilibrium computation under constraints, equilibrium selection under learning dynamics, applications in cooperative multi-agent reinforcement learning, and links to the complexity of contrastive learning. In the first part, a distributed Lagrangian framework is developed for potential games with private, uncoupled constraints, enabling agents to compute approximate Nash equilibria in polynomial time and extending classical results to realistic congestion and resource-allocation settings with constraints. Learning dynamics are then examined through Q-Replicator Dynamics, a broad class of no-regret dynamics that include gradient descent, replicator, and log-barrier updates. These dynamics converge pointwise to Nash equilibria in almost all finite potential games. By characterizing regions of attraction, an Average Price of Anarchy (APoA) is derived to quantify the expected efficiency of learning outcomes. Contrary to the worst-case Price of Anarchy, which can be unbounded, the average-case measure under gradient-based learning is well defined, clarifying when various dynamics perform better on average. This thesis also applies the framework of potential games to a sequential setting, modeled as a Markov Potential Game in a location-aware scheduling environment. Agents learn to allocate tasks under partial observability, using compact state and action representations, and a common reward signal. Experiments show how agents reach a Nash equilibrium and also how floor-plan geometry, task parallelizability, and localization shape coordination efficiency, transfer to unseen layouts, and performance degradation, highlighting the modeling value of potential games in the multi-agent reinforcement learning domain. Finally, a conceptual link between potential games and contrastive learning objectives is revealed. By interpreting the triplet-loss formulation as a potential function (betweenness ranking) over data points, the task of finding locally optimal embeddings can be viewed through the lens of equilibrium computation. This perspective reveals that identifying local optima is PLS-hard in discrete settings, even for one-dimensional embeddings. These results highlight the inherent computational limits of local search methods in representation learning.