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 maximin 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 - ε) times her maximin share and the welfare of the computed allocation is at least the optimal, here ε >0 is a fixed constant. Our results for EF1 and MMS are based on establishing interesting majorization inequalities.