{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T02:28:39Z","timestamp":1771381719706,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T00:00:00Z","timestamp":1612828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. In this spirit, we study the case where the items form a hereditary set system. We present a simple algorithm that allocates each agent a bundle of items whose value is at least 0.3666 times the maximin share of the agent. This improves upon the current best known guarantee of 0.2 due to Ghodsi et\u00a0al. The analysis of the algorithm is almost tight; we present an instance where the algorithm provides a guarantee of at most 0.3738. We also show that the algorithm can be implemented in polynomial time given a valuation oracle for each agent.<\/jats:p>","DOI":"10.1145\/3434410","type":"journal-article","created":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T13:49:34Z","timestamp":1612964974000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Fair Division of Hereditary Set Systems"],"prefix":"10.1145","volume":"9","author":[{"given":"Z.","family":"Li","sequence":"first","affiliation":[{"name":"Computer Science Department, \u00c9cole Normale Sup\u00e9rieure Paris"}]},{"given":"A.","family":"Vetta","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, and School of Computer Science, McGill University"}]}],"member":"320","published-online":{"date-parts":[[2021,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM Conference on Economics and Computation (EC\u201917)","author":"Barman S.","unstructured":"S. Barman and S. Krishna Murthy . 2017. Approximation algorithms for maximin fair division . In Proceedings of the ACM Conference on Economics and Computation (EC\u201917) . 647--664. S. Barman and S. Krishna Murthy. 2017. Approximation algorithms for maximin fair division. In Proceedings of the ACM Conference on Economics and Computation (EC\u201917). 647--664."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"S. Bouveret K. Cechl\u00e1rov\u00e1 E. Elkind A. Igarashi and D. Peters. 2017. Fair division of a graph. arXiv preprint arXiv:1705.10239 (2017).  S. Bouveret K. Cechl\u00e1rov\u00e1 E. Elkind A. Igarashi and D. Peters. 2017. Fair division of a graph. arXiv preprint arXiv:1705.10239 (2017).","DOI":"10.24963\/ijcai.2017\/20"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 19th ACM Conference on Economics and Computation (EC\u201918)","author":"Ghodsi M.","unstructured":"M. Ghodsi , M. Hajiaghayi , M. Seddighin , S. Seddighin , and H. Yami . 2018. Fair allocation of indivisible goods: Improvements and generalizations . In Proceedings of the 19th ACM Conference on Economics and Computation (EC\u201918) . 539--556. M. Ghodsi, M. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami. 2018. Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC\u201918). 539--556."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.05.018"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"e_1_2_1_11_1","volume-title":"Operations and Production Systems with Multiple Objectives","author":"Malakooti B.","unstructured":"B. Malakooti . 2014. Operations and Production Systems with Multiple Objectives . John Wiley 8 Sons. B. Malakooti. 2014. Operations and Production Systems with Multiple Objectives. John Wiley 8 Sons."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(90)90003-Z"},{"key":"e_1_2_1_13_1","volume-title":"Fair Division and Collective Welfare","author":"Moulin H.","unstructured":"H. Moulin . 2004. Fair Division and Collective Welfare . The MIT Press . H. Moulin. 2004. Fair Division and Collective Welfare. The MIT Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863855"},{"key":"e_1_2_1_16_1","first-page":"101","article-title":"The problem of fair division","volume":"16","author":"Steihaus H.","year":"1948","unstructured":"H. Steihaus . 1948 . The problem of fair division . Econometrica 16 (1948), 101 -- 104 . H. Steihaus. 1948. The problem of fair division. Econometrica 16 (1948), 101--104.","journal-title":"Econometrica"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434410","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,9]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3434410"],"URL":"https:\/\/doi.org\/10.1145\/3434410","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,9]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}