Learning to Contest: Decentralized Robust Fairness
in Cooperative MARL via Cross-Attention
June 04, 2026
Abstract
Fair cooperative multi-agent reinforcement learning (MARL) teams that maximize an egalitarian welfare are exploitable: a single self-interested agent free-rides on the surplus that fair agents forgo to raise the worst-off. A centralized need-based allocator removes the exploit, but only by taking allocation out of the agents’ hands; whether decentralized policies can be robust was left open. We show that the futility of a decentralized defense is an artifact of all-or-nothing contention. Under graded contention—where a contested resource still delivers a fraction \(1{-}c\) and wastes \(c\)—we prove that for any \(c<1\) a worst-off cooperator that contests a free-rider strictly improves on yielding, so decentralized leverage exists (Prop. 1). Realizing it, however, requires solving a coordination problem under uncertainty: the number of free-riders is unknown and variable, so any fixed rule is dominated (always-contest wastes \(c\) when nobody defects; always-yield collapses when someone does). We introduce CAN, a permutation-equivariant cross-attention policy over agents’ observed behaviour that infers how many free-riders are present and responds proportionally—turn-taking when none, contesting just enough when some. Trained against an adversarial league (PSRO), CAN keeps best-response exploitability low (\(\rho{\approx}1.2\)–\(1.5\), vs.\(\rho{=}N\) unprotected) across the full contention range while wasting essentially nothing when no free-rider is present (efficiency \({\approx}1.0\) vs.the \(1{-}c\) of always-contest) and retaining most of that efficiency even with a free-rider present (\(D{\ge}1\) efficiency \(0.83\)–\(0.96\), so its robustness is not bought with waste), thereby approaching the centralized oracle on both axes without a central allocator. On the same game the fair-MARL learners fail on complementary axes—GGF/FEN learn to yield and are exploitable (\(\rho{\approx}N\)), SOTO learns to all-contest and is wasteful (waste \(c\))—while CAN is the only method that is both robust and efficient. On two further games we find a clear scope rather than blanket generality: CAN stays efficient (\(D{=}0\) efficiency \(0.94\)–\(1.0\)) and Pareto-dominates the welfare-fair learners throughout, but its robustness holds only in proportion to the contest leverage a game provides—strong on a multi-server game, partial when leverage weakens (high-value, high-contention steps), and absent under a winner-take-all rule where Prop. 1 fails. We further report where the approach is fragile—weak leverage and zero-shot transfer to much larger teams both degrade it at high contention—giving an honest account of how far decentralized robust fairness currently reaches.
multi-agent reinforcement learning, fairness, exploitability, cross-attention, decentralized execution, league training
1 Introduction↩︎
Cooperative multi-agent reinforcement learning (MARL) increasingly optimizes not only efficiency but fairness: methods such as FEN [1] and SOTO [2] maximize a fairness-inducing welfare (typically the Generalized Gini Welfare [3]) over agents’ returns so that no agent is starved. These methods assume every agent cooperates in being fair. When one does not—one stakeholder upgrades a controller to minimize its own delay, one client maximizes its own throughput—the fair team is exploitable: because team-oriented agents sacrifice their own utility to raise the worst-off, a self-interested agent free-rides on that sacrifice [4]. In a strictly rivalrous (all-or-nothing) resource—where a contested unit is either won by one agent or wasted—this exploit is hard to defend against at the policy level: a cooperator that contests a free-rider merely causes a collision, gaining nothing, so a welfare-fair team is indifferent between yielding and contesting; a recent study formalizes this futility and the centralized need-based remedy that sidesteps it [5]. The robust remedy is then to take allocation out of the agents’ hands entirely, via a centralized need-based mechanism. This paper takes up the harder question that centralization sidesteps: can decentralized policies—acting only on local, observed information—retain fairness under a self-interested agent?
We answer affirmatively, with caveats, in three steps.
(1) Leverage exists once contention is graded. The policy-level futility above hinges on all-or-nothing contention: a contested resource is either won by one agent or wasted, so a cooperator that contests a free-rider gains nothing. We introduce a graded-contention game in which \(m\ge 2\) claimers split a fraction \(1{-}c\) of the resource (waste \(c\)). We prove (Prop. 1) that for any \(c<1\) a worst-off cooperator that contests a lone free-rider receives \((1{-}c)/2>0\) instead of \(0\), so contesting strictly dominates yielding: decentralized leverage reappears. All-or-nothing is the limiting case \(c{=}1\).
(2) The residual difficulty is coordination under uncertainty. Leverage is not a policy. The number of free-riders \(D\) is unknown and varies episode to episode (including \(D{=}0\)). A fixed rule cannot win: always-contest pays the waste \(c\) even when nobody defects, and always-yield collapses the moment someone does. A robust cooperator must infer \(D\) from observed behaviour and respond proportionally—do nothing (turn-take) when \(D{=}0\), contest just enough when \(D\ge 1\).
(3) A cross-attention policy, trained against a league, realizes it. We introduce CAN (Cross-Attention Networks), a shared, permutation-equivariant policy in which each agent attends over the observed behaviour of all agents (utilities, claim-rates, who is worst-off) to estimate contention and act. What is load-bearing is behaviour-conditioning with adaptive aggregation—the response must depend on how many others are grabbing, not on fixed identities—and among permutation-respecting aggregators cross-attention is the most stable instance (Sec. 5.7). We train CAN against an adversarial league (PSRO [6]) and audit it with a fresh best-response defector. CAN keeps exploitability low (\(\rho{\approx}1.2\)–\(1.5\)) across all contention levels while wasting essentially nothing when no free-rider is present (efficiency \({\approx}1.0\)), approaching the centralized oracle without any central allocator.
We are deliberate about limits. We report a negative-leaning result—single adversary co-training is unreliable at low contention—and a genuine fragility: zero-shot transfer of an \(N{=}6\) policy to teams of \(12\) and \(24\) holds at low contention but degrades at high contention. The contribution is a controlled, honest map of how far decentralized robust fairness reaches, not a claim that the decentralization gap is closed.
2 Background and Related Work↩︎
Welfare-based fair MARL. Given per-agent returns \(\mathbf{u}=(u_1,\dots,u_N)\), fair-MARL maximizes a Schur-concave welfare \(W(\mathbf{u})\) that is increasing (efficiency) and favours equity, e.g.the Generalized Gini Welfare \(W(\mathbf{u})=\sum_k w_k u^{\uparrow}_k\) with decreasing weights \(w_k\) so the worst-off agent dominates [3]. FEN [1] and SOTO [2] are representative learners. These objectives create the appropriable surplus we must defend.
Exploitability and the decentralization gap. The vulnerability is a fairness-specific instance of free-riding in sequential social dilemmas [7]; that welfare-maximizing cooperation is gameable in general was noted by Ivanov et al. [4], who restore cooperation through an incentive-compatible mediator. Under strictly rivalrous (all-or-nothing) contention, policy-level reciprocity has no efficient lever, and a centralized need-based allocator—which decides who receives each resource—is an upper bound on fairness that any decentralized method should aim to match [5]. We take that target seriously and pursue the decentralized side it leaves open.
Reciprocity and conditional cooperation. Inequity aversion [8] and learned reciprocity [9] make cooperation conditional on others’ behaviour in social dilemmas. Our cooperators are likewise behaviour-conditioned, but the obstacle here is sharper: under all-or-nothing contention reciprocity has no efficient lever at all; we show graded contention restores one and that a learned attention policy can exploit it.
Attention in MARL. Attention over agents is well established for value/critic mixing and communication, e.g.actor-attention critics [10] and the centralized critics of MADDPG [11]. We use a single-head self-attention block [12] in the decentralized policy over observed behaviour tokens; its role is contention inference, and its permutation-equivariance gives a single \(N\)-agnostic policy that can be evaluated at unseen team sizes.
League / population training. Training against a growing population of past best responses—fictitious play [13] and PSRO [6]—yields policies robust to a history of adversaries rather than to a single co-evolving one. We use it to stabilize the cooperator against the worst free-rider it has seen, which we find is what makes robustness consistent across contention levels.
3 The Graded-Contention Game↩︎
Game. \(N\) agents act over \(T\) steps. Each step every agent chooses Claim (\(1\), the self-interested act) or Yield (\(0\)). Let \(\mathbf{u}\ge 0\) accumulate the resource each agent has collected and let \(m\) be the number of claimers this step. The unit resource is allocated by the graded-contention rule \[g(m)=\begin{cases} 1 & m=1,\\[2pt] (1{-}c)\,/\,m & m\ge 2,\\[2pt] \text{routed to the worst-off agent} & m=0, \end{cases}\] where each claimer receives \(g(m)\) and \(c\in[0,1]\) is the contention waste. A sole claimer wins the whole unit; \(m\ge 2\) claimers split a discounted \(1{-}c\); if nobody claims, the resource flows (losslessly) to the worst-off agent. The parameter \(c\) interpolates from lossless sharing (\(c{=}0\)) to the all-or-nothing model (\(c{=}1\), where contesting destroys the resource).
Threat model. Each episode, each agent is independently a defector with some probability, so the number of free-riders \(D\) is variable and unknown (including \(D{=}0\)); defectors always claim. The remaining cooperators share one policy and seek to keep the allocation fair and efficient. We audit a trained cooperator policy by freezing it and training a fresh best-response defector to maximize its own utility—an exploitability test stronger than a fixed always-claim adversary.
Bounded free-ride metric. We measure exploitation by the free-ride factor of the defector group: its share of the delivered total, normalized by its fair share \(n_{\mathrm{def}}/N\), \[\rho \;=\; \frac{N\,\sum_{i\in\mathcal{D}} u_i}{\,n_{\mathrm{def}}\,\sum_{j} u_j\,}\;\in\;[0,\,N/n_{\mathrm{def}}], \label{eq:rho}\tag{1}\] where \(\mathcal{D}\) is the defector set. \(\rho{=}1\) is exactly fair; \(\rho{=}N\) means a lone defector took everything. Eq. 1 is bounded by construction, unlike the naive ratio of defector utility to mean-cooperator utility, which diverges when cooperators are starved as \(c\to1\); the delivered total is always positive, so \(\rho\) stays in range and is comparable across \(c\). We also report Jain’s index [14] and efficiency (delivered\(/T\)).
Leverage. Under all-or-nothing contention (\(c{=}1\)) a cooperator cannot deny a free-rider except by wasteful levelling-down—contesting collides and destroys the unit—so a welfare-fair team is indifferent between yielding and contesting and has no efficient defense. Graded contention breaks that premise.
Proposition 1 (Decentralized leverage under graded contention). Fix \(c<1\) and a step at which a single free-rider claims. Let a worst-off cooperator choose Claim rather than Yield. Then the cooperator’s received resource rises from \(0\) to \((1{-}c)/2>0\), while the free-rider’s falls from \(1\) to \((1{-}c)/2\). Hence contesting strictly dominates* yielding for the worst-off cooperator, and strictly reduces the free-rider’s appropriated surplus.*
Proof. If the worst-off cooperator yields, the free-rider is the sole claimer (\(m{=}1\)), receives \(g(1){=}1\), and the cooperator receives \(0\). If the cooperator contests, \(m{=}2\) and each receives \(g(2){=}(1{-}c)/2\). Since \(c<1\), \((1{-}c)/2>0\), so the cooperator strictly gains and the free-rider strictly loses. \(\square\)
The dominant action is also objective-aligned: lifting the worst-off cooperator from \(0\) to \((1{-}c)/2\) raises the cooperator mean and lowers their spread, so it strictly increases the training welfare \(W_{\mathrm{coop}}{=}\mathrm{mean}{-}\mathrm{std}\) (Sec. IV). Contesting is thus rewarded both at the level of the individual worst-off agent and of the team objective.
Proposition 1 establishes that the lever exists for every \(c<1\); it does not say how to pull it. The cooperator must contest only when a free-rider is present (else it pays the waste \(c\) for nothing) and only enough cooperators must contest (over-contesting wastes; under-contesting leaves surplus). Because \(D\) is unknown and variable, this is an inference-and-coordination problem, which motivates a behaviour-conditioned learned policy.
4 Method: Cross-Attention Networks (CAN)↩︎
Observed-behaviour tokens. At step \(t\) each agent \(i\) is represented by a token of six features computable from public state—no access to others’ intentions or rewards: \[\textstyle x_i=\Big[\tfrac{u_i}{T},\,\tfrac{u_i-\bar u}{T},\,\tfrac{u_i-u_{\min}}{T},\, \mathbf{1}[u_i{=}u_{\min}],\,\tfrac{c\!c_i}{t},\,\tfrac{t}{T}\Big],\] where \(\bar u,u_{\min}\) are the team mean/min utilities and \(cc_i/t\) is agent \(i\)’s running claim-rate. The claim-rate channel is what lets a cooperator estimate how many others are grabbing.
Architecture. CAN is a single-head self-attention block over the \(N\) tokens: with \(Q,K,V\) linear projections of \(\{x_i\}\), \(\mathrm{ctx}=\mathrm{softmax}(QK^\top/\sqrt{d})V\); each agent concatenates its token with its context, passes a \(\tanh\) layer, and outputs Claim/Yield logits (Fig. 1a). The block is shared by all cooperators and permutation-equivariant, so (i) the policy is decentralized—agent \(i\) acts on the public tokens, no central allocator decides the allocation—and (ii) it is \(N\)-agnostic, enabling zero-shot evaluation at unseen team sizes.
Cooperator objective. Cooperators maximize a per-step welfare reward-to-go with welfare \[W_{\mathrm{coop}}=\mathrm{mean}_{i\in\mathcal{C}}(u_i)-\mathrm{std}_{i\in\mathcal{C}}(u_i),\] over cooperators \(\mathcal{C}\): the mean term rewards reclaiming utility from a free-rider (contest when \(D\ge1\)), the std term rewards turn-taking (share evenly), and doing nothing when \(D{=}0\) avoids the waste \(c\). Training is REINFORCE with an annealed entropy bonus; the defector(s) during training draw \(D\sim\mathrm{Unif}\{0, \dots,d_{\max}\}\) per episode so the policy sees a variable, unknown adversary count.
Training schemes. We compare three ways to provide the adversary, holding the cooperator architecture fixed: (i) single co-training—cooperators and one co-evolving defector policy trained together; (ii) population co-training—a population of \(K{=}4\) co-evolving defectors, one assigned per episode; (iii) league (PSRO) [6]—alternate training the cooperators against the frozen pool of all past best-response defectors and adding a fresh best response to the pool (Fig. 1b). League training targets the multi-equilibrium fragility of single co-training: the cooperator becomes robust to the whole adversary history rather than to one moving target.
Baselines and oracle. Two fixed scripts bracket the problem: all-contest (everyone always claims; \(\rho{\approx}1\) but efficiency \(1{-}c\)) and yield (cooperators always yield; efficiency \(1\) but \(\rho{=}N\)). The centralized oracle allocates by need (worst-off first), achieving \(\rho{=}1\) at efficiency \(1\)—the unbeatable upper bound a decentralized policy aims to approach.
5 Experiments↩︎
Setup. Unless noted, \(N{=}6\), \(T{=}100\), \(d_{\max}{=}2\), \(c\in\{0.3,0.5,0.7,0.9\}\), \(5\) seeds; all policies are shared single-head cross-attention nets (hidden \(64\)) trained with REINFORCE/Adam (lr \(3\times10^{-3}\), \(B{=}512\) parallel episodes). Every reported policy is audited by a freshly trained best-response defector (Eq. 1 ). Implementation details are in the appendix.
5.1 Head-to-head with fair-MARL learners↩︎
We first place CAN against the welfare-fair learners that motivate the problem, on the same graded-contention game and under the same bounded audit: a shared-policy GGF maximizer, a faithful SOTO (Self-/Team-Oriented sub-nets, annealing \(\beta{:}1{\to}0\)) [2], and a FEN-style learner whose agents maximize the fair-efficient reward \(\bar u/(c_0{+}|u_i{-}\bar u|)\) [1]. All three see the same six behaviour features and are trained cooperatively (no defector at train time, as in their originals); we then freeze each team and train a best-response defector. This comparison is therefore fair-as-published vs.robust-by-design: it isolates whether the fair objective alone confers robustness (it does not), not whether these objectives could be hardened by adversarial training. The training axis itself— cooperative vs.league—is isolated separately in Sec. 5.6 on CAN’s own architecture.
The result is a clean two-axis separation (Fig. 2, Table 1). Every fair learner is fair at \(D{=}0\) (Jain \({\approx}1.0\)), but each collapses onto one of the two scripted extremes and fails on one axis. GGF learns to yield: efficient (\(D{=}0\) eff.\(1.00\)) but maximally exploitable (\(\rho{=}6{=}N\) at every \(c\)—a lone defector takes everything). SOTO learns to all-contest: robust (\(\rho{=}1.0\)) but wasteful—its \(D{=}0\) efficiency is exactly \(1{-}c\) (down to \(0.10\) at \(c{=}0.9\)), because its “be selfish first, then anneal to fair” schedule settles in a fair-by-symmetry but resource-destroying equilibrium. FEN is unstable, landing in either bad corner depending on seed and \(c\) (at \(c{=}0.5\) most seeds learn yield, \(\rho{\approx}5.9\), a minority all-contest, \(\rho{=}1.0\), giving a high-variance mean); its fair-efficient reward does not reliably resolve the tradeoff. CAN is the only method in the good corner: efficient (\(0.98\)) and robust (\(\rho{=}1.2\)–\(1.5\)), clustered beside the centralized oracle. The remaining experiments isolate the two properties that put it there.
| Method | \(D{=}0\) eff. | best-resp.\(\rho\) | outcome |
|---|---|---|---|
| GGF (welfare) | \(1.00\) | \(6.0\) | efficient, exploitable |
| FEN | \(0.68\)–\(0.98\) | \(3.0\)–\(6.0\) | unstable, mostly exploitable |
| SOTO | \(1{-}c\) | \(1.0\) | robust, wasteful |
| CAN (league) | \(\mathbf{0.98}\) | \(\mathbf{1.2}\)–\(\mathbf{1.5}\) | both |
| centralized oracle | \(1.00\) | \(1.0\) | (upper bound) |
5.2 Efficiency when no free-rider is present↩︎
A robust cooperator must not pay for a defense it does not need. Fig. 3 shows the \(D{=}0\) efficiency of CAN against the fixed all-contest script. CAN delivers \(0.99\)–\(1.00\) of the resource at every contention level, whereas all-contest delivers only \(1{-}c\) (down to \(0.10\) at \(c{=}0.9\)). Because CAN turn-takes when it detects no free-rider, it incurs essentially no contention waste—matching the centralized oracle on efficiency. This is the half of the problem fixed rules cannot get right.
5.3 Efficiency under a defector: is robustness free?↩︎
\(D{=}0\) is the easy case. The axis where a decentralized policy could lose to the centralized oracle—which delivers \(\rho{=}1\) and efficiency \(1\) simultaneously—is efficiency with a free-rider present, since contesting forces \(m\ge2\) and delivers only \(1{-}c\) on contested steps; in principle a policy could buy a low \(\rho\) at \(c{=}0.9\) by contesting so hard that it wastes as much as the all-contest equilibrium it is meant to beat. It does not. Under the best-response defector, league-trained CAN keeps \(D{\ge}1\) efficiency at \(0.88\), \(0.88\), \(0.83\), \(0.96\) for \(c{=}0.3,0.5,0.7,0.9\) (pooled over \(10\) seed-runs)—at the hardest setting it delivers \(0.96\) versus the all-contest equilibrium’s \(1{-}c{=}0.10\). CAN contests selectively (just enough, and mostly via turn-taking rather than collisions), so its robustness is essentially free: it sits near the oracle on both axes even with a defector present, where SOTO reaches \(\rho{=}1\) only by destroying \(90\%\) of the resource. A residual gap to the oracle remains (efficiency \(<1\)), as expected for a decentralized policy, but it is small, not the structural \(1{-}c\) collapse.
5.4 Robustness across the contention range↩︎
Fig. 4 and Table 2 report best-response exploitability \(\rho\) vs.\(c\) for CAN trained with vanilla co-training (against a fixed always-claim adversary) versus league (PSRO) training (against a growing pool of learned exploiters; to average over run-to-run variance we pool three independent gen-6 league runs, \(15\) seed-runs per \(c\)). League training keeps \(\rho\) low across the entire range (\(1.20\)–\(1.51\)), far below the vanilla co-trained policy (\(1.90\)–\(2.24\)) and well below the unprotected \(\rho{=}N{=}6\). It is in fact most robust at the highest contention (\(\rho{=}1.20\) at \(c{=}0.9\), the lowest point)—consistent with leverage: at higher waste a single contest caps the free-rider’s per-step take at \((1{-}c)/2\), so targeted contention denies it more effectively (Prop. 1). Vanilla co-training shows the opposite drift, rising to \(2.24\): training against a static adversary does not teach when to contest. Training against a learned exploiter is what converts the existence of leverage (Prop. 1) into robustness.
| \(c\) | 0.3 | 0.5 | 0.7 | 0.9 |
|---|---|---|---|---|
| vanilla co-train | \(1.90\) | \(2.03\) | \(2.06\) | \(2.24\) |
| [1.83,1.96] | [1.98,2.09] | [1.97,2.15] | [2.07,2.42] | |
| CAN (league) | \(1.33\) | \(1.36\) | \(1.51\) | \(\mathbf{1.20}\) |
| [1.26,1.42] | [1.22,1.53] | [1.25,1.85] | [1.10,1.32] |
5.5 Larger \(d_{\max}\) and defector coalitions↩︎
The main results cap the per-episode defector count at \(d_{\max}{=}2\), an easy “0/1/2 grabbers” inference. We stress this by training CAN with \(d_{\max}{=}4\) (up to four of six defecting) and auditing against a best-response coalition of \(D\) defectors sharing one policy. CAN remains robust at all \(c\) and \(D\) (Table 3): the worst case is a lone free-rider (\(\rho{=}1.13\)–\(1.60\), comparable to the \(d_{\max}{=}2\) results), and larger coalitions are easier—\(\rho{\to}1.0\) for \(D{\ge}2\)—because with more agents defecting there is less cooperative surplus to appropriate. The harder inference and coordinated free-riders thus do not break the policy.
| \(c\) | \(D{=}1\) | \(D{=}2\) | \(D{=}3\) |
|---|---|---|---|
| 0.3 | 1.22 | 1.11 | 1.07 |
| 0.5 | 1.13 | 1.00 | 1.00 |
| 0.7 | 1.51 | 1.00 | 1.00 |
| 0.9 | 1.60 | 1.05 | 1.00 |
5.6 Choice of adversarial training scheme↩︎
Does the result depend on the league specifically? Fig. 5 compares three adversarial schemes—single co-training (one co-evolving defector), population co-training (\(K{=}4\) defectors), and the league—at the two lower contention levels, per seed. The schemes are statistically indistinguishable: at \(c{=}0.3\) all three average \(\rho{\approx}1.48\), and at \(c{=}0.5\) they span \(1.18\)–\(1.46\) with overlapping CIs. What carries the result is that the cooperator is trained against a learned, adapting exploiter at all: every adversarial scheme lands near \(\rho{=}1.2\)–\(1.5\), versus \(1.8\)–\(2.2\) for the static-adversary vanilla baseline (Table 2). We adopt the league for its robustness to the whole adversary history, but the headline robustness is not an artifact of that choice.
5.7 What is load-bearing? Architecture ablation↩︎
Is the win the attention, or just behaviour-conditioning with some adaptive aggregation? We test this by replacing the cross-attention block with three alternative aggregators of the same behaviour tokens, under identical league training and the same best-response audit: a mean-pool policy (each agent conditions on its token and the mean of all tokens), a deep-sets policy (mean-pool of a learned per-agent embedding), and a bidirectional GRU over the agent tokens. Table 4 reports best-response \(\rho\) (mean over \(c\), 5 seeds).
The clear conclusion is that aggregation matters but pooling is not enough: the mean-pool and deep-sets policies are markedly more exploitable than CAN (\(\rho{=}1.78,1.75\) vs.\(1.37\)), so the natural objection “a permutation-equivariant pool should already match attention” does not hold. The gap to the strongest alternative is narrower and we do not overstate it: the bidirectional GRU is competitive on the mean (\(1.56\) vs.\(1.37\)) and even better at low \(c\), so we credit behaviour-conditioning plus adaptive aggregation, not attention per se. Where cross-attention earns its place is stability: at the hardest contention (\(c{=}0.9\)) CAN holds \(\rho{=}1.16{\pm}0.20\) while the GRU is erratic (\(1.99{\pm}1.50\)), so attention is the most stable instance of the family rather than categorically superior. These comparisons are at the deployed training budget; we found that under a lighter budget the CAN–GRU ranking reverses, underscoring that architecture ablations must use the budget at which the method is actually trained.
| Policy (aggregator) | best-resp.\(\rho\) | \(\rho\) at \(c{=}0.9\) |
|---|---|---|
| mean-pool\(^\dagger\) | 1.78 | 2.05 |
| deep-sets\(^\dagger\) | 1.75 | 2.06 |
| bidirectional GRU | 1.56 | \(1.99{\pm}1.50\) |
| cross-attention (CAN) | 1.37 | \(\mathbf{1.16{\pm}0.20}\) |
5.8 Zero-shot transfer across team size (a limitation)↩︎
Because CAN is permutation-equivariant it can be evaluated at team sizes it never trained on. Fig. 7 applies the \(N{=}6\) policy to teams of \(12\) and \(24\). Transfer holds well at low contention—at \(c{=}0.3\) a \(4\times\) larger team is still close to fair (\(\rho{=}1.85\) at \(N{=}24\))—but degrades at high contention, reaching \(\rho{=}8.8\) at \(N{=}24\), \(c{=}0.9\). The bounded metric keeps these readable (all curves stay below the all-yield ceiling \(\rho{=}N\)), and the ordering is clean: difficulty grows with both team size and waste. We report this as a genuine fragility—the contention-inference learned at \(N{=}6\) does not fully generalize to crowds at high waste—rather than smoothing it over. The obvious remedy does not work: training on a size curriculum (\(N\in\{4,6,8,12\}\), evaluating at the held-out \(N{=}24\)) helps only at \(c{=}0.3\) and worsens mid-range transfer (it dilutes the per-size budget), leaving the high-contention gap unchanged (\(\rho{=}4.5\) at \(c{=}0.9\), vs.\(4.5\) for \(N{=}6\)-only). Closing it is open.
5.9 Generality across environments↩︎
The experiments so far use the single-resource graded game. To test whether CAN’s behaviour-conditioned contention inference is specific to that game, we replicate the head-to-head on two further leverage-preserving environments that pose different inference problems (Fig. 8, Table 5). (i) Congestion: \(M{=}3\) parallel servers; each agent claims one or yields; equal-split per server; empty servers route to the neediest. The cooperators must infer which server each free-rider targets and contest just that one. (ii) Stakes: a single resource whose value \(v_t\) is random (lumpy: usually small, occasionally a jackpot, \(\mathbb{E}[v]{=}1\)). The cooperators must contest selectively, on the high-stakes steps where a free-rider’s surplus concentrates. Both keep equal-split contention, so Prop. 1 leverage holds; CAN and the three welfare-fair learners are trained and audited exactly as before.
The efficiency axis is what carries over. On exploitability alone the games differ in difficulty (the congestion exploit is structurally capped at \(\rho{=}N/M{=}2\); stakes restores the \(\rho{=}N\) ceiling). The one property that is consistent is efficiency: CAN keeps \(D{=}0\) efficiency \(0.94\)–\(1.00\) in all three games, so it never buys robustness by wasting the resource—unlike the only baseline that attains low \(\rho\), SOTO, whose all-contesting collapses efficiency to \(0.40\)–\(0.47\) (and to \(0.10\) at stakes \(c{=}0.9\)). GGF and FEN are Pareto-dominated by CAN in every game. Robustness, however, does not carry over uniformly: CAN is both efficient and robust on base and congestion, but on stakes it is only partially robust—robust up to moderate contention and exploited at \(c{=}0.9\)—so we claim a clear scope, not blanket generality.
An honest gradient: leverage strength governs success. CAN is not uniformly robust; its exploitability tracks how much leverage Prop. 1 actually delivers. With strong leverage (base: a contest caps the free-rider at \((1{-}c)/2\) for any \(c\)) CAN is robust at every \(c\) and most robust at the highest contention (\(\rho{=}1.20\) at \(c{=}0.9\)). With structurally capped leverage (congestion) it is robust but cannot beat the \(\rho{=}2\) ceiling by much at high \(c\). With weakening leverage (stakes: contesting a jackpot at \(c{=}0.9\) returns only \(0.05\,v\)) it degrades to \(\rho{=}4.05\) at \(c{=}0.9\)—while still staying efficient (\(0.97\)) where the robust alternative (SOTO) delivers only \(0.10\). And with absent leverage—a rich-get-richer (Matthew) rule where the richest claimer wins, so a worst-off contester captures nothing and Prop. 1 fails by construction—CAN is exploited (\(\rho{\approx}5.5\)), marking the boundary of the approach. The method works as far as the leverage it is built on, and no further.
| base (\(\rho_{\max}{=}6\)) | congestion (\(2\)) | stakes (\(6\)) | ||||
|---|---|---|---|---|---|---|
| 2-3(lr)4-5(lr)6-7 Method | eff | \(\rho\) | eff | \(\rho\) | eff | \(\rho\) |
| GGF | 1.00 | 6.00 | 1.00 | 2.01 | 0.98 | 5.75 |
| FEN | 0.81 | 4.20 | 0.96 | 2.05 | 0.70 | 3.27 |
| SOTO | 0.40 | 1.00 | 1.00 | 2.01 | 0.47 | 1.64 |
| CAN | 0.98 | 1.35 | 1.00 | 1.60 | 0.94 | 2.32 |
6 Discussion and Limitations↩︎
What this shows. The decentralization gap left open by prior work [5] is not fundamental: on the graded game a decentralized cross-attention policy trained against an adversarial league recovers most of the centralized oracle’s incentive-compatibility (\(\rho{\approx}1.2\)–\(1.5\)) and its efficiency (\({\approx}1.0\) when no free-rider is present), with no central allocator. The all-or-nothing futility result is the boundary case \(c{=}1\). The effect is not automatic for every graded rule, though: it requires that contesting a free-rider actually return a positive share to the contester (Prop. 1), which the stakes and Matthew games show can be weak or absent.
Where it is fragile. (i) Zero-shot transfer to much larger teams degrades at high contention (Fig. 7), and a naive size curriculum does not fix it (it dilutes the per-size budget and leaves the \(c{=}0.9\) gap unchanged); crowd-scale robustness at high waste is an open problem. (ii) The single-adversary scheme is seed-sensitive at low contention; league training is needed for consistency, at extra training cost. (iii) Robustness is bounded by leverage: on the stakes game it degrades at high contention (where contesting a jackpot returns almost nothing), and under a winner-take-all (Matthew) rule it disappears entirely—CAN is robust only as far as Prop. 1’s leverage extends. (iv) Our games are controlled abstractions with a single shared cooperator policy; spatial/continuous environments are still open (coordinated defector coalitions, by contrast, we do test, and they are no harder than a lone free-rider). (v) The oracle remains an upper bound CAN approaches but does not reach.
Takeaway. Fair-MARL methods are usually reported on the fairness they achieve under full cooperation. We argue they should also be reported on the fairness they retain under self-interest—and that, contrary to the all-or-nothing intuition, a decentralized policy can retain much of it whenever the contention rule leaves a contester a real share to capture.
7 Conclusion↩︎
We gave a decentralized account of robust fairness in cooperative MARL. Graded contention makes contesting a free-rider strictly worthwhile for the worst-off (Prop. 1), but exploiting this requires inferring an unknown, variable number of free-riders and responding proportionally. CAN—a permutation-equivariant cross-attention policy over observed behaviour, trained against an adversarial league—does so, holding best-response exploitability low across the contention range (and most robust at the highest contention) while wasting essentially nothing when no free-rider is present, thereby approaching a centralized need-based oracle without a central allocator. We are explicit about scope rather than claiming blanket generality: across additional games CAN stays efficient and dominates the welfare-fair learners, but its robustness holds in proportion to the contest leverage—strong on a multi-server game, only partial where the leverage weakens (high-value steps at high contention), and absent under a winner-take-all rule. We hope this reframes decentralized robust fairness as a tractable, measurable target—bounded by a clear condition—rather than an impossibility.
Code Availability↩︎
All code (the graded-contention game, CAN, the architecture and training-scheme ablations, and all experiments) and the LaTeX source are available at https://github.com/highcansavci/can-fair-marl.
Use of AI-Assisted Technologies↩︎
The author used Claude (Anthropic), including Claude Code, to assist with the experimental code, manuscript review and revision, and formatting. All AI-assisted content was verified by the author, who is solely responsible for the methodology, results, and conclusions of this paper.
8 Environment Details↩︎
All environments share a skeleton: \(N{=}6\) agents act for \(T{=}100\) steps; at each step divisible resource is available; each agent chooses a self-interested act (Claim) or to Yield; accumulated utilities \(\mathbf{u}\) determine fairness. They differ only in the allocation rule mapping the joint action to utility increments, and (for stakes/congestion) in the action space and one extra observation. Let \(m\) be the number of claimers of a resource and \(c\in[0,1]\) the contention waste.
Base (single-resource graded contention). One resource per step, binary action. Each claimer receives \[g(m)=\begin{cases} 1 & m{=}1,\\ (1{-}c)/m & m\ge 2,\\ \text{(unit to worst-off } \arg\min_i u_i) & m{=}0, \end{cases}\] so a sole claimer wins the unit, \(m\ge2\) claimers split a discounted \(1{-}c\), and an unclaimed unit flows losslessly to the neediest agent. \(c{=}1\) recovers the all-or-nothing model.
Congestion (multi-server). \(M{=}3\) parallel unit resources (“servers”) per step; action space \(\{\mathrm{\small Yield},\,\text{claim }1,\dots,\text{claim }M\}\) (\(M{+}1\) actions). Each server is allocated independently by the base rule (\(k\) claimers \(\!\to\!1\) if \(k{=}1\), \((1{-}c)/k\) if \(k\ge2\)); the \(E\) empty servers route to the \(E\) lowest-utility agents (one unit each, no waste). A lone free-rider can monopolise only one of \(M\) servers, so the exploit ceiling is \(\rho{=}N/M{=}2\). Each token is augmented with the agent’s per-server running claim-rates (so the policy can infer which server is being grabbed): \(5{+}M\) features, \((M{+}1)\)-way head.
Stakes (stochastic value). One resource per step with random value \(v_t\) drawn i.i.d.as \(v_t{=}3.25\) w.p.\(0.25\) and \(v_t{=}0.25\) otherwise (lumpy jackpots, \(\mathbb{E}[v_t]{=}1\), so efficiency normalises as in base). The base rule scales by \(v_t\): a sole claimer gets \(v_t\), \(m\ge2\) claimers get \((1{-}c)v_t/m\) each, an unclaimed unit gives \(v_t\) to the worst-off. The current \(v_t\) is appended to each token (\(7\) features), so the policy can contest selectively on high-value steps.
Matthew (rich-get-richer; boundary). One resource, binary action, but among claimers the richest wins: \(m{=}1\) gives the sole claimer \(1\); \(m\ge2\) gives the richest claimer \((1{-}c)\) and the rest \(0\) (ties broken uniformly at random); \(m{=}0\) routes to the worst-off. A worst-off cooperator that contests a richer free-rider receives \(0\), so Prop. 1 leverage vanishes; we use this environment only to mark the boundary of the method.
Threat model and metric (all environments). Each episode, \(D\) agents are defectors with \(D\sim\mathrm{Unif}\{0,\dots,d_{\max}\}\) (\(d_{\max}{=}2\) unless noted; the stress study uses \(d_{\max}{=}4\)); defectors always take the self-interested act and the \(N{-}D\) cooperators share one policy. To audit a frozen cooperator policy we train a best-response defector (or a \(D\)-agent coalition sharing one policy) to maximise the defector group’s utility, and report the bounded free-ride factor \[\rho=\frac{N\sum_{i\in\mathcal{D}}u_i}{\,n_{\mathrm{def}}\sum_j u_j\,}\in[0,\,N/n_{\mathrm{def}}],\] \(\rho{=}1\) exactly fair, \(\rho{=}N\) a lone defector taking everything. Cooperators maximise the per-step increment of \(W_{\mathrm{coop}}{=}\mathrm{mean}_{i\in\mathcal{C}}(u_i){-}\mathrm{std}_{i\in\mathcal{C}}(u_i)\).
9 Implementation Details↩︎
CAN and all adversaries are shared single-head self-attention blocks (hidden width \(64\)): \(Q,K,V\) linear maps of the \(N{\times}6\) token matrix, scaled-dot-product attention, a \(\tanh\) layer on \([\,x_i\,\|\,\mathrm{ctx}_i\,]\), and a \(2\)-logit head. All policies train with REINFORCE and Adam (lr \(3\times10^{-3}\)), \(B{=}512\) parallel episodes, episodes of \(T{=}100\) steps, with the entropy coefficient annealed from \(0.05\) to \(0.003\). Per-episode defector count is \(D\sim\mathrm{Unif}\{0,1,2\}\). Vanilla/population co-training run \(3000\) updates; league training runs \(6\) generations of \(1200\) cooperator updates against the pool and \(1000\) updates per fresh best response. Every audit trains a best-response defector for \(1500\) updates against the frozen cooperator and reports \(\rho\) from Eq. 1 . The cooperator welfare is the masked \(\mathrm{mean}{-}\mathrm{std}\) over cooperators; advantages are discounted (\(\gamma{=}0.99\)) per-step welfare increments with a batch-mean (or learned value) baseline. The architecture ablation reuses this league setup with the cross-attention block replaced by a mean-pool, deep-sets, or bi-GRU aggregator; the mixed-\(N\) curriculum cycles the team size over \(\{4,6,8,12\}\) per update with the same total step budget. Unless noted, all numbers average \(5\) seeds and error bars are \(95\%\) bootstrap confidence intervals. League training is mildly sensitive to GPU non-determinism, which compounds over generations; the headline league/vanilla robustness (Table 2, Fig. 4) therefore pools several independent gen-6 runs (\(15\) and \(10\) seed-runs) so the CIs absorb run-to-run as well as seed variance.