Introduction
In the field of fair division, the "envy-free" (EF) criterion is considered the gold standard for equity: an allocation is envy-free if every agent believes their assigned bundle of goods is at least as valuable as any other agent's bundle. However, when dealing with indivisible goods—such as houses, specific work shifts, or unique equipment—envy-free allocations often do not exist. To resolve this, researchers frequently employ subsidies, where small monetary payments are used to compensate agents who receive less desirable bundles, thereby "leveling the playing field."
A central challenge in this domain is determining the minimum subsidy required to eliminate envy. While previous research established bounds for specific preference types like unit-demand or binary additive valuations, this paper investigates dichotomous valuations. This is a broad and complex class where an agent's marginal utility for adding a new good to their current set is always either 0 or 1. This captures scenarios where a good's value depends on the existing bundle—for instance, a work shift might only be valuable if it is contiguous with another—provided the utility increase remains binary.
The Algorithmic Framework
The authors propose a constructive algorithmic approach to guarantee envy-freeness with minimal subsidies. The primary tool used is the envy-graph, a directed graph where nodes represent agents and edge weights represent the degree of envy one agent has for another's bundle. An allocation is considered "envy-freeable" if and only if its envy-graph contains no positive-weight cycles.
The core algorithm, designated as ALG, allocates goods incrementally while maintaining an envy-freeable state. It restricts subsidies to the set $\{0, 1\}$ per agent. The algorithm relies on two sophisticated subroutines:
- EXTEND: This routine checks if current bundles can be reassigned among agents to maximize social welfare. It attempts to give a new good to a "highly subsidized" agent who values it, without requiring the subsidy to exceed 1 unit.
- FINDSINK: If a simple extension is not possible, this routine searches for a "sink" agent in the envy-graph. The good is assigned to this agent in a way that keeps the resulting required subsidies within the $\{0, 1\}$ range.
By carefully reassigning bundles to maximize social welfare as new goods are introduced, the algorithm ensures the "envy gap" never exceeds the capacity of a single unit of subsidy per agent.
Key Insights and Theoretical Results
The paper provides several significant contributions to the theory of fair division:
- Generality of Results: Unlike prior work restricted to additive or submodular valuations, these results hold for any monotone valuation with binary marginals. This significantly expands the class of functions for which tight subsidy bounds are known.
- Tightness of the Bound: The authors prove that a total subsidy of $n-1$ (where $n$ is the number of agents) is both sufficient and tight. For example, in a scenario with $n$ agents and only one good that everyone values at 1, the $n-1$ agents who do not receive the good must each receive a subsidy of 1 to prevent envy.
- Linear Improvement: For general monotone valuations, the best-known total subsidy bound was $O(n^2)$. By focusing on the dichotomous case, this research provides a linear improvement (a factor of $n$), showing that $O(n)$ total subsidy always suffices.
- Computational Efficiency: The proposed algorithm finds the allocation and subsidy vector in polynomial time. It only requires a "value oracle"—a mechanism to query an agent's valuation of any given set of goods—making it computationally practical.
Conclusion and Future Work
This work establishes that for any instance with dichotomous valuations, there exists an allocation and a subsidy vector where every agent receives at most 1 unit of subsidy, and the total subsidy does not exceed $n-1$.
Despite these advances, the authors note certain limitations. The "0 or 1" subsidy guarantee is strictly dependent on the dichotomous nature of the valuations; if marginal values are non-binary, the bound no longer holds. Additionally, while the algorithm guarantees limited subsidies, it does not necessarily produce an EF1 allocation (Envy-Free up to one good). Future research may focus on finding allocations that simultaneously satisfy limited subsidies and the EF1 property, or seeking tighter, linear subsidy bounds for general monotone valuations, which remains a major open challenge in the field.
Summary updated