Mechanism design for fair division: allocating divisible items without payments

Richard Cole, Vasilis Gkatzelis, Gagan Goel

TL;DR

This paper introduces a novel mechanism for fairly dividing divisible resources among agents without using monetary payments. Their "Partial Allocation" mechanism guarantees each agent receives at least 36.8% of their "Proportionally Fair" share, a significant improvement for truthful resource allocation. They also show that achieving better than 50% for even simpler scenarios is impossible with truthful mechanisms.

What Problem Does This Paper Address?

The fair division of resources is a long-standing problem with applications from inheritance disputes to modern cloud computing. A key challenge in designing systems that allocate resources is ensuring agents report their true preferences (valuations) truthfully. This is crucial for achieving fair and efficient outcomes. While monetary payments are a common tool in mechanism design to incentivize truthfulness, many real-world scenarios, like internal resource allocation within companies or certain types of auctions, prohibit their use. This paper tackles the problem of designing truthful mechanisms for fair division of divisible items without relying on monetary transfers, focusing on the widely accepted "Proportional Fairness" (PF) as the benchmark for a desirable outcome.

Methods

The core contribution is the Partial Allocation (PA) mechanism. This mechanism works by:

  1. Computing the ideal "Proportionally Fair" (PF) allocation based on reported valuations. The PF allocation is a Pareto-optimal allocation that balances fairness and efficiency, related to Nash bargaining and competitive equilibrium.
  2. Calculating what each agent would have received if they were absent from the system.
  3. Discarding a carefully calculated fraction of each agent's allocated resources. This "money burning" or resource discarding is the key to incentivizing truthfulness. The fraction discarded for agent i is derived from the ratio of valuations of other agents in the full PF allocation versus the PF allocation without agent i.

The paper also introduces the Strong Demand Matching (SDM) mechanism for a specific scenario: additive linear valuations where items are highly demanded. This mechanism uses a rising price approach to match bidders to items, achieving better approximation factors in these specific cases.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanism design and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • "Money Burning" as a Truthfulness Incentive: The paper demonstrates that strategically discarding a portion of allocated resources can effectively incentivize truthful reporting, even without monetary payments. This is a powerful insight for designing mechanisms in payment-restricted environments.
  • Proportional Fairness is Hard to Implement Truthfully: A fundamental finding is that achieving the ideal Proportional Fairness allocation is impossible with truthful mechanisms. This motivates the search for good approximations.
  • The 1/e Guarantee is Significant: Achieving at least a 1/e (approx. 36.8%) fraction of an agent's ideal PF valuation is a strong positive result for a general class of valuation functions and a large number of agents. This is the first such constant-factor guarantee for PF.
  • The 0.5 Impossibility is a Tight Bound: The negative result showing that no truthful mechanism can guarantee more than a 0.5 approximation, even for simple additive linear valuations, highlights the inherent limitations of truthful mechanisms in this domain.
  • Connection to VCG Payments: The paper reveals a surprising connection between the resource discarding in the PA mechanism and VCG payments. By using a logarithmic transformation of valuations, the "payment" in the PA mechanism becomes analogous to the externality payments in VCG mechanisms, suggesting a deeper theoretical link.

Key Results

  • Partial Allocation (PA) Mechanism: Guarantees every agent receives at least a 1/e ≈ 0.368 fraction of their Proportionally Fair (PF) valuation for homogeneous valuation functions of degree one.
  • Negative Result: No truthful mechanism can guarantee an approximation factor better than 0.5 for additive linear valuations, even for two players. This bound drops further with more players.
  • Envy-Freeness: The PA mechanism is proven to be envy-free for additive linear and Leontief valuations, meaning no agent prefers another agent's bundle.
  • Strong Demand Matching (SDM) Mechanism: Achieves an approximation factor of min; {p/[p]} for additive linear valuations when items are highly demanded (where p is the PF price of item j). This can be significantly better than 1/e in such scenarios.

Limitations and Future Work

  • Closing the Approximation Gap: The paper highlights the gap between the 1/e approximation guarantee (for general homogeneous valuations) and the 0.5 impossibility result (for additive linear valuations). Closing this gap is a key open problem.
  • Maximizing Product of Ratios: The authors suggest exploring an objective that maximizes the product of agents' achieved valuations relative to their PF valuations, rather than the minimum ratio. This might allow for better overall outcomes, potentially by sacrificing individual guarantees.
  • Generalizing Homogeneous Valuations: The paper extends results to general homogeneous valuations of degree d and hints at further generalization for functions of the form v(fx) = g(f)v(x).
  • Understanding "Money Burning": Further research is needed to understand the power and implications of "money burning" (resource discarding) in mechanism design, especially in contrast to monetary payments.
  • Efficiency of PA Mechanism: While the PA mechanism provides truthful and fair outcomes, its efficiency (how close the outcome is to the optimal social welfare) is not the primary focus and could be a direction for future work.

Summary updated

Abstract

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1/e ≈ 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design. We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded.
BibTeX
@inproceedings{cole2013mechanism,
  author = {Richard Cole and Vasilis Gkatzelis and Gagan Goel},
  title = {{Mechanism design for fair division: allocating divisible items without payments}},
  booktitle = {EC},
  year = {2013},
  doi = {10.1145/2492002.2482582},
}
Figure