2019/02/12 by Ioannis Caragiannis, Caragiannis, Ioannis, Nick Gravin +3 · 4 citations
Economics, Econometrics and Finance · Social Sciences · Neuroscience · #Game Theory and Voting Systems #Experimental Behavioral Economics Studies #Free Will and Agency
paper · pdf · doi:10.48550/arxiv.1902.04319
Several fairness concepts have been proposed recently in attempts to\napproximate envy-freeness in settings with indivisible goods. Among them, the\nconcept of envy-freeness up to any item (EFX) is arguably the closest to\nenvy-freeness. Unfortunately, EFX allocations are not known to exist except in\na few special cases. We make significant progress in this direction. We show\nthat for every instance with additive valuations, there is an EFX allocation of\na subset of items with a Nash welfare that is at least half of the maximum\npossible Nash welfare for the original set of items. That is, after donating\nsome items to a charity, one can distribute the remaining items in a fair way\nwith high efficiency. This bound is proved to be best possible. Our proof is\nconstructive and highlights the importance of maximum Nash welfare allocation.\nStarting with such an allocation, our algorithm decides which items to donate\nand redistributes the initial bundles to the agents, eventually obtaining an\nallocation with the claimed efficiency guarantee. The application of our\nalgorithm to large markets, where the valuations of an agent for every item is\nrelatively small, yields EFX with almost optimal Nash welfare. To the best of\nour knowledge, this is the first use of large market assumptions in the fair\ndivision literature. We also show that our algorithm can be modified to\ncompute, in polynomial-time, EFX allocations that approximate optimal Nash\nwelfare within a factor of at most 2\ρ, using a \ρ-approximate\nallocation on input instead of the maximum Nash welfare one.\n