TY - GEN

T1 - Integrality Gap of Nash Welfare Maximization with Money

AU - Дементьев, Юрий Ильич

AU - Гравин, Николай

AU - Игнатьев, Артур Андреевич

PY - 2025/10/21

Y1 - 2025/10/21

N2 - 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. Wemodel 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 theamount 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.

AB - 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. Wemodel 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 theamount 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.

U2 - 10.3233/faia251380

DO - 10.3233/faia251380

M3 - Conference contribution

BT - ECAI 2025

T2 - 28th European Conference on Artificial Intelligence

Y2 - 25 October 2025 through 30 October 2025

ER -