Abstract
We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight
the fact that commonly-used algorithms that work
well for the allocation of goods to asymmetric
agents, and even for chores to symmetric agents do
not provide good approximations for allocation of
chores to asymmetric agents under WMMS. As a
consequence, we present a novel polynomial-time
constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms