AI summaryⓘ
The authors introduce a fairness concept called Shapley Value Fairness (SVF) for dividing resources among agents based on their contributions to overall value, rather than just equal shares. SVF uses the Shapley value, a tool from cooperative game theory, to measure each agent's fair entitlement in terms of their marginal contribution to social welfare. They analyze how closely this fairness ideal can be approximated in practice when dividing divisible goods without money, finding tight bounds depending on the type of valuation agents have. Additionally, the authors provide efficient methods to find near-best approximations for general valuation types. Overall, their work links fairness and efficiency in resource allocation when agents contribute differently to the collective outcome.
Shapley valuefairnessresource allocationdivisible goodssocial welfareconcave valuationslinear valuationsapproximation ratiocooperative game theorymarginal contribution
Authors
Xiaohui Bei, Pinyan Lu, Xiaowei Wu, Shengwei Zhou
Abstract
In many resource allocation problems, agents' valuations are best interpreted not as subjective preferences, but as the value they generate from receiving resources. Such valuations capture productivity, effectiveness, or technology, and may differ significantly across agents. In these settings, classical fairness notions such as proportionality or envy-freeness fail to reflect agents' heterogeneous contributions to the collective outcome. Motivated by this perspective, we introduce \emph{Shapley Value Fairness (SVF)} for the allocation of divisible goods without monetary transfers. SVF interprets an agent's entitlement as her expected marginal contribution to optimal social welfare, and uses the Shapley value of the associated welfare maximization game as a normative fairness benchmark. We position SVF relative to existing fairness notions and show that it provides a natural bridge between fairness and efficiency in contribution-based environments. Since exact implementation of the Shapley value is generally infeasible without transfers, SVF naturally leads to the problem of finding allocations that approximate this benchmark as well as possible. We provide a systematic worst-case analysis of the achievable Shapley approximation ratio. For general concave valuations, we establish a tight $Θ(\ln n)$ bound. For capped concave valuations with bounded demands, this bound improves to $Θ(\ln D)$, where $D$ is the maximum aggregate demand for any item. For linear valuations, we further refine the bound to $Θ(\min\{k, \ln γ, \ln n\})$ in terms of the number of agent types $k$ and the value fluctuation ratio $γ$, and show that all bounds are asymptotically tight. Regarding per-instance guarantees, we show that a near-optimal approximation allocation can be computed efficiently (with high probability) via sampling for general concave valuations.