The maximum Nash welfare (MNW) solution-which selects an allocation that maximizes the product of utilities-is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy-free up to one good-a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and-even more so-in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation and demonstrate that it scales well on real data. These results establish MNW as a compelling solution for allocating indivisible goods and underlie its deployment on a popular fair-division website. 12:2 I. Caragiannis et al. We are interested in the problem of fairly allocating indivisible goods, such as jewelry or artworks. But to better understand the context for our work, let us start with an easier problem: fairly allocating divisible goods. Specifically, let there be m homogeneous divisible goods, and n players with linear valuations over these goods; that is, if player i receives an x iд fraction of good д, her value The question, of course, is what fraction of each good to allocate to each player; and it has an elegant answer, given more than four decades ago by Varian [41] . Under his competitive equilibrium from equal incomes (CEEI) solution, all players are endowed with an equal budget, say $1 each. The equilibrium is an allocation coupled with (virtual) prices for the goods, such that each player buys her favorite bundle of goods for the given prices, and the market clears (all goods are sold). One formal way to argue that this solution is fair is through the compelling notion of envy freeness [23]: Each player weakly prefers her own bundle to the bundle of any other player. This property is obviously satisfied by CEEI, as each player can afford the bundle of any other player, but instead chooses to buy her own bundle. While the CEEI solution may seem technically unwieldy at first glance, it always exists, and, in fact, has a very simple structure in the foregoing setting: the CEEI allocations (which are what we care about, as the prices are virtual) exactly coincide with allocations x that maximize the Nash social welfare i v i (x i ) [5, Volume 2, Chapter 14]. Consequently, a CEEI allocation can be computed in polynomial time via the convex program of Eisenberg and Gale [22] . Let us now revisit our original problem-that of allocating indivisible goods, under additive valuations: the utility of a player for her bundle of goods is simply the sum of her values for the individual goods she receives. This is an inhospitable world where central fairness notions like envy freeness cannot be guaranteed (just think of a single indivisible good and two players). Needless to say, the existence of a CEEI allocation is no longer assured. Nevertheless, the idea of maximizing the Nash social welfare (that is, the product of utilities) seems natural in and of itself [19, 37] . Informally, it hits a sweet spot between Bentham's utilitarian notion of social welfare-maximize the sum of utilities-and the egalitarian notion of Rawlsmaximize the minimum utility. Moreover, this solution is scale-free, in the sense that scaling a player's valuation function would not change the outcome [31] . But, when the maximum Nash welfare solution is wrenched from the world of divisible goods, it seems to lose its potency. Or does it? Our goal in this article is to demonstrate the "unreasonable effectiveness" [43]-or unreasonable fairness, if you will-of the maximum Nash welfare (MNW) solution, even when the goods are indivisible. We wish to convince the reader that . . . the MNW solution exhibits an elusive combination of fairness and efficiency properties, and can be easily computed in practice. It provides the most practicable approach to date-arguably, the ultimate solution-for the division of indivisible goods under additive valuations. Our quest for fairer algorithms is part of the growing body of work on practical applications of computational fair division [1, 16, 24, 27, 36] . We are especially excited about making a real-world impact through Spliddit (www.spliddit.org), a not-for-profit fair-division website [25] . Since its launch in November 2014, the website has attracted more than 90K users. The motto of Spliddit is provably fair solutions, meaning that the solutions obtained from each of the website's five applications satisfy guaranteed fairness properties. These properties are carefully explained to users,
As mentioned earlier, Caragiannis et al. REF introduced the notion of EFX: whether such allocations always exist is an enigmatic open problem.
The Unreasonable Fairness of Maximum Nash Welfare
TEAC
Computer Science