Meritocratic Fairness via $K$-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback
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 t...
| Authors | Shradha Sharma, Shweta Jain, Swapnil Dhamal |
|---|---|
| Primary category | cs.LG |
| Published | 1 May 2026 |
| Last updated at source | 2 August 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.