Maxmin Share Fair Allocation of Indivisible Chores to Asymmetric Agents

We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concepts we focus on are natural generalizations of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for 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 constantapproximation algorithm, via linear program, for OWMMS. For two special cases: binary valuation case and 2-agent case, we provide exact or better constant-approximation algorithms.