| paper | Fair Division of Time: Multi-layered Cake Cutting |
| authors | Hadi Hosseini, Ayumi Igarashi, Andrew Searns |
| venue | IJCAI 2020 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\) and dyadic input data. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given \(m=2^a\), a finite type set \(\Theta\) with masses \(\mu_\theta\), valuation densities \(v_{\theta j}\), and per-capita capacities \(\kappa_j(x)\), compute a finite mass allocation \(\{(w_{\theta r},B^{\theta r})\}\) such that \(\sum_r w_{\theta r}=\mu_\theta\), every \(B^{\theta r}\) is contiguous and non-overlapping across layers, \(\sum_{\theta,r}w_{\theta r}\mathbf 1[x\in B^{\theta r}_j]=\kappa_j(x)\) almost everywhere, and \(V_\theta(B^{\theta r})\ge p_\theta=\sum_j\int_0^1\kappa_j(x)v_{\theta j}(x)\,dx\) for every supported bundle.
Types \(\theta\) are complete valuation templates with masses \(\mu_\theta\); decision variables are masses \(w_{\theta r}\) assigned to integral contiguous bundle patterns \(B^{\theta r}\). The task is to construct a complete per-capita allocation satisfying capacity, non-overlap, contiguity, and type-wise proportionality constraints.
Theorem 7 supplies no finite representation or explicit complexity bound, so proving a polynomial-time weighted continuum algorithm would be new work.
fatal: False
The mirror covers the proportional, feasible, contiguous regime for \(m=2^a\) and \(n\ge m\) represented by Theorem 7; it leaves the envy-free results, non-contiguous proportionality, and explicit query bounds of other theorems unaddressed.
The strongest positive case is a population-continuum version of the paper’s proportionality theorem, with Theorem 7 as the lead anchor.
The relevant regime is a large cohort of agents sharing a small number of complete preference types. For example, there may be \(N\) medical professionals drawn from \(\tau\ll N\) preference templates over wards and time intervals. A type includes the entire valuation density \(v_{\theta j}(x)\) over every layer \(j\), together with every other parameter affecting feasibility or value. Agents of one type are interchangeable; the mass \(\mu_\theta\) is their fraction of the population.
The paper’s cake is already divisible, but that is continuity of the outcome space, not of the population. The proposed mirror continuizes the agents. Because a literal one-copy cake gives every agent vanishingly little resource in the limit, I would use the natural per-capita modification: let \(\kappa_j(x)\) be the amount of layer-\(j\) capacity available per unit population at position \(x\). The direct finite analogue has \(\kappa_j(x)=1/N\); a genuine high-multiplicity application can instead have a fixed per-capita supply, represented physically by repeated identical shifts, rooms, or facility slots.
The named anchor is Theorem 7, proved in this paper:
For every number of layers \(m\) and agents \(n\ge m\), when \(m=2^a\) for some \(a\in\mathbb Z^+\), there exists a complete multi-allocation that is proportional, feasible, and contiguous.
In full, “complete” means that every layer is allocated; “proportional” means every agent receives value at least \(1/n\) of the value of the entire cake; “feasible” means that no agent receives overlapping pieces from distinct layers; and “contiguous” means that the piece allocated to each agent on each layer is an interval. This is a result proved by the authors, via the recursive constructions behind Theorems 5 and 6. Theorem 7 itself does not state a query-complexity bound, so it is an existence/constructibility anchor rather than a claimed polynomial-time theorem.
I would name the continuous problem Per-Capita Proportional Multi-Layer Allocation\(_\infty\).
An instance consists of:
An integral bundle is \(B=(B_1,\ldots,B_m)\), where every \(B_j\) is empty or a contiguous interval and \(B_j\cap B_{j'}=\varnothing\) for \(j\ne j'\). Its value to type \(\theta\) is
\[ V_\theta(B)=\sum_{j=1}^m\int_{B_j}v_{\theta j}(x)\,dx. \]
The per-capita proportional benchmark for type \(\theta\) is the value of its share of the available cake,
\[ p_\theta=\sum_{j=1}^m\int_0^1\kappa_j(x)v_{\theta j}(x)\,dx. \]
A solution is a finite mass allocation \(\{(w_{\theta r},B^{\theta r})\}\) such that
\[ \sum_r w_{\theta r}=\mu_\theta \]
for every type, every supported bundle \(B^{\theta r}\) is integral and satisfies
\[ V_\theta(B^{\theta r})\ge p_\theta, \]
and the resource is completely allocated:
\[ \sum_{\theta,r}w_{\theta r}\, \mathbf 1[x\in B^{\theta r}_j] =\kappa_j(x) \]
for every layer \(j\), almost everywhere.
The weights \(w_{\theta r}\) are fractions of a type population, not fractional bundles. Every infinitesimal agent receives an integral contiguous, non-overlapping bundle; only the type-level average is fractional. That distinction is exactly the high-multiplicity interpretation of the paper’s named-agent allocation.
This is recognisably the authors’ problem. It preserves the objects that matter in their model—layered time, additive valuations, contiguity, completeness, and the non-overlap constraint—while replacing a long list of named professionals by masses of interchangeable professionals. If \(\mu_\theta=n_\theta/N\) and \(\kappa_j=1/N\), an ordinary \(N\)-agent allocation induces this formulation by giving each agent mass \(1/N\). Conversely, rational mass allocations can be expanded into large finite populations, with rounding error controlled by the population size. With fixed \(\kappa\), the interpretation is a repeated-shift or parallel-capacity version of the same scheduling problem, which is the natural co-modification when population size grows.
I would expect this mirror to be Class A. The proof strategy of Theorem 7 is unusually compatible with masses. Its recursive ingredients are a switching point, a partition of the agents into two equally sized preference sides, and a merge operation preserving feasibility and contiguity. In the continuum, “equally sized” becomes equal mass, and agents tied at a switching point can be split within their type. The number of named agents disappears; the remaining input is the finite type profile and the valuation-query structure. A plausible algorithm would recursively find weighted switching points, split type masses, merge diagonal pieces, and return a finite mixture of integral bundles.
The main further questions are computational rather than merely existential: whether the recursive construction has polynomial query complexity in \(m\), \(\tau=|\Theta|\), and the encoding length; whether a polynomial-size finite mixture always suffices; how to round the continuous solution back to a finite population; and whether the restriction \(m=2^a\) is a proof artefact or a genuine boundary. The paper’s Theorem 6 suggests a second direction: perhaps arbitrary products \(2^a3^b\) remain tractable once contiguity is relaxed, while the continuous analogue of contiguity for other \(m\) may expose a real obstruction.
The weakest point is that this is not a literal limit of the paper’s single-copy cake unless one allows the per-capita capacity modification. With one physical copy of each layer and a genuinely nonatomic population, individual bundles collapse and proportionality becomes vacuous. Moreover, Theorem 7 supplies no hardness result and no explicit polynomial-time bound. Thus the case is not that the paper already contains a continuous-complexity theorem; it is that its strongest structural result appears to survive the high-multiplicity transformation in a precise, application-level model. The paper contains no named NP-hardness anchor to support a “discrete hardness dissolves” claim, so this positive case rests on the plausibility and tractability of the continuous mirror rather than on a hardness separation.
The strongest negative case is that the proposed anchor is not a computational result. Theorem 7 is an existence theorem: it gives no finite encoding, running-time bound, approximation guarantee, or parameterized complexity statement. Its “constructive” proof is not an algorithmic result in the sense ChoCo is meant to study. Thus \(\mathrm{Per\text{-}Capita\ Proportional\ Multi\text{-}Layer\ Allocation}_\infty\) would add a new computational problem around the theorem, rather than mirror one of the paper’s computational claims.
The literal population limit also degenerates. With one copy of each layer and \(N\) agents, the empirical continuum has \(\kappa_j(x)=1/N\). If total population mass is normalized to one, then
\[ \sum_{\theta,r} w_{\theta r}\sum_j |B_j^{\theta r}| = \sum_j\int_0^1\kappa_j(x)\,dx = \frac{m}{N}. \]
Hence the average amount of cake assigned per agent tends to zero, as does the proportional benchmark \(1/N\). The limiting society has no nonzero per-capita resource and no nontrivial proportionality requirement. This is a genuine collapse of the object, not merely a technical issue about strict inequalities or tie-breaking.
The proposed repair—holding \(\kappa\) fixed—is defensible, but it changes the resource economy. It amounts to introducing a number of parallel copies of every layer that grows linearly with the population. That may be a sensible scheduling model, but it is not the high-multiplicity limit of the paper’s single-copy cake. The benchmark \(p_\theta\), the capacity equation, and the scarcity structure are all newly defined. Theorem 7 does not establish this model; one would need a new existence and computational theory for it.
Nor does the population continuum create a new source of combinatorial structure here. Once a type includes its complete valuation density, masses merely replace counts in the paper’s switching-point arguments. “Split a tied type at the switching point” is a weighted restatement of the finite proof. The paper’s substantive difficulty is the interaction between interval contiguity, layer non-overlap, and valuation geometry—already continuous in the cake coordinate—not population multiplicity.
A better computational anchor fares little better. Theorem 1, Theorem 3, and Lemma 6 have Robertson–Webb query bounds, but their main cases concern two or three agents or identical valuations; those are not high-multiplicity regimes. Theorem 7 is the only plausible large-\(n\) anchor, and it lacks the required complexity statement. To obtain a genuine computational problem one must add objectives such as minimizing cuts, handle finite encodings of valuation densities, or study arbitrary numbers of layers. Those could be worthwhile new projects, but their interest comes from newly added optimization and representation choices, not from continuizing this paper’s population.
I would therefore reject the proposed mirror as a strong ChoCo case: it is a sensible weighted extension of a fair-division existence theorem, but not a computational mirror with a clear complexity landscape. The universal claim is not airtight, however. If ChoCo is willing to treat the replicated-capacity scheduling model and a newly specified finite representation as sufficient co-modifications, then a legitimate continuous-population problem can be built. The honest negative conclusion is consequently that this paper supplies a weak and poorly computationally anchored candidate—not that every conceivable high-multiplicity reformulation is meaningless.
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.