Technical Summary: Procedural Fairness in Multi-Agent Bandits

Problem Statement

In Multi-Agent Multi-Armed Bandits (MA-MAB), fairness is traditionally defined through outcome-based metrics, such as maximizing utilitarian welfare, minimizing inequality, or optimizing Nash Social Welfare (NSW). These approaches focus on the aggregate results of decisions (e.g., total utility or distribution of rewards). However, the authors argue that this perspective overlooks procedural fairness: the principle that fairness is inherent in the decision-making process itself, specifically regarding equal voice and representation.

Existing literature often treats fairness as an external criterion imposed on the system (consequentialism), ignoring the agency of the participants. In contrast, procedural fairness posits that a decision is legitimate only if it cannot be reasonably rejected by those subject to it, requiring that each agent has an equal share of influence over the policy, regardless of whether that influence leads to their optimal outcome.

Methodology

Formalization of Procedural Fairness

The paper introduces a formal definition of procedural fairness for MA-MABs based on equal representation within a policy.

• Decision Share: For an agent $i$, the decision share $\beta_i(P)$ is the total probability mass assigned to their favorite arms (those with the highest mean reward $\mu^*_{i,k}$).
• Procedural Fairness Definition: A policy $P$ is procedurally fair if the probability distribution over arms can be decomposed into $N$ equal shares ($1/N$), where each agent's share is allocated exclusively to their favorite arms.
• Procedural Fairness Score (PF): The authors formulate an optimization problem to measure how close a given policy is to being procedurally fair. The score represents the maximum fraction of the $1/N$ decision share that can be allocated to each agent's favorite arms without violating the policy's total probability constraints. A score of 1 indicates perfect procedural fairness.

Algorithmic Approach

To learn a procedurally fair policy in an online setting where reward means are unknown:

1. Objective: The authors maximize Decision-Share-Based Nash Welfare ($NW_\beta$), defined as the product of agents' decision shares: $\prod_{i=1}^N \beta_i(P)$.
2. Theoretical Guarantee: They prove (Theorem 1) that maximizing $NW_\beta$ yields a policy that is procedurally fair (i.e., it lies in the Procedural Core).
3. Learning Algorithm (Algorithm 1):
   • Uses Upper Confidence Bound (UCB) style concentration bounds to estimate favorite arm sets ($\hat{F}_i$).
   • Incorporates a randomized exploration mechanism (pulling a random arm with probability $t^{-(1-\gamma)}$) to ensure all arms are sampled sufficiently to shrink confidence intervals and recover true favorite sets.
   • At each step, the algorithm solves the $NW_\beta$ optimization over the estimated favorite sets to determine the policy $P_t$.
4. Regret Analysis: The paper defines Procedural Fairness Regret ($R_{PF}$) based on the number of rounds where the estimated favorite sets do not match the true sets. They prove a sublinear regret bound of $O(K + T^\gamma/\gamma + (\dots)^{1/\gamma})$, showing that the algorithm converges to a procedurally fair policy.

Key Contributions

1. Formal Definition: A rigorous definition of procedural fairness for MA-MABs, distinguishing representation (voice) from outcome quality (utility).
2. Impossibility Results: The paper proves that procedural fairness is fundamentally incompatible with outcome-based fairness notions.
   • Proposition 2 & 3: There exist reward structures where no policy can simultaneously achieve perfect procedural fairness and perfect inequality minimization or perfect utilitarianism.
   • Theorem 6: Utility-based Nash welfare-optimal policies and procedurally fair policies are not guaranteed to Pareto dominate one another; they prioritize different, often conflicting, values.
3. Core Stability: The authors establish that policies maximizing decision-share-based Nash welfare lie in the Procedural Core. This means no coalition of agents can use their proportional share of decision power to improve every member's representation (with at least one strict improvement), ensuring stability against deviations based on voice.
4. Algorithm and Regret Bounds: An algorithm for learning procedurally fair policies with sublinear regret guarantees, ensuring that agents' voices are represented as the system learns.

Empirical Results

The authors evaluated their approach against outcome-based benchmarks (Utilitarianism, Inequality Minimization, Egalitarian Welfare, Nash Social Welfare, and Generalized Gini Index) across:

• Synthetic Data: 7,776 instances varying agents, arms, and preference distributions (Uniform, Single-Peaked, Impartial Culture, Mallows).
• Real-World Data: A dataset from Mechanical Turk (PrefLib) with 50 voters and 4 candidates.

Findings:

• Trade-offs: Policies optimized for outcome-based metrics (Utilitarianism, NSW) consistently achieved low procedural fairness scores (often < 0.8), indicating that optimizing for outcomes does not inadvertently preserve equal voice.
• Balance: The procedurally fair policy achieved a perfect procedural fairness score (1.0) while maintaining high scores in inequality minimization and utilitarianism (often > 0.9), demonstrating a superior balance across all three dimensions.
• Robustness: As agent disagreement increased (e.g., in Mallows models with high dispersion), the procedural fairness of outcome-based policies eroded significantly, whereas the procedurally fair policy maintained its representation guarantees.
• Convergence: In the real-world experiment, the learning algorithm converged to a policy that maintained high equality and utility while guaranteeing equal representation, outperforming all other benchmarks on the procedural metric.

Significance and Claims

The paper argues that procedural legitimacy is a distinct and necessary objective in multi-agent systems, separate from efficiency or equality.

• Normative Choice: The authors emphasize that fairness is not a single mathematical solution but a set of competing values. Choosing a fairness objective is a normative decision: prioritizing efficiency (Utilitarianism) inherently sacrifices equal voice, while prioritizing procedural fairness accepts potential inefficiencies to ensure legitimacy.
• Legitimacy over Optimization: Drawing on political philosophy (Rawls, Scanlon) and psychology (Lind & Tyler), the paper claims that systems are more likely to be perceived as legitimate and accepted by agents if they respect the "dignity of participation."
• Design Principle: Procedural fairness is presented not just as a theoretical concept but as a practical design principle that yields systems which are stable (core-stable), robust, and reflective of human values regarding fairness as "equal voice."

The paper concludes that while outcome-based metrics are elegant and tractable, they impose values from the outside. Procedural fairness shifts the focus to "whose preferences shaped the decision," offering a framework for building multi-agent systems that are not only intelligent but also legitimate.