TL;DR
In the world of fair division, "envy-freeness" is the gold standard, but it’s often impossible to achieve when dividing indivisible goods like houses or shifts. This paper proves that if agents have "dichotomous valuations"—meaning they value any additional item as either a 0 or a 1—you can always achieve perfect envy-freeness by giving each person a subsidy of at most one dollar.
What Problem Does This Paper Address?
Fair division is a classic problem in economics and computer science: how do we allocate resources among people with different preferences so that everyone is satisfied? The most popular fairness criterion is Envy-Freeness (EF), where no agent prefers someone else's bundle over their own.
When goods are divisible (like cake or land), EF is usually possible. But when goods are indivisible (like a car or a specific time slot), EF often fails—think of two people fighting over a single diamond. To fix this, researchers use subsidies (money) to "level the playing field."
The big question is: How much money do we need to eliminate envy? Previous research showed that for general preferences, you might need a lot of money ($O(n^2)$ total for $n$ agents). This paper looks at a specific but common case called dichotomous valuations, where an agent's marginal value for any good is either 0 or 1. This captures scenarios like "I need any three of these five shifts" or "I only care about items from category A."
Methods
The authors propose a constructive algorithm called ALG that builds a fair allocation one item at a time. Their approach relies on two key technical pillars:
- Envy-Graphs: They model the allocation as a directed graph where nodes are agents and edge weights represent how much one agent envies another. A known result states that an allocation is "envy-freeable" (can be made EF with some subsidy) if and only if this graph has no positive-weight cycles.
- Iterative Allocation with Subroutines:
- EXTEND: When a new good is introduced, the algorithm first tries to reassign existing bundles (using maximum-weight matching in bipartite graphs) to find an agent who can take the new good without pushing anyone's required subsidy above $1$.
- FINDSINK: If the allocation isn't "extendable," the algorithm uses a search process to find a "sink" agent. They prove that assigning the good to this specific agent keeps the required subsidies within the $\{0, 1\}$ range, even if it creates some temporary envy that the subsidy then covers.
The algorithm operates in the value-oracle model, meaning it doesn't need to know the agents' entire preference list upfront; it just needs to be able to ask, "How much do you value this specific set of goods?"
Datasets
As a theoretical paper in mathematical economics and computer science, it does not use empirical datasets or training data. Instead, it provides mathematical proofs of existence and algorithmic complexity. The "evaluation" is done through rigorous proof and a "non-example" (Appendix C) that demonstrates the algorithm's behavior on a specific five-good, three-agent instance.
Key Insights and Ideas
- The Power of "1": The most striking insight is that for any dichotomous valuation—no matter how complex the synergies between items are—a measly $1$ unit of subsidy per person is enough to kill all envy.
- Generality: Unlike previous work that focused on additive binary valuations (where the value of a bundle is just the sum of its parts), this result holds for general dichotomous valuations. This includes cases where items are substitutes or have complex requirements, as long as the marginal gain of one more item is never more than 1.
- Linear Improvement: By capping the per-agent subsidy at 1, the total subsidy required is at most $n-1$. This is a linear improvement over the previously known $O(n^2)$ bounds for more general monotone valuations.
- The "Sink" Existence: The proof that a "sink" agent always exists in the non-extendable case is the core technical achievement, involving intricate arguments about path weights in envy-graphs.
Key Results
- Existence Theorem: For any fair division instance with dichotomous valuations, there exists an envy-free solution where every agent's subsidy $p_i$ is either $0$ or $1$.
- Efficiency: Such an allocation and its corresponding subsidies can be computed in polynomial time.
- Tightness: The authors show their bound is tight. If you have $n$ agents and only one good that everyone values at 1, you must give the other $n-1$ agents a subsidy of 1 to prevent envy.
Limitations and Future Work
- Conflict with EF1: While the algorithm achieves envy-freeness with subsidies, it does not necessarily satisfy EF1 (Envy-Free up to One Good). EF1 is a popular "subsidy-free" fairness notion. The authors provide an example where their algorithm produces a result that is EF with subsidies but violates EF1.
- Monotone Valuations: The $O(n)$ total subsidy bound is specific to dichotomous valuations. Finding similarly tight bounds for general monotone valuations (where marginal values can be anything) remains an open challenge.
- Strategic Behavior: The paper focuses on finding a fair allocation assuming agents report their true values. It does not explore "strategy-proofness"—how to prevent agents from lying about their preferences to get a higher subsidy.
Summary updated