Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods

Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao

TL;DR

This paper investigates the challenge of fairly and truthfully allocating a mix of divisible (like money) and indivisible (like a car) goods. They prove that achieving both perfect fairness (envy-freeness) and truthfulness is impossible in general, even for simple scenarios. However, they design truthful and fair mechanisms for specific, more restricted settings.

What Problem Does This Paper Address?

The fair allocation of resources is a long-standing problem with applications ranging from school admissions to resource management. A key fairness criterion is "envy-freeness," where no agent prefers another agent's bundle to their own. When dealing with indivisible goods, perfect envy-freeness can be impossible, leading to relaxations like "envy-freeness up to one good" (EF1). This paper tackles the more complex scenario of allocating a mixture of divisible and indivisible goods, aiming for a fairness notion called "envy-freeness for mixed goods" (EFM).

Crucially, the paper also considers "truthfulness," meaning agents should not benefit from lying about their preferences. Designing mechanisms that are both fair (EFM) and truthful is a significant challenge. Previous work has addressed these properties separately or for purely divisible or indivisible goods. This paper bridges this gap by exploring their compatibility in the mixed goods setting, which is more representative of real-world resource allocation problems.

Methods

The paper starts by establishing a strong impossibility result: they prove that it's impossible to design a mechanism that is both truthful and achieves EFM (even a relaxed version called EFM>0) in general, even with just two agents and one divisible and one indivisible good. This is a significant finding, highlighting the inherent difficulty of the problem.

Following this, they propose constructive mechanisms for specific scenarios:

  • Binary valuations on indivisible goods and identical valuation on a single divisible good: Here, agents have simple "yes/no" preferences for indivisible items and the same value for each unit of a divisible good (like money). They design a truthful and EFM mechanism that first uses a truthful EF1 mechanism (MNWtie) for the indivisible goods and then employs a "water-filling" process to distribute the divisible good. This process aims to equalize agent utilities in a fair and truthful manner.
  • Binary valuations on both divisible and indivisible goods: For this setting, they consider two sub-cases:
  • Two agents: They develop a truthful and EFM mechanism that leverages MNWtie for indivisible goods and then strategically allocates divisible goods to resolve potential envy.
  • A single divisible good: They design a truthful and EFM mechanism that again uses MNWtie for indivisible goods and then distributes the single divisible good to agents with the lowest valuations on their indivisible bundles.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanism design and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Incompatibility is the norm: The most striking insight is the general incompatibility of truthfulness and envy-freeness for mixed goods. This suggests that achieving both perfectly is often impossible, forcing trade-offs.
  • The power of MNWtie: The paper leverages existing truthful mechanisms for indivisible goods (specifically, MNWtie which is truthful and outputs leximin/MNW allocations) as a foundation for their mixed-goods mechanisms. This highlights the modularity of mechanism design.
  • "Water-filling" for fairness: The "water-filling" approach for allocating divisible goods is a key technique. It's an intuitive way to distribute a resource to equalize agent satisfaction or utility, and here it's adapted to maintain truthfulness and fairness.
  • Restricted settings unlock solutions: The paper demonstrates that by imposing specific constraints on agent valuations (e.g., binary valuations, identical values for divisible goods), it becomes possible to design mechanisms that are both truthful and fair. This is a common theme in mechanism design: generality often leads to impossibility, while restrictions enable solutions.

Key Results

  • Impossibility Result: There is no general truthful and EFM mechanism for mixed divisible and indivisible goods, even with two agents and one of each good type.
  • Constructive Mechanisms:
    • A truthful and EFM mechanism is designed for binary valuations on indivisible goods and identical valuations on a single divisible good. This mechanism also achieves leximin and MNW properties.
  • Truthful and EFM mechanisms are developed for the case of two agents with binary valuations on all goods.
  • A truthful and EFM mechanism is presented for the case of multiple agents with binary valuations on indivisible goods and a single divisible good.

Limitations and Future Work

  • General Case Remains Open: The paper's impossibility result highlights that a general solution for arbitrary valuations and mixed goods is unlikely.
  • Focus on Binary Valuations: Many of the constructive results rely on agents having binary valuations. Extending these to more general valuation functions is a natural next step.
  • Weaker Notions of Truthfulness: Given the impossibility of full truthfulness, the authors suggest exploring weaker notions like maximin strategy-proofness, not obviously manipulation (NOM), and risk-averse truthfulness.
  • Determining Compatibility: A key future direction is to fully characterize the conditions under which truthfulness and EFM are compatible for agents with binary valuations on all goods.

Summary updated

Abstract

We study the problem of designing truthful and fair mechanisms when allocating a mixture of divisible and indivisible goods. We first show that there does not exist an EFM (envy-free for mixed goods) and truthful mechanism in general. This impossibility result holds even if there is only one indivisible good and one divisible good and there are only two agents. Thus, we focus on some more restricted settings. Under the setting where agents have binary valuations on indivisible goods and identical valuations on a single divisible good (e.g., money), we design an EFM and truthful mechanism. When agents have binary valuations over both divisible and indivisible goods, we first show there exist EFM and truthful mechanisms when there are only two agents or when there is a single divisible good. On the other hand, we show that the mechanism maximizing Nash welfare cannot ensure EFM and truthfulness simultaneously.
BibTeX
@inproceedings{li2023truthful,
  author = {Zihao Li and Shengxin Liu and Xinhang Lu and Biaoshuai Tao},
  title = {{Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/313},
}
Figure