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 weighted equitable up to one item and the efficiency criterion of fractional Pareto-Optimal. Inspired by Fisher Market equilibrium [9] , we construct a WEQ1 allocation among Market equilibrium through item transferring and price raising. Our algorithm provides a WEQ1+fPO allocation for additive valuations in pseudo-polynomial time. Moreover, we consider a special k -ary instance, i.e., each agent has at most k different disutility values for chores when k is a constant. We show that a WEQ1+fPO allocation can be computed in polynomial time in such case.