An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

Abstract

In this paper, we consider the problem of how to fairly dividing $m$ indivisible chores among $n$ agents. The fairness measure we considered here is the maximin share. The previous best known result is that there always exists a $\frac{4}{3}$ approximation maximin share allocation. With a novel algorithm, we can always find a $\frac{11}{9}$ approximation maximin share allocation for any instances. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem.

In Proceedings of the 22nd ACM Conference on Economics and Computation (EC '21)

Cited by in corpus (8)

• Ordinal Maximin Share Approximation for Goods
• Maximin Fairness with Mixed Divisible and Indivisible Goods
• Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores
• Equitable Allocations of Indivisible Goods
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
• The Maximin Share Dominance Relation
• Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
• Fairness Criteria for Allocating Indivisible Chores: Connections and Efficiencies