Subquadratic subsidies reduce envy in fair item allocation
Subquadratic Subsidies for Nonnegative or Nonpositive Valuations
Computer Science and Game Theory
Summary
The paper deals with how to fairly share items among people without making anyone feel jealous. The authors found a way to add small subsidies (extra payments) that ensure everyone feels their share is fair, even when values are not simple additions and can be all positive or all negative. This improves on previous methods by reducing the total required subsidy amount, especially when there are many people. Their work applies to many real cases like dividing chores or distributing goods.
What this means in practice
- •For marketplace platform designers: Design fair resource-sharing systems that minimize extra payments needed to keep users satisfied when dividing goods or chores.
- •For algorithm engineers: Build allocation algorithms that ensure envy-freeness with lower subsidy budgets for diverse valuation scenarios including all-positive or all-negative preferences.
A theory result. No direct application yet.
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.