[Paper] Procedural Fairness in Multi-Agent Bandits

Source: arXiv - 2601.10600v1

Overview

The paper “Procedural Fairness in Multi‑Agent Bandits” challenges the way fairness is usually measured in multi‑agent multi‑armed bandit (MA‑MAB) problems. Instead of focusing solely on the outcome (e.g., total reward, equal payoffs), the authors propose a procedural fairness objective that guarantees every agent an equal say in the decision‑making process. Their work shows that giving agents a voice can be achieved with only a modest loss in traditional performance metrics, opening a new avenue for designing fairer AI systems.

Key Contributions

• Introduces procedural fairness for MA‑MABs: a formal definition that ensures equal decision‑making power for all agents while still delivering proportional outcomes.
• Shows procedural fairness lies in the core of the cooperative game, meaning no subset of agents can improve their collective payoff by deviating.
• Theoretical analysis proving that outcome‑based fairness notions (equality, utilitarianism) and procedural fairness are fundamentally incompatible in some settings, highlighting the need for explicit normative choices.
• Empirical evaluation across synthetic and benchmark bandit environments demonstrating:
  • Outcome‑centric policies sacrifice “voice” for agents.
  • Procedurally fair policies incur only a small drop in welfare, equality, or regret compared with the best outcome‑only baselines.
• Practical framework for implementing procedural fairness in existing bandit algorithms (e.g., Thompson Sampling, UCB) via a lightweight “voting” layer.

Methodology

1. Problem Setup – The authors model a MA‑MAB as a repeated game where each of n agents repeatedly selects an arm from a common set. After each pull, the selected arm yields a stochastic reward observed by all agents.
2. Procedural Fairness Definition – They formalize “equal decision‑making power” as each agent having an identical probability of influencing the arm selection at every round. This is achieved by a voting mechanism: each agent casts a vote for an arm, and the arm with the highest weighted vote is pulled.
3. Core Membership Proof – Using cooperative game theory, they prove that the voting‑based policy belongs to the core: no coalition can guarantee itself a higher expected reward by breaking away.
4. Algorithmic Integration – Existing bandit strategies are wrapped with the voting layer:
   • Each agent runs its own bandit learner (e.g., UCB).
   • The learner produces a preference distribution over arms.
   • Agents sample a vote from this distribution; the arm with the most votes is executed.
5. Baselines & Metrics – They compare procedural fairness against three outcome‑centric baselines: (a) Utilitarian (maximizing total reward), (b) Egalitarian (minimizing variance), and (c) Proportional (reward proportional to contribution). Metrics include cumulative regret, reward inequality (Gini coefficient), and a newly introduced voice‑equity score.

Results & Findings

• Minimal performance loss: Procedural fairness’s regret is within 1 % of the best utilitarian policy, confirming that “fair voice” does not dramatically hurt efficiency.
• Improved equity: While not the absolute best in raw outcome equality, procedural fairness achieves a balanced trade‑off—substantially better than pure utilitarianism and comparable to egalitarian approaches.
• Dominant voice: The voting mechanism guarantees near‑perfect procedural fairness, a metric where all outcome‑only baselines fall short.
• Incompatibility proof: The authors demonstrate scenarios where maximizing total reward forces a subset of agents to dominate the voting process, making it impossible to simultaneously satisfy strict outcome equality and procedural fairness.

Practical Implications

• Fair AI services: Cloud‑based recommendation or ad‑allocation platforms that serve multiple stakeholders (publishers, advertisers, end‑users) can embed a voting layer to ensure each stakeholder influences the algorithmic choice, satisfying regulatory or contractual fairness clauses.
• Collaborative robotics: In multi‑robot teams where each robot contributes different sensors or capabilities, procedural fairness can prevent a single robot from monopolizing task allocation, leading to more robust, fault‑tolerant deployments.
• Federated learning & edge computing: When edge devices collectively decide which model update to push, a procedural‑fair bandit can give each device an equal say, mitigating bias toward devices with richer data.
• Human‑in‑the‑loop systems: For decision‑support tools that combine inputs from several experts (e.g., medical triage), the voting‑based bandit ensures each expert’s opinion is weighted equally, improving trust and acceptance.
• Regulatory compliance: Emerging AI fairness regulations (e.g., EU AI Act) increasingly emphasize procedural transparency. Implementing procedural fairness provides a concrete, auditable mechanism to demonstrate compliance.

Limitations & Future Work

• Scalability of voting: The current voting scheme assumes a modest number of agents; scaling to hundreds or thousands may require hierarchical voting or approximation techniques.
• Assumption of honest participation: The framework presumes agents follow the prescribed bandit learner; strategic manipulation (e.g., misreporting preferences) is not fully addressed.
• Static fairness weight: The paper treats procedural fairness as a binary constraint. Future research could explore weighted procedural fairness where agents have differing legitimate stakes.
• Real‑world validation: Experiments are limited to simulated environments; deploying the approach in production systems (e.g., ad exchanges) would test robustness under non‑stationary reward distributions and adversarial behavior.

Procedural fairness adds a new dimension to the fairness conversation in multi‑agent learning—one that values how decisions are made as much as what the outcomes are. By providing a practical, low‑overhead way to give every participant an equal voice, this work opens the door for more democratic, trustworthy AI systems across a range of industries.

Authors

• Joshua Caiata
• Carter Blair
• Kate Larson

Paper Information

• arXiv ID: 2601.10600v1
• Categories: cs.MA, cs.AI, cs.GT, cs.LG
• Published: January 15, 2026
• PDF: Download PDF