Fair Division by Contribution: A Shapley Value Perspective
For resource allocation problems where agents have heterogeneous contributions, this work provides a novel fairness notion and theoretical guarantees that bridge fairness and efficiency.
The paper introduces Shapley Value Fairness (SVF) for allocating divisible goods without monetary transfers, where agents' valuations reflect productivity. It provides tight asymptotic bounds on the approximation ratio for achieving SVF: Θ(ln n) for general concave valuations, Θ(ln D) for capped concave valuations, and Θ(min{k, ln γ, ln n}) for linear valuations, with efficient near-optimal allocations via sampling.
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.