Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback

2026/05/31 by Shradha Sharma, Shweta Jain, Swapnil Dhamal
Computer Science · #cs.LG #cs.AI #cs.MA

paper · pdf

arxiv created 2026/08/02 · arxiv updated 2026/08/04

Abstract

We study meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback, where a learner selects at most K arms per time step and observes only the noisy aggregate reward of the selected set. To define merit under budgeted coalition constraints, we introduce the K-Shapley value, an adaptation of the classical Shapley value that measures marginal contributions using only coalitions of size at most K. We show that the K-Shapley value is the unique solution concept satisfying symmetry, linearity, null player, and K-efficiency axioms. We then establish an Ω(T^2/3) lower bound on fairness regret for monotone submodular valuation functions. We show that an explore-then-commit algorithm MURaS (Meritocratic Uniform Random Sampling) achieves O(T^2/3) fairness regret by exploring all arms uniformly in exploration phase. To improve empirical regret, we propose IW-KSVFair, a meritocratic full-bandit algorithm that learns a selection policy whose arm marginals are proportional to the unknown K-Shapley values. To correct the bias induced by adaptive sampling, IW-KSVFair uses importance-weighted estimation and mixes the adaptive set distribution with a uniform distribution to keep importance weights bounded. We prove that IW-KSVFair achieves O(T^2/3) fairness regret, matching the lower bound up to logarithmic factors. Experiments on synthetic and real-world datasets show that IW-KSVFair achieves low cumulative fairness regret and closely aligns empirical selection frequencies with K-Shapley value-based merit.

Citations

• Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays
• Nearly Minimax Optimal Submodular Maximization with Bandit Feedback
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback
• GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning
• Game of Gradients: Mitigating Irrelevant Clients in Federated Learning
• Fairness of Exposure in Stochastic Bandits
• Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
• Asymmetric Shapley values: incorporating causal knowledge into model-agnostic explainability
• Measure Contribution of Participants in Federated Learning
• The many Shapley values for model explanation
• Top-k Combinatorial Bandits with Full-Bandit Feedback
• Data Shapley: Equitable Valuation of Data for Machine Learning
• Combinatorial Sleeping Bandits with Fairness Constraints
• Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback
• Dependent rounding and its applications to approximation algorithms