Lower Bound for Online MMS Assignment of Indivisible Chores

Masoud Seddighin, Saeed Seddighin · 2025

Read Lower Bound for Online MMS Assignment of Indivisible Chores by Masoud Seddighin, Saeed Seddighin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12984.txt.

Introduction

Masoud Seddighin and Saeed Seddighin prove that dividing chores online is hopeless in the worst case. Their 2025 paper studies the online assignment of indivisible chores under maximin share criteria, where items arrive one by one and must be handed out immediately and permanently.

Fairness benchmarks from offline division set the bar each agent should reach. Earlier work showed no deterministic online algorithm could guarantee better than half that benchmark. The new result is far harsher: for n agents, no deterministic online algorithm can beat a factor of n, meaning the guarantee collapses as the group grows. In other words, the order of arrival alone, without any malice in the chores themselves, defeats deterministic fairness online.

Catalog record

CREATORMasoud Seddighin, Saeed Seddighin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12984

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bound for Online MMS Assignment of Indivisible Chores Masoud Seddighin, Saeed Seddighin Abstract We consider the problem of online assignment of indivisible chores under MMS criteria. The previous work proves that any deterministic online algorithm for chore division has a competitive ratio of at least 2. In this work, we improve this bound by showing that no deterministic online algorithm can obtain a competitive ratio better than n n for n n agents. 1 Introduction Fair division is a well-established problem in mathematics and economics, with broad relevance to disciplines such as political science, social science, and computer science [ 7 , 19 , 4 ] . The concept was first formally introduced by Hugo Steinhaus under the framework of "cake cutting," which focuses on distributing a divisible resource—the "cake"—among multiple agents with varying preferences. For over eight decades, this problem has attracted significant scholarly interest [ 8 , 20 , 4 ] . In more recent years, attention has shifted toward a discrete variant of the problem involving the allocation of indivisible tasks or goods, especially within computer science [ 13 , 10 , 6 , 3 , 5 , 15 , 16 ] . Rather than dividing a divisible resource such as a cake, the goal here is to allocate a set of indivisible items or tasks among n agents. In such cases, direct proportional division is often impossible—for example, when only a single item must be assigned. This work focuses on the dual problem: the fair assignment of chores. Unlike goods, which are desirable, chores represent undesirable tasks that impose costs on the agents. The objective is to distribute these chores in a way that no agent bears more than their fair share of the burden. Our focus lies specifically on the indivisible setting, using the maximin ( MMS ) fairness criterion introduced by Budish [ 5 ] to guide the allocation which has been used in many works [ 9 , 17 , 2 , 18 , 1 , 13 , 14 , 12 ] . Formally, let N be a set of n agents, and M be a set of m chores. We denote the agents by N=\{a_{1},a_{2},\ldots,a_{n}\} and chores by M=\{b_{1},b_{2},\ldots,b_{m}\} . Each agent a_{i} has an additive function V_{i} over the chores which denotes her cost for each subset of chores. Let \Pi(M) denote the set of all n -partitionings of the chores. The maximin value of agent a_{i} (denoted by \textsf{MMS}_{i} ) is defined as \textsf{MMS}_{i}=\max_{\langle\pi_{1},\pi_{2},\ldots,\pi_{n}\rangle\in\Pi}\min_{1\leq j\leq n}V_{i}(\pi_{j}), where \Pi represents the set of all possible partitionings of M into n bundles, and V_{i}(\pi_{j}) is the cost that agent a_{i} assigns to bundle \pi_{j} . An allocation is called MMS (or \beta - MMS ) if every agent a_{i} receives a bundle which costs at most \textsf{MMS}_{i} (or \beta\cdot\textsf{MMS}_{i} ) to her. In this setting, the goal is to assign chores to agents such that the cost each agent incurs from their assigned bundle is within a constant multiplicative factor of their MMS value. The MMS value acts as a natural lower bound, since even in the case of identical costs across agents, at least one agent must receive a bundle with cost no less than their MMS . This leads to the central question: Can we find chore assignments where each agent’s total cost is bounded by a constant multiple of their MMS value? The current best known upper bound for this factor is \frac{13}{11} [ 11 ] . A natural and practical extension of the fair chore division problem is its online variant, where chores arrive sequentially over time rather than being known in advance. In this setting, we assume that the number of agents is known ahead of time, but the chores—and the agents’ costs for them—are revealed one by one as they arrive. Upon the arrival of each chore, we learn how costly it is for each agent and must assign it immediately and irrevocably, without knowledge of future chores. This online formulation captures real-world scenarios such as task assignment in dynamic work environments, where decisions must be made in real time. The central challenge is to design an online algorithm that ensures fairness—measured, for instance, by the maximin share ( MMS ) benchmark—despite the uncertainty and lack of full information. Previous work [ 21 ] shows that for online allocation of indivisible goods, no fraction of the MMS benchmark can be guaranteed to all agents via a deterministic algorithm. For the online assignment of indivisible chores, the best known lower bound for deterministic algorithms is a lower bound of 2 [ 21 ] . In other words, it is proven that for any deterministic online algorithm for assignment of indivisible chores there is one scenario in which one agent receives a bundle of chores that is twice as costly as her MMS value. In this work, we improve this bound to a lower bound of n for n agents. 2 Preliminaries Let N be a set of n agents, and M be a set of m chores. We denote the agents by N=\{a_{1},a_{2},\ldots,a_{n}\} and chores by M=\{b_{1},b_{2},\ldots,b_{m}\} . Each agent a_{i} has an additive function V_{i} over the chores which denotes her cost for each subset of chores. As proposed by Budish [ 5 ] , the maximin value of agent a_{i} (denoted by \textsf{MMS}_{i} ) is defined as \textsf{MMS}_{i}=\min_{\langle A_{1},A_{2},\ldots,A_{n}\rangle\in\Pi(M)}\max_{a_{j}\in N}V_{i}(A_{j}). (1) We define an assignment as being \alpha - MMS if all chores are assigned to agents and each agent a_{i} receives a bundle S_{i} of chores such that V_{i}(S_{i})\leq\alpha\cdot\textsf{MMS}_{i} . In our online setting, initially, our algorithm is aware of the value of n . It is important to note that our algorithm is not even aware of the value of m in the beginning. The chores then arrive one by one, and each time a chore arrives our algorithm learns the cost of each chore for each agent. After that, it has to make an irrevocable decision as to which agent the chore is assigned to. The algorithm terminates after all chores arrive. We call an algorithm \alpha -competitive, if it assigns the chores to the agents in a way that after the termination of the algorithm, the assignment is \alpha - MMS . 3 Lower Bound of n for Deterministic Algorithms It has been proven in previous work [ 21 ] that any deterministic online algorithm for chore division has a competitive ratio of at least 2 . Indeed, the trivial algorithm that assigns all chores to an agent has a competitive ratio of n . We improve the lower bound of 2 to a lower bound of n and close this gap by showing that no deterministic algorithm for online chore division has a competitive ratio better than n . Theorem 3.1 . No deterministic algorithm for online chore division has competitive ratio better than n for n agents. Proof. For any \epsilon>0 , we construct an online scenario, namely \textsf{sc}(n,\epsilon) , for which any deterministic algorithm fails to be (n-n\epsilon) -competitive. We construct our scenario in a recursive manner. We parametrize our scenarios by two quantities. More precisely, we represent a scenario by \textsf{sc}(i,\epsilon) where the algorithm is guaranteed

Read the complete text