Randomized method fairly divides chores as agents arrive sequentially
Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals
Computer Science and Game Theory
Summary
The paper addresses how to fairly assign chores to people who arrive one by one, without knowing their preferences in advance. The authors study a fairness measure called maximin share (MMS), which tries to ensure everyone gets a fair share of chores. They develop a random algorithm that performs nearly as well as possible when everyone has simple 'binary' dislike levels for chores and also when dislike levels are more general. Their algorithm can give strong fairness guarantees both on average and with high probability even though assignments must be made immediately as each person arrives.
What this means in practice
- •For distributed task schedulers: Allocate sequentially arriving tasks among workers fairly, ensuring no one is overloaded despite unknown costs until arrival.
- •For cloud resource managers: Assign incoming maintenance jobs to servers fairly and efficiently using predictable randomized methods under online conditions.
Authors
Haolong Li, Fangxiao Wang, Xiaowei Wu
Abstract
We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.