{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T13:45:42Z","timestamp":1781271942019,"version":"3.54.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,29]],"date-time":"2020-02-29T00:00:00Z","timestamp":1582934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Akiko Yamazaki and Jerry Yang Engineering Fellowship"},{"name":"Ramanujan Fellowship","award":["SERB- SB\/S2\/RJN-128\/2015"],"award-info":[{"award-number":["SERB- SB\/S2\/RJN-128\/2015"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>\n            We consider the problem of allocating indivisible goods\n            <jats:italic>fairly<\/jats:italic>\n            among\n            <jats:italic>n<\/jats:italic>\n            agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the\n            <jats:italic>maximin share<\/jats:italic>\n            , which is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into\n            <jats:italic>n<\/jats:italic>\n            bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations, a 2\/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.\n          <\/jats:p>\n          <jats:p>\n            Furthermore, we initiate the study of approximate maximin fair division under\n            <jats:italic>submodular valuations<\/jats:italic>\n            . Specifically, we show that when the valuations of the agents are\n            <jats:italic>nonnegative<\/jats:italic>\n            ,\n            <jats:italic>monotone<\/jats:italic>\n            , and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the article is to analyze the performance of this combinatorial algorithm by employing the concept of\n            <jats:italic>multilinear extensions<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3381525","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:36:18Z","timestamp":1583789778000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Approximation Algorithms for Maximin Fair Division"],"prefix":"10.1145","volume":"8","author":[{"given":"Siddharth","family":"Barman","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Karnataka, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanath Kumar","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence. 31--37","author":"Amanatidis Georgios","year":"2016","unstructured":"Georgios Amanatidis , Georgios Birmpas , and Evangelos Markakis . 2016 . On truthful mechanisms for maximin share allocations . In Proceedings of the 25th International Joint Conference on Artificial Intelligence. 31--37 . Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2016. On truthful mechanisms for maximin share allocations. In Proceedings of the 25th International Joint Conference on Artificial Intelligence. 31--37."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915)","author":"Amanatidis G.","unstructured":"G. Amanatidis , E. Markakis , A. Nikzad , and A. Saberi . 2015. Approximation algorithms for computing maximin share allocations . In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915) . G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. 2015. Approximation algorithms for computing maximin share allocations. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915)."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 1357--1372","author":"Annamalai Chidambaram","year":"2014","unstructured":"Chidambaram Annamalai , Christos Kalaitzis , and Ola Svensson . 2014 . Combinatorial algorithm for restricted max-min fair allocation . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 1357--1372 . Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. 2014. Combinatorial algorithm for restricted max-min fair allocation. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 1357--1372."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080723491"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence.","author":"Aziz H.","unstructured":"H. Aziz , G. Rauchecker , G. Schryen , and T. Walsh . 2017. Approximation algorithms for max-min share allocations of indivisible chores and goods . In Proceedings of the 31st AAAI Conference on Artificial Intelligence. H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh. 2017. Approximation algorithms for max-min share allocations of indivisible chores and goods. In Proceedings of the 31st AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th International Workshop on Computational Social Choice (COMSOC\u201916)","author":"Bouveret Sylvain","year":"2016","unstructured":"Sylvain Bouveret and Lema\u00eetre. 2016 . Efficiency and sequenceability in fair division of indivisible goods with additive preferences . In Proceedings of the 6th International Workshop on Computational Social Choice (COMSOC\u201916) . Sylvain Bouveret and Lema\u00eetre. 2016. Efficiency and sequenceability in fair division of indivisible goods with additive preferences. In Proceedings of the 6th International Workshop on Computational Social Choice (COMSOC\u201916)."},{"key":"e_1_2_1_10_1","volume-title":"Taylor","author":"Brams Steven J.","year":"1996","unstructured":"Steven J. Brams and Alan D . Taylor . 1996 . Fair Division : From Cake-Cutting to Dispute Resolution. Cambridge University Press . Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1544"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940726"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.51"},{"key":"e_1_2_1_16_1","unstructured":"Chandra Chekuri and Jan Vondr\u00e1k. 2009. Randomized pipage rounding for matroid polytopes and applications. arXiv:0909.4348.  Chandra Chekuri and Jan Vondr\u00e1k. 2009. Randomized pipage rounding for matroid polytopes and applications. arXiv:0909.4348."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 287--293","author":"Feige Uriel","year":"2008","unstructured":"Uriel Feige . 2008 . On allocations that maximize fairness . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 287--293 . Uriel Feige. 2008. On allocations that maximize fairness. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 287--293."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219238"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.59"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728732.2728738"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.60"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence. 523--529","author":"Kurokawa David","year":"2016","unstructured":"David Kurokawa , Ariel D. Procaccia , and Junxing Wang . 2016 . When can the maximin share guarantee be guaranteed? In Proceedings of the 30th AAAI Conference on Artificial Intelligence. 523--529 . David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2016. When can the maximin share guarantee be guaranteed? In Proceedings of the 30th AAAI Conference on Artificial Intelligence. 523--529."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(90)90003-Z"},{"key":"e_1_2_1_31_1","volume-title":"Fair Division and Collective Welfare","author":"Moulin Herv\u00e9","unstructured":"Herv\u00e9 Moulin . 2004. Fair Division and Collective Welfare . MIT Press , Cambridge, MA . Herv\u00e9 Moulin. 2004. Fair Division and Collective Welfare. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_32_1","volume-title":"Cooperative Microeconomics: A Game-Theoretic Introduction","author":"Moulin Herv\u00e9","year":"2014","unstructured":"Herv\u00e9 Moulin . 2014 . Cooperative Microeconomics: A Game-Theoretic Introduction . Princeton University Press , Princeton, NJ . Herv\u00e9 Moulin. 2014. Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_33_1","volume-title":"Handbook of Computational Social Choice","author":"Moulin Herv\u00e9","unstructured":"Herv\u00e9 Moulin , Felix Brandt , Vincent Conitzer , Ulle Endriss , Ariel D. Procaccia , and J\u00e9r\u00f4me Lang . 2016. Handbook of Computational Social Choice . Cambridge University Press . Herv\u00e9 Moulin, Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D. Procaccia, and J\u00e9r\u00f4me Lang. 2016. Handbook of Computational Social Choice. Cambridge University Press."},{"key":"e_1_2_1_34_1","volume-title":"Marshall","author":"Olkin Ingram","year":"2016","unstructured":"Ingram Olkin and Albert W . Marshall . 2016 . Inequalities : Theory of Majorization and Its Applications. Vol. 143 . Academic Press . Ingram Olkin and Albert W. Marshall. 2016. Inequalities: Theory of Majorization and Its Applications. Vol. 143. Academic Press."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 15th ACM Conference on Economics and Computation. 675--692","author":"Ariel","unstructured":"Ariel D. Procaccia and Junxing Wang. 2014. Fair enough: Guaranteeing approximate maximin shares . In Proceedings of the 15th ACM Conference on Economics and Computation. 675--692 . Ariel D. Procaccia and Junxing Wang. 2014. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the 15th ACM Conference on Economics and Computation. 675--692."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90033-0"},{"key":"e_1_2_1_37_1","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 -- 104 . Hugo Steinhaus. 1948. The problem of fair division. Econometrica 16, 1 (1948), 101--104.","journal-title":"Econometrica"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.08.032"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,29]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3381525"],"URL":"https:\/\/doi.org\/10.1145\/3381525","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,29]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}