2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.

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

academic

Online MMS Allocation for Chores

基本信息

论文ID: 2507.14039
标题: Online MMS Allocation for Chores
作者: Jiaxin Song (University of Illinois Urbana-Champaign), Biaoshuai Tao (Shanghai Jiao Tong University), Wenqian Wang (Shanghai Jiao Tong University), Yuhao Zhang (Shanghai Jiao Tong University)
分类: cs.GT (Computer Science - Game Theory)
发表时间: 2025年10月11日 (arXiv v2)
论文链接: https://arxiv.org/abs/2507.14039

摘要

本文研究在线环境下n个智能体之间不可分割家务(chores)的公平分配问题。在该设置中，物品按顺序到达，必须在到达时不可撤销地分配给某个智能体，目标是最终产生α-MMS分配。尽管最近的工作在限制性假设下取得了进展，但对于一般情况，已知的最佳保证仍然是平凡的n-MMS，而最强的下界仅为2。本文通过证明对于任何固定的n和ε，没有算法能够保证(n-ε)-MMS分配，从而在负面结果上封闭了这一差距。同时，本文还提出了一个在线算法，保证min{n, O(k), O(log D)}-MMS分配，其中k是所有智能体中不同负效用值的最大数量，D是任何智能体最大和最小负效用之间的最大比率。