Skip to content
Preprint

Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings

Aug 2026 · 10 citations · 72 references
Computer Science

TL;DR

Although deciding whether a TEF1 allocation exists is NP-hard even for goods, this work identifies several tractable settings and gives an exact pseudo-polynomial algorithm for deciding TEF1 existence.

Abstract

We study temporal fair division of indivisible mixed manna. Items arrive over time and must be allocated irrevocably; an item may be a good for some agents, a chore for others, and neutral for the rest. We require the cumulative allocation after every round to be envy-free up to one item (TEF1). Although deciding whether a TEF1 allocation exists is NP-hard even for goods, we identify several tractable settings. First, with at most $k$ item types, an online cyclic rule guarantees EF$\lceil k/2\rceil$ after every item arrival. Thus, every instance with at most two types admits an online TEF1 allocation; moreover, when the numbers of agents and types are fixed, TEF1 existence can be decided in polynomial time. Second, under agreement after agent-specific scaling, provided that the scaling factors are known before arrivals begin, an online rule produces an allocation that is EF1 and Pareto optimal after every item arrival. Third, for a two-part arrival sequence with common rankings, we give a rule that is EF1 after every item arrival. Fourth, when the number of agents is fixed and values are bounded integers, we give an exact pseudo-polynomial algorithm for deciding TEF1 existence. Finally, for goods, every TEF1 allocation gives each agent at least $1/n$ of her maximin share after every round; this factor is tight even for identical valuations and two rounds. Deciding whether an exact temporal maximin-share allocation exists is NP-hard for both goods and chores, even with identical valuations, two agents, and two rounds.

View source

Similar papers

Preprint Oct 2026

Minimizing Cumulative Envy in Allocating a Sequence of Items

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: th...

Paul W. Goldberg, Isaac Robinson, Nicholas J. Teh · 7 citations
Preprint Sep 2026

Weighted Fair Division of Indivisible Mixed Manna

We study weighted fair division of indivisible mixed manna under additive valuations. First, we resolve the general existence open question for weighted envy-freeness up to one item (WEF1), and show that every instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time....

Nicholas J. Teh · 1 citation
Preprint Sep 2026

Closing Gaps in Online Fair Division

This work determines the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively, and improves when fewer agents value the same good, unlike uniform random allocation.

Tzeh Yuan Neoh, Nicholas J. Teh · 9 citations · ⚡2
Preprint Sep 2026

Online Fair Division: Pushing the Frontier of Approximate Proportionality

Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study determinist...

Ying-Jian Du, An-Kang Sun · 4 citations · ⚡1
Preprint Sep 2026

Reconfiguration in Fair Division Revisited

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1...

F. Frank, Warut Suksompong · 0 citations
Preprint Oct 2026

Online Fair Division under Eligibility Constraints

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties wi...

Joes Biburger, Nicole Megow, Golnoosh Shahkarami · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.