b'@online{Afshinmehr2410.18655,'b"\nTITLE = {Approximate {EFX} and Exact t{EFX} Allocations for Indivisible Chores: Improved Algorithms},\nAUTHOR = {Afshinmehr, Mahyar and Ansaripour, Matin and Danaei, Alireza and Mehlhorn, Kurt},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2410.18655},\nEPRINT = {2410.18655},\nEPRINTTYPE = {arXiv},\nYEAR = {2024},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {We explore the fair distribution of a set of $m$ indivisible chores among $n$<br>agents, where each agent's costs are evaluated using a monotone cost function.<br>Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and<br>a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX).<br>We demonstrate that a 2-approximate EFX allocation exists and is computable in<br>polynomial time for three agents with subadditive cost functions, improving<br>upon the previous $(2 + \\sqrt{6})$ approximation for additive cost functions.<br>This result requires extensive case analysis. Christoforidis et al. (IJCAI'24)<br>independently claim the same approximation for additive cost functions;<br>however, we provide a counter-example to their algorithm. We expand the number<br>of agents to any number to get the same approximation guarantee with the<br>assumption of partially identical ordering (IDO) for the cost functions.<br>Additionally, we establish that a tEFX allocation is achievable for three<br>agents if one has an additive 2-ratio bounded cost function, while the others<br>may have general monotone cost functions. This is an improvement from the prior<br>requirement of two agents with additive 2-ratio bounded cost functions. This<br>allocation can also be extended to agent groups with identical valuations.<br>Further, we show various analyses of EFX allocations for chores, such as the<br>relaxations for additive $\\alpha$-ratio-bounded cost functions.<br>},\n}\n"