{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:58Z","timestamp":1750309438294,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Hong Kong SAR Research Grants Council","award":["PolyU 15224823"],"award-info":[{"award-number":["PolyU 15224823"]}]},{"DOI":"10.13039\/501100021171","name":"Guangdong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["2024A1515011524"],"award-info":[{"award-number":["2024A1515011524"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            We evaluate the fairness of a rule allocating among agents with equal rights by computing their utility for a hypothetical worst-case share, which only depends on their own valuation and the number of agents. For indivisible goods, Budish proposed the\n            <jats:italic>maximin share<\/jats:italic>\n            : the least utility of a bundle in the best partition of the objects; unfortunately maximin share is not always satisfiable. Earlier, Hill proposed the worst maximin share over all utilities with the same largest possible single-object value. More conservative than maximin share, it is guaranteed to be satisfiable for any possible profile of utilities and its computation is elementary, whereas it is NP-hard to compute maximin share. We apply Hill\u2019s approach to the allocation of indivisible bads (objects with disutilities) and compute in closed form the worst-case minimax share for a given value of the worst single bad. We show that the worst-case minimax share is close to the original minimax share and that its monotonic closure is the best guaranteed share for all allocation instances with a common upper bound on the value of the worst single bad.\n          <\/jats:p>","DOI":"10.1145\/3703845","type":"journal-article","created":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T10:56:28Z","timestamp":1731322588000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Hill\u2019s Worst-Case Guarantee for Indivisible Bads"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7500-8355","authenticated-orcid":false,"given":"Bo","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computing, The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3358-6290","authenticated-orcid":false,"given":"Herve","family":"Moulin","sequence":"additional","affiliation":[{"name":"Adam Smith Business School, University of Glasgow, Glasgow, United Kingdom of Great Britain and Northern Ireland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1464-1979","authenticated-orcid":false,"given":"Ankang","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Computing, The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6799-8379","authenticated-orcid":false,"given":"Yu","family":"Zhou","sequence":"additional","affiliation":[{"name":"College of Information Sciences and Technology, The Pennsylvania State University, University Park, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,12,5]]},"reference":[{"key":"e_1_3_4_2_2","article-title":"Breaking the 3\/4 barrier for approximate maximin share","volume":"2307","author":"Akrami Hannaneh","year":"2023","unstructured":"Hannaneh Akrami and Jugal Garg. 2023. Breaking the 3\/4 barrier for approximate maximin share. CoRR abs\/2307.07304 (2023).","journal-title":"CoRR"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965"},{"issue":"4","key":"e_1_3_4_4_2","first-page":"Article 52, 28","article-title":"Approximation algorithms for computing maximin share allocations","volume":"13","author":"Amanatidis Georgios","year":"2017","unstructured":"Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. 2017. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms 13, 4 (2017), Article 52, 28 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_4_5_2","article-title":"Algorithmic fair allocation of indivisible items: A survey and new questions","author":"Aziz Haris","year":"2022","unstructured":"Haris Aziz, Bo Li, Herv\u00e9 Moulin, and Xiaowei Wu. 2022. Algorithmic fair allocation of indivisible items: A survey and new questions. ACM SIGecom Exch. 20, 1 (2022), 24\u201340.","journal-title":"ACM SIGecom Exch."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.07.005"},{"key":"e_1_3_4_7_2","first-page":"335","volume-title":"Proceedings of AAAI","author":"Aziz Haris","year":"2017","unstructured":"Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. 2017. Algorithms for max-min share fair allocation of indivisible chores. In Proceedings of AAAI. 335\u2013341."},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","unstructured":"Moshe Babaioff Tomer Ezra and Uriel Feige. 2022. On best-of-both-worlds fair-share allocations. In Web and Internet Economics. Lecture Notes in Computer Science Vol. 13778. Springer 237\u2013255.","DOI":"10.1007\/978-3-031-22832-2_14"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-018-1157-x"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"issue":"3","key":"e_1_3_4_12_2","first-page":"Article 12, 32","article-title":"The unreasonable fairness of maximum Nash welfare","volume":"7","author":"Caragiannis Ioannis","year":"2019","unstructured":"Ioannis Caragiannis, David Kurokawa, Herv\u00e9 Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7, 3 (2019), Article 12, 32 pages.","journal-title":"ACM Trans. Econ. Comput."},{"issue":"1","key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2311357","article-title":"How to cut a cake fairly","volume":"68","author":"Dubins Lester E.","year":"1961","unstructured":"Lester E. Dubins and Edwin H. Spanier. 1961. How to cut a cake fairly. Am. Math. Mon. 68, 1P1 (1961), 1\u201317.","journal-title":"Am. Math. Mon."},{"key":"e_1_3_4_14_2","doi-asserted-by":"crossref","unstructured":"Uriel Feige Ariel Sapir and Laliv Tauber. 2021. A tight negative example for MMS fair allocations. In Web and Internet Economics. Lecture Notes in Computer Science Vol. 13112. Springer 355\u2013372.","DOI":"10.1007\/978-3-030-94676-0_20"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103547"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2728732.2728738"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.04.029"},{"key":"e_1_3_4_18_2","first-page":"804","article-title":"Partitioning general probability measures","author":"Hill Theodore P.","year":"1987","unstructured":"Theodore P. Hill. 1987. Partitioning general probability measures. Ann. Probab. 15, 2 (1987), 804\u2013813.","journal-title":"Ann. Probab."},{"key":"e_1_3_4_19_2","first-page":"630","volume-title":"Proceedings of EC","author":"Huang Xin","year":"2021","unstructured":"Xin Huang and Pinyan Lu. 2021. An algorithmic framework for approximating maximin share allocation of chores. In Proceedings of EC. ACM, 630\u2013631."},{"issue":"2","key":"e_1_3_4_20_2","first-page":"Article 8, 27 p","article-title":"Fair enough: Guaranteeing approximate maximin shares","volume":"65","author":"Kurokawa David","year":"2018","unstructured":"David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2018. Fair enough: Guaranteeing approximate maximin shares. J. ACM 65, 2 (2018), Article 8, 27 pages.","journal-title":"J. ACM"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_3_4_22_2","first-page":"125","volume-title":"Proceedings of EC","author":"Lipton Richard J.","year":"2004","unstructured":"Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings of EC. ACM, 125\u2013131."},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","unstructured":"Evangelos Markakis and Christos-Alexandros Psomas. 2011. On worst-case allocations in the presence of indivisible goods. In Internet and Network Economics. Lecture Notes in Computer Science Vol. 7090. Springer 278\u2013289.","DOI":"10.1007\/978-3-642-25510-6_24"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"e_1_3_4_25_2","first-page":"675","volume-title":"Proceedings of EC","author":"Procaccia Ariel D.","year":"2014","unstructured":"Ariel D. Procaccia and Junxing Wang. 2014. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of EC. ACM, 675\u2013692."},{"key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.2307\/1907319","article-title":"Sur la division pragmatique","volume":"17","author":"Steinhaus Hugo","year":"1949","unstructured":"Hugo Steinhaus. 1949. Sur la division pragmatique. Econometrica 17, Suppl. (1949), 315\u2013319.","journal-title":"Econometrica"},{"key":"e_1_3_4_27_2","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\/3703845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3703845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:42Z","timestamp":1750295382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,5]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3703845"],"URL":"https:\/\/doi.org\/10.1145\/3703845","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2024,12,5]]},"assertion":[{"value":"2024-01-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}