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

Computer Science > Multiagent Systems arXiv:2603.05789 (cs) [Submitted on 6 Mar 2026 (v1), last revised 21 Mar 2026 (this version, v4)] Title:The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games Authors:Nikolaos Al. Papadopoulos, Konstantinos Psannis View a PDF of the paper titled The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games, by Nikolaos Al. Papadopoulos and 1 other authors View PDF HTML (experimental) Abstract:Multi-agent coordination dilemmas expose a fundamental tension between individual optimization and collective welfare, yet characterizing such coordination requires metrics sensitive to temporal structure and collective dynamics. As a diagnostic testbed, we study a BoE-derived multi-agent variant of the Battle of the Exes, formalizing it as a Markov game in which turn-taking emerges as a periodic coordination regime. Conventional outcome-based metrics (e.g., efficiency and min/max fairness) are temporally blind (they cannot distinguish structured alternation from monopolistic or random access patterns) and fairness ratios lose discriminative power as n grows, obscuring inequities. To address this limitation, we introduce Perfect Alternation (PA) as a reference coordination regime and propose six novel Alternation (ALT) metrics designed as temporally sensitive observables of coordination quality. Using Q-learning agents as a minimal adaptive diagnostic baseline, and comparing ag...