Finding Fair and Efficient Allocations of Indivisible Chores

Fair resource allocation has found widespread application across various fields, such as economics and computer science, and has garnered significant attention. In this paper, we address the problem of allocating a set of indivisible chores among a group of agents. Our objective is to achieve an allocation that satisfies the fairness criterion of envy-free up to one item and the efficiency criterion of Pareto-Optimal. Inspired by Fisher Market equilibrium [7], we construct an EF1 allocation among equilibrium through item transfers and price raising. For additive valuations, our algorithm provides a \( 7\epsilon \) -EF1 and \( \epsilon \) -PO allocation with \( O(m,n,\frac{1}{\epsilon },\ln {c_{max}}) \) complexity.