{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:37Z","timestamp":1778231437165,"version":"3.51.4"},"reference-count":40,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or [Formula: see text] for some fixed coprime numbers [Formula: see text] such that [Formula: see text]. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the value of q. We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, [Formula: see text]. We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, [Formula: see text]. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever [Formula: see text].<\/jats:p>\n                  <jats:p>Funding: M. Hoefer and G. Varricchio were supported by the DFG [Grant Ho 3831\/5-1].<\/jats:p>","DOI":"10.1287\/moor.2023.0204","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T14:54:32Z","timestamp":1737471272000},"page":"853-876","source":"Crossref","is-referenced-by-count":0,"title":["Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability"],"prefix":"10.1287","volume":"51","author":[{"given":"Hannaneh","family":"Akrami","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, 66123 Saarbr\u00fccken, Germany; and Hertz Chair for Algorithms and Optimization, Bonn University, 53113 Bonn, Germany; and Universit\u00e4t des Saarlandes, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7808-1483","authenticated-orcid":false,"given":"Bhaskar Ray","family":"Chaudhury","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, Illinois 61820; and Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana-Champaign, Urbana, Illinois 61820"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0131-5605","authenticated-orcid":false,"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4020-4334","authenticated-orcid":false,"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, 66123 Saarbr\u00fccken, Germany; and Universit\u00e4t des Saarlandes, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Schmalhofer","sequence":"additional","affiliation":[{"name":"Institute for Computer Science, Goethe University Frankfurt, 60629 Frankfurt am Main, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6169-7337","authenticated-orcid":false,"given":"Golnoosh","family":"Shahkarami","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, 66123 Saarbr\u00fccken, Germany; and Saarbr\u00fccken Graduate School of Computer Science, Universit\u00e4t des Saarlandes, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6839-8551","authenticated-orcid":false,"given":"Giovanna","family":"Varricchio","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Calabria, 87036 Arcavacata, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quentin","family":"Vermande","sequence":"additional","affiliation":[{"name":"INRIA Centre at Universit\u00e9 C\u00f4te d\u2019Azur, 06902 Sophia Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ernest","family":"van Wijland","sequence":"additional","affiliation":[{"name":"IRIF, Universit\u00e9 Paris-Cit\u00e9, 75006 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21919-1"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Akrami H, Chaudhury BR, Hoefer M, Mehlhorn K, Schmalhofer M, Shahkarami G, Varricchio G, Vermande Q, van Wijland E (2022) Maximizing Nash social welfare in 2-value instances: The half-integer case. Preprint, submitted July 22, https:\/\/arxiv.org\/abs\/2207.10949v1.","DOI":"10.1609\/aaai.v36i5.20402"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20402"},{"key":"B4","unstructured":"Aleksandrov M, Aziz H, Gaspers S, Walsh T (2015) Online fair division: Analysing a food bank problem. Yang Q, Wooldridge M, eds.\n                      Proc. 24th Internat. Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 2540\u20132546."},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.02.020"},{"key":"B6","unstructured":"Anari N, Gharan SO, Saberi A, Singh M (2017) Nash social welfare, matrix permanent, and stable polynomials. Papadimitriou CH, ed.\n                      8th Innovations Theoret. Comput. Sci. Conf. (ITCS 2017)\n                      (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 36:1\u201336:12."},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Anari N, Mai T, Gharan SO, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Czumaj A, ed.\n                      Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 2274\u20132290.","DOI":"10.1137\/1.9781611975031.147"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16647"},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Tardos E, ed.\n                      Proc. 2018 ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 557\u2013574.","DOI":"10.1145\/3219166.3219176"},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Barman S, Krishnamurthy SK, Vaish R (2018) Greedy algorithms for maximizing Nash social welfare. Andre E, Koenig S, eds.\n                      Proc. 17th Internat. Conf. Autonomous Agents Multiagent Systems\n                      (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 7\u201313.","DOI":"10.65109\/GDEM1172"},{"key":"B11","unstructured":"Barman S, Bhaskar U, Krishna A, Sundaram RG (2020) Tight approximation algorithms for p-mean welfare under subadditive valuations. Grandoni F, Herman G, Sanders P, eds.\n                      28th Annual Eur. Sympos. Algorithms (ESA 2020)\n                      (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 11:1\u201311:17."},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Brown A, Laddha A, Pittu MR, Singh M (2024) Approximation algorithms for the weighted Nash social welfare via convex and non-convex programs. Woodruff DP, ed.\n                      Proc. 2024 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 1307\u20131327.","DOI":"10.1137\/1.9781611977912.52"},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Caragiannis I, Gravin N, Huang X (2019) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Karlin A, ed.\n                      Proc. 2019 ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 527\u2013545.","DOI":"10.1145\/3328526.3329574"},{"issue":"3","key":"B15","first-page":"12:1","volume":"7","author":"Caragiannis I","year":"2019","journal-title":"ACM Trans. Econom. Comput."},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16665"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Chaudhury BR, Kavitha T, Mehlhorn K, Sgouritsa A (2020) A little charity guarantees almost envy-freeness. Chawla S, ed.\n                      31st Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2020)\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 2658\u20132672.","DOI":"10.1137\/1.9781611975994.162"},{"key":"B18","unstructured":"Chaudhury BR, Cheung YK, Garg J, Garg N, Hoefer M, Mehlhorn K (2018) On fair division for indivisible items. Ganguly S, Pandya P, eds.\n                      38th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci.\n                      (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 25:1\u201325:17."},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Cole R, Devanur N, Gkatzelis V, Jain K, Mai T, Vazirani V, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Daskalakis C, ed.\n                      Proc. 2017 ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 459\u2013460.","DOI":"10.1145\/3033274.3085109"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90068-8"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.05.071"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.04.008"},{"key":"B24","unstructured":"Dobzinski S, Li W, Rubinstein A, Vondr\u00e1k J (2023) A constant factor approximation for Nash social welfare with subadditive valuations. Preprint, submitted September 9, https:\/\/arxiv.org\/abs\/2309.04656."},{"key":"B25","unstructured":"Fitzsimmons Z, Viswanathan V, Zick Y (2024) On the hardness of fair allocation under ternary valuations. Preprint, submitted March 1, https:\/\/arxiv.org\/abs\/2403.00943v1."},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Freeman R, Sikdar S, Vaish R, Xia L (2019) Equitable allocations of indivisible goods. Kraus S, ed.\n                      Proc. 28th Internat. Joint Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 280\u2013286.","DOI":"10.24963\/ijcai.2019\/40"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"B28","doi-asserted-by":"crossref","unstructured":"Garg J, Murhekar A (2021) Computing fair and efficient allocations with few utility values. Caragiannis I, Hansen KA, eds.\n                      Algorithmic Game Theory SAGT 2021\n                      (Springer, Cham, Switzerland), 345\u2013359.","DOI":"10.1007\/978-3-030-85947-3_23"},{"key":"B29","doi-asserted-by":"crossref","unstructured":"Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Czumaj A, ed.\n                      29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2018)\n                      (Society for Applied and Industrial Mathematics, Philadelphia), 2326\u20132340.","DOI":"10.1137\/1.9781611975031.150"},{"key":"B30","doi-asserted-by":"crossref","unstructured":"Garg J, Husic E, V\u00e9gh L (2021) Approximating Nash social welfare under rado valuations. Khuller S, ed.\n                      Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 1412\u20131425.","DOI":"10.1145\/3406325.3451031"},{"key":"B31","doi-asserted-by":"crossref","unstructured":"Garg J, Kulkarni P, Kulkarni R (2020) Approximating Nash social welfare under submodular valuations through (un)matchings. Chawla S, ed.\n                      31st Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2020)\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 2673\u20132687.","DOI":"10.1137\/1.9781611975994.163"},{"key":"B32","unstructured":"Garg J, Husi\u0107 E, Li W, V\u00e9gh LA, Vondr\u00e1k J (2022) Approximating Nash social welfare by matching and local search. Preprint, submitted November 7, https:\/\/arxiv.org\/abs\/2211.03883v1."},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Halpern D, Procaccia AD, Psomas A, Shah N (2020) Fair division with binary valuations: One rule to rule them all. Chen X, Gravin N, Hoefer M, Mehta R, eds.\n                      Web Internet Econom. WINE 2020\n                      (Springer, Cham, Switzerland), 370\u2013383.","DOI":"10.1007\/978-3-030-64946-3_26"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"B35","doi-asserted-by":"crossref","unstructured":"Li W, Vondr\u00e1k J (2021) A constant-factor approximation algorithm for Nash social welfare with submodular valuations.\n                      Proc. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci.\n                      (IEEE, New York), 25\u201336.","DOI":"10.1109\/FOCS52979.2021.00012"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80033-3"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.09.009"},{"key":"B38","unstructured":"Mehlhorn K (2024) Maximizing Nash social welfare in 2-value instances: A simpler proof for the half-integer case. Preprint, submitted November 11, https:\/\/arxiv.org\/abs\/2411.06924."},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2022.03.004"},{"key":"B40","volume":"164","author":"Tutte WT","year":"1987","journal-title":"Classic Papers in Combinatorics (Springer, Berlin),"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:26:40Z","timestamp":1778228800000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0204"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0204","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}