Algorithms for Max-Min Share Fair Allocation of Indivisible Chores: Greedy Round-Robin Gives Every Agent at Least (2 − 1/N) Times Her Max-Min Share, and the Factor Cannot Be ImprovedResearch Paper
Many allocation problems distribute work rather than benefits: household and office tasks, teaching loads, shifts, maintenance duties, or jobs assigned to parallel machines. Each item is a chore, which every agent would rather not receive, and chores cannot be split. Under indivisibility an exactly fair split usually does not exist, so the fair-division…