Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

概要

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$.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

# 概要
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.

# 原典
https://arxiv.org/abs/2610.15443

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。