An arXiv preprint finds that fair allocation can be maintained as indivisible items arrive in some structured cases. With at most two item types, an online cyclic rule provides temporal EF1, or TEF1, after every item arrival. For additive goods, TEF1 guarantees 1/n-TMMS, and a two-round construction rules out every factor α in (1/n, 1].
The study works with formal temporal-fair-division instances involving n agents, T rounds and items arriving in round t. It asks when TEF1 allocations exist and can be found efficiently, when TEF1 can coexist with Pareto optimality, and what temporal maximin-share guarantees are possible.
What can be done as items arrive
To address those questions, the paper develops three allocation rules for mixed manna, two algorithms for deciding TEF1 existence, and two results on temporal maximin-share fairness.
With at most k item types, the online cyclic rule guarantees EF⌈k/2⌉ after every arrival. When there are at most two types, that becomes an online TEF1 allocation.
Another online rule combines EF1 with Pareto optimality under agreement after agent-specific scaling, provided the scaling factors are known before arrivals begin. It guarantees both properties after every item arrival.
For rational valuations, a valid scale vector can be found in O(mn²) arithmetic operations when one exists. The same online EF1-and-Pareto-optimal guarantee covers scaled ternary and proportional valuations.
The paper also handles every two-part common-ranking sequence. Once a valid split and the relevant set PG are known from the full sequence, a polynomial-time rule gives EF1 after every item arrival. Because that information must be known before the first assignment, the rule is not online.
For fixed n and k, a dynamic program decides TEF1 existence for instances with at most k item types and returns an allocation when one exists. A separate procedure handles fixed n and integer values bounded by |vᵢ(o)| ≤ U in time polynomial in the number of items, rounds and U; if U is written in binary, its running time is pseudo-polynomial.
The ceiling on temporal maximin share
The sharpest boundary concerns additive goods. Every TEF1 allocation is 1/n-TMMS; for every n ≥ 2 and every α in (1/n, 1], a two-round identical-valuation goods instance can have a TEF1 allocation but no α-TMMS allocation. The 1/n factor is therefore tight in this setting.
Exact TMMS existence is also computationally hard: deciding it is NP-hard even with two agents, two rounds and identical valuations, for both goods and chores.
Allowing a looser condition, TEFℓ with ℓ ≥ 2, does not restore a general TMMS guarantee. In the formal worst case, it provides no positive TMMS factor.
Useful results with strict conditions
The positive results are conditional on structured settings such as few item types, agreement after scaling, common rankings or bounded integer values. The scaling factors must be known before arrivals; the common-ranking rule requires advance knowledge of the split and PG and is therefore not online; and the bounded-integer method is pseudo-polynomial when U is encoded in binary.
Taken together, the preprint gives constructive TEF1 guarantees in several restricted cases while placing formal limits on stronger temporal fairness and exact TMMS guarantees. Its 1/n TMMS result is for additive goods, and exact TMMS remains NP-hard even in the two-agent, two-round case.
Paper data and sources
Original title: Temporal Fair Division of Indivisible Mixed Manna: Tractable Settings
Authors: Kui-Wang Choi, Minming Li, Nicholas Teh
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text