Game-Theoretic Understandings of Multi-Agent Systems with Multiple Objectives

Zixin Lin; Qianyi Tan; Sihong He; Yue Wang

cs.MASep 27, 2025

Game-Theoretic Understandings of Multi-Agent Systems with Multiple Objectives

Authors: Zixin Lin, Qianyi Tan, Sihong He, Yue Wang

Organizations: Department of Electrical and Computer Engineering, Department of Computer Science, University of Central Florida, Orlando, FL 32816

Abstract

Agents in many multi-agent systems must balance several, possibly conflicting, objectives, and the trade-offs an agent can achieve depend on how the other agents behave. We study this setting through the Multi-Objective Markov Game (MOMG), a Markov game in which each agent receives a vector of rewards, and adopt the Pareto-Nash Equilibrium (PNE) as the solution concept: at a PNE, no agent can unilaterally improve one of its objectives without sacrificing another. We show that PNEs always exist and coincide with the Nash equilibria of the linearly scalarized games with strictly positive weights, so standard single-objective Markov-game solvers suffice to compute them. We further define the Weak Pareto-Nash Equilibrium (WPNE), which excludes only unilateral deviations that strictly improve all objectives at once. The associated gap (WPNG) is zero exactly at WPNEs and never exceeds the Nash gap of any linearly scalarized game; hence an approximate Nash equilibrium of a scalarized game is also an approximate WPNE. When the preference profile is known in advance, learning in an MOMG therefore reduces to learning in a single scalarized Markov game, for which we provide a sample-efficient algorithm. When preferences are revealed only after data collection, we design a two-phase algorithm that first explores without any preference information; with high probability, every Nash equilibrium of the learned scalarized game is then an approximate WPNE for every queried preference profile, and the WPNG of any policy can be estimated accurately from the learned model. Experiments on tabular games and four multi-objective multi-agent environments illustrate the theory and show the effect of preference-free exploration.

Figures & tables

Figure 1: WPNGs of Approximate Scalarized NEs, computed exactly by the linear program in Appendix D.2 . Left: WPNG against the scalarized Nash gap of each solution; the dashed line marks WPNG $=$ Nash gap. Right: each column is a game type. Boxes show interquartile range; black lines indicate medians; whiskers the 2nd and 98th percentiles.

Environment	Method	Nash gap ( $\downarrow$ )	Worst-case ( $\downarrow$ )	AUT ( $\uparrow$ )
MO-Predator Prey	Two-Phase + EQ (Ours)	$\mathbf{10.5}\pm 1.2$	$\mathbf{43.4}\pm 2.9$	$\mathbf{19.2}\pm 1.5$
	Two-Phase (no EQ)	$26.0\pm 0.9$	$52.6\pm 1.6$	$3.4\pm 0.2$
	Fixed $\lambda$ (equal)	$26.3\pm 0.9$	$50.2\pm 1.3$	$4.4\pm 0.1$
	Indep. MORL	$25.5\pm 1.1$	$50.4\pm 2.9$	$3.2\pm 0.2$
	Indep. MORL + EQ	$25.6\pm 1.5$	$53.0\pm 2.7$	$2.1\pm 1.1$
MO-Traffic Control	Two-Phase + EQ (Ours)	$\mathbf{7.1}\pm 0.8$	$\mathbf{13.7}\pm 1.3$	$\mathbf{15.0}\pm 0.8$

Table 1: Strategic metrics on MO environments: mean and 95% confidence interval over

10

seeds, each evaluated on

60

test preference profiles.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Environment	Method	Worst-case Nash gap	BR-AUT	$\Delta$
MO-Predator Prey	Two-Phase + EQ (Ours)	$43.4\pm 2.9$	$26.02\pm 1.24$	$-6.80\pm 0.99$
	Two-Phase (no EQ)	$52.6\pm 1.6$	$25.21\pm 1.15$	$-21.80\pm 0.97$
	Fixed $\lambda$ (equal)	$50.2\pm 1.3$	$25.60\pm 1.43$	$-21.25\pm 1.31$
	Indep. MORL	$50.4\pm 2.9$	$25.37\pm 0.95$	$-22.13\pm 0.78$
	Indep. MORL + EQ	$53.0\pm 2.7$	$23.80\pm 0.72$	$-21.71\pm 1.15$
MO-Traffic Control	Two-Phase + EQ (Ours)	$13.7\pm 1.3$	$13.15\pm 1.25$	$1.80\pm 0.52$

Appendix

Table 2: Further results for Table 1 (mean and 95% confidence interval over

10

seeds). Worst-case Nash gap: maximum over the

60

test profiles. BR-AUT and

\Delta=\mathrm{AUT}-\text{BR-AUT}

: utility of the agent that does not deviate.

Environment (easy variant)	Method	Nash gap ( $\downarrow$ )	AUT ( $\uparrow$ )
MO-Predator Prey	Two-Phase + EQ (Ours)	$6.78\pm 1.73$	$45.79\pm 1.59$
	Two-Phase (no EQ)	$6.71\pm 1.48$	$46.12\pm 2.53$
	Fixed $\lambda$ (equal)	$1.66\pm 0.82$	$54.92\pm 2.76$
	Indep. MORL	$4.11\pm 2.02$	$49.58\pm 3.43$
	Indep. MORL + EQ	$3.62\pm 0.44$	$50.26\pm 4.18$
MO-Traffic Control	Two-Phase + EQ (Ours)	$0.12\pm 0.01$	$34.58\pm 1.60$

Appendix

Table 3: Control experiment: the environments of Table 1 with the region or event made easy to reach (mean and 95% confidence interval over

5

seeds).

Panel of Figure 2 — Figure 2: The experimental testbeds. (left) Multi-Objective Item Gathering (MOIG), requiring agents to navigate and select resources based on preference profiles. (right) Multi-Objective MultiWalker (MOMW), challenging agents to maintain dynamic balance and coordination under continuous physical constraints.

Method	MO-IG AUT ( $\uparrow$ )	MO-IG HV ( $\uparrow$ )	MO-MW AUT ( $\uparrow$ )	MO-MW HV ( $\uparrow$ )
MOMAPPO	$1.65\pm 0.25$	$2.59\pm 2.14$	$-98.86\pm 69.97$	$4.52\times 10^{4}\pm 2.91\times 10^{4}$
PCN	$1.60\pm 0.22$	$4.11\pm 1.65$	$-41.75\pm 36.27$	$6.80\times 10^{4}\pm 1.90\times 10^{4}$
DML-NUQ	$\mathbf{1.82\pm 0.19}$	$\mathbf{4.60\pm 1.85}$	$\mathbf{-32.53\pm 35.92}$	$\mathbf{7.26\times 10^{4}\pm 1.89\times 10^{4}}$

Appendix

Table 4: Performance comparison using Average Utility (AUT) and Hypervolume (HV). The arrow (

\uparrow

) indicates that higher values are preferred. DML-NUQ (Ours) achieves the highest AUT and HV across all four settings.

Method	MO-IG AUT ( $\uparrow$ )	MO-IG HV ( $\uparrow$ )	MO-MW AUT ( $\uparrow$ )	MO-MW HV ( $\uparrow$ )
w/ zero int. reward	$1.65\pm 0.25$	$2.59\pm 2.14$	$-96.86\pm 69.97$	$4.52\times 10^{4}\pm 2.91\times 10^{4}$
w/ random int. reward	$1.74\pm 0.26$	$3.62\pm 2.80$	$-43.30\pm 63.86$	$6.92\times 10^{4}\pm 2.83\times 10^{4}$
DML-NUQ (Ours)	$\mathbf{1.82\pm 0.19}$	$\mathbf{4.60\pm 1.85}$	$\mathbf{-32.53\pm 35.92}$	$\mathbf{7.26\times 10^{4}\pm 1.89\times 10^{4}}$

Appendix

Table 5: Ablation study on the NUQ component. Removing or randomizing NUQ leads to consistent degradation across both environments and both metrics.

Hyperparameter	Value
Total Timesteps	$10^{7}$
Random Seed	42
Training Strategy
Weight Generation Method	OLS
Number of Weights	10
Timesteps per Weight	$10^{6}$

Appendix

Table 6: Common Hyperparameters for all experiments.

Parameter	MO-Item Gathering (MO-IG)	MO-MultiWalker (MO-MW)
Action Space	Discrete	Continuous
Learning Rate	$2.5\times 10^{-4}$	$1.0\times 10^{-3}$
Entropy Coefficient	$0.01$	$0.0$
Reference Point	$[0.0,0.0,0.0]$	$[-300.0,-300.0]$
NUQ Module (Ours)	Configuration
Intrinsic Reward Coeff. ( $\beta$ )	$0.1$

Appendix

Table 7: Environment-specific hyperparameters and NUQ module configuration.

Game Theory

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

See all 236 papers

May 7, 2026

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address efficient learning, measured by Pareto regret, and incorporate fair learning as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop Pareto UCB1 Gossip, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose Simulated NSW UCB Gossip, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that Pareto UCB1 Gossip achieves

\mathcal{O}(\log T)

regret and an instance-independent rate of

\mathcal{O}(\sqrt{T})

, while Simulated NSW UCB Gossip achieves an instance-independent regret bound of

\mathcal{O}(T^{3/4})

. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately

100\%

and

50\%

in the efficiency and fairness settings, respectively.

John Wang, Mengfan Xu

University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent System Optimization Multi-Agent Bandits Algorithmic Fairness Multi-Objective Optimization Social Welfare Maximization

Ask PDF

Jun 12, 2026

Learning Coordinated Preference for Multi-Objective Multi-Agent Reinforcement Learning

Cooperative multi-objective multi-agent reinforcement learning (MOMARL) models team decision making under multiple, potentially conflicting objectives. In this setting, conflicts arise not only across objectives but also across agents with different observations, roles, and contributions. We propose Preference Coordinated Multi-agent Policy Optimization (PCMA), which learns coordinated agent-specific preferences to enable complementary trade-offs among agents. Theoretically, we formulate cooperative MOMARL as a team-optimal equilibrium problem, and show that, under suitable conditions, preference diversity yields a first-order improvement in the team objective. Experiments on multiple cooperative MOMA environments and a practical traffic-control scenario show that PCMA improves both performance and trade-off coordination.

Pengxin Wang, Lihao Guo, Yi Xie +3

Department of Electrical and Computer Engineering, University of Arizona

Multi-Objective Reinforcement Learning Multi-Agent System Optimization Multi-Agent Coordination Cooperative MARL

Ask PDF

Mar 7, 2026

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

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.

Addison Kalanther, Sanika Bharvirkar, Shankar Sastry +1

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

Ask PDF

Abstract

Game Theory

Explore similar work

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

Learning Coordinated Preference for Multi-Objective Multi-Agent Reinforcement Learning

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