标题： 在线MMS分配用于任务 显示英文标题

标题： Online MMS Allocation for Chores

摘要： 我们研究在在线设置中，将不可分割的负担公平分配给$n$个代理的问题，其中物品按顺序到达，并且必须在到达时不可撤销地进行分配。 目标是在最后生成一个$\alpha$-MMS 分配。 最近的几项研究已经探讨了这个模型，但仅在一些限制性假设下取得了非平凡的算法，例如两代理的双值特殊情况（Wang 和 Wei，2025），或者通过假设知道每个代理的总不满度（Zhou、Bai 和 Wu，2023）。 对于一般情况，平凡的$n$-MMS 保证仍然是已知的最佳结果，而最强的下界仍然只是$2$。 我们通过证明对于任何固定的$n$和$\varepsilon$，没有算法可以保证一个$(n - \varepsilon)$-MMS 分配，从而在负面方面填补了这一差距。 值得注意的是，这个下界恰好适用于每个$n$，而没有在大$O$符号中隐藏常数，从而精确地匹配平凡的上界。 尽管有这个强烈的不可能性结果，我们还提出了积极的结果。 我们提供了一个在线算法，适用于一般情况，保证一个$\min\{n, O(k), O(\log D)\}$-MMS 分配，其中$k$是所有代理之间不同不满值的最大数量，$D$是任何代理的最大和最小不满值之间的最大比率。 这个界限在广泛的场景中是合理的，例如，当$k$是常数时，意味着我们可以实现一个$O(1)$-MMS 分配。 此外，为了优化重要个性化双值情况下的常数，我们证明如果每个代理至多有两种不同的不满意度，我们的算法保证一个$(2 + \sqrt{3}) \approx 3.7$-MMS 分配。 显示英文摘要

摘要： We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $\alpha$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.