aiqbench analysis
This research introduces the $K$-Shapley value as a novel fairness metric for budgeted combinatorial bandits, addressing how limited resources should be distributed among agents with varying contributions. By proving matching upper and lower bounds on regret, the authors establish that their proposed algorithms can effectively learn selection policies aligned with this meritocratic framework without incurring excessive performance loss. The work advances theoretical understanding of fairness constraints within resource-constrained sequential decision-making environments.
Meritocratic Fairness via $K$-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback
arXiv:2605.00762v2 Announce Type: replace-cross Abstract: 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(T^{2/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(T^{2/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(T^{2/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.
Abstract: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(T^{2/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(T^{2/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(T^{2/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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA)
arXiv:2605.00762 [cs.LG]
(or arXiv:2605.00762v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2605.00762 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 315 words
Related coverage
AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints
arXiv · Oct 7, 2026
Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
arXiv · Oct 2, 2026
Deadlock in the Parliament of the Self
LessWrong · Oct 10, 2026
Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
arXiv · Jul 28, 2026