{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:40:35Z","timestamp":1767318035496,"version":"3.48.0"},"publisher-location":"Singapore","reference-count":38,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819548385","type":"print"},{"value":"9789819548392","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-981-95-4839-2_12","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:37:54Z","timestamp":1767317874000},"page":"148-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating EFX Through a\u00a0New Notion of\u00a0Fairness"],"prefix":"10.1007","author":[{"given":"Rui","family":"Dai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxuan","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhengyang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zihe","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Akrami, H., Alon, N., Chaudhury, B.R., Garg, J., Mehlhorn, K., Mehta, R.: Efx: a simpler approach and an (almost) optimal guarantee via rainbow cycle number. In: 24th ACM Conference on Economics and Computation, EC 2023, p.\u00a061. Association for Computing Machinery (2023)","DOI":"10.1145\/3580507.3597799"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Akrami, H., Ray\u00a0Chaudhury, B., Garg, J., Mehlhorn, K., Mehta, R.: Fair and efficient allocation of indivisible chores with surplus. In: Thirty-Second International Joint Conference on Artificial Intelligence, pp. 2494\u20132502. IJCAI (2023)","DOI":"10.24963\/ijcai.2023\/277"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N.: Splitting necklaces. Adv. Math. 63(3), 247\u2013253 (1987)","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2021.02.020","volume":"863","author":"G Amanatidis","year":"2021","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Hollender, A., Voudouris, A.A.: Maximum Nash welfare and other stories about EFX. Theoret. Comput. Sci. 863, 69\u201385 (2021)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Filos-Ratsikas, A., Sgouritsa, A.: Pushing the frontier on approximate EFX allocations. arXiv preprint arXiv:2406.12413 (2024)","DOI":"10.1145\/3670865.3673582"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2020.07.006","volume":"841","author":"G Amanatidis","year":"2020","unstructured":"Amanatidis, G., Markakis, E., Ntokos, A.: Multiple birds with one stone: beating 1\/2 for EFX and GMMS via envy cycle elimination. Theoret. Comput. Sci. 841, 94\u2013109 (2020)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-022-01855-y","volume":"203","author":"H Aziz","year":"2024","unstructured":"Aziz, H., Li, B., Wu, X.: Approximate and strategyproof maximin share allocation of chores with ordinal preferences. Math. Program. 203(1), 319\u2013345 (2024)","journal-title":"Math. Program."},{"key":"12_CR8","unstructured":"Aziz, H., Lindsay, J., Ritossa, A., Suzuki, M.: Fair allocation of two types of chores. In: 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 143\u2013151 (2023)"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Aziz, H., Rauchecker, G., Schryen, G., Walsh, T.: Algorithms for max-min share fair allocation of indivisible chores. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a031 (2017)","DOI":"10.1609\/aaai.v31i1.10582"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Barman, S., Biswas, A., Krishnamurthy, S., Narahari, Y.: Groupwise maximin fair allocation of indivisible goods. In: 32nd AAAI Conference on Artificial Intelligence (2018)","DOI":"10.1609\/aaai.v32i1.11463"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3485006","volume":"9","author":"N Benabbou","year":"2021","unstructured":"Benabbou, N., Chakraborty, M., Igarashi, A., Zick, Y.: Finding fair and efficient allocations for matroid rank valuations. ACM Trans. Econ. Comput. 9(4), 1\u201341 (2021)","journal-title":"ACM Trans. Econ. Comput."},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Berger, B., Cohen, A., Feldman, M., Fiat, A.: Almost full EFX exists for four agents. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a036, pp. 4826\u20134833 (2022)","DOI":"10.1609\/aaai.v36i5.20410"},{"key":"12_CR13","unstructured":"Bhaskar, U., Sricharan, A., Vaish, R.: On approximate envy-freeness for indivisible chores and mixed resources. Randomization, and Combinatorial Optimization. Algorithms and Techniques, Approximation (2021)"},{"issue":"6","key":"12_CR14","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."},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3355902","volume":"7","author":"I Caragiannis","year":"2019","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. (TEAC) 7(3), 1\u201332 (2019)","journal-title":"ACM Trans. Econ. Comput. (TEAC)"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Chan, H., Chen, J., Li, B., Wu, X.: Maximin-aware allocations of indivisible goods. In: 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1871\u20131873 (2019)","DOI":"10.24963\/ijcai.2019\/20"},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3616009","volume":"71","author":"BR Chaudhury","year":"2024","unstructured":"Chaudhury, B.R., Garg, J., Mehlhorn, K.: EFX exists for three agents. J. ACM 71(1), 1\u201327 (2024)","journal-title":"J. ACM"},{"issue":"4","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1336","DOI":"10.1137\/20M1359134","volume":"50","author":"BR Chaudhury","year":"2021","unstructured":"Chaudhury, B.R., Kavitha, T., Mehlhorn, K., Sgouritsa, A.: A little charity guarantees almost envy-freeness. SIAM J. Comput. 50(4), 1336\u20131358 (2021). https:\/\/doi.org\/10.1137\/20M1359134","journal-title":"SIAM J. Comput."},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Fiat, A., Koutsoupias, E., Sgouritsa, A.: Fair allocation in graphs. In: Proceedings of the 24th ACM Conference on Economics and Computation, pp. 473\u2013488 (2023)","DOI":"10.1145\/3580507.3597764"},{"key":"12_CR20","unstructured":"Christoforidis, V., Santorinaios, C.: On the pursuit of EFX for chores: non-existence and approximations. arXiv preprint arXiv:2406.10752 (2024)"},{"key":"12_CR21","unstructured":"Foley, D.K.: Resource allocation and the public sector. Yale University (1966)"},{"issue":"3\u20134","key":"12_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3618116","volume":"11","author":"Y Gafni","year":"2023","unstructured":"Gafni, Y., Huang, X., Lavi, R., Talgam-Cohen, I.: Unified fair allocation of goods and chores via copies. ACM Trans. Econ. Comput. 11(3\u20134), 1\u201327 (2023)","journal-title":"ACM Trans. Econ. Comput."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Gorantla, P., Marwaha, K., Velusamy, S.: Fair allocation of a multiset of indivisible items. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 304\u2013331. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch13"},{"key":"12_CR24","unstructured":"Gourv\u00e8s, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: ECAI 2014, pp. 393\u2013398. IOS Press (2014)"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-030-64946-3_26","volume-title":"Web and Internet Economics","author":"D Halpern","year":"2020","unstructured":"Halpern, D., Procaccia, A.D., Psomas, A., Shah, N.: Fair division with binary valuations: one rule to rule them all. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds.) WINE 2020. LNCS, vol. 12495, pp. 370\u2013383. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64946-3_26"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Hosseini, H., Sikdar, S., Vaish, R., Xia, L.: Fair and efficient allocations under lexicographic preferences. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a035, pp. 5472\u20135480 (2021)","DOI":"10.1609\/aaai.v35i6.16689"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Huang, X., Segal-Halevi, E.: A reduction from chores allocation to job scheduling. In: Proceedings of the 24th ACM Conference on Economics and Computation, pp. 908\u2013908 (2023)","DOI":"10.1145\/3580507.3597676"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Mahara, R., Sakamoto, S.: EFX allocations for indivisible chores: matching-based approach. In: International Symposium on Algorithmic Game Theory, pp. 257\u2013270. Springer (2023)","DOI":"10.1007\/978-3-031-43254-5_15"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Li, B., Li, Y., Wu, X.: Almost (weighted) proportional allocations for indivisible chores. In: 31st ACM World Wide Web Conference. WWW 2022, pp. 122\u2013131. Inc, Association for Computing Machinery (2022)","DOI":"10.1145\/3485447.3512057"},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce. p. 125\u2013131. EC \u201904, Association for Computing Machinery, New York, NY, USA (2004). https:\/\/doi.org\/10.1145\/988772.988792","DOI":"10.1145\/988772.988792"},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.dam.2023.06.035","volume":"340","author":"R Mahara","year":"2023","unstructured":"Mahara, R.: Existence of EFX for two additive valuations. Discret. Appl. Math. 340, 115\u2013122 (2023)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"12_CR32","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1287\/moor.2022.0044","volume":"49","author":"R Mahara","year":"2024","unstructured":"Mahara, R.: Extension of additive valuations to general valuations on the existence of EFX. Math. Oper. Res. 49(2), 1263\u20131277 (2024)","journal-title":"Math. Oper. Res."},{"key":"12_CR33","unstructured":"Markakis, E.K.: Approximation algorithms and hardness results for fair division with indivisible goods (2017). https:\/\/api.semanticscholar.org\/CorpusID:32862104"},{"issue":"1","key":"12_CR34","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1146\/annurev-economics-080218-025559","volume":"11","author":"H Moulin","year":"2019","unstructured":"Moulin, H.: Fair division in the internet age. Ann. Rev. Econ. 11(1), 407\u2013441 (2019)","journal-title":"Ann. Rev. Econ."},{"issue":"2","key":"12_CR35","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/19M124397X","volume":"34","author":"B Plaut","year":"2020","unstructured":"Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2), 1039\u20131068 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"12_CR36","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":"12_CR37","doi-asserted-by":"crossref","unstructured":"Tao, B., Wu, X., Yu, Z., Zhou, S.: On the existence of EFX (and pareto-optimal) allocations for binary chores. arXiv preprint arXiv:2308.12177 (2023)","DOI":"10.1007\/978-981-97-7752-5_3"},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Zhou, S., Wu, X.: Approximately EFX allocations for indivisible chores. Artif. Intell. 326, 104037 (2024)","DOI":"10.1016\/j.artint.2023.104037"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-4839-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:37:56Z","timestamp":1767317876000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-4839-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819548385","9789819548392"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-4839-2_12","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":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jinan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.maths.sdnu.edu.cn\/TAMC2025.htm","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}