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

Abstract:Many intelligent computing and autonomous systems rely on multiple independent, often learning, agents repeatedly sharing a limited resource. Examples include autonomous robots accessing a shared workstation, wireless devices competing for communication opportunities, and distributed AI agents coordinating access to shared computational resources. While conventional fairness measures assess whether resources are shared equally overall, they cannot distinguish orderly turn-taking from irregular access patterns that produce long and unpredictable waiting times despite similar cumulative outcomes. We introduce Rotational Periodicity (RP), a computationally efficient metric that evaluates both the regularity of waiting times between successful accesses and the balance of access frequencies across agents. We evaluate RP alongside a family of more detailed alternation metrics using a repeated threshold-congestion game in which two to ten reinforcement-learning agents compete for exclusive access to a shared resource. Our experiments reveal that independently trained agents often coordinate substantially worse than random-policy agents, even though conventional fairness metrics consistently report highly favourable outcomes. At the same time, RP closely reproduces the rankings of the more computationally expensive alternation metrics while computing twelve to twenty-five times faster as the number of agents increases. These findings show that evaluating multi-agent learning systems requires temporally aware measures of coordination, not only aggregate outcomes, and that efficient proxy metrics such as RP make this type of evaluation practical for larger intelligent computing systems.

Multiagent Systems (cs.MA); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

I.2.11; F.2.2; J.4

arXiv:2605.14879 [cs.MA]

(or arXiv:2605.14879v2 [cs.MA] for this version)

https://doi.org/10.48550/arXiv.2605.14879 Focus to learn more arXiv-issued DOI via DataCite

supplementary_materials.pdf

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.