{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:38:07Z","timestamp":1761176287899,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>The Nash Welfare (NW) objective\u2014the geometric mean of utilities\u2014is often considered as a good compromise between fairness and efficiency. The respective maximization problem (MNW) for indivisible goods was first proposed in\u00a0[11] and has received significant attention in the recent years with the current best e1\/e-approximation 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\u00a0[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\u2014money, 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 \u00b7 m) dollars. On the positive side, we construct a polynomial scheme that with the amount of money c \u00b7 n produces an integral allocation with integrality gap IG(s) \u2264 max\u03b1\u2208[0,1](2c\/(2c \u2013 1 + \u03b1))\u03b1, where IG(s) &lt; 1.43 for c = 0.51, IG(s) &lt; 1.16 for c = 1, and IG(s) &lt; 1.07 for c = 2.<\/jats:p>","DOI":"10.3233\/faia251380","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:59:59Z","timestamp":1761127199000},"source":"Crossref","is-referenced-by-count":0,"title":["Integrality Gap of Nash Welfare Maximization with Money"],"prefix":"10.3233","author":[{"given":"Yuriy","family":"Dementiev","sequence":"first","affiliation":[{"name":"Saint Petersburg State University"},{"name":"St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[{"name":"Key Laboratory of Interdisciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artur","family":"Ignatiev","sequence":"additional","affiliation":[{"name":"Saint Petersburg State University"},{"name":"St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:59:59Z","timestamp":1761127199000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251380","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}