{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:04:10Z","timestamp":1778493850598,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>\n            We consider the problem of fairly allocating a set of indivisible items under the criteria of the maximin share guarantee. Specifically, we study approximation of maximin share allocations under hereditary set system valuations, in which each valuation function is based on the independent sets of an underlying hereditary set system. Using a lone divider approach, we show the existence of 1\/2-approximate MMS allocations, improving on the 11\/30 guarantee of Li and Vetta [\n            <jats:xref ref-type=\"bibr\">37<\/jats:xref>\n            ]. Moreover, we prove that (2\/3 + \u03b5)-approximate MMS allocations do not always exist in this model for every \u03b5 &gt; 0, an improvement from the recent 3\/4 + \u03b5 result of Li and Deng [\n            <jats:xref ref-type=\"bibr\">36<\/jats:xref>\n            ]. Our existence proof is constructive but does not directly yield a polynomial-time approximation algorithm. However, we show that a 2\/5-approximate MMS allocation can be found in polynomial time, given valuation oracles. Finally, we show that our existence and approximation results transfer to a variety of problems within constrained fair allocation, improving on existing results in some of these settings.\n          <\/jats:p>","DOI":"10.1145\/3727149","type":"journal-article","created":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:54:39Z","timestamp":1743155679000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Maximin Shares in Hereditary Set Systems"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5691-8177","authenticated-orcid":false,"given":"Halvard","family":"Hummel","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology","place":["Trondheim, Norway"]}]}],"member":"320","published-online":{"date-parts":[[2025,6,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.11.059"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.4"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/276"},{"key":"e_1_3_3_5_2","first-page":"58821","article-title":"Randomized and deterministic maximin-share approximations for fractionally subadditive valuations","volume":"36","author":"Akrami Hannaneh","year":"2023","unstructured":"Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami. 2023. Randomized and deterministic maximin-share approximations for fractionally subadditive valuations. Advan. Neural Inf. Process. Syst. 36 (Dec.2023), 58821\u201358832.","journal-title":"Advan. Neural Inf. Process. Syst."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301420"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i5.25681"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381525"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/13"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33019921"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/3635637.3663094"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-7184-8_7"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/20"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i9.28815"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01079-8"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13779"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-94676-0_20"},{"key":"e_1_3_3_23_2","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASICS.SOSA.2019.20"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399526"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103633"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1096"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.05.018"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/34"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13317"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-021-09537-3"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20614-6_11"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1148438"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400877386-004"},{"key":"e_1_3_3_35_2","first-page":"2875","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201923)","author":"Kulkarni Pooja","year":"2023","unstructured":"Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. 2023. Maximin share allocations for assignment valuations. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201923). International Foundation for Autonomous Agents and Multiagent Systems, 2875\u20132876."},{"key":"e_1_3_3_36_2","first-page":"21744","volume-title":"Advances in Neural Information Processing Systems","author":"Li Bo","year":"2021","unstructured":"Bo Li, Minming Li, and Ruilong Zhang. 2021. Fair scheduling for time-dependent resources. In Advances in Neural Information Processing Systems, Vol. 34. Curran Associates, Inc., 21744\u201321756."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","unstructured":"Weidong Li and Bin Deng. 2023. The budgeted maximin share allocation problem. DOI:10.21203\/rs.3.rs-3333303\/v1","DOI":"10.21203\/rs.3.rs-3333303\/v1"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434410"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602835"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104049"},{"issue":"1","key":"e_1_3_3_41_2","first-page":"101","article-title":"The problem of fair division","volume":"16","author":"Steinhaus Hugo","year":"1948","unstructured":"Hugo Steinhaus. 1948. The problem of fair division. Econometrica 16, 1 (1948), 101\u2013104.","journal-title":"Econometrica"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3505156.3505162"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","unstructured":"Gilad Ben Uziahu and Uriel Feige. 2023. On fair allocation of indivisible goods to submodular agents. DOI:10.48550\/arXiv.2303.12444","DOI":"10.48550\/arXiv.2303.12444"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/65"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T04:48:57Z","timestamp":1750135737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,16]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3727149"],"URL":"https:\/\/doi.org\/10.1145\/3727149","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,16]]},"assertion":[{"value":"2024-05-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}