2025/07/18 by Song, Jiaxin, Tao, Biaoshuai, Wang, Wenqian +1 · 3 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.14039
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 ε, no algorithm can guarantee an (n - ε)-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 + √(3)) ≈ 3.7-MMS allocation.