Lower Bound for Online MMS Assignment of Indivisible Chores
By: Masoud Seddighin, Saeed Seddighin
Potential Business Impact:
Makes chores fairer when done one by one.
We consider the problem of online assignment of indivisible chores under \MMS\ criteria. The previous work proves that any deterministic online algorithm for chore division has a competitive ratio of at least 2. In this work, we improve this bound by showing that no deterministic online algorithm can obtain a competitive ratio better than $n$ for $n$ agents.
Similar Papers
Fair Assignment of Indivisible Chores to Asymmetric Agents
CS and Game Theory
Fairly divides chores even with unequal rights.
Constant Weighted Maximin Share Approximations for Chores
CS and Game Theory
Divides chores fairly, even with different needs.
Asymptotic Fair Division: Chores Are Easier Than Goods
CS and Game Theory
Divides chores fairly, even with many people.