A fair and truthful mechanism with limited subsidy

Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations.

Original languageEnglish
Pages (from-to)49-70
Number of pages22
JournalGames and Economic Behavior
Volume144
DOIs
Publication statusPublished - 2024 Mar

Keywords

  • Algorithmic game theory
  • Envy-freeness
  • Mechanism design with money
  • Resource allocation

ASJC Scopus subject areas

  • Finance
  • Economics and Econometrics

Fingerprint

Dive into the research topics of 'A fair and truthful mechanism with limited subsidy'. Together they form a unique fingerprint.

Cite this