A credit-based arbitration mechanism with finite-time fairness guarantees for autonomous multi-agent systems

Abstract

This paper addresses repeated unfairness in multi-robot coordination, where the same agents may repeatedly yield at shared bottlenecks, leading to missed deadlines, reduced throughput, and safety violations. The purpose is to propose a lightweight arbitration mechanism that guarantees bounded unfairness for autonomous agents in warehouse logistics and urban unmanned systems. Each robot maintains a bounded local credit state that increases after yielding and decreases after passing. During every contention event, robots are ranked according to their credit values, with deterministic ID-based tie-breaking used when credits are equal. A finite-time theoretical analysis is developed to derive an explicit worst-case bound on cumulative cost disparity between any pair of robots. The proposed method is evaluated through numerical simulations involving corridor- and intersection-style contention scenarios and is further validated through deployment on a TI LaunchXL-F28379D embedded controller. Experimental measurements demonstrate an average execution latency of 2.738 µs over 1,000 arbitration events, confirming the feasibility of real-time edge deployment. The proposed mechanism guarantees that the cumulative cost difference between any two robots remains uniformly bounded regardless of interaction history, preventing persistent unfairness and starvation. Simulation results demonstrate lower unfairness than representative baseline methods while requiring only a bounded integer credit state and minimal communication, making the approach suitable for practical warehouse and autonomous traffic applications. Unlike existing approaches that provide fairness only in expectation or at equilibrium, this work provides a deterministic finite-time worst-case fairness guarantee that holds for every agent at every moment. The mechanism is parameter-insensitive, requires minimal communication, and integrates into existing robot software stacks without hardware modifications, offering practical value for real-world unmanned systems.