Private algorithms improve fair division of indivisible goods
Differentially Private Multicolor Discrepancy and Fair Division of Indivisible Goods
Computer Science and Game Theory
Summary
Fairly dividing items among people is hard when the items can’t be split and privacy about preferences is important. The authors study how to do this division so that people mostly feel things are fair, while protecting their private preferences. They improve previous methods by reducing how many items need to be ignored for fairness when keeping privacy. They also show faster methods if item values come from a small set, and prove some limits on how fair you can get while being private.
What this means in practice
- •For marketplace platform developers: Implement privacy-preserving methods to fairly allocate indivisible items among users while reducing fairness violations.
- •For data privacy engineers: Develop algorithms that balance fairness and strong privacy guarantees when allocating limited resources or items.
A theory result. No direct application yet.
Authors
Max Dupré la Tour
Abstract
We study the fair division of indivisible goods under pure differential privacy, continuing the line of work initiated by Manurangsi and Suksompong. For $n$ agents with nonnegative additive utilities over $m$ goods and a fixed privacy parameter, we give an entry-private algorithm that, with high probability, achieves consensus envy-freeness up to $O(\sqrt n+\log^3 m)$ goods. This substantially improves the dependence on $n$ over the previous $O(n\log m)$ guarantee for ordinary envy-freeness, while providing the stronger consensus guarantee. A key ingredient is a private algorithm for multicolor discrepancy, which may be of independent interest. Our algorithm may require exponential time. We also obtain substantially stronger guarantees under additional structure: when all item values belong to a public alphabet of size $D$, we give a polynomial-time entry-private algorithm achieving ordinary envy-freeness up to $O(\operatorname{polylog}(mD))$ goods with high probability. Finally, we prove an $Ω(\log n)$ lower bound on the number of goods that must be removed to achieve ordinary envy-freeness under entry privacy, for sufficiently many goods, even with binary utilities.