A potentialization algorithm for games with applications to multi-agent learning in repeated games

Philipp Lakheshar; Sharwin Rezagholi

cs.MAFeb 21, 2026

A potentialization algorithm for games with applications to multi-agent learning in repeated games

Authors: Philipp Lakheshar, Sharwin Rezagholi

Organizations: University of Applied Sciences Technikum Wien, Vienna, Austria

Abstract

We investigate an algorithm that assigns to any game in normal form an approximating game that admits an ordinal potential function. Due to the properties of potential games, the algorithm equips every game with a surrogate reward structure that allows efficient multi-agent learning. Numerical simulations using the replicator dynamics show that 'potentialization' guarantees convergence to stable agent behavior.

Figures & tables

Panel of Figure 1 — Figure 1: Construction of the potential function.

Panel of Figure 2 — Figure 2: Coordination game. The pure Nash equilibria of the original game are Pareto-ordered: $\alpha>\beta>\gamma$ . The second and the third action of both players is weakly dominated. There is a cycle containing all vertices but $\alpha$ . All pure equilibria are retained and two additional pure equilibria are created.

Panel of Figure 3 — Figure 3: Game from Voorneveld and Nolde (1997). The vertices denoted by $\bullet$ form a cycle. All three equilibria are retained but the Pareto-best original equilibrium becomes preferable to both players.

Figure 4: Experimental results for

(10\times 10)

-games (

\pm

empirical standard deviation).

Figure 5: Experimental results for

(4\times 4\times 4)

-games (

\pm

empirical standard deviation).

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning
Mar 7, 2026Addison Kalanther, Sanika Bharvirkar, Shankar Sastry +1Multi-Agent Reinforcement Learning Game-Theoretic RL
Electrical Engineering and Computer Sciences, UC Berkeley · Electrical and Computer Engineering, Data Science & Artificial Intelligence Institute, Johns Hopkins University
What preferences can - and cannot - predict in multi-agent online learning
Aug 13, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosGame Theory Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, Moroccan Center for Game Theory, 11103 Rabat, Morocco. · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
Distributed Algorithms for $α$ -Potential Functions in General-Sum Games
Oct 4, 2026Yifei Chen, Chinmay MaheshwariDistributed Optimization Potential Games
Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, Maryland, USA · Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, Maryland, USA

Mar 7, 2026J/K move · Enter open · S save

NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning

Addison Kalanther, Sanika Bharvirkar, Shankar Sastry, Chinmay Maheshwari

Electrical Engineering and Computer Sciences, UC Berkeley · Electrical and Computer Engineering, Data Science & Artificial Intelligence Institute, Johns Hopkins University

Multi-Agent Reinforcement Learning Game-Theoretic RL Nash Equilibrium Computation Potential Games

Open paper AskPDF arXiv

Multi-agent reinforcement learning (MARL) is increasingly used to design learning-enabled agents that interact in shared environments. However, training MARL algorithms in general-sum games remains challenging: learning dynamics can become unstable, and convergence guarantees typically hold only in restricted settings such as two-player zero-sum or fully cooperative games. Moreover, when agents have heterogeneous and potentially conflicting preferences, it is unclear what system-level objective should guide learning. In this paper, we propose a new MARL pipeline called Near-Potential Policy Optimization (NePPO) for computing approximate Nash equilibria in mixed cooperative--competitive environments. The core idea is to learn a player-independent potential function such that the Nash equilibrium of a cooperative game with this potential as the common utility approximates a Nash equilibrium of the original game. To this end, we introduce a novel MARL objective such that minimizing this objective yields the best possible potential function candidate and consequently an approximate Nash equilibrium of the original game. We develop an algorithmic pipeline that minimizes this objective using zeroth-order gradient descent and returns an approximate Nash equilibrium policy. We empirically show the superior performance of this approach compared to popular baselines such as IPPO and MAPPO.

Abstract

Game Theory

Explore similar work

NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning

What preferences can - and cannot - predict in multi-agent online learning

Distributed Algorithms for ααα-Potential Functions in General-Sum Games

Distributed Algorithms for $α$ -Potential Functions in General-Sum Games