{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T16:19:20Z","timestamp":1771345160364,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T00:00:00Z","timestamp":1771286400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T00:00:00Z","timestamp":1771286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NTNU Norwegian University of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. We consider the fairness criterion known as the\n                    <jats:italic>maximin share<\/jats:italic>\n                    (MMS)\n                    <jats:italic>guarantee<\/jats:italic>\n                    , and propose a novel polynomial-time algorithm for finding 1\/2-approximate MMS allocations for goods\u2014an improvement from the previously best available guarantee of 11\/30. For single-category instances, we show that a modified variant of our algorithm is guaranteed to produce 2\/3-approximate MMS allocations. Among various other existence and non-existence results, we show that a\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(\\sqrt{n}\/(2\\sqrt{n} - 1))$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -approximate MMS allocation always exists for goods. For chores, we show similar results as for goods, with a 2-approximate algorithm in the general case and a 3\/2-approximate algorithm for single-category instances. We extend the notions and algorithms related to\n                    <jats:italic>ordered<\/jats:italic>\n                    and\n                    <jats:italic>reduced instances<\/jats:italic>\n                    to work with cardinality constraints, and combine these with\n                    <jats:italic>bag filling<\/jats:italic>\n                    style procedures to construct our algorithms.\n                  <\/jats:p>","DOI":"10.1007\/s10458-026-09731-1","type":"journal-article","created":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T15:48:15Z","timestamp":1771343295000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximin shares under cardinality constraints"],"prefix":"10.1007","volume":"40","author":[{"given":"Halvard","family":"Hummel","sequence":"first","affiliation":[]},{"given":"Magnus Lie","family":"Hetland","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,17]]},"reference":[{"key":"9731_CR1","doi-asserted-by":"crossref","unstructured":"Aigner-Horev, E., & Segal-Halevi, E. (2022). Envy-free matchings in bipartite graphs and their applications to fair division. Information Sciences, 587, 164\u2013187. https:\/\/doi.org\/10.1016\/j.ins.2021.11.059. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020025521011816","DOI":"10.1016\/j.ins.2021.11.059"},{"key":"9731_CR2","doi-asserted-by":"publisher","unstructured":"Amanatidis, G., Markakis, E., Nikzad, A., & Saberi, A. (2017). Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms, 13(4):52:1\u201352:28, https:\/\/doi.org\/10.1145\/3147173","DOI":"10.1145\/3147173"},{"key":"9731_CR3","doi-asserted-by":"publisher","unstructured":"Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., Voudouris, A. A., & Wu, X. (2023). Fair division of indivisible goods: recent progress and open questions. Artificial Intelligence, 103965. https:\/\/doi.org\/10.1016\/j.artint.2023.103965. arxiv:2208.08782","DOI":"10.1016\/j.artint.2023.103965"},{"key":"9731_CR4","doi-asserted-by":"publisher","unstructured":"Babaioff, M., Nisan, N., & Talgam-Cohen, I. (2021). Competitive equilibrium with indivisible goods and generic budgets. Mathematics of Operations Research, 46(1), 382\u201340. https:\/\/doi.org\/10.1287\/moor.2020.1062. https:\/\/pubsonline.informs.org\/doi\/abs\/10.1287\/moor.2020.1062, publisher: INFORMS","DOI":"10.1287\/moor.2020.1062"},{"key":"9731_CR5","doi-asserted-by":"publisher","unstructured":"Barman, S., & Krishna\u00a0Murthy, S. K. (2017). Approximation Algorithms for Maximin Fair Division. In: Proceedings of the 2017 ACM conference on economics and computation, association for computing machinery, Cambridge, Massachusetts, USA, EC \u201917, (pp. 647\u2013664). https:\/\/doi.org\/10.1145\/3033274.3085136","DOI":"10.1145\/3033274.3085136"},{"key":"9731_CR6","unstructured":"Bil\u00f3, V., Caragiannis, I., Flammini, M. c., Igarashi, A., Monaco, G., Peters, D., Vinci, C., & Zwicker, W. S. (2018). Almost envy-free allocations with connected bundles. In A Blum (Eds.), 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs) (vol 124, pp. 14:1\u201314:21). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.14. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/10107, iSSN: 1868-8969"},{"key":"9731_CR7","doi-asserted-by":"crossref","unstructured":"Biswas, A., & Barman, S. (2018). Fair division under cardinality constraints. In Proceedings of the twenty-seventh international joint conference on artificial intelligence (pp. 91\u201397), International Joint Conferences on Artificial Intelligence Organization, Stockholm, Sweden. https:\/\/doi.org\/10.24963\/ijcai.2018\/13. https:\/\/www.ijcai.org\/proceedings\/2018\/13","DOI":"10.24963\/ijcai.2018\/13"},{"issue":"2","key":"9731_CR8","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","volume":"30","author":"S Bouveret","year":"2016","unstructured":"Bouveret, S., & Mc, L. (2016). Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2), 259\u201329. https:\/\/doi.org\/10.1007\/s10458-015-9287-3","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9731_CR9","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., & Peters, D. (2017). Fair division of a graph. In Proceedings of the twenty-sixth international joint conference on artificial intelligence (pp. 135\u2013141), International Joint Conferences on Artificial Intelligence Organization, Melbourne, Australia. https:\/\/doi.org\/10.24963\/ijcai.2017\/20. https:\/\/www.ijcai.org\/proceedings\/2017\/20","DOI":"10.24963\/ijcai.2017\/20"},{"key":"9731_CR10","doi-asserted-by":"publisher","unstructured":"Budish, E. (2011). The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6), 1061\u2013110. https:\/\/doi.org\/10.1086\/664613. https:\/\/www.journals.uchicago.edu\/doi\/full\/10.1086\/664613, publisher: The University of Chicago Press","DOI":"10.1086\/664613"},{"key":"9731_CR11","doi-asserted-by":"publisher","unstructured":"Chiarelli, N., Krnc, M., Milani\u010d, M., Pferschy, U., Piva\u010d, N., & Schauer, J. (2020). Fair packing of independent sets. In Combinatorial algorithms (pp. 154\u2013165). Springer International Publishing, Cham, Lecture Notes in Computer Science. https:\/\/doi.org\/10.1007\/978-3-030-48966-3_12","DOI":"10.1007\/978-3-030-48966-3_12"},{"key":"9731_CR12","doi-asserted-by":"publisher","unstructured":"Feige, U., Sapir, A., & Tauber, L. (2022). A tight negative example for\u00a0MMS fair allocations. In M Feldman, H Fu, I Talgam-Cohen (Eds.), Web and internet economics (pp. 355\u2013372). Springer International Publishing, Cham, Lecture Notes in Computer Science. https:\/\/doi.org\/10.1007\/978-3-030-94676-0_20","DOI":"10.1007\/978-3-030-94676-0_20"},{"key":"9731_CR13","doi-asserted-by":"publisher","unstructured":"Ferraioli, D., Gourv\u00e9s, L., & Monnot, J. (2014). On regular and approximately fair allocations of indivisible goods. In Proceedings of the 2014 international conference on autonomous agents and multi-agent systems (pp. 997\u20131004), International Foundation for Autonomous Agents and Multiagent Systems, Paris, France, AAMAS \u201914. https:\/\/doi.org\/10.5555\/2615731.2617405","DOI":"10.5555\/2615731.2617405"},{"key":"9731_CR14","doi-asserted-by":"publisher","unstructured":"Garg, J., & Taki, S. (2020). An improved approximation algorithm for maximin shares. In Proceedings of the 21st ACM conference on economics and computation (pp. 379\u2013380), Association for Computing Machinery, New York, NY, USA, EC \u201920. https:\/\/doi.org\/10.1145\/3391403.3399526, arXiv: 1903.00029","DOI":"10.1145\/3391403.3399526"},{"key":"9731_CR15","unstructured":"Garg, J., McGlaughlin, P., & Taki, S. (2019). Approximating Maximin Share Allocations. In J. T. Fineman, & M. Mitzenmacher (Eds.), 2nd Symposium on simplicity in algorithms (SOSA 2019) (vol. 69, pp. 20:1\u201320:11), Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, OpenAccess Series in Informatics (OASIcs). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.20. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/10046"},{"key":"9731_CR16","doi-asserted-by":"publisher","unstructured":"Ghodsi, M., Hajiaghayi, M., Seddighin, M., Seddighin, S., & Yami, H. (2018). Fair allocation of indivisible goods: improvements and generalizations. In Proceedings of the 2018 ACM conference on economics and computation (pp. 539\u2013556), Association for Computing Machinery, Ithaca, NY, USA, EC \u201918. https:\/\/doi.org\/10.1145\/3219166.3219238","DOI":"10.1145\/3219166.3219238"},{"key":"9731_CR17","doi-asserted-by":"crossref","unstructured":"Gourv\u00e9s, L., & Monnot, J. (2019). On maximin share allocations in matroids. Theoretical Computer Science, 754, 50\u201364. https:\/\/doi.org\/10.1016\/j.tcs.2018.05.018. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397518303384","DOI":"10.1016\/j.tcs.2018.05.018"},{"key":"9731_CR18","unstructured":"Gourv\u00e9s, L., Monnot, J., & Tlilane, L. (2014). Near fairness in matroids. In Proceedings of the twenty-first european conference on artificial intelligence (pp. 393\u2013398), IOS Press, Prague, Czech Republic, ECAI\u201914"},{"key":"9731_CR19","doi-asserted-by":"crossref","unstructured":"Greco, G., & Scarcello, F. (2020). The complexity of computing maximin share allocations on graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 2006\u2013201. https:\/\/doi.org\/10.1609\/aaai.v34i02.5572. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/5572, number: 02","DOI":"10.1609\/aaai.v34i02.5572"},{"key":"9731_CR20","doi-asserted-by":"publisher","unstructured":"Huang, X., & Segal-Halevi, E. (2023). A reduction from chores allocation to job scheduling.https:\/\/doi.org\/10.48550\/arXiv.2302.04581. arxiv:2302.04581","DOI":"10.48550\/arXiv.2302.04581"},{"issue":"1","key":"9731_CR21","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/s10458-021-09537-3","volume":"36","author":"H Hummel","year":"2021","unstructured":"Hummel, H., & Hetland, M. L. (2021). Fair allocation of conflicting items. Autonomous Agents and Multi-Agent Systems, 36(1), 8. https:\/\/doi.org\/10.1007\/s10458-021-09537-3","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9731_CR22","doi-asserted-by":"crossref","unstructured":"Hummel, H., & Hetland, M. L. (2022a). Guaranteeing half-maximin shares under cardinality constraints. In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, AAMAS \u201922 (pp. 1633\u20131635).","DOI":"10.65109\/AYHC6673"},{"key":"9731_CR23","doi-asserted-by":"publisher","unstructured":"Hummel, H., & Hetland, M. L. (2022b). Maximin shares under cardinality constraints. In D. Baumeister, J. Rothe (Eds.), Multi-agent systems (pp. 188\u2013206). Springer International Publishing, Cham, Lecture Notes in Computer Science. https:\/\/doi.org\/10.1007\/978-3-031-20614-6_11","DOI":"10.1007\/978-3-031-20614-6_11"},{"key":"9731_CR24","doi-asserted-by":"crossref","unstructured":"Kurokawa, D., Procaccia, A. D., & Wang, J. (2016). When can the maximin share guarantee be guaranteed? In Proceedings of the Thirtieth AAAI conference on artificial intelligence, AAAI Press, Phoenix, Arizona, AAAI\u201916 (pp. 523\u2013529).","DOI":"10.1609\/aaai.v30i1.10041"},{"key":"9731_CR25","doi-asserted-by":"publisher","unstructured":"Kurokawa, D., Procaccia, A. D., & Wang, J. (2018) Fair enough: guaranteeing approximate maximin shares. Journal of the ACM, 65(2), 8:1\u20138:27. https:\/\/doi.org\/10.1145\/3140756","DOI":"10.1145\/3140756"},{"key":"9731_CR26","doi-asserted-by":"publisher","unstructured":"Li, Z., & Vetta, A. (2021). The fair division of hereditary set systems. ACM Transactions on Economics and Computation, 9(2), 1\u201319. https:\/\/doi.org\/10.1145\/3434410","DOI":"10.1145\/3434410"},{"key":"9731_CR27","doi-asserted-by":"publisher","unstructured":"Lonc, Z., & Truszczynski, M. (2018). Maximin share allocations on cycles. In Proceedings of the twenty-seventh international joint conference on artificial intelligence, IJCAI-18, International joint conferences on artificial intelligence organization (pp. 410\u2013416). https:\/\/doi.org\/10.24963\/ijcai.2018\/57","DOI":"10.24963\/ijcai.2018\/57"},{"key":"9731_CR28","doi-asserted-by":"publisher","unstructured":"Procaccia, A. D., & Wang, J. (2014). Fair enough: guaranteeing approximate maximin shares. In Proceedings of the fifteenth ACM conference on Economics and computation (pp. 675\u2013692). Association for Computing Machinery, Palo Alto, California, USA, EC \u201914. https:\/\/doi.org\/10.1145\/2600057.2602835","DOI":"10.1145\/2600057.2602835"},{"key":"9731_CR29","doi-asserted-by":"crossref","unstructured":"Shoshan, H., Hazon, N., & Segal-Halevi, E. (2023). Efficient nearly-fair division with capacity constraints. In Proceedings of the 2023 international conference on autonomous agents and multiagent systems, International foundation for autonomous agents and multiagent systems, Richland, SC, AAMAS \u201923 (pp. 206\u2013214).","DOI":"10.65109\/KVXG2484"},{"issue":"2","key":"9731_CR30","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3505156.3505162","volume":"19","author":"W Suksompong","year":"2021","unstructured":"Suksompong, W. (2021). Constraints in fair division. ACM SIGecom Exchanges, 19(2), 46\u201361. https:\/\/doi.org\/10.1145\/3505156.3505162","journal-title":"ACM SIGecom Exchanges"},{"key":"9731_CR31","doi-asserted-by":"crossref","unstructured":"Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4), 149\u2013154. https:\/\/doi.org\/10.1016\/S0167-6377(96)00055-7. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167637796000557","DOI":"10.1016\/S0167-6377(96)00055-7"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-026-09731-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-026-09731-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-026-09731-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T15:48:18Z","timestamp":1771343298000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-026-09731-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,17]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["9731"],"URL":"https:\/\/doi.org\/10.1007\/s10458-026-09731-1","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,17]]},"assertion":[{"value":"8 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"A preprint (\n                      \n                      ) of this paper contains some preliminary experimental results, along with source code.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Experiments"}}],"article-number":"9"}}