Learning to Contest: Decentralized Robust Fairness in Cooperative MARL via Cross-Attention

Technical Summary: Learning to Contest: Decentralized Robust Fairness in Cooperative MARL via Cross-Attention

1. Problem Statement

Cooperative Multi-Agent Reinforcement Learning (MARL) often optimizes for fairness (e.g., Generalized Gini Welfare) to prevent agent starvation. However, these "fair" teams are inherently exploitable in the presence of self-interested agents (free-riders). When a team sacrifices individual utility to raise the worst-off agent, a self-interested agent can free-ride on this surplus.

In strictly rivalrous (all-or-nothing) resource contention, this exploitation is difficult to counter at the policy level. If a cooperator contests a free-rider for a resource, the resource is either won by one or wasted entirely (collision). Consequently, a welfare-fair team is indifferent between yielding and contesting, rendering decentralized defense futile. Prior work suggests that only a centralized, need-based allocator can resolve this, leaving the question of whether decentralized policies can achieve robust fairness open.

This paper addresses this gap by introducing a graded-contention model. In this model, contested resources are not entirely wasted; if $m \ge 2$ agents claim a resource, they split a fraction $1-c$ (where $c$ is the waste factor), rather than destroying it. The core challenge becomes a coordination problem under uncertainty: the number of free-riders ($D$) is unknown and variable. A fixed policy fails because "always-contest" wastes resources when no one defects, while "always-yield" collapses when a defector appears.

2. Methodology: CAN (Cross-Attention Networks)

The authors propose CAN, a decentralized policy designed to infer the presence of free-riders and respond proportionally.

• Theoretical Foundation (Proposition 1): The paper proves that under graded contention ($c < 1$), a worst-off cooperator strictly improves their outcome by contesting a lone free-rider rather than yielding. Contesting yields $(1-c)/2 > 0$ instead of $0$, while reducing the free-rider's gain. This establishes the existence of decentralized leverage.
• Architecture:
  • Input: Each agent observes a token of public state features: current utility ($u_i$), deviation from team mean ($u_i - \bar{u}$), deviation from minimum utility ($u_i - u_{min}$), an indicator for being the worst-off, a running claim-rate ($cc_i$), and the time step.
  • Mechanism: CAN employs a permutation-equivariant single-head self-attention block. Agents attend to the observed behavior tokens of all other agents. This allows the policy to infer the number of claimers (contention) without relying on fixed agent identities.
  • Output: The policy outputs logits for CLAIM or YIELD.
• Training Regime:
  • Objective: Cooperators maximize a welfare function $W_{coop} = \text{mean}(u) - \text{std}(u)$, rewarding both utility reclamation and equitable distribution.
  • Adversarial Training: To ensure robustness, CAN is trained against an adversarial league (PSRO). Instead of training against a single co-evolving defector, the system alternates between training cooperators against a frozen pool of past best-response defectors and adding new best-response exploiters to the pool. This prevents the policy from overfitting to a specific adversary strategy.

3. Key Results

The paper evaluates CAN against welfare-fair baselines (GGF, FEN, SOTO) and a centralized oracle across various contention levels ($c \in \{0.3, \dots, 0.9\}$) and team sizes ($N=6$).

• Robustness vs. Efficiency Trade-off:
  • Baselines: Welfare-fair learners fail on one axis. GGF learns to yield (efficient but maximally exploitable, $\rho \approx N$). SOTO learns to always contest (robust but wasteful, efficiency $\approx 1-c$). FEN is unstable.
  • CAN: Achieves both robustness and efficiency. It maintains low best-response exploitability ($\rho \approx 1.2\text{--}1.5$) across all contention levels while retaining near-perfect efficiency ($\approx 1.0$) when no free-rider is present.
• Mechanism Validation:
  • Adaptive Behavior: CAN learns to "turn-take" (yield) when $D=0$ to avoid waste, and "contest just enough" when $D \ge 1$.
  • Training Scheme: League training is critical. Vanilla co-training against a static adversary results in higher exploitability ($\rho \approx 2.0$) and drifts upward, whereas league training keeps $\rho$ low and stable.
  • Architecture: Cross-attention is superior to simple pooling (mean-pool, deep-sets) and more stable than bidirectional GRUs, particularly at high contention levels ($c=0.9$).
• Generalization and Limits:
  • Team Size: CAN transfers zero-shot to larger teams ($N=12, 24$) at low contention but degrades at high contention, indicating a fragility in scaling contention inference.
  • Environment Scope: CAN remains efficient and Pareto-dominates baselines in congestion and "stakes" (variable value) games. However, its robustness is bounded by the leverage provided by the game rules. In a "winner-take-all" (Matthew) rule where the richest agent wins regardless of contention, the leverage vanishes, and CAN is exploited.

4. Significance and Claims

The paper claims to provide a controlled, honest map of the limits of decentralized robust fairness, rather than a claim that the decentralization gap is fully closed.

• Refuting Futility: The authors demonstrate that the futility of decentralized defense is an artifact of "all-or-nothing" contention. By introducing graded contention, they prove that decentralized leverage exists.
• Achieving Oracle Proximity: CAN approaches the performance of a centralized need-based oracle (which is the theoretical upper bound) without requiring a central allocator. It achieves this by learning to condition its actions on the observed behavior of others to infer the number of defectors.
• Scope of Applicability: The paper explicitly states that robustness is not universal. It holds only in proportion to the "contest leverage" a game provides. If the game rules do not allow a contester to capture a positive share of the resource (e.g., winner-take-all), the approach fails.
• Contribution: The work shifts the paradigm from viewing fair MARL as inherently exploitable to viewing it as a tractable, measurable target, provided the environment allows for graded contention and the policy is trained against a diverse history of adversaries.

The authors conclude that while decentralized robust fairness is achievable, it is bounded by specific conditions: the existence of graded contention leverage, the ability to infer adversary counts via attention, and the use of adversarial league training to stabilize the policy.