Abstract
We consider the problem of fairly allocating a set
of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly
growing field of fair division, but the Nash social
welfare (NSW) serves as a focal point. In part,
this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic
concept of efficiency, Pareto optimality. However,
existing approximation algorithms fail to satisfy all
of the remarkable fairness guarantees offered by
a max NSW allocation, instead targeting only the
specific NSW objective. We address this issue by
presenting a 2 max NSW, Prop-1, 1/(2n) MMS,
and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market
interpretation of a fractional max NSW allocation.
We present novel definitions of fairness concepts in
terms of market prices, and design a new scheme
to round a market equilibrium into an integral allocation in a way that provides most of the fairness
properties of an integral max NSW allocation