| paper | Temporal Fair Division |
| authors | Benjamin Cookson, Soroush Ebadian, Nisarg Shah |
| venue | AAAI 2025 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 9
statement extracted from the paper’s text layer
Given rational masses of complete agent types, k identical days with rational per-capita supplies of finitely many indivisible good categories, and type rankings/values respecting the identical-days condition, output a finite-support rational census x over integral bundle histories whose row masses equal the type masses and whose aggregate supplies equal the per-capita supplies, such that every supported pair of histories satisfies SD-EF1 on every day and every supported type-history satisfies the per-capita clone version of SD-PROP1 overall.
A typed high-multiplicity temporal fair-division model: type mass is continuous, goods remain indivisible, per-capita supplies scale with population, and decision variables assign population mass to integral bundle histories subject to aggregate supply and support-wise fairness constraints.
Theorem 9's expanded-instance algorithm does not establish a polynomial algorithm or polynomial-support census in the compressed encoding by type masses and per-capita supplies.
fatal: False
The mirror covers the algorithmic possibility results Theorems 9 and 7 in repeated-good and common-ordering regimes; it leaves Theorem 1, Theorems 3–6, Theorem 8, and the paper's open questions untreated.
There is a credible positive case, but it is a high-multiplicity extension rather than the literal substitution \(n=\infty\). My strongest anchor is the paper’s repeated-goods result.
The mirror I would use is a typed, high-multiplicity version of temporal fair division. There is a finite set \(T\) of complete preference/value types, with rational masses \(\mu_t\) summing to one. On day \(d\), there are finitely many good categories \(G_d\), with \(q_{d,g}\) indivisible copies per unit population. Thus a finite realization with \(N\) agents has \(N\mu_t\) agents of type \(t\) and \(Nq_{d,g}\) copies of good \(g\). The number of agents and the supply of goods scale together; goods themselves remain indivisible.
An individual receives an integral bundle history \(h=(b_1,\ldots,b_k)\), where each \(b_d\) is an integer multiset of day-\(d\) goods. The continuous action is a rational mass \(x_{t,h}\): the fraction of type \(t\) receiving history \(h\). It must satisfy
\[ \sum_h x_{t,h}=\mu_t,\qquad \sum_{t,h}x_{t,h}b_{d,g}=q_{d,g}. \]
This is not fractional allocation to an individual. It is only a compressed census of discrete bundle assignments. Clearing denominators gives an ordinary finite temporal-fair-division instance.
The fairness constraints are imposed support-wise. Whenever \(x_{t,h}>0\) and \(x_{u,h'}>0\), the bundle \(b_d\) must be SD-EF1 relative to \(b'_d\) under type \(t\)’s ranking, for every day \(d\). Thus every individual represented in the continuum has exactly the pairwise guarantee required in the paper.
For SD-PROP1, the natural high-multiplicity normalization is also exact. If \(H\) is a top-ranked prefix of the total goods and \(Q_t(H)\) is its supply per population unit, then a type-\(t\) bundle \(b\) must, after adding one available good \(g\), contain at least \(\lceil Q_t(H)\rceil\) goods from \(H\). In an \(N\)-agent clone this is precisely
\[ \left\lceil\frac{|H|}{N}\right\rceil = \lceil Q_t(H)\rceil. \]
So the “one good” remains one indivisible good, while the proportional target is normalized per capita.
The lead anchor is Theorem 9, which states:
“For any temporal fair division instance with identical days, it is possible to find an allocation that is SD-EF1 per day and SD-PROP1 overall in polynomial time.”
This is a result proved by the authors; the short paper places the detailed proof in the full version. My continuous problem is:
Temporal Identical-Day SD-EF1/SD-PROP1\(_\infty\). Given rational type masses \(\mu\), a finite set of recurring good categories, rational per-capita daily supplies \(q_g\), and type rankings/values satisfying the paper’s identical-days condition, output a finite-support rational census \(x_{t,h}\) of integral bundle histories such that:
The objective is constructive feasibility: output the allocation census, not merely decide that one exists.
This is a plausible Class A problem. The paper’s identical-days proof already exploits the fact that the daily and global rank structures can be aligned. In the high-multiplicity version, the natural algorithmic question is whether those structures can be represented by a polynomial-size flow, configuration LP, or column-generation formulation whose complexity depends on \(|T|\), \(k\), the number of good categories, and the encoding length of the masses—not on the number \(N\) of cloned agents. The source theorem supplies strong evidence that the combinatorial structure is tractable; it does not itself supply the compressed algorithm.
The scenario is quite natural. Consider a large food-bank or workplace-meal programme serving millions of households over thirty days. Each day has the same menu categories, and households fall into perhaps twenty or fifty recurring preference types. There are millions of recipients but only a small number of distinct preference profiles; daily food packages remain indivisible. The paper’s “identical days” restriction is exactly the structural assumption in this story. The continuous formulation records how much of each preference cohort receives each discrete bundle history, while preserving both per-day and end-of-horizon fairness.
A second, cleaner anchor is Theorem 7, also proved by the authors:
“For temporal fair division with identical orderings, an allocation that is SD-EF1 per day and SD-EF1 overall exists and can be computed in polynomial time.”
The corresponding problem is Common-Ordering Temporal SD-EF1\(_\infty\). It has the same typed population and integral bundle-history representation, but all types induce the same ordering over goods. The required output is an \(x\) satisfying SD-EF1 both separately on every day and on the total allocation.
This is an even stronger Class A candidate. The paper’s proof uses the two rank-block systems \(P_1\) and \(P_2\), one for daily prefixes and one for global prefixes. In the high-multiplicity formulation those become constraints on rank mass, while individual bundle contents remain integral. A compact flow or block-structured allocation algorithm should plausibly produce the required census. The regime could be a large workforce whose members agree on the ordinal desirability of shifts or meal categories but differ in cardinal intensity; for the SD-EF1 problem, those agents are behaviourally equivalent with respect to the relevant type description.
I would not anchor on Theorems 3–5. Their central setting has exactly two agents, which is a poor population-continuum regime. Nor would I use Theorem 2 as an anchor: it is explicitly cited from Biswas and Barman rather than proved as this paper’s result. The general Theorem 1 is also a promising future target, but I would not rely on it here because compressing its heterogeneous daily preferences into a polynomial-size high-multiplicity algorithm raises a less settled configuration/separation question.
The strongest point for the case is rational-clone fidelity. Given a rational \(x\), clearing denominators produces \(N\) cloned agents and \(Nq_g\) named copies of every good category. Assigning \(Nx_{t,h}\) clones to history \(h\) recovers an ordinary allocation with exactly the paper’s fairness predicates. Conversely, every finite allocation induces such a mass census. This is the right kind of high-multiplicity bridge, rather than merely replacing utilities by probabilities.
The weakest point is that scaling the supply of indivisible goods with the population is essential. If the paper’s fixed finite set of goods is held constant while \(N\) grows, most agents receive nothing and the fairness notions become degenerate. If instead goods are made divisible, the problem becomes fractional fair division and is no longer the paper’s problem. The proposed mirror therefore needs the authors to accept a joint population/resource scaling convention and a support-wise integral configuration model. I regard that as an author-recognizable high-multiplicity extension, but not as an automatic theorem of the paper.
The further questions are substantive: whether Theorem 9 admits a polynomial compressed algorithm; whether the necessary allocation census has polynomial support; whether the same holds for the paper’s open general-setting question; and whether the impossibility in Theorem 8 for SD-EF1 up to each day survives unchanged under this continuum representation. Thus this paper offers a credible Class A mirror, with Theorem 9 as the lead and Theorem 7 as a particularly clean supporting case.
The strongest negative case is that the proposed mirror is not actually a population continuization. It is a joint high-multiplicity model of agents and goods, followed by a distribution over complete integral allocation histories.
If the paper’s goods remain fixed while the number of agents tends to infinity, the model degenerates. Only finitely many agents can receive goods, while almost everyone receives nothing. EF1 can be satisfied by spreading the finitely many goods among distinct agents, and PROP1 becomes an essentially vacuous one-good correction. The temporal structure likewise disappears. Thus a population-only limit does not preserve the paper’s object.
The proponent avoids that degeneration by scaling the goods as well: \(Nq_g\) copies for \(N\) agents. That is a sensible model, but it is no longer the paper’s population continuization. It introduces a second high-multiplicity resource system. More importantly, the continuous variable is not the society mass \(\mu\); it is \(x_{t,h}\), a distribution over integral bundle histories. The masses merely provide row capacities. The substantive problem is a configuration or random-assignment problem over discrete outcomes, which belongs to outcome-space continuity and high-multiplicity allocation rather than to ChoCo’s population-as-continuous-object programme.
This is not repaired by support-wise EF1. Support-wise constraints are necessary to preserve the paper’s individual guarantee, but they make the proposed object discontinuous in exactly the wrong way: an arbitrarily small positive mass assigned to a bundle affects every pairwise fairness constraint, while zero mass makes that bundle disappear entirely. Aggregate or expected fairness would produce a genuinely fractional continuous problem, but it would no longer mirror SD-EF1 or SD-PROP1. Preserving ex-post indivisibility instead leaves a discrete assignment problem encoded by a census.
Theorem 7 is especially weak as an anchor. Its hypothesis gives all agents the same ordering, and SD-EF1 depends only on those orderings. Cardinal differences between agents are irrelevant. For the theorem’s purpose the population therefore collapses to a single relevant type. The \(P_1/P_2\) construction balances rank blocks of goods; it does not exploit a continuous society. Its proposed mirror is consequently a continuous allocation of goods, not a continuous population model.
Theorem 9 is the serious case. A repeated-menu programme with many recurring household types is genuinely plausible, and the proponent’s cloning correspondence is mathematically coherent. But it works only after accepting the joint scaling of resources and the allocation-history census. That may be a worthwhile separate high-multiplicity fair-division project, but it is not evidence that this paper has a population-continuous mirror in the stated ChoCo sense. The theorem itself supplies no compressed algorithm in the encoding of type masses and per-capita supplies; it supplies an algorithm for the expanded named-agent, named-good instance. The proposed configuration formulation is a new problem whose tractability and even polynomial-support representation remain open.
This negative case has an important limitation: if ChoCo is willing to broaden its scope to joint high multiplicity of agents and indivisible resources, then Theorem 9 survives as a credible mirror, and the food-bank example is a good one. I cannot honestly claim that scenario is nonsensical. The defensible conclusion is narrower: under the programme’s population-only notion of continuization, Theorem 7 collapses to goods balancing, while Theorem 9 requires a different, joint resource-and-outcome continuization.
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.