Subquadratic subsidies help share goods fairly among many people

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations

Computer Science and Game Theory

Summary

The paper looks at how to fairly share items among people when those items can have positive or negative value, like goods or chores. It studies a fairness idea called envy-freeness, where no one prefers someone else’s share over their own if some extra value (subsidy) is added. The authors show that the total subsidy needed to keep everyone happy grows slower than the square of the number of people, which is an improvement over previous results. This applies to cases where people value all items nonnegatively or all nonpositively, but without needing values to neatly increase or decrease. Their work helps understand fair division when preferences are more complex than just adding up simple values.

envy-freenesssubsidiesindivisible itemsvaluationmonotone goodsmonotone choresfair divisioncomputational social choicecomplex preferencessubquadratic bounds

Authors

Max Dupré la Tour, Mashbat Suzuki

Abstract

We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.
View PDFOpen arXiv