The Nash Welfare (NW) objective—the geometric mean of utilities—is often considered as a good compromise between fairness and efficiency. The respective maximization problem (MNW) for indivisible goods was first proposed in [11] and has received significant attention in the recent years with the current best e1/eapproximation guarantee. A natural approach of first solving fractional MNW (i.e., where all items are divisible) and then rounding solution does not work, as the integrality gap of MNW can be unbounded [11]. However, from a practical perspective, e.g., in inheritance division, many instances are actually mixed. I.e., the instance has a significant amount of liquid assets, which can be easily converted into money and thus divided fractionally between agents. We
model such instances with a set of indivisible goods and a single divisible good—money, which has the same value for every agent. We study the integrality gap of the MNW parametrized by the amount of money s in the instance. This parametrization is closely related to the literature on fair division with subsidies initiated by [17], where it is assumed that the maximum value of any agent per item is vmax = 1. We find that the IG may be non-monotone in s and could be strictly larger than 1 for a large amount of money s = O(n · m) dollars.
On the positive side, we construct a polynomial scheme that with the
amount of money c · n produces an integral allocation with integrality gap IG(s) ≤ maxα∈[0,1]( 2c2c−1+α )α, where IG(s) < 1.43 for c = 0.51, IG(s) < 1.16 for c = 1, and IG(s) < 1.07 for c = 2.