How to Cut a Discrete Cake Fairly

The three relevant numbered theorems assert existence only, while the paper explicitly leaves the complexity of finding an EF1 connected division open, so bit (a) fails. The proposed mass-matching formulation is statable but permits fractional sharing of bundle slots or requires repeated paths, changing the paper's one-path indivisible allocation. The opponent therefore wins the strict triage decision.

The objection that survived

The mass assignment allows positive fractions of distinct agents to share one indivisible bundle, while avoiding that requires multiple replicated paths and hence a different resource model.

What the mirror covers

The proposal targets ordinary EF1outer existence from Theorem 3.1; it does not faithfully cover the secretive or extra variants in Theorems 4.1 and 4.2.

Open questions for a prover

The case FOR (proponent)

The strongest honest case is necessarily a near-miss: this paper has no eligible computational anchor. Its named results are Theorem 3.1, Theorem 4.1, and Theorem 4.2, all proved here, but all are existential. The paper explicitly leaves “the complexity of finding an EF1 connected division” open. Algorithm 1 is only a rounding component, with no polynomial-time bound, and Theorem 2.2 is the cited standard Sperner lemma. Thus I would not present any theorem here as proving P, NP-hardness, FPT, or similar.

The best positive mirror is nevertheless the following.

Call it Mass-EF1outer Path Division∞. An instance consists of a path of \(m\) indivisible items, an integer \(q\le m\) denoting the number of connected bundle positions, a finite set \(T\) of valuation types, and a population distribution \(\mu\in\Delta(T)\). Each type \(t\) has a monotone valuation \(v_t([a,b])\) for every interval, represented explicitly by rational values. Define

\[ v_t^{-}(I)= \begin{cases} 0,&I=\varnothing,\\ \min\{v_t(I\setminus\{\ell\}),v_t(I\setminus\{r\})\},&I=[\ell,r]. \end{cases} \]

The output is a cut vector \(0=p_0\le p_1\le\cdots\le p_q=m\), giving whole-item connected bundles \(I_j=[p_{j-1}+1,p_j]\), together with a mass-assignment matrix \(y_{t,j}\ge0\). It must satisfy

\[ \sum_j y_{t,j}=\mu_t,\qquad \sum_t y_{t,j}=1/q, \]

and, whenever \(y_{t,j}>0\),

\[ v_t(I_j)\ge v_t^{-}(I_k) \quad\text{for every bundle }k. \]

So every positive mass of type \(t\) assigned to bundle \(j\) regards that bundle as EF1outer relative to every other bundle. The problem is to find such cuts and such a mass assignment, or report that none exists. This is a feasibility/search problem, matching the paper’s existential objective rather than adding an unrelated welfare objective.

The natural regime is a large population of researchers, employees, or advertisers using many repeated copies of an ordered schedule or broadcast calendar. Agents have one of a small number of complete valuation types—identical preferences over contiguous time blocks—and \(\mu_t\) records the fraction of the population of each type. The path and its items remain discrete; only the population-to-bundle assignment is represented by mass. For rational \(\mu\), this is exactly the normalized high-multiplicity representation of many agents sharing valuation tables.

This is recognisably the authors’ question: their own motivating example is scheduling meeting slots, and the mirror preserves monotonicity, contiguity, whole items, and EF1outer. For a fixed division, the \(y\)-part is a capacitated bipartite-flow problem, so continuization genuinely replaces an individual matching problem by a mass-assignment problem.

The lead anchor would therefore be the near-anchor Theorem 3.1, proved here: every finite population with monotone valuations admits a connected EF1outer division. The corresponding continuous question asks whether the same existence phenomenon survives for arbitrary population masses, and whether a division and mass assignment can be computed efficiently from the type description.

My expectation is mixed. The assignment subproblem is tractable once the cuts are fixed, and fixed-parameter or bounded-\(q\) variants look like plausible Class A targets. But choosing the cut positions remains a discrete segmentation problem; population continuization does not automatically remove that combinatorics. For unrestricted \(q\), I would regard this as an open Class-C candidate rather than claim either transferred hardness or a polynomial algorithm.

Theorem 4.1 and Theorem 4.2 suggest further questions but are not good anchors. Deleting one secretive or extra individual has zero effect in an atomless population, making the literal continuum versions vacuous. A meaningful mirror would have to delete a positive-mass secretive or extra cohort, which is a new robustness problem rather than a direct translation. One should also ask whether continuous solutions can be rounded to \(N\)-agent assignments while preserving EF1outer exactly or with a controlled additive loss.

The weakest point is fundamental: a single indivisible path cannot literally serve an atomless population. The model therefore needs a repeated-calendar or high-multiplicity interpretation, and the mass assignment \(y\) can look like fractional sharing of bundle roles. A referee could reasonably say that this changes the one-shot fair-division problem. My defence is that the path itself is not fractionalized and the repeated-schedule interpretation is natural, but I would not hide that this is a substantial modelling commitment.

So the honest assessment is: a credible continuous population problem exists, with Theorem 3.1 as its strongest near-anchor, but the paper fails ChoCo’s strict named-computational-result gate.

The case AGAINST (opponent, writing after the proponent)

The paper fails the programme’s anchor test before the modelling debate begins. Theorem 3.1, Theorem 4.1, and Theorem 4.2 are existential fairness results, not complexity results, algorithms, approximation theorems, or parameterized classifications. Algorithm 1 is only a proof component; no running time or computational guarantee is claimed. The paper explicitly identifies “the complexity of finding an EF1 connected division” as open. Thus the proposed Mass-EF1outer problem is not a continuous mirror of a named computational result. It is a new computational problem inspired by an existential theorem.

The proposed mirror also changes the central object in a more serious way than the proponent admits. In the paper, a path is divided into exactly \(n\) indivisible bundles, and a bijection assigns those bundles to \(n\) individual agents. In Mass-EF1outer, each bundle receives mass \(1/q\) through the matrix \(y\). A positive mass of distinct agents can therefore be assigned the same indivisible bundle. That is not merely replacing named agents by a distribution: it makes bundle slots fractionally shareable.

The repeated-calendar interpretation repairs physical feasibility only by changing the problem. One must supply many copies of the entire path, allocate one bundle per agent on each copy, and then aggregate assignments across copies. The result is a common segmentation of many independent cakes, or a fractional transport problem over bundle roles. It is not the one-shot connected division studied in the paper. If one insists on a single path and indivisible goods, population mass cannot become atomless: only finitely many agents can receive bundles. If one scales the number of agents, the number of bundles and hence the path length must scale too. If one keeps the path fixed, the high-multiplicity regime simply does not exist.

The rationality observation does not close this gap. When \(q\mu_t\) is integral, multiplying the proposed masses by \(q\) gives \(q\) agent slots and \(q\) bundles. That is a finite \(q\)-agent instance, not a replication of a fixed discrete-cake instance. Replicating the original instance by a factor \(r\) would produce \(rn\) agents and require \(rn\) bundles, which the same path generally cannot provide. Repeated copies are therefore a new resource model, not the high-multiplicity relaxation of the paper’s model.

Theorem 4.1 is even less suitable. A secretive individual has vanishing population mass in the continuum, so deleting that individual cannot affect a mass assignment. The fact that the individual chooses an entire bundle creates the opposite mismatch: the agent has zero mass but removes a positive bundle slot. To make the question nonvacuous one must delete a positive-mass secretive cohort and specify how bundle capacities change. That is a robust cohort-departure problem, not a continuization of “one secretive agent.” The same objection applies to Theorem 4.2: an extra individual disappears in the atomless limit, while a positive-mass departing cohort is a new model.

It would be wrong to object that repeated valuation types are inherently implausible. A population of researchers or advertisers with identical valuation tables is a legitimate high-multiplicity regime. The problem is that, for this paper, repeated types do not by themselves produce a continuous version of the allocation problem. They require either fractional sharing of indivisible bundles or many replicated paths. The former is outcome-side fractionalization; the latter is a new repeated-resource problem. Neither preserves the paper’s central one-path, one-bundle-per-agent structure.

The honest negative conclusion is therefore strong as a ChoCo triage decision: there is no named computational result here to mirror, and the most natural proposed mirror is not a population continuization of the paper’s problem. The literal universal claim is less airtight than the strict verdict: a repeated-calendar mass-matching problem could be a reasonable independent project. But it would not be justified as a worthwhile continuous mirror of this paper, and the paper itself supplies no computational theorem that would make such a project a ChoCo priority.

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.