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

Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies
May 14, 2026Nikolaos Al. Papadopoulos, Ismael Tito Freire, Marti Sanchez-Fibla +1Multi-Agent Coordination Fair Resource Allocation
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
$α$ -fair heterogeneous agent reinforcement learning
Jun 11, 2026Yao-hua Franck Xu, Tayeb Lemlouma, Jean-Marie Bonnin +1Algorithmic Fairness Policy Optimization
Orange Innov Lannion, France · IRISA Université de Rennes Lannion, France · IRISA IMT Atlantique Rennes, France
The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination
Jul 19, 2026Jovan Nikolic, Maciej Krzysztof Zuziak, Evangelos PournarasMulti-Agent Coordination Fair Resource Allocation
Google, Zurich, 8002 Zurich, Switzerland. · School of Computer Science, University of Leeds, Leeds, UK. · School of Energy Systems, LUT University, 53850 Lappeenranta, Finland

May 14, 2026J/K move · Enter open · S save

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

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

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

Open paper AskPDF arXiv

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

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