On Truthful Mechanisms for Maximin Share Allocations

Abstract

We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of $n$ players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem mostly algorithmically, providing constant factor approximation algorithms. In this work we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

References in corpus (1)

• A Social Welfare Optimal Sequential Allocation Procedure

Cited by in corpus (7)

• Approximation Algorithms for Computing Maximin Share Allocations
• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Asymptotic Existence of Fair Divisions for Groups
• Approximate Maximin Shares for Groups of Agents
• Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors
• Ordinal Maximin Share Approximation for Goods
• An Improved Approximation Algorithm for Maximin Shares