用K-Shapley值实现预算约束下的公平选择,理论与实验均验证其有效性。
Meritocratic Fairness via $K$-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback

- 引入K-Shapley值衡量每臂在最多选K个时的边际贡献,满足公平性公理。
- 提出IW-KSVFair算法,在真实数据上实现接近理论最优的公平后悔率。
- 适合关注资源分配公平性、带预算约束的推荐系统研究者。
我们研究预算约束下的组合多臂老虎机中基于全反馈的功绩公平性问题,即每轮最多选择K个臂,仅观测所选集合的噪声总回报。为定义预算限制下的功绩,提出K-Shapley值——一种仅考虑大小不超过K的联盟的古典Shapley值变体。证明其是唯一满足对称性、线性性、零玩家和K-效率公理的解。针对单调亚模估值函数,建立Ω(T^{2/3})的公平后悔下界。设计探索-然后-承诺算法MURaS,通过均匀探索所有臂,达到~O(T^{2/3})公平后悔。为提升实际性能,提出IW-KSVFair算法,学习一个选择策略,使各臂被选概率与其未知的K-Shapley值成比例。通过重要性加权估计并混合自适应分布与均匀分布,控制重要性权重有界。证明该算法实现~O(T^{2/3})公平后悔,逼近下界。合成与真实数据集上的实验表明,IW-KSVFair具有低累积公平后悔,且实测选择频率高度匹配基于K-Shapley值的功绩排序。
原文摘要 · Abstract (English)
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 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。