{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:38:54Z","timestamp":1787323134466,"version":"build-2736575974"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["639945"],"award-info":[{"award-number":["639945"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["639945"],"award-info":[{"award-number":["639945"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=\\Omega(n\\log n\/\\log\\log n)$, matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as $m\\geq n$, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between $m$ and $n$. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from nonexistence to existence with respect to envy-free assignments occurs at $m=en$.<\/jats:p>","DOI":"10.1137\/20m1353381","type":"journal-article","created":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T14:13:46Z","timestamp":1617891226000},"page":"668-706","source":"Crossref","is-referenced-by-count":14,"title":["Closing Gaps in Asymptotic Fair Division"],"prefix":"10.1137","volume":"35","author":[{"given":"Pasin","family":"Manurangsi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.006"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M. Babaioff, N. Nisan, and I. Talgam-Cohen,\n                      Fair allocation through competitive equilibrium from generic incomes\n                      , in Proceedings of the 2nd Conference on Fairness, Accountability, and Transparency (FAT*), 2019.","DOI":"10.1145\/3287560.3287582"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"X. Bei, A. Igarashi, X. Lu, and W. Suksompong,\n                      The price of connectivity in fair division\n                      , in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), forthcoming, 2021.","DOI":"10.1609\/aaai.v35i6.16651"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"X. Bei, X. Lu, P. Manurangsi, and W. Suksompong,\n                      The price of fairness for indivisible goods\n                      , in Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019, pp. 81-87.","DOI":"10.24963\/ijcai.2019\/12"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0003498-3"},{"key":"atypb7","unstructured":"V. Bil\u00f2, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker,\n                      Almost envy-free allocations with connected bundles\n                      , in Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019, pp. 14:1-14:21."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"A. Biswas and S. Barman,\n                      Fair division under cardinality constraints\n                      , in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018, pp. 91-97.","DOI":"10.24963\/ijcai.2018\/13"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2004.00483.x"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. J. Brams and A. D. Taylor,\n                      Fair Division: From Cake-Cutting to Dispute Resolution\n                      , Cambridge University Press, Cambridge, 1996.","DOI":"10.1017\/CBO9780511598975"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"I. Caragiannis, N. Gravin, and X. Huang,\n                      Envy-freeness up to any item with high Nash welfare: The virtue of donating items\n                      , in Proceedings of the 20th ACM Conference on Economics and Computation (EC), 2019, pp. 527-545.","DOI":"10.1145\/3328526.3329574"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Chakraborty, A. Igarashi, W. Suksompong, and Y. Zick,\n                      Weighted envy-freeness in indivisible item allocation\n                      , in Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020, pp. 231-239.","DOI":"10.65109\/XYWL8760"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"B. R. Chaudhury, J. Garg, and K. Mehlhorn,\n                      EFX exists for three agents\n                      , in Proceedings of the 21st ACM Conference on Economics and Computation (EC), 2020, pp. 1-19.","DOI":"10.1145\/3391403.3399511"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa,\n                      A little charity guarantees almost envy-freeness\n                      , in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 2658-2672.","DOI":"10.1137\/1.9781611975994.162"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"J. P. Dickerson, J. Goldman, J. Karp, A. D. Procaccia, and T. Sandholm,\n                      The computational rise and fall of fairness\n                      , in Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), 2014, pp. 1405-1411.","DOI":"10.1609\/aaai.v28i1.8884"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1961.11989615"},{"key":"atypb19","first-page":"455","volume":"8","author":"Erd\u00f6s P.","year":"1964","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"atypb20","first-page":"1","volume":"28","author":"Esseen C.-G.","year":"1942","journal-title":"Astronom. Fysik"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11291"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2019.07.005"},{"key":"atypb23","unstructured":"N. Immorlica and M. Mahdian,\n                      Marriage, honesty, and stability\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 53-62."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369025"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"R. M. Karp and M. Sipser,\n                      Maximum matchings in sparse random graphs\n                      , in Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (FOCS), 1981, pp. 364-375.","DOI":"10.1109\/SFCS.1981.21"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1257\/aer.99.3.608"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/3274641"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"D. Kurokawa, A. D. Procaccia, and J. Wang,\n                      When can the maximin share guarantee be guaranteed?\n                      , in Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 2016, pp. 523-529.","DOI":"10.1609\/aaai.v30i1.10041"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.008"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi,\n                      On approximately fair allocations of indivisible goods\n                      , in Proceedings of the 5th ACM Conference on Electronic Commerce (EC), 2004, pp. 125-131.","DOI":"10.1145\/988772.988792"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Mahdian,\n                      Random popular matchings\n                      , in Proceedings of the 7th ACM Conference on Economics and Computation (EC), 2006, pp. 238-242.","DOI":"10.1145\/1134707.1134733"},{"key":"atypb33","first-page":"165","volume":"4","author":"Manea M.","year":"2009","journal-title":"Theor. Econ."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2017.05.006"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279125"},{"key":"atypb36","first-page":"231","author":"Markakis E.","year":"2017","journal-title":"AI Access"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"H. Moulin,\n                      Fair Division and Collective Welfare\n                      , MIT Press, Cambridge, MA, 2003.","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"H. Oh, A. D. Procaccia, and W. Suksompong,\n                      Fairly allocating many goods with few queries\n                      , in Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019, pp. 2141-2148.","DOI":"10.1609\/aaai.v33i01.33012141"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103167"},{"key":"atypb43","first-page":"101","volume":"16","author":"Steinhaus H.","year":"1948","journal-title":"Econometrica"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1980.11995109"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2016.03.007"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2017.09.004"},{"key":"atypb47","unstructured":"W. Suksompong,\n                      Resource Allocation and Decision Making for Groups\n                      , Ph.D. thesis, Stanford University, 2018."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.03.039"},{"key":"atypb49","first-page":"261","author":"Thomson W.","year":"2016","journal-title":"Cambridge"},{"key":"atypb50","unstructured":"L. Warnke,\n                      On Wormald's Differential Equation Method\n                      , CoRR, abs\/1905.08928, 2019."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004612"},{"key":"atypb52","first-page":"73","author":"Wormald N. C.","year":"1999","journal-title":"Wydawnictwo Naukowe PWN"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1353381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:43:46Z","timestamp":1787319826000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1353381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1353381"],"URL":"https:\/\/doi.org\/10.1137\/20m1353381","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}