{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T00:22:59Z","timestamp":1771460579112,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"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":[],"published-print":{"date-parts":[[2022,4,25]]},"DOI":"10.1145\/3485447.3512057","type":"proceedings-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T05:13:07Z","timestamp":1650863587000},"page":"122-131","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Almost (Weighted) Proportional Allocations for Indivisible Chores\u2731\u2731"],"prefix":"10.1145","author":[{"given":"Bo","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computing, Hong Kong Polytechnic University, China"}]},{"given":"Yingkai","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Northwestern University, USA"}]},{"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"State Key Lab of IOTSC, University of Macau, China"}]}],"member":"320","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Georgios Amanatidis Georgios Birmpas Aris Filos-Ratsikas Alexandros Hollender and Alexandros\u00a0A. Voudouris. 2020. Maximum Nash Welfare and Other Stories About EFX. In IJCAI. ijcai.org 24\u201330.","DOI":"10.24963\/ijcai.2020\/4"},{"key":"e_1_3_2_1_3_1","volume-title":"On Truthful Mechanisms for Maximin Share Allocations","author":"Amanatidis Georgios","unstructured":"Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2016. On Truthful Mechanisms for Maximin Share Allocations. In IJCAI. IJCAI\/AAAI Press, 31\u201337."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Haris Aziz Hau Chan and Bo Li. 2019. Weighted Maxmin Fair Share Allocation of Indivisible Chores. In IJCAI. ijcai.org 46\u201352.","DOI":"10.24963\/ijcai.2019\/7"},{"key":"e_1_3_2_1_5_1","unstructured":"Haris Aziz Bo Li and Xiaowei Wu. 2020. Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences. CoRR abs\/2012.13884(2020)."},{"key":"e_1_3_2_1_6_1","volume-title":"A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents","author":"Aziz Haris","unstructured":"Haris Aziz and Simon Mackenzie. 2016. A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. In FOCS. IEEE Computer Society, 416\u2013427."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.07.005"},{"key":"e_1_3_2_1_8_1","volume-title":"Algorithms for Max-Min Share Fair Allocation of Indivisible Chores","author":"Aziz Haris","unstructured":"Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. 2017. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In AAAI. AAAI Press, 335\u2013341."},{"key":"e_1_3_2_1_9_1","volume-title":"Fair-Share Allocations for Agents with Arbitrary Entitlements. EC","author":"Babaioff Moshe","year":"2021","unstructured":"Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2021. Fair-Share Allocations for Agents with Arbitrary Entitlements. EC (2021)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1062"},{"key":"e_1_3_2_1_11_1","volume-title":"WINE(Lecture Notes in Computer Science, Vol.\u00a012495)","author":"Barman Siddharth","unstructured":"Siddharth Barman, Umang Bhaskar, and Nisarg Shah. 2020. Optimal Bounds on the Price of Fairness for Indivisible Goods. In WINE(Lecture Notes in Computer Science, Vol.\u00a012495). Springer, 356\u2013369."},{"key":"e_1_3_2_1_12_1","volume-title":"Sanath Kumar\u00a0Krishna Murthy, and Yadati Narahari","author":"Barman Siddharth","year":"2018","unstructured":"Siddharth Barman, Arpita Biswas, Sanath Kumar\u00a0Krishna Murthy, and Yadati Narahari. 2018. Groupwise Maximin Fair Allocation of Indivisible Goods. In AAAI. AAAI Press, 917\u2013924."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Siddharth Barman and Sanath\u00a0Kumar Krishnamurthy. 2017. Approximation Algorithms for Maximin Fair Division. In EC. ACM 647\u2013664.","DOI":"10.1145\/3033274.3085136"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Xiaohui Bei Xinhang Lu Pasin Manurangsi and Warut Suksompong. 2019. The Price of Fairness for Indivisible Goods. In IJCAI. ijcai.org 81\u201387.","DOI":"10.24963\/ijcai.2019\/12"},{"key":"e_1_3_2_1_15_1","unstructured":"Ben Berger Avi Cohen Michal Feldman and Amos Fiat. 2021. (Almost Full) EFX Exists for Four Agents (and Beyond). CoRR abs\/2102.10654(2021)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0865"},{"key":"e_1_3_2_1_17_1","first-page":"1","article-title":"On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In APPROX-RANDOM(LIPIcs, Vol.\u00a0207)","volume":"1","author":"Bhaskar Umang","year":"2021","unstructured":"Umang Bhaskar, A.\u00a0R. Sricharan, and Rohit Vaish. 2021. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In APPROX-RANDOM(LIPIcs, Vol.\u00a0207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 1:1\u20131:23.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_1_20_1","volume-title":"WINE(Lecture Notes in Computer Science, Vol.\u00a05929)","author":"Caragiannis Ioannis","unstructured":"Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. 2009. The Efficiency of Fair Division. In WINE(Lecture Notes in Computer Science, Vol.\u00a05929). Springer, 475\u2013482."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_1_22_1","volume-title":"Weighted Envy-Freeness in Indivisible Item Allocation","author":"Chakraborty Mithun","unstructured":"Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. 2020. Weighted Envy-Freeness in Indivisible Item Allocation. In AAMAS. International Foundation for Autonomous Agents and Multiagent Systems, 231\u2013239."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Bhaskar\u00a0Ray Chaudhury Jugal Garg and Kurt Mehlhorn. 2020. EFX Exists for Three Agents. In EC. ACM 1\u201319.","DOI":"10.1145\/3391403.3399511"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Vincent Conitzer Rupert Freeman and Nisarg Shah. 2017. Fair Public Decision Making. In EC. ACM 629\u2013646.","DOI":"10.1145\/3033274.3085125"},{"key":"e_1_3_2_1_25_1","volume-title":"Rental harmony: Sperner\u2019s lemma in fair division. The American mathematical monthly 106, 10","author":"Edward\u00a0Su Francis","year":"1999","unstructured":"Francis Edward\u00a0Su. 1999. Rental harmony: Sperner\u2019s lemma in fair division. The American mathematical monthly 106, 10 (1999), 930\u2013942."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11291"},{"key":"e_1_3_2_1_27_1","unstructured":"Duncan Foley. 1967. Resource Allocation and the Public Sector. Yale Economic Essays(1967) 45\u201398."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Daniel Halpern and Nisarg Shah. 2021. Fair and Efficient Resource Allocation with Partial Information. CoRR abs\/2105.10064(2021).","DOI":"10.24963\/ijcai.2021\/32"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.041"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Felix H\u00f6hne and Rob van Stee. 2021. Allocating contiguous blocks of indivisible chores fairly. Information and Computation(2021) 104739.","DOI":"10.1016\/j.ic.2021.104739"},{"key":"e_1_3_2_1_31_1","unstructured":"Xin Huang and Pinyan Lu. 2019. An algorithmic framework for approximating maximin share allocation of chores. CoRR abs\/1907.04505(2019)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Richard\u00a0J. Lipton Evangelos Markakis Elchanan Mossel and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In EC. ACM 125\u2013131.","DOI":"10.1145\/988772.988792"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"e_1_3_2_1_36_1","first-page":"101","article-title":"The problem of fair division","volume":"16","author":"Steihaus Hugo","year":"1948","unstructured":"Hugo Steihaus. 1948. The problem of fair division. Econometrica 16(1948), 101\u2013104.","journal-title":"Econometrica"}],"event":{"name":"WWW '22: The ACM Web Conference 2022","location":"Virtual Event, Lyon France","acronym":"WWW '22","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM Web Conference 2022"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512057","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485447.3512057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:07Z","timestamp":1750188607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":36,"alternative-id":["10.1145\/3485447.3512057","10.1145\/3485447"],"URL":"https:\/\/doi.org\/10.1145\/3485447.3512057","relation":{},"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"2022-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}