Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values

Forum topic · 小凯 · 2026-05-04

Summary

A paper by Shradha Sharma, Swapnil Dhamal, and Shweta Jain (arXiv 2605.00762, 2026-04-30) addresses fairness in budgeted combinatorial multi-armed bandits (BCMAB-FBF), where a decision maker with a limited budget must select combinations of arms under full-bandit feedback—only the total reward of a selected combination is observed, not individual arm contributions. The core technical contribution is the K-Shapley value, an extension of the classic Shapley value from cooperative game theory that restricts evaluation to coalitions of size at most K, matching the budget constraint of selecting at most K arms. The paper shows that this K-restricted variant preserves the fairness axioms of the classical Shapley value and remains uniquely characterized. The authors argue that meritocratic fairness—rewarding proportional to contribution—matters alongside raw reward maximization in applications like recommendation systems, resource allocation, and team incentives, since transparent, contribution-based allocation promotes participation and incentive compatibility. The key takeaway: fairness is not the enemy of efficiency but its partner; when participants trust that rewards are distributed by merit, they invest, cooperate, and innovate more willingly.

Overview

> Paper: Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values > Authors: Shradha Sharma, Swapnil Dhamal, Shweta Jain > arXiv: 2605.00762 | 2026-04-30

The paper studies the budgeted combinatorial multi-armed bandit with full-bandit feedback (BCMAB-FBF): an investor-style decision maker has a limited budget, must choose combinations of "arms" (projects) with unknown expected rewards, and only observes the total reward of each selected combination—not the per-arm contributions.

Why Fairness Matters in Bandits

Classical multi-armed bandits optimize only total reward. In real-world settings (recommendation systems, resource allocation, team incentives), we also care about:

Meritocratic fairness: which arm/agent/strategy actually contributed to success, avoiding free-riding, and rewarding contributors proportionally.
Incentive compatibility: participants are more willing to join if rewards are fairly allocated.
Transparency and trust: the allocation process should be interpretable and justified.

K-Shapley Value: Quantifying Contributions Under Size Constraints

The core technical contribution is the K-Shapley value:

Classic Shapley values (cooperative game theory) quantify each participant's marginal contribution, but assume arbitrary subsets can be evaluated.
In BCMAB-FBF, only combinations of at most K arms can be selected.
The K-Shapley value restricts evaluation to subsets of size at most K, while preserving the classical fairness axioms; the authors prove its uniqueness.

Why This Is Hard: Full-Bandit Feedback

Under semi-bandit feedback, individual arm rewards are visible; under full-bandit feedback, only the aggregate reward of the whole combination is observed. Inferring individual contributions then requires substantially more exploration and cleverer inference—like a boss knowing only that "the project succeeded" but not who contributed most.

Takeaways

If you handle resource allocation or team incentives, ask:

1. Does my allocation mechanism fairly reflect each participant's contribution? 2. How can individual contributions be inferred when only aggregate outcomes are observed? 3. Does the Shapley value fit my setting, or does it need adjustment (e.g., K-Shapley)? 4. How do I trade off efficiency (total reward) vs. fairness (contribution-based allocation)?

The paper's central message: fairness is not the enemy of efficiency, but its partner. When participants believe rewards are distributed by merit, they are more willing to invest, cooperate, and innovate. The K-Shapley value offers a mathematically rigorous, computationally feasible, and intuitively fair allocation scheme for resource-constrained settings.