| paper | Temporal Fair Division of Indivisible Items |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.6
Given a finite set ϴ of complete valuation types with rational masses μθ, ∑θ μθ = 1, two indivisible good classes, and a known sequence of rational per-population supplies qᵣ,ᵍ for rounds r = 1,…,R, decide whether and construct temporally EF1 mass transitions xᵣ,θ,b,b′. Each household has an integer bundle b ∈ ℤ≥0², transitions preserve its valuation type and satisfy b′ ≥ b coordinatewise, mass is conserved, and ∑θ,b,b′ (b′g − bg)xᵣ,θ,b,b′ = qᵣ,ᵍ. After every prefix r, every pair of positive-mass states (θ,b) and (θ′,b′) must satisfy vθ·b ≥ minₙ:b′g>0 vθ·(b′−eₙ).
A finite intrinsic type set Θ carries valuation vectors and population masses μ; the evolving society is represented by masses νᵣθ,b over integer bundle states, with temporally consistent mass-flow variables xᵣθ,b,b′, exact supply constraints, and constructive TEF1 feasibility as the objective.
The effective bundle-state space can be exponential in the binary encoding of total supplies, and Theorem 3.6 does not prove a polynomial-size symbolic representation of the temporally consistent mass transitions or their TEF1 constraints.
fatal: False
The mirror covers the goods half of Theorem 3.6 for two item types. It leaves the chores half, the other restricted settings, the hardness results, Pareto-optimality variants, and general multi-type instances untreated.
The strongest honest positive case is a mirror of Theorem 3.6, proved in this paper:
“When there are two types of items, a TEF1 allocation for goods or chores exists and can be computed in polynomial time.”
I would use only the goods part as my anchor. I would not anchor the NP-hardness results: Theorems 3.11, 3.14, 4.3, 4.4, and 5.2 rely on a small number of named agents or on item-level integrality in ways that may disappear when agent mass becomes divisible.
My lead problem is Two-Type Temporal TEF1\(_\infty\).
Consider a large relief-distribution system serving millions of households. Goods arrive in a known sequence of deliveries, cannot be stored, and must be assigned immediately. There are only two catalogued good types, say food and clothing. Households fall into a small number \(\tau\) of complete valuation types: a type \(\theta\) is specified by \(v_{\theta,1},v_{\theta,2}\in\mathbb{Q}_{\ge0}\), where every food item is worth \(v_{\theta,1}\) and every clothing item is worth \(v_{\theta,2}\). The population is given by masses \(\mu_\theta\), with \(\sum_\theta\mu_\theta=1\) and \(\tau\ll N\), where \(N\) is the eventual number of households.
At round \(r\), let \(q_{r,g}\in\mathbb{Q}_{\ge0}\) be the number of goods of class \(g\) arriving per unit of population. The schedule is known in advance, but allocations are irrevocable. The input is therefore \((\Theta,\mu,v,(q_{r,1},q_{r,2})_{r=1}^R)\).
The population is continuous, but goods remain indivisible. To express this, let \(b=(b_1,b_2)\in\mathbb{Z}_{\ge0}^2\) be an individual household’s bundle. Let \(z^r_{\theta,b}\) be the mass of type-\(\theta\) households holding bundle \(b\) after round \(r\). The action variable is a transition mass \(x^r_{\theta,b,b'}\): the mass of type-\(\theta\) households whose bundle changes from \(b\) to \(b'\) at round \(r\), where \(b'\ge b\) coordinatewise. It must satisfy mass conservation and the supply equations \( \sum_{\theta,b,b'}(b'_g-b_g)x^r_{\theta,b,b'}=q_{r,g} \) for \(g\in\{1,2\}\). Thus a positive mass \(x^r_{\theta,b,b'}\) means that many whole households each receive the integer bundle increment \(b'-b\); it does not mean that an individual food item is fractionally allocated.
The TEF1 requirement is imposed on every prefix. For every round \(r\), every supported type-bundle pair \((\theta,b)\), and every supported \((\theta',b')\), we require
\(v_{\theta,1}b_1+v_{\theta,2}b_2\ge \min_{g:b'_g>0} v_\theta\cdot(b'-e_g)\).
If \(b'\) is empty, the condition is automatic. This is exactly the paper’s EF1 condition, applied to every pair of households, at every temporal prefix. A solution is a rational transition table \(x\) satisfying the supply, conservation, and TEF1 constraints. The objective is constructive feasibility: output a TEF1 allocation, not an average or an expected allocation.
This is a genuine high-multiplicity mirror. Given a common denominator \(N\), replace mass \(\mu_\theta\) by \(N\mu_\theta\) cloned households of type \(\theta\), and replace \(q_{r,g}\) by \(Nq_{r,g}\) indivisible goods. If \(x\) is rational, choose \(N\) large enough that every \(Nx^r_{\theta,b,b'}\) is integral. Then exactly \(Nx^r_{\theta,b,b'}\) cloned households make the transition \(b\to b'\). Conversely, every finite allocation aggregates to such a mass allocation. The dictionary is therefore exact on rational instances, rather than merely an analogy.
The scenario is recognizable as the authors’ problem: the same additive valuations, the same two item classes, the same known future, the same immediate and irrevocable assignment, and the same TEF1 condition. Only the irrelevant names of exchangeable households have been removed. The paper itself already motivates two-type goods by food and clothing distribution, so the population regime is not artificial.
I expect Class A. The proof of Theorem 3.6 allocates one item type in forward round-robin order and the other in reverse round-robin order. In the mirror, those cyclic operations can be performed on mass intervals using rational floor-and-remainder arithmetic, without expanding \(N\) cloned households. The main expected result is a polynomial-time compressed construction in \(\tau\), \(R\), and the encoding length of \(\mu\), \(v\), and \(q\). The two item types are doing real structural work: they prevent the general configuration/pricing explosion that would arise with many unrelated item classes.
The main further questions are whether one can prove a polynomial bound on the support of the transition table independent of the clone population \(N\); whether the construction remains efficient when per-round supplies are binary-encoded and very large; and whether the same approach extends to three or more item types, generalized binary valuations, or simultaneous TEF1 and Pareto optimality.
The weakest point is that Theorem 3.6’s published algorithm is stated for named finite agents, so its order-sensitive round-robin argument does not automatically yield a compact, order-free continuum algorithm. That compression theorem still has to be proved. Moreover, this is a modest Class A mirror: it shows that a natural high-multiplicity version remains tractable, rather than producing continuum-specific hardness or a dramatic change in complexity. But that is still a legitimate positive case. The population is the continuous object, indivisibility is preserved at the household level, and the paper’s central temporal fairness question survives intact.
The strongest negative case is that the proposed mirror is not actually a finite-type continuous society of the programme’s central kind. TEF1 is not determined by the population masses \(\mu_\theta\), or even by aggregate item totals. It is a pointwise condition on every household’s bundle at every prefix.
A faithful model therefore needs a measure \(\nu^r\) over \((\theta,b)\), where \(b\in\mathbb{Z}_{\ge 0}^2\) is the household’s current bundle, together with temporally consistent transitions. This is not a fixed type space: if \(Q_g=\sum_r q_{r,g}\), then there may be \((Q_1+1)(Q_2+1)\) possible bundle states and quadratically many transitions. With binary-encoded supplies, that is exponential in the input length. Aggregating bundles by utility does not solve the problem, since TEF1 depends on which item can be removed and on future coordinatewise increments.
Thus the displayed transition table is not a polynomial-size continuous formulation. It is a mass-indexed encoding of the original discrete allocation problem. To obtain a genuinely efficient mirror, one would need an additional symbolic representation—perhaps intervals, periodic patterns, or arithmetic progressions—and a proof that it preserves every pairwise TEF1 constraint at every temporal prefix. Theorem 3.6 does not provide that compression theorem. Its round-robin algorithm is stated over named agents, and translating it into a measurable, type-compressed schedule is precisely the new difficulty.
There is also a temporal scaling problem. If \(N\) clones are used to realize a mass solution, then either the \(N\) copies of each item arrive as one batch, in which case TEF1 is checked only after a much coarser event, or they arrive as \(N\) separate events, in which case the horizon grows by a factor of \(N\). The former changes the temporal problem; the latter defeats the claimed population-only compression. This is not merely a technical issue about strict inequalities or tie-breaking: temporal fairness is sensitive to the granularity of arrival events.
The proponent’s repair—continuum many households, each retaining an integer bundle, with mass flows between bundle states—is mathematically legitimate. It also gives an exact rational high-multiplicity dictionary. But that concession exposes the limit of the negative case: the relief-distribution scenario is genuinely plausible, the household type \((v_{\theta,1},v_{\theta,2})\) can be complete, and indivisibility can be preserved at household level. I therefore cannot honestly establish the universal claim that no worthwhile mirror exists. The defensible negative conclusion is narrower: Theorem 3.6 alone does not yet establish the proposed mirror as a compact continuous-computational problem; it identifies a potentially valuable high-multiplicity compression theorem that still has to be proved.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.