The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games

Nikolaos Al. Papadopoulos; Ismael Tito Freire; Marti Sanchez-Fibla; Konstantinos E. Psannis

cs.MAMar 6, 2026

The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games

Authors: Nikolaos Al. Papadopoulos, Ismael Tito Freire, Marti Sanchez-Fibla, Konstantinos E. Psannis

Organizations: Department of Applied Informatics, University of Macedonia, Egnatia 156, Thessaloniki 54636, Greece · Institut des Systèmes Intelligents et de Robotique (ISIR), Sorbonne Université, Paris, France · Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain

Abstract

Repeated multi-agent interactions require evaluation metrics that capture not only payoff distributions but also their temporal organization. Conventional outcome-based fairness measures can assign similar aggregate scores to temporally distinct coordination patterns, obscuring whether access to a shared resource is genuinely rotating or persistently monopolized. We study this problem in the Honey-Jar Game (HJG), a minimally dynamic repeated threshold-congestion Markov game in which n agents compete for exclusive access to a single high-reward resource. We introduce Perfect Alternation (PA), a reference turn-taking regime corresponding to the n-periodic round-robin picking sequence, together with six novel Alternation (ALT) metrics and a benchmarking methodology mapping ALT values to interpretable PA-equivalent performance. Using Q-learning agents as a minimal adaptive baseline against analytically derived random-policy baselines, we uncover a clear measurement failure: despite deceptively high traditional metrics (e.g., reward fairness often exceeding 0.9), learned policies perform worse than random on every ALT metric, by 34-74% on CALT and up to 92% on EALT, with PA-equivalent coordination falling to roughly one-fifth of the population at n=10. EALT further reveals two distinct failure patterns: without episodic memory (Type-A), the deficit grows from -20% at n=2 to -92% at n=10; with episodic memory (Type-B), it reaches a trough of -76% at n=5 before partially recovering to -10% at n=10. Conventional efficiency and fairness metrics do not reveal these differences. The ALT framework complements the temporal fair division and picking-sequence literature by diagnosing whether temporal fairness emerges spontaneously in decentralized adaptive systems rather than how to enforce it.

Figures & tables

	Action 1	Action 2
Action 1	(0, 0)	(3, 2)
Action 2	(2, 3)	(0, 0)

Table 1: Two-player Battle of the Exes payoff matrix

Metric Pair	Temporal	Fair Outcome	Key Failure Mode
(with Efficiency)	Structure	Confirmed?
Fairness	None	No	Considers only min/max agents; ignores intermediate distribution and temporal sequence
Turn-Taking Fairness	None	No	Collision inflation: ties increment all agents’ counts equally, conflating arrival with turn-taking
Reward Fairness	None	Only at (E=1, RF=1)	Payoff-based; high values achievable via ties alone; temporal sequence entirely invisible

Table 2: Diagnostic limitations of traditional metric combinations. Each pairing was systematically evaluated across all nine value combinations arising from Efficiency

\in\{0,(0,1),1\}

and the respective Fairness variant

\in\{0,(0,1),1\}

. Complete cell-by-cell analysis appears in Supplementary Section S3 (Tables 2 to 4).

Window	$(A,B,C)$	$(B,C,\{A{,}B\})$	$(C,\{A{,}B\},C)$	$(\{A{,}B\},C,A)$	Mean
$\beta^{\mathrm{FALT}}$	1.000	0.750	0.750	0.750	0.812
$\beta^{\mathrm{CALT}}$	1.000	0.469	0.469	0.469	0.602
$\beta^{\mathrm{AALT}}$	1.000	0.500	0.000	0.500	0.500

Table 3: Worked example: batch weights for the six-episode sequence

A,B,C,\{A,B\},C,A

across the four sliding windows.

Figure 1: CALT for Q-learning (orange bars; mean across the four Type-A/B $\times$ ILF/IQF modes, with min–max range markers) versus the random baseline (light blue bars). Q-learning falls below the chance level at every agent count.

Figure 2: PA-equivalent agents ( $n\times\sqrt{\mathrm{CALT}}$ ) for Q-learning (orange bars; mean across the four modes, with min–max range) versus random baselines (light blue). As $n$ grows from 2 to 10, Q-learning rises only from 1.13 to 1.74 equivalent agents (17% of the system at $n=10$ ), remaining below the random baseline throughout.

Figure 3: Traditional metrics hide coordination failure (Type-B, IQF). Panels top to bottom: Efficiency, Reward Fairness, and CALT, for Q-learning (solid lines) versus random baselines (dashed light blue). Reward Fairness stays above $0.9$ for $n\geq 3$ while Efficiency declines for both processes; only the CALT panel reveals that Q-learning lies consistently below the random baseline.

Figure 4: Coordination failure at $n=3$ (Type-B, IQF): Reward Fairness remains high for both Q-learning and the random baseline (0.909 vs. 0.969), while CALT exposes a severe deficit for Q-learning relative to random (0.146 vs. 0.359, a $-59.3\%$ relative drop), showing that a high, seemingly successful Reward Fairness value can co-occur with coordination well below chance.

Figure 5: CALT progression during Q-learning training (Type-B, IQF) for all five agent counts, with training progress normalized to $[0,1]$ episodes and each agent count’s random-policy baseline shown as a horizontal dotted line of matching color. Every curve rises during early exploration and then declines as $\epsilon$ decays toward exploitation, falling below its own random baseline well before training ends, so that learned policies converge to worse coordination than the early exploration phase achieved.

Agents	CALT	FALT	EALT	Efficiency (ILF / IQF)	Fairness
2	0.486	0.717	0.651	0.818 / 0.818	0.972
3	0.359	0.630	0.545	0.866 / 0.742	0.967
5	0.243	0.526	0.410	0.727 / 0.532	0.927
8	0.147	0.416	0.251	0.526 / 0.305	0.816
10	0.111	0.363	0.183	0.443 / 0.219	0.846

Table 4: Random Policy Baseline Performance (10,000 episodes per configuration; averaged across Type-A/B state representations). CALT, FALT, EALT, and Fairness are identical across ILF/IQF reward types: these metrics measure win/loss patterns independent of reward magnitudes. Only Efficiency reflects the reward structure, and from

n=3

onward it declines more sharply under IQF (tie reward

=r_{\mathrm{high}}/n^{2}

) as multi-agent ties become more frequent with

n

. Despite producing no temporal coordination, random policies achieve Fairness

\geq 0.816

and Efficiency

\geq 0.219

across all configurations.

Agents	Metric	Q-Learning	Random	Rel. Change (%)	Coord. Score (%)
2	CALT	0.322	0.486	-33.7%	-31.8%
	EALT	0.513	0.651	-21.2%	-39.6%
	AALT	0.284	0.435	-34.8%	-26.8%
	FALT	0.642	0.717	-10.5%	-26.8%
3	CALT	0.142	0.359	-60.3%	-33.7%
	EALT	0.203	0.545	-62.7%	-75.0%

Table 5: Q-Learning vs Random Baseline: Coordination Score Analysis (BASE=1000; Type-B state representation). All coordination scores are negative , indicating Q-learning performs worse than random baselines on every primary ALT metric across all agent counts. Coordination scores narrow as

n

increases because both Q-learning and random ALT values converge toward zero (see Supplementary Section S6); the magnitude of the gap is best interpreted via Table 6 . Relative Change:

(\text{QL}-\text{Random})/\text{Random}\times 100

. Coord. Score:

(\text{QL}-\text{Random})/(\text{Perfect}-\text{Random})\times 100

Agents	Reward	CALT (QL)	ALT Ratio	PA Equiv.	Performance
	Type			Agents	(% of Perfect)
2	ILF	0.3222	0.568	1.14	56.8%
2	IQF	0.3222	0.568	1.14	56.8%
3	ILF	0.1423	0.377	1.13	37.7%
3	IQF	0.1459	0.382	1.15	38.2%
5	ILF	0.0624	0.250	1.25	25.0%

Table 6: Perfect Alternation Equivalent Analysis (CALT, BASE=1000; Type-B state representation).

\text{ALT Ratio}=\sqrt{\text{CALT}}

(the fitted intercept of the benchmarking regression,

\sim\!2\times 10^{-10}

, is a numerical-precision artifact and is treated as zero);

\text{PA Equiv.}=n\times\text{ALT Ratio}

. IQF (tie reward

=r_{\mathrm{high}}/n^{2}

) consistently yields slightly higher CALT than ILF (tie reward

=r_{\mathrm{high}}/n

) at intermediate

n

: the lower tie incentive under IQF exerts marginally stronger pressure toward exclusive wins, improving coordination structure. However, the effect is small (

\Delta\leq 0.004

) and both reward structures produce a sharp degradation from

\sim

57% at

n=2

\sim

21% at

n\geq 8

, confirming that coordination failure is reward-structure-agnostic.

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 516 papers

May 14, 2026

Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies

Many multi-agent games and simulated environments involve several independent, often learning, agents repeatedly competing for a shared resource. Conventional fairness measures assess whether resources are shared equally overall, but cannot distinguish orderly turn-taking from irregular access patterns that produce long, unpredictable waiting times despite similar cumulative outcomes. We introduce Rotational Periodicity, a family of computationally efficient metrics combining two complementary measurements, the regularity of waiting times between successful accesses and the balance of access frequencies across agents. We evaluate them against a more detailed family of alternation metrics in a repeated threshold-congestion game, the Honey-Jar Game, in which two to ten reinforcement-learning agents compete for exclusive access to a shared high-value resource. Our experiments show that independently trained Q-learning agents often coordinate substantially worse than random-policy agents, even though conventional fairness metrics consistently report favourable outcomes. Every member of the family closely reproduces the rankings of the more computationally expensive alternation metrics, while computing six to twenty times faster as the number of agents grows. A direct timing study, which separates the two quantities that drive that cost, measures the advantage growing in proportion to the number of agents out to two thousand agents. These findings show that evaluating multi-agent learning systems requires temporally aware measures of coordination, not only aggregate outcomes, and that efficient proxies make this practical for larger multi-a

Nikolaos Al. Papadopoulos, Ismael Tito Freire, Marti Sanchez-Fibla +1

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece · Sorbonne Université, Institut des Systèmes Intelligents et de Robotique (ISIR), Paris, France · Universitat Pompeu Fabra, Department of Information and Communication Technologies, Barcelona, Spain

Multi-Agent Coordination Fair Resource Allocation Algorithmic Fairness Multi-Agent Resource Allocation Multi-Agent Systems

Ask PDF

Jun 11, 2026

$α$ -fair heterogeneous agent reinforcement learning

Cooperation in multi-agent systems is typically optimized through utilitarian objectives that maximize overall efficiency but fail to account for reward distribution, often resulting in inequitable "leader-follower" dynamics. While fairness-based approaches encourage pro-social behaviors where every agent benefits from cooperation, many current algorithms - including those utilizing reward shaping - break the stationarity of Markov Games or lack rigorous theoretical guarantees. This creates a critical gap between fair objective methods and theoretically safe learning frameworks. We propose a novel framework that bridges

α

-fairness with Heterogeneous-Agent Trust Region Learning (HATRL), ensuring monotonic improvement and convergence toward Nash Equilibria. Our approach leverages a fair advantage function that dynamically weights agent utilities based on their expected returns, allowing the global objective to transition from purely utilitarian efficiency to

α

-fairness welfare based on the parameter

α

. We introduce two practical algorithms,

α

-fair HATRPO and

α

-fair HAPPO, and demonstrate through experiments in sequential social dilemmas like CleanUp and CommonHarvest that they perform better than HATRL's algorithms from a utilitarian point of view while achieving socially higher outcomes.

Yao-hua Franck Xu, Tayeb Lemlouma, Jean-Marie Bonnin +1

Orange Innov Lannion, France · IRISA Université de Rennes Lannion, France · IRISA IMT Atlantique Rennes, France

Algorithmic Fairness Policy Optimization Trust Region Policy Optimization Cooperative MARL Multi-Agent Reinforcement Learning Heterogeneous MARL

Ask PDF

Jul 19, 2026

The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

The problem of fair multi-agent coordination in decentralized settings is one of the most pressing challenges for building efficient collaborative systems. Resource allocation is based on optimized collective arrangements accounting for agents' needs. Such coordination should not only be computationally efficient but also account for fairness, i.e., equitable redistribution of costs incurred by all agents. Recent literature has proposed several algorithms that efficiently determine optimal plan combinations balancing system-wide efficiency and individual discomfort of agents in a centralized setting. However, these works do not address equitable resource optimization in fully decentralized scenarios, specifically, the optimized redistribution of discomfort among coordinating agents so that none experiences a discomfort level that could lead to loss of incentive or polarization that can disrupt planned operations. In this work, we study the problem of optimizing three objectives: (i) system-wide efficiency, (ii) individuals' comfort and (iii) fairness (i.e., balancing of incurred discomfort costs) in decentralized multi-agent coordination. We design a novel model to optimize those three orthogonal objectives, without any substantial increase in communication and computational overhead. Through experiments on two real-world datasets, we validate the model and demonstrate that it can achieve fairer optimization outcomes, while satisfying agents' preferences and system goals.

Jovan Nikolic, Maciej Krzysztof Zuziak, Evangelos Pournaras

Google, Zurich, 8002 Zurich, Switzerland. · School of Computer Science, University of Leeds, Leeds, UK. · School of Energy Systems, LUT University, 53850 Lappeenranta, Finland

Multi-Agent Coordination Fair Resource Allocation Group Fairness Multi-Objective Optimization Decentralized Optimization

Ask PDF

Abstract

Multi-Agent Coordination

Explore similar work

Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies

ααα-fair heterogeneous agent reinforcement learning

The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

$α$ -fair heterogeneous agent reinforcement learning