Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values
This work addresses the challenge of ensuring meritocratic fairness in combinatorial bandits with limited feedback, which is important for applications like resource allocation and recommendation systems.
The paper introduces a fairness-aware bandit algorithm for budgeted combinatorial multi-armed bandits with full-bandit feedback, using a novel K-Shapley value to measure arm contributions. The algorithm achieves O(T^{3/4}) fairness regret and outperforms baselines on federated learning and social influence maximization tasks.
We propose a new framework for meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback (BCMAB-FBF). Unlike semi-bandit feedback, the contribution of individual arms is not received in full-bandit feedback, making the setting significantly more challenging. To compute arm contributions in BCMAB-FBF, we first extend the Shapley value, a classical solution concept from cooperative game theory, to the $K$-Shapley value, which captures the marginal contribution of an agent restricted to a set of size at most $K$. We show that $K$-Shapley value is a unique solution concept that satisfies Symmetry, Linearity, Null player, and efficiency properties. We next propose K-SVFair-FBF, a fairness-aware bandit algorithm that adaptively estimates $K$-Shapley value with unknown valuation function. Unlike standard bandit literature on full bandit feedback, K-SVFair-FBF not only learns the valuation function under full feedback setting but also mitigates the noise arising from Monte Carlo approximations. Theoretically, we prove that K-SVFair-FBF achieves $O(T^{3/4})$ regret bound on fairness regret. Through experiments on federated learning and social influence maximization datasets, we demonstrate that our approach achieves fairness and performs more effectively than existing baselines.