Algorithms improve fairness in dividing items with complex preferences
Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations
Data Structures and Algorithms
Summary
The paper studies how to fairly divide a set of items among people who value combinations differently. It focuses on two fairness goals: making the least happy person as happy as possible and balancing happiness across people with different weights. The authors develop new algorithms that give better guarantees on how fair the division can be, especially when people's preferences are complex but satisfy certain mathematical properties. They also show limits on how well any algorithm can do based on known mathematical models.
What this means in practice
- •For resource allocation engineers: Use improved algorithms to allocate limited resources fairly among agents with complex value assessments, ensuring no agent is left with disproportionately low value.
- •For marketplace platform developers: Implement fair item distribution mechanisms that balance user satisfaction weighted by priority or customer importance in complex-valued preference settings.
Authors
Yuhang Chen, Yuda Feng, Weijiang Hu, Shi Li, Ruilong Zhang
Abstract
We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known as the Santa Claus problem, which maximizes the smallest value of an agent, and the weighted Nash social welfare, which maximizes the weighted geometric mean of the agents' values. For the max-min allocation problem, we give a randomized polynomial-time $O(\sqrt n)$-approximation algorithm for subadditive valuations with demand queries, improving the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value queries, we give simpler $O(\sqrt n)$-approximation algorithms. For additive valuations, this improves the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon)$-approximation algorithms are also known for every constant $\varepsilon>0$. Our ratios depend only on $n$ and match, up to constants, the $Ω(\sqrt n)$ integrality gap of the configuration LP. For the weighted Nash social welfare problem with subadditive valuations and demand queries, we give an $O(Γ(w))$-approximation algorithm, where $Γ(w)=\exp\bigl((\ln n-H(w))/2\bigr)$ and $H(w)$ is the entropy of the weight vector $w$. The factor $Γ(w)$ equals $1$ for equal weights and is at most $\sqrt n$ for all weights. We show that this ratio is tight for algorithms analyzed against the configuration LP: for every weight vector, the configuration LP has an integrality gap of $Θ(Γ(w))$, even for XOS valuations, and this gap is $Ω(\sqrt n)$ when one agent has almost all the weight. For submodular valuations, the configuration LP has a constant integrality gap for all weights.