The Coordination Gap: Alternation Metrics for Temporal Dynamics in Multi-Agent Battle of the Exes

• URL: http://arxiv.org/abs/2603.05789v2
• Date: Tue, 10 Mar 2026 19:21:45 GMT
• Title: The Coordination Gap: Alternation Metrics for Temporal Dynamics in Multi-Agent Battle of the Exes
• Abstract summary: We study a BoE-derived multi-agent variant of the Battle of the Exes as a Markov game.<n>We show that high aggregate payoffs can coexist with poor temporal coordination.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 against random-policy null processes, we uncover a clear measurement failure: despite exhibiting deceptively high traditional metrics (e.g., reward fairness often exceeding 0.9), learned policies perform up to 81% below random baselines under ALT-variant evaluation, a deficit already present in the two-agent case and intensifying as n grows. These results demonstrate, in this setting, that high aggregate payoffs can coexist with poor temporal coordination, and that conventional metrics may severely mischaracterize emergent dynamics. Our findings underscore the necessity of temporally aware observables for analyzing coordination in multi-agent games and highlight random-policy baselines as essential null processes for interpreting coordination outcomes relative to chance-level behavior.

Related papers

• When Does Hierarchy Help? Benchmarking Agent Coordination in Event-Driven Industrial Scheduling [7.912877527497326]
  DESBench is a benchmark for evaluating agent coordination in hierarchical event-driven scheduling.<n>We focus on four representative coordination paradigms: centralized, hierarchical, heterarchical, and holonic.
  arXiv  Detail & Related papers  (2026-05-13T08:33:28Z)
• Coordination Matters: Evaluation of Cooperative Multi-Agent Reinforcement Learning [1.9806597528054068]
  We propose a coordination-aware evaluation perspective that supplements return with process-level diagnostics.<n>We instantiate this perspective using STAT, a controlled commitment-constrained spatial task-allocation testbed.<n>Our results show that similar return trends can reflect distinct coordination mechanisms, including differences in redundant assignment, assignment diversity, and task-completion efficiency.
  arXiv  Detail & Related papers  (2026-05-07T16:50:53Z)
• Multimodal Learning on Low-Quality Data with Conformal Predictive Self-Calibration [72.0672328514289]
  Multimodal learning often grapples with the challenge of low-quality data.<n>We propose a unified framework, termed Conformal Predictive Self-Calibration.<n>Our framework consistently outperforms existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-05T14:48:52Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Probing Dec-POMDP Reasoning in Cooperative MARL [6.246549316580709]
  We introduce a diagnostic suite combining statistically grounded performance comparisons and information-theoretic probes.<n>We audit the behavioural complexity of baseline policies across 37 scenarios spanning MPE, SMAX, Overcooked, Hanabi, and MaBrax.<n>Our diagnostics reveal that success on these benchmarks rarely requires genuine Dec-POMDP reasoning.
  arXiv  Detail & Related papers  (2026-02-24T11:44:46Z)
• The Emergence of Lab-Driven Alignment Signatures: A Psychometric Framework for Auditing Latent Bias and Compounding Risk in Generative AI [0.0]
  This paper introduces a novel auditing framework to quantify latent trait estimation under ordinal uncertainty.<n>The research audits nine leading models across dimensions including Optimization Bias, Sycophancy, and Status-Quo Legitimization.
  arXiv  Detail & Related papers  (2026-02-19T06:56:01Z)
• A Generalized Adaptive Joint Learning Framework for High-Dimensional Time-Varying Models [0.8594140167290097]
  This article introduces Adaptive Joint Learning (AJL), a regularization framework designed to simultaneously perform functional variable selection and structural changepoint detection.<n>The analysis uncovers synchronized phase transitions in disease progression and identifies a parsimonious set of time-varying prognostic markers.
  arXiv  Detail & Related papers  (2026-01-08T02:07:49Z)
• Adaptive Accountability in Networked MAS: Tracing and Mitigating Emergent Norms at Scale [2.28438857884398]
  Large-scale networked multi-agent systems increasingly underpin critical infrastructure.<n>We introduce an adaptive accountability framework that traces responsibility flows through a lifecycle-aware audit ledger.<n>We prove a bounded-compromise theorem showing that whenever the expected intervention cost exceeds an adversary's payoff, the long-run proportion of compromised interactions is bounded by a constant strictly less than one.
  arXiv  Detail & Related papers  (2025-12-21T02:04:47Z)
• Efficient Thought Space Exploration through Strategic Intervention [54.35208611253168]
  We propose a novel Hint-Practice Reasoning (HPR) framework that operationalizes this insight through two synergistic components.<n>The framework's core innovation lies in Distributional Inconsistency Reduction (DIR), which dynamically identifies intervention points.<n> Experiments across arithmetic and commonsense reasoning benchmarks demonstrate HPR's state-of-the-art efficiency-accuracy tradeoffs.
  arXiv  Detail & Related papers  (2025-11-13T07:26:01Z)
• Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning [56.87989363424]
  We show that a low-rank structure naturally emerges in the shifted successor measure.<n>We quantify the amount of shift needed for effective low-rank approximation and estimation.
  arXiv  Detail & Related papers  (2025-09-05T15:48:20Z)
• Offline Multi-agent Reinforcement Learning via Score Decomposition [51.23590397383217]
  offline cooperative multi-agent reinforcement learning (MARL) faces unique challenges due to distributional shifts.<n>This work is the first work to explicitly address the distributional gap between offline and online MARL.
  arXiv  Detail & Related papers  (2025-05-09T11:42:31Z)
• Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis [55.13545823385091]
  Federated reinforcement learning (FedRL) enables collaborative learning while preserving data privacy by preventing direct data exchange between agents.<n>In real-world applications, each agent may experience slightly different transition dynamics, leading to inherent model mismatches.<n>We show that even moderate levels of information sharing significantly mitigate environment-specific errors.
  arXiv  Detail & Related papers  (2025-03-21T18:06:28Z)
• Time-series Generation by Contrastive Imitation [87.51882102248395]
  We study a generative framework that seeks to combine the strengths of both: Motivated by a moment-matching objective to mitigate compounding error, we optimize a local (but forward-looking) transition policy. At inference, the learned policy serves as the generator for iterative sampling, and the learned energy serves as a trajectory-level measure for evaluating sample quality.
  arXiv  Detail & Related papers  (2023-11-02T16:45:25Z)
• DSDF: An approach to handle stochastic agents in collaborative multi-agent reinforcement learning [0.0]
  We show how thisity of agents, which could be a result of malfunction or aging of robots, can add to the uncertainty in coordination. Our solution, DSDF which tunes the discounted factor for the agents according to uncertainty and use the values to update the utility networks of individual agents.
  arXiv  Detail & Related papers  (2021-09-14T12:02:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.