Abstract
In the division of indivisible items—such as houses, cars, or specific tasks—standard fairness guarantees like envy-freeness or equitability are often impossible to satisfy. This research, authored by Haris Aziz (UNSW Sydney and Data61 CSIRO), demonstrates that by incorporating monetary transfers, it is possible to achieve both properties simultaneously for a broad class of preferences. By introducing the concept of "transfer-stability," the paper provides a complete characterization of allocations that can be made fair and presents a polynomial-time algorithm to find them.
1. Introduction
In the field of computational social choice, fair division typically focuses on two primary objectives: Envy-Freeness (EF), where no agent prefers another's bundle over their own, and Equitability (EQ), where all agents receive the exact same level of utility. While these are achievable with divisible goods (like land or liquids), they are often mutually exclusive or mathematically impossible when items cannot be split.
To bridge this gap, researchers utilize monetary transfers—subsidies or side payments—to "level the playing field." While previous literature has addressed achieving envy-freeness with money (e.g., the "room-rent" problem), achieving simultaneous EF and EQ is significantly more complex. This paper addresses this challenge by identifying the necessary conditions and algorithmic paths to dual fairness.
2. Defining Transfer-Stability
The central contribution of this work is the identification of transfer-stability. An allocation is considered transfer-stable if no agent $i$ can take another agent $j$’s bundle and derive more value from the combined set than the sum of their individual current values. Formally, for any two agents $i$ and $j$:
$$v_i(X_i \cup X_j) \leq v_i(X_i) + v_j(X_j)$$
For additive utilities, this condition is both necessary and sufficient for an allocation to be "EFEQ-convertible"—meaning it can be transformed into an envy-free and equitable state through specific payments.
3. The Mechanism: Knaster Payments
To achieve equitability, the paper employs Knaster payments. Under this scheme, each agent $i$ makes a payment $p_i$ calculated based on their valuation of their assigned bundle $X_i$ relative to the average social welfare:
$$p_i = v_i(X_i) - \frac{SW(X)}{n}$$
Where $SW(X)$ represents the total social welfare (the sum of all agents' valuations) and $n$ is the number of agents. This formula ensures that every agent’s net utility (value of items minus payment) is exactly equal to the average social welfare ($SW(X)/n$). By design, this satisfies the equitability requirement. The challenge then lies in ensuring that these payments also satisfy envy-freeness, which is guaranteed if the underlying allocation is transfer-stable.
4. Algorithmic Framework
Aziz proposes a greedy distributed algorithm to reach a transfer-stable allocation efficiently:
- Initialization: Start with any arbitrary allocation of items among the agents.
- Welfare Improvement: If an agent $i$ can take agent $j$'s bundle and increase the total social welfare, the bundle is moved to agent $i$.
- Convergence: This process repeats until no further welfare-improving transfers are possible.
- Finalization: Apply the Knaster payment formula to the resulting allocation.
The paper proves that this algorithm is guaranteed to find a transfer-stable allocation in polynomial time, specifically requiring at most $O(n^2)$ transfers.
5. Key Theoretical Insights
- Hierarchy of Fairness: The research establishes a clear relationship between fairness classes. EFEQ-convertible allocations (those that can be made both EF and EQ) are a subset of envy-freeable allocations, which are themselves a subset of equitable-convertible allocations.
- Social Welfare and Fairness: A significant finding is that any allocation maximizing social welfare is inherently EFEQ-convertible. This implies that global efficiency and individual fairness are not necessarily in conflict when monetary transfers are permitted.
- Beyond Additivity: While much of the analysis focuses on additive valuations, the paper extends the sufficiency of transfer-stability to superadditive valuations, where the value of a combined bundle is greater than or equal to the sum of its parts.
6. Complexity and Subsidies
While finding any EFEQ outcome is computationally efficient, finding the optimal one—specifically the one requiring the minimum total subsidy—is a different matter. Theorem 5 proves that minimizing the total subsidy is strongly NP-hard and difficult to approximate.
However, the paper shows that if the goal is to avoid out-of-pocket costs for agents (a "subsidies only" approach), one can simply add a uniform subsidy to all Knaster payments until the largest payment is zero. This adjustment maintains both EF and EQ while ensuring no agent is financially penalized for participating.
7. Conclusion and Future Work
Haris Aziz’s work provides a robust mathematical foundation for achieving perfect fairness in the division of indivisible goods. By leveraging transfer-stability and Knaster payments, the paper offers a practical algorithmic approach to a long-standing problem in social choice.
Limitations remain, such as the "one agent takes all" problem, where an agent with significantly higher efficiency might receive all items—a result that is technically fair under the utility definitions but potentially socially undesirable. Future research may focus on addressing these edge cases or developing heuristics for the NP-hard problem of subsidy minimization.
Summary updated