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

arXiv: https://arxiv.org/abs/2605.00762 · HTML: https://mlsanity.com/paper/2605.00762/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 17 of 17)

- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Asymmetric Shapley values: incorporating causal knowledge into model-agnostic explainability](https://mlsanity.com/paper/1910.06358/) (2019)
- [Measure Contribution of Participants in Federated Learning](https://mlsanity.com/paper/1909.08525/) (2019)
- [GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning](https://mlsanity.com/paper/2109.02053/) (2021)
- [Shapley Q-value: A Local Reward Approach to Solve Global Reward Games](https://mlsanity.com/paper/1907.05707/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Game of Gradients: Mitigating Irrelevant Clients in Federated Learning](https://mlsanity.com/paper/2110.12257/) (2021)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback](https://mlsanity.com/paper/1811.11925/) (2018)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Improving Fairness in Adaptive Social Exergames via Shapley Bandits](https://mlsanity.com/paper/2302.09298/) (2023)
- [Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays](https://mlsanity.com/paper/2407.15439/) (2024)

## Abstract (arXiv)

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 Omega(T2/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 tilde O(T2/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 tilde O(T2/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.