{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T07:09:37Z","timestamp":1784012977359,"version":"3.55.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE-T2EP20221-0001"],"award-info":[{"award-number":["MOE-T2EP20221-0001"]}],"id":[{"id":"10.13039\/501100001459","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":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where [Formula: see text] chores are allocated to [Formula: see text] agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that [Formula: see text], and moreover, [Formula: see text] must be at least [Formula: see text] in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as [Formula: see text], and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.<\/jats:p>","DOI":"10.1137\/25m180161x","type":"journal-article","created":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T07:00:36Z","timestamp":1784012436000},"page":"1048-1065","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotic Fair Division: Chores Are Easier Than Goods"],"prefix":"10.1137","volume":"40","author":[{"given":"Pasin","family":"Manurangsi","sequence":"first","affiliation":[{"name":"Google Research, Bangkok, Thailand."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,14]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-021-09532-8"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2024.104118"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh, Algorithms for max-min share fair allocation of indivisible chores, in Proceedings of the 31st AAAI Conference on Artificial Intelligence, 2017, pp. 335\u2013341.","DOI":"10.1609\/aaai.v31i1.10582"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"Y. Bai, U. Feige, P. G\u00f6lz, and A. D. Procaccia, Fair allocations for smoothed utilities, in Proceedings of the 23rd ACM Conference on Economics and Computation, 2022, pp. 436\u2013465.","DOI":"10.1145\/3490486.3538285"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Y. Bai and P. G\u00f6lz, Envy-free and Pareto-optimal allocations for agents with asymmetric random valuations, in Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022, pp. 53\u201359.","DOI":"10.24963\/ijcai.2022\/8"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"G. Benad\u00e8, D. Halpern, A. Psomas, and P. Verma, On the existence of envy-free allocations beyond additive valuations, in Proceedings of the 25th ACM Conference on Economics and Computation, 2024, arXiv:2307.09648v1.","DOI":"10.1145\/3670865.3673466"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"J. P. Dickerson, J. Goldman, J. Karp, A. D. Procaccia, and T. Sandholm, The computational rise and fall of fairness, in Proceedings of the 28th AAAI Conference on Artificial Intelligence, 2014, pp. 1405\u20131411.","DOI":"10.1609\/aaai.v28i1.8884"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"S. Ebadian, D. Peters, and N. Shah, How to fairly allocate easy and difficult chores, in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022, pp. 372\u2013380.","DOI":"10.65109\/PGYF2278"},{"key":"ref13","first-page":"455","volume":"8","author":"Erd\u0151s P.","year":"1964","journal-title":"Publ. Math. Inst. Hungarian Acad. Sci."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11291"},{"key":"ref15","first-page":"45","volume":"7","author":"Foley D. K.","year":"1967","journal-title":"Yale Economics Essays"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"J. Garg, A. Murhekar, and J. Qin, Constant-factor EFX exists for chores, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025, pp. 1580\u20131589.","DOI":"10.1145\/3717823.3718305"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"P. G\u00f6lz, A. Igarashi, P. Manurangsi, and W. Suksompong, Fair allocation of indivisible goods with variable groups, in Proceedings of the 40th AAAI Conference on Artificial Intelligence, 2026, pp. 16954\u201316962.","DOI":"10.1609\/aaai.v40i20.38742"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.3390\/math11163616"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.115010"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"D. Kurokawa, A. D. Procaccia, and J. Wang, When can the maximin share guarantee be guaranteed? in Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016, pp. 523\u2013529.","DOI":"10.1609\/aaai.v30i1.10041"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"B. Li, F. Wang, and Y. Zhou, Fair allocation of indivisible chores: Beyond additive costs, in Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.","DOI":"10.52202\/075280-2368"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2017.05.006"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279125"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/20M1353381"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115533"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863855"},{"key":"ref28","first-page":"101","volume":"16","author":"Steinhaus H.","year":"1948","journal-title":"Econometrica"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2016.03.007"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/3505156.3505162"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"T. Yokoyama and A. Igarashi, Asymptotic existence of class envy-free matchings, in Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2025, pp. 2244\u20132252.","DOI":"10.65109\/ISMH6144"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104037"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T07:00:38Z","timestamp":1784012438000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M180161X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,14]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M180161X"],"URL":"https:\/\/doi.org\/10.1137\/25m180161x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,14]]}}}