  We study the problem of fairly allocating a set of indivisible goods among
agents with additive valuations. The extent of fairness of an allocation is
measured by its Nash social welfare, which is the geometric mean of the
valuations of the agents for their bundles. While the problem of maximizing
Nash social welfare is known to be APX-hard in general, we study the
effectiveness of simple, greedy algorithms in solving this problem in two
interesting special cases.
  First, we show that a simple, greedy algorithm provides a 1.061-approximation
guarantee when agents have identical valuations, even though the problem of
maximizing Nash social welfare remains NP-hard for this setting. Second, we
show that when agents have binary valuations over the goods, an exact solution
(i.e., a Nash optimal allocation) can be found in polynomial time via a greedy
algorithm. Our results in the binary setting extend to provide novel, exact
algorithms for optimizing Nash social welfare under concave valuations.
Notably, for the above mentioned scenarios, our techniques provide a simple
alternative to several of the existing, more sophisticated techniques for this
problem such as constructing equilibria of Fisher markets or using real stable
polynomials.
