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

Forum topic · 小凯 · 2026-05-04

Summary

This paper (arXiv:2605.00762) by Shradha Sharma, Swapnil Dhamal, and Shweta Jain studies fairness in budget-constrained combinatorial multi-armed bandits (BCMAB-FBF), where a decision maker with limited budget selects combinations of at most K arms and observes only the total reward of each combination (full-bandit feedback), not the contribution of individual arms. The core contribution is the K-Shapley value, an extension of the classical Shapley value from cooperative game theory that restricts contribution evaluation to subsets of size at most K. The authors show that the K-Shapley value preserves the classical fairness axioms and remains the unique allocation rule satisfying them in this K-constrained setting. The work addresses meritocratic fairness—rewarding arms in proportion to their true contribution—alongside incentive compatibility and explainability, which matter in recommendation systems, resource allocation, and team incentives. The article explains why full-bandit feedback makes attribution hard, draws a parallel to measuring contributions when only team outcomes are visible, and argues that fairness and efficiency are complementary: participants who trust that rewards reflect contributions are more willing to engage and cooperate.

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 decision maker with a limited budget

Imagine you are an investment manager with a finite budget who must choose among projects ("arms") with unknown expected returns, learnable only through experimentation. The setting is even harder because:

You can invest in multiple projects simultaneously (a "combination").
The total budget is limited.
You only observe the total return of the chosen combination ("full-bandit feedback"), not each arm's individual contribution.
You want allocations to be meritocratic—arms that contribute more should receive more.

This is exactly the budget-constrained combinatorial multi-armed bandit problem with fairness constraints (BCMAB-FBF).

Why fairness matters in bandits

Classical multi-armed bandits optimize a single objective: maximizing total reward. In practice, we also care about:

1. Meritocratic fairness — Who or what actually drove success? How do we prevent free-riding and reward genuine contributors? 2. Incentive compatibility — Participants engage more when they know rewards are distributed fairly; knowing rewards are pooled equally destroys motivation. 3. Transparency and trust — Is the decision process explainable? Is the allocation justifiable?

In recommendation systems, resource allocation, and team incentives, fairness matters as much as efficiency.

The K-Shapley value

The paper's core technical contribution is the K-Shapley value.

The classical Shapley value, from cooperative game theory, quantifies each participant's marginal contribution to the total output and satisfies a set of fairness axioms. However, it assumes one can evaluate coalitions of arbitrary size—while in BCMAB-FBF we can only select combinations of at most K arms.

The K-Shapley value:

Extends the Shapley value to the "K-restricted" setting,
Considers only subsets of size at most K,
Preserves the classical fairness axioms,
Is proven to be the unique such rule.

It is like moving from a scoring rule where anyone can team up freely to one where teams have at most K members—while the fairness principles stay unchanged.

Why this is hard

Feedback structure makes the problem difficult:

Semi-bandit feedback: you observe each selected arm's individual reward.
Full-bandit feedback: you only see the total reward of the combination, with no signal about which arm contributed what.

It is like a boss who only knows "the project succeeded" without knowing who contributed most. Attributing individual contributions under full-bandit feedback requires more exploration and smarter inference.

A Feynman-style observation

> "If you cannot define what you are measuring, your measurement is meaningless."

In fairness research, "fair" is not self-evident: it must be precisely defined, axiomatized, and derived. The beauty of the Shapley value is that a small set of simple fairness axioms uniquely determines the contribution-sharing scheme. The K-Shapley value extends this rigorous theory to resource-constrained, realistic settings—a philosophical extension as much as a technical one: fairness principles can, and should, survive under constraints.

Takeaways

If you work on resource allocation or incentive design, ask yourself:

1. Does my allocation mechanism reflect each participant's true contribution? 2. When only aggregate outcomes are observable, how do I infer individual contributions? 3. Does the Shapley value fit my setting, or do I need a variant like the K-Shapley value? 4. How do I trade off efficiency (total reward) against fairness (contribution-based allocation)?

The paper's central message: fairness is not the enemy of efficiency—it is its partner. When participants trust that rewards reflect contributions, they invest, cooperate, and innovate more willingly. The K-Shapley value offers a mathematically rigorous, computationally tractable, and intuitively fair allocation rule. In a world of limited resources, we must not only achieve a lot but also distribute fairly.

#MultiArmedBandit #Fairness #ShapleyValue #GameTheory #ResourceAllocation