{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:29:10Z","timestamp":1767320950845,"version":"3.48.0"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032085597","type":"print"},{"value":"9783032085603","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-08560-3_32","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:24:18Z","timestamp":1767320658000},"page":"564-590","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Fair Allocation is Approximately Optimal for\u00a0Indivisible Chores, or\u00a0Is It?"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7500-8355","authenticated-orcid":false,"given":"Bo","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1464-1979","authenticated-orcid":false,"given":"Ankang","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8442-3708","authenticated-orcid":false,"given":"Shiji","family":"Xing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","volume":"322","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis, G., et al.: Fair division of indivisible goods: recent progress and open questions. Artif. Intell. 322, 103965 (2023)","journal-title":"Artif. Intell."},{"issue":"4","key":"32_CR2","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, \u00c9., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"32_CR3","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.ejor.2022.10.013","volume":"307","author":"H Aziz","year":"2023","unstructured":"Aziz, H., Huang, X., Mattei, N., Segal-Halevi, E.: Computing welfare-maximizing fair allocations of indivisible goods. Eur. J. Oper. Res. 307(2), 773\u2013784 (2023)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"32_CR4","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1016\/j.orl.2020.07.005","volume":"48","author":"H Aziz","year":"2020","unstructured":"Aziz, H., Moulin, H., Sandomirskiy, F.: A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation. Oper. Res. Lett. 48(5), 573\u2013578 (2020)","journal-title":"Oper. Res. Lett."},{"key":"32_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-030-64946-3_25","volume-title":"Web and Internet Economics","author":"S Barman","year":"2020","unstructured":"Barman, S., Bhaskar, U., Shah, N.: Optimal bounds on the price of fairness for indivisible goods. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds.) WINE 2020. LNCS, vol. 12495, pp. 356\u2013369. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64946-3_25"},{"key":"32_CR6","unstructured":"Barman, S., Ghalme, G., Jain, S., Kulkarni, P., Narang, S.: Fair division of indivisible goods among strategic agents. In: AAMAS, pp. 1811\u20131813. International Foundation for Autonomous Agents and Multiagent Systems (2019)"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Barman, S., Krishnamurthy, S.K.: On the proximity of markets with integral equilibria. In: AAAI, pp. 1748\u20131755. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33011748"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: EC, pp. 557\u2013574. ACM (2018)","DOI":"10.1145\/3219166.3219176"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"1156","DOI":"10.1137\/20M1388310","volume":"36","author":"X Bei","year":"2022","unstructured":"Bei, X., Igarashi, A., Lu, X., Suksompong, W.: The price of connectivity in fair division. SIAM J. Discret. Math. 36(2), 1156\u20131186 (2022)","journal-title":"SIAM J. Discret. Math."},{"key":"32_CR10","unstructured":"Bei, X., Lam, A., Lu, X., Suksompong, W.: Welfare loss in connected resource allocation. CoRR abs\/2405.03467 (2024)"},{"issue":"7","key":"32_CR11","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1007\/s00224-021-10039-8","volume":"65","author":"X Bei","year":"2021","unstructured":"Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. Theory Comput. Syst. 65(7), 1069\u20131093 (2021)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"32_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/opre.1100.0865","volume":"59","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17\u201331 (2011)","journal-title":"Oper. Res."},{"key":"32_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975","volume-title":"Fair Division - From Cake-Cutting to Dispute Resolution","author":"SJ Brams","year":"1996","unstructured":"Brams, S.J., Taylor, A.D.: Fair Division - From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)"},{"key":"32_CR14","unstructured":"Bu, X., Li, Z., Liu, S., Song, J., Tao, B.: On the complexity of maximizing social welfare within fair allocations of indivisible goods. CoRR abs\/2205.14296 (2022)"},{"key":"32_CR15","unstructured":"Buchem, M., Rohwedder, L., Vredeveld, T., Wiese, A.: Additive approximation schemes for load balancing problems. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. LIPIcs, vol.\u00a0198, pp. 42:1\u201342:17 (2021)"},{"issue":"6","key":"32_CR16","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"key":"32_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1007\/978-3-030-94676-0_29","volume-title":"Web and Internet Economics","author":"I Caragiannis","year":"2022","unstructured":"Caragiannis, I., Ioannidis, S.D.: Computing envy-freeable allocations with\u00a0limited subsidies. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds.) WINE 2021. LNCS, vol. 13112, pp. 522\u2013539. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-94676-0_29"},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-642-10841-9_45","volume-title":"Internet and Network Economics","author":"I Caragiannis","year":"2009","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 475\u2013482. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10841-9_45"},{"issue":"4","key":"32_CR19","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589\u2013610 (2012)","journal-title":"Theory Comput. Syst."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7(3), 12:1\u201312:32 (2019)","DOI":"10.1145\/3355902"},{"key":"32_CR21","unstructured":"Ebadian, S., Peters, D., Shah, N.: How to fairly allocate easy and difficult chores. In: AAMAS, pp. 372\u2013380. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) (2022)"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Freeman, R., Sikdar, S., Vaish, R., Xia, L.: Equitable allocations of indivisible goods. In: IJCAI, pp. 280\u2013286. ijcai.org (2019)","DOI":"10.24963\/ijcai.2019\/40"},{"key":"32_CR23","unstructured":"Freeman, R., Sikdar, S., Vaish, R., Xia, L.: Equitable allocations of indivisible chores. In: AAMAS, pp. 384\u2013392. International Foundation for Autonomous Agents and Multiagent Systems (2020)"},{"key":"32_CR24","unstructured":"Gamow, G., Stern, M.: Puzzle-Math. Viking Press (1958)"},{"key":"32_CR25","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Garg, J., Murhekar, A., Qin, J.: Fair and efficient allocations of chores under bivalued preferences. In: AAAI, pp. 5043\u20135050. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i5.20436"},{"key":"32_CR27","unstructured":"Garg, J., Murhekar, A., Qin, J.: Weighted EF1 and PO allocations with few types of agents or chores. CoRR abs\/2402.17173 (2024)"},{"key":"32_CR28","unstructured":"Gourv\u00e8s, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: ECAI 2014. Frontiers in Artificial Intelligence and Applications, vol.\u00a0263, pp. 393\u2013398. IOS Press (2014)"},{"issue":"2","key":"32_CR29","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"32_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104739","volume":"281","author":"F H\u00f6hne","year":"2021","unstructured":"H\u00f6hne, F., van Stee, R.: Allocating contiguous blocks of indivisible chores fairly. Inf. Comput. 281, 104739 (2021)","journal-title":"Inf. Comput."},{"key":"32_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404\u2013413. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_38"},{"key":"32_CR32","doi-asserted-by":"crossref","unstructured":"Li, B., Li, Y., Wu, X.: Almost (weighted) proportional allocations for indivisible chores. In: WWW 2022: The ACM Web Conference 2022, Virtual Event, Lyon, France, 25\u201329 April 2022, pp. 122\u2013131. ACM (2022)","DOI":"10.1145\/3485447.3512057"},{"key":"32_CR33","unstructured":"Li, Z., Liu, S., Lu, X., Tao, B., Tao, Y.: A complete landscape for the price of envy-freeness. In: AAMAS, pp. 1183\u20131191. International Foundation for Autonomous Agents and Multiagent Systems\/ACM (2024)"},{"key":"32_CR34","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, 17\u201320 May 2004, pp. 125\u2013131. ACM (2004)","DOI":"10.1145\/988772.988792"},{"key":"32_CR35","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus, H.: The problem of fair division. Econometrica 16, 101\u2013104 (1948)","journal-title":"Econometrica"},{"key":"32_CR36","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.dam.2019.01.036","volume":"260","author":"W Suksompong","year":"2019","unstructured":"Suksompong, W.: Fairly allocating contiguous blocks of indivisible items. Discret. Appl. Math. 260, 227\u2013236 (2019)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"32_CR37","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/s10458-022-09587-1","volume":"37","author":"A Sun","year":"2023","unstructured":"Sun, A., Chen, B., Doan, X.V.: Equitability and welfare maximization for allocating indivisible items. Auton. Agents Multi Agent Syst. 37(1), 8 (2023)","journal-title":"Auton. Agents Multi Agent Syst."},{"issue":"2","key":"32_CR38","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s10458-023-09618-5","volume":"37","author":"A Sun","year":"2023","unstructured":"Sun, A., Chen, B., Doan, X.V.: Fairness criteria for allocating indivisible chores: connections and efficiencies. Auton. Agents Multi Agent Syst. 37(2), 39 (2023)","journal-title":"Auton. Agents Multi Agent Syst."},{"key":"32_CR39","doi-asserted-by":"crossref","unstructured":"Sun, A., Li, B.: On the price of fairness in the connected discrete cake cutting problem. In: ECAI. Frontiers in Artificial Intelligence and Applications, vol.\u00a0372, pp. 2242\u20132249. IOS Press (2023)","DOI":"10.3233\/FAIA230522"},{"key":"32_CR40","unstructured":"Sun, A., Li, B.: Allocating contiguous blocks of indivisible chores fairly: revisited. In: AAMAS, pp. 1800\u20131808. International Foundation for Autonomous Agents and Multiagent Systems\/ACM (2024)"},{"key":"32_CR41","doi-asserted-by":"crossref","unstructured":"Thomson, W.: Introduction to the theory of fair allocation. In: Handbook of Computational Social Choice, pp. 261\u2013283. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.012"},{"key":"32_CR42","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0531(74)90075-1","volume":"9","author":"HR Varian","year":"1974","unstructured":"Varian, H.R.: Equity, envy and efficiency. J. Econ. Theory 9, 63\u201391 (1974)","journal-title":"J. Econ. Theory"},{"key":"32_CR43","doi-asserted-by":"crossref","unstructured":"Wu, X., Zhang, C., Zhou, S.: Weighted EF1 allocations for indivisible chores. In: EC, p.\u00a01155. ACM (2023)","DOI":"10.1145\/3580507.3597763"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-08560-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:24:20Z","timestamp":1767320660000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-08560-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032085597","9783032085603"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-08560-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edinburgh","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2024.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}