On The Pursuit of EFX for Chores: Non-Existence and Approximations
<|reference_start|>On The Pursuit of EFX for Chores: Non-Existence and Approximations: We study the problem of fairly allocating a set of chores to a group of agents. The existence of envy-free up to any item (EFX) allocations is a long-standing open question for both goods and chores. We resolve this question by providing a negative answer for the latter, presenting a simple construction that admits no EFX solutions for allocating six items to three agents equipped with superadditive cost functions, thus proving a separation result between goods and bads. In fact, we uncover a deeper insight, showing that the instance has unbounded approximation ratio. Moreover, we show that deciding whether an EFX allocation exists is NP-complete. On the positive side, we establish the existence of EFX allocations under general monotone cost functions when the number of items is at most $n+2$. We then shift our attention to additive cost functions. We employ a general framework in order to improve the approximation guarantees in the well-studied case of three additive agents, and provide several conditional approximation bounds that leverage ordinal information.<|reference_end|>
@article{christoforidis2024on,
    title={On The Pursuit of EFX for Chores: Non-Existence and Approximations},
    author={Vasilis Christoforidis and Christodoulos Santorinaios},
    journal={arXiv preprint arXiv:2406.10752},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.10752},
    primaryClass={cs.GT}
}