cs.GTOct 30, 2026

Online Fair Division of Chores with Upgrade Recourse

Authors: Yichen Huang, Nicholas Teh

Organizations: Harvard University, USA · University of Oxford, UK

Abstract

We study the online fair division of indivisible chores among nn agents under upgrade recourse, where earlier assignments may be revised but each chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. We show that a simple adaptation of round robin maintains envy-freeness up to one chore (EF1) together with a (2−1/n)(2-1/n)-approximation of the maximin share (MMS), and that no deterministic algorithm without predictions can do better, even when all agents rank the chores in the same order. This stands in contrast to the allocation of goods, where the optimal MMS factor vanishes as nn grows and cannot be achieved together with EF1. Moreover, knowing only the number of chores modulo a period of length O(n)O(n) (and nothing about the costs) suffices to improve upon this factor at the final configuration, while the same algorithm retains a factor below 33 even if this information is wrong. On the other hand, envy-freeness up to any chore (EFX) essentially requires the exact number of chores: uncertainty between two consecutive values already rules out every finite approximation, and even exact knowledge does not allow EFX to be combined with an MMS guarantee better than the trivial factor of nn.

Figures & tables

Explore similar work

Jul 25, 2026

Online Fair Division with Budget Constraints

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.
Oct 11, 2026

Improving the Bounds on Approximating Weighted Maximin Share for Chores

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be αα-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most αα times her weighted maximin share. We establish that every instance admits a 4.1242345284.124234528-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a 4.124244.12424-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to ee. Together, our results substantially narrow the previously best-known gap of [2,12][2,12] established by Li et al.~\cite{LWX26} to [e,4.12424][e,4.12424].
Aug 26, 2026

Simultaneous Envy and Equitability Guarantees

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.