Weighted Maxmin Fair Share Allocation of Indivisible Chores

Haris Aziz, Hau Chan, Bo Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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 symmetric 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.
Original languageEnglish
Title of host publicationIJCAI
Number of pages7
Publication statusPublished - 2019
Externally publishedYes


Dive into the research topics of 'Weighted Maxmin Fair Share Allocation of Indivisible Chores'. Together they form a unique fingerprint.

Cite this