A fair and truthful mechanism with limited subsidy

• 成果类型: Article
• 署名作者: Goko, Hiromichi; Igarashi, Ayumi; Kawase, Yasushi; Makino, Kazuhisa; Sumita, Hanna; Tamura, Akihisa; Yokoi, Yu; Yokoo, Makoto
• 署名单位: Toyota Motor Corporation; University of Tokyo; Kyoto University; Institute of Science Tokyo; Tokyo Institute of Technology; Keio University; Kyushu University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2023.12.006
• 发表日期: 2024
• 页码: 49-70
• 关键词: Mechanism design with money; Envy-freeness; resource allocation; Algorithmic game theory

摘要

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.