@inproceedings{62b9ab20037c402b827efed52e293f6c,
title = "Approximating EFX Through a New Notion of Fairness",
abstract = "This paper addresses the fair division of indivisible chores in the additive setting. We propose a polynomial-time algorithm that guarantees either a 3.69-EFX or 1.24-proportional allocation for three agents. Additionally, we introduce a new fairness concept called discrete perfect (DP), which applies to chore allocations. We prove the existence of DP for two agents by providing an efficient algorithm and extend this by proposing an algorithm that approximates DP for the general case with n agents. We believe the DP concept holds independent value and could have broader applications.",
keywords = "Approximation Algorithm, Fair Division, Game Theory",
author = "Rui Dai and Yuxuan Wang and Zhengyang Liu and Zihe Wang",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.; 19th Annual Conference on Theory and Applications of Models of Computation, TAMC 2025 ; Conference date: 19-09-2025 Through 21-09-2025",
year = "2026",
doi = "10.1007/978-981-95-4839-2\_12",
language = "English",
isbn = "9789819548385",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "148--162",
editor = "Min Li and Mingji Xia and Peng Zhang",
booktitle = "Theory and Applications of Models of Computation - 19th Annual Conference, TAMC 2025, Proceedings",
address = "Germany",
}