Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values
| Authors | Shradha Sharma et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2605.00762 |
| Download | |
| Categories | cs.LG, cs.AI, cs.MA |
Abstract
We propose a new framework for meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback (BCMAB-FBF). Unlike semi-bandit feedback, the contribution of individual arms is not received in full-bandit feedback, making the setting significantly more challenging. To compute arm contributions in BCMAB-FBF, we first extend the Shapley value, a classical solution concept from cooperative game theory, to the -Shapley value, which captures the marginal contribution of an agent restricted to a set of size at most . We show that -Shapley value is a unique solution concept that satisfies Symmetry, Linearity, Null player, and efficiency properties. We next propose K-SVFair-FBF, a fairness-aware bandit algorithm that adaptively estimates -Shapley value with unknown valuation function. Unlike standard bandit literature on full bandit feedback, K-SVFair-FBF not only learns the valuation function under full feedback setting but also mitigates the noise arising from Monte Carlo approximations. Theoretically, we prove that K-SVFair-FBF achieves O(T^{3/4}) regret bound on fairness regret. Through experiments on federated learning and social influence maximization datasets, we demonstrate that our approach achieves fairness and performs more effectively than existing baselines.
Engineering Breakdown
Plain English
This paper tackles the problem of fair arm selection in budgeted combinatorial multi-armed bandits when you only receive full-bandit feedback (meaning you don't see the individual contribution of each arm, only aggregate outcomes). The authors extend Shapley value—a game theory concept for measuring fair credit attribution—into K-Shapley value, which computes each arm's marginal contribution when restricted to groups of size K or smaller. They propose K-SVFair-FBF, an algorithm that adaptively estimates K-Shapley values in this challenging feedback regime. This enables principled, meritocratic allocation of a fixed budget across arms while respecting their true individual contributions.
Core Technical Contribution
The paper's core novelty is the K-Shapley value—a new solution concept that extends classical Shapley values to work in constrained settings where agent contributions are bounded by group size K. Unlike standard Shapley value, K-Shapley is provably the unique concept satisfying Symmetry, Linearity, Null player, and efficiency axioms in this restricted framework. The authors then engineer K-SVFair-FBF, a bandit algorithm that solves the harder problem of estimating K-Shapley values under full-bandit feedback (where individual arm signals are hidden), not just semi-bandit feedback where partial signal is observable. This bridges game-theoretic fairness with online learning in an information-constrained setting where prior methods break down.
How It Works
The algorithm operates in rounds over a budget-constrained horizon. In each round, the system must select a subset of arms respecting a budget constraint. K-SVFair-FBF maintains running estimates of each arm's K-Shapley value by inferring individual contributions from aggregate feedback only—this is the core challenge since full-bandit feedback provides no direct signal of what each arm contributed. The algorithm uses an adaptive exploration-exploitation strategy: it explores arm combinations to estimate marginal contributions (the delta when adding arm i to a coalition of size < K), and exploits by preferentially selecting high-Shapley-value arms in subsequent rounds. The K-Shapley estimation leverages the fact that in a coalition of size at most K, each arm's value is determined by its marginal impact—the algorithm accumulates these observations to build empirical estimates. Over time, uncertainty shrinks and selections increasingly favor arms with higher true Shapley values, achieving both statistical learning and fairness simultaneously.
Production Impact
For engineers building resource-allocation systems (ad networks, recommendation platforms, workforce scheduling), this approach directly solves unfair bias in arm selection when feedback is sparse or aggregated. Instead of assuming all arms contribute equally or using heuristic weighting, K-SVFair-FBF grounds allocation in principled game-theoretic fairness—each arm gets credit proportional to its actual marginal value. This prevents dominant strategies from monopolizing budget; weaker arms still get exploration chances if they show potential. Production trade-offs include: (1) computational overhead of estimating K-Shapley values scales with arm count and K, requiring O(2^K) coalition evaluations in worst case; (2) convergence is slower than non-fair baselines because exploration for accurate credit attribution takes samples; (3) requires ability to run controlled arm combinations and observe their aggregate impact, which isn't always feasible. Integration requires careful instrumentation to capture outcome signals that feed back into Shapley estimation.
Limitations and When Not to Use This
The paper assumes you can observe some aggregate feedback signal from arm coalitions, but in truly black-box settings (e.g., user clicks on a combined recommendation set) this may not isolate which arms mattered. K-Shapley computation becomes exponentially harder as K grows, limiting applicability to high-dimensional arm spaces without additional structure or approximations. The framework requires stationarity (arm quality doesn't drift over time), which breaks in non-stationary environments like competitive marketplaces. The abstract cuts off before stating convergence rates or sample complexity bounds, so it's unclear how many samples are actually needed to achieve good fairness guarantees in realistic regimes—this is a critical gap for production deployment decisions.
Research Context
This work extends the intersection of cooperative game theory (Shapley values) and online learning (multi-armed bandits), a growing area driven by fairness concerns in automated allocation systems. Prior work primarily addressed semi-bandit feedback where arms partially reveal their contributions; this paper pushes to the harder full-bandit regime common in real systems. The K-Shapley concept itself builds on classical game-theoretic solution concepts and the recent trend of using Shapley values for explainability and fairness in ML (e.g., SHAP for model interpretation). The contribution opens research directions in: (1) handling non-stationary environments with fairness, (2) approximation algorithms for K-Shapley when K is large, (3) combining fairness guarantees with other objectives like efficiency or diversity.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::