Fair division of indivisible goods among strategic agents

Abstract

We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and max-imin share guarantee (MMS). We show that (in a single-parameter environment) the problem of maximizing welfare, subject to the constraint that the allocation of the indivisible goods is EF1, admits a polynomial-time, 1/2-approximate, truthful auction. Under MMS setup, we develop a truthful auction which efficiently finds an allocation wherein each agent gets a bundle of value at least (1/2-f) times her maximin share and the welfare of the computed allocation is at least the optimal, here e > 0 is a fixed constant. Our results for EF1 and MMS are based on establishing interesting majorization inequalities. � 2019 International Foundation for Autonomous Agents and Multiagent Systems. All rights reserved.