The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address \emph{efficient learning}, measured by Pareto regret, and incorporate \emph{fair learning} as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop \textsc{Pareto UCB1 Gossip}, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose \textsc{Simulated NSW UCB Gossip}, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that \textsc{Pareto UCB1 Gossip} achieves $\mathcal{O}(\log T)$ regret and an instance-independent rate of $\mathcal{O}(\sqrt{T})$, while \textsc{Simulated NSW UCB Gossip} achieves an instance-independent regret bound of $\mathcal{O}(T^{3/4})$. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately $100\%$ and $50\%$ in the efficiency and fairness settings, respectively.

A plethora real-world environments require agents to compete repeatedly for the same limited resource, calling for a temporal notion of fairness judged across entire interaction histories. This paper advances the theory of temporal fair division by introducing Rotational Periodicity (RP), a family of lightweight metrics, alongside the ALT family of sliding-window measures, within a unified framework for repeated multi-agent resource competition. We formalise the Multi-Agent Battle of the Exes (MBoE) as a repeated fair division instance and establish Perfect Alternation (PA) as its canonical temporally fair solution, drawing connections to proportionality, envy-freeness, and n-periodic round-robin allocation. RP decomposes temporal fairness into two complementary sub-measures: Rotational Score (RS) and Waiting Periods Evaluation (WPE), achieving O(nu+n) time complexity versus the O(nu*n) of ALT, where nu is the episode count and n the agent count. Empirical evaluation across n in {2,3,5,8,10} reveals three findings. First, both RP and ALT expose a coordination failure invisible to traditional metrics: Q-learning agents perform worse than random policies by 10-73% on RP and 7-35% on CALT, while Reward Fairness remains misleadingly high (above 0.92 for n>=3). Second, RP achieves 12-25x computational speedup over ALT, growing with n. Third, the two families are complementary: ALT provides richer discrimination for small populations; RP scales reliably where ALT becomes intractable. Together they form a diagnostic toolkit for temporal fair division.

Coordination research collapses four objects: operative control, authorization, a model-derived friction score, and observed outcomes. The Axiom of Consent is a stake-weighted unanimity principle; majority and supermajority thresholds are explicit relaxations, not versions of the axiom. Decision loci are structural facts, whereas authorization and legitimacy require normative and measurement premises. Alignment, calibrated stakes, and information deficit are candidate coordinates, and F = sigma(1 + epsilon)/(1 + alpha) is a phenomenological ansatz. The Replicator-Optimization Mechanism supplies a conditional persistence interface: irreducibility suffices for its finite, static, positive-fitness continuous-time Perron result; primitivity is required only for the corresponding discrete-time power convergence, and the componentwise ranking is narrower. Neither persistence result derives authorization. A resource-allocation instantiation specifies an identification contract but observes no authorization acts or effective voice. Its exploratory MARL companion uses target-vector correlation and observation noise as narrow proxy treatments, not measures of general alignment or information deficit. Under that proxy and reward-gap design, the composite loses to an independent-effects model and a feasible-centred frozen crossing yields the opposite interaction direction. Cooperative target correlation lowers the gap under shared-state contention; separable IQL is structurally invariant and separable VDN is a non-detection. Paired partial sharing modulates the gradient without establishing an exact dose law or endpoint equivalence. Target support changes opposition and residual-policy conclusions. The surviving contribution is an authorization architecture and measurement discipline, not a universal friction law.