| paper | Mind the Gap: Cake Cutting With Separation |
| authors | Edith Elkind, Erel Segal-Halevi, Warut Suksompong |
| venue | AAAI 2021 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 3.11
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), rational separation intensity \(\sigma\), and rational piecewise-constant densities \(f_t\) on \([0,1]\), define \(q_t=\sup_p\operatorname*{ess\,inf}_{z\in[0,1]} f_t(X_p(z))p(z)\), where the supremum ranges over measurable \(p\ge0\) with \(X_p(z)=\int_0^z(p(u)+\sigma)\,du\) and \(\int_0^1(p(z)+\sigma)\,dz\le1\). Decide whether there exist a measurable type order \(\theta\) and piece-length profile \(p\) with \(\operatorname{Leb}\{z:\theta(z)=t\}=\mu_t\) and \(f_{\theta(z)}(X_p(z))p(z)\ge q_{\theta(z)}\) almost everywhere; more generally, compute the maximum \(\rho\) after replacing the right side by \(\rho q_{\theta(z)}\), with a finite cell-and-boundary encoding of the schedule and gaps.
A finite-type, nonstrategic fluid cake-allocation model with type masses \(\mu_t\), per-capita separation \(s_n=\sigma/n\), connected infinitesimal pieces of rescaled length \(p(z)\), and objective \(\rho\) maximizing the minimum rescaled value \(f_{\theta(z)}(X(z))p(z)/q_{\theta(z)}\). The continuum retains individual bundles and separation through \(X'(z)=p(z)+\sigma\); it does not replace agents by average bundles.
The proposed cell inequalities omit explicit bookkeeping for separation gaps crossing valuation-cell boundaries, and the case supplies no formal convergence theorem connecting finite \(n\)-agent MMS with the fluid benchmarks \(q_t\).
fatal: False
The mirror covers the explicit-input cake branch: Theorem 3.10's exact benchmark computation, Theorem 3.1's allocation procedure, and Corollary 3.11's polynomial-time MMS-fair allocation. It leaves Robertson–Webb impossibility and query bounds, pie cutting, envy-freeness, equitability, and purely existential topological results outside the mirror.
My lead mirror is a high-multiplicity version of the paper’s explicit piecewise-constant cake-cutting problem.
The anchor is Corollary 3.11, proved in this paper. It states that, when agents have piecewise-constant valuations given explicitly by rational breakpoints and rational densities encoded in binary, an allocation in which every agent \(i\) receives value at least \(\mathrm{MMS}^{n,s}_i\) can be computed in polynomial time. The corollary follows from the paper’s Theorem 3.10, which computes an individual agent’s maximin share in polynomial time, and Theorem 3.1, which constructs an MMS-fair allocation once the benchmarks are known.
The natural high-multiplicity setting is a large market of vendors or jobs competing for locations on a long street or time horizon. There are \(n\) agents but only finitely many complete types \(T\), with \(n\gg |T|\). A type \(t\) specifies the entire piecewise-constant valuation density \(f_t\); agents of the same type are indistinguishable. The population is represented by \(\mu_t\), the fraction of agents of type \(t\).
A fixed physical safety gap is compatible with this regime if the cake is normalized by the size of the market. Thus the finite \(n\)-agent instance uses separation \(s_n=\sigma/n\), where \(\sigma\) is the total normalized separation intensity. This scaling is necessary: with fixed positive \(s\), a unit cake cannot accommodate arbitrarily many separated agents.
The continuous problem I would ask is:
Fluid MMS-Fair Allocation with Separation. Given a finite type set \(T\), a distribution \(\mu\), a separation intensity \(\sigma\), and explicit densities \(f_t\), compute a continuum allocation maximizing \(\lambda\), where almost every unit of population of type \(t\) receives a connected infinitesimal piece whose rescaled value is at least \(\lambda q_t\). Here \(q_t\) is the type’s continuum maximin benchmark,
\[
q_t=\sup_{p}\operatorname*{ess\,inf}_{z\in[0,1]}
f_t(X_p(z))p(z),
\]
where \(p(z)\) is the scaled length assigned to the agent at population position \(z\), and
\[
X_p(z)=\int_0^z(p(u)+\sigma)\,du,
\qquad
\int_0^1(p(u)+\sigma)\,du\le 1.
\]
The type assignment \(\theta(z)\) must satisfy
\[
\lambda\bigl(\{z:\theta(z)=t\}\bigr)=\mu_t.
\]
The decision version asks whether \(\lambda\ge1\); a solution is the type assignment and the corresponding ordered micro-schedule.
This is not an average bundle given to a type. Each infinitesimal agent receives its own connected piece; \(f_t(X_p(z))p(z)\) is the limiting per-agent value after multiplying the finite agent’s value by \(n\). A finite instance with \(n_t\approx n\mu_t\) clones of each type, pieces of length \(p(z)/n\), and gaps \(\sigma/n\), is the natural discretization. Conversely, bounded finite allocations have fluid subsequences. Thus the bridge is genuinely two-way.
For explicit piecewise-constant densities, the problem has a finite cell description. If \(I_j\) is a common breakpoint interval and \(f_{tj}\) is type \(t\)’s density there, let \(y_{tj}\) be the mass of type \(t\) placed in \(I_j\). At guarantee level \(\lambda\), that mass requires physical length
\[
y_{tj}\left(\sigma+\frac{\lambda q_t}{f_{tj}}\right).
\]
Hence the core feasibility constraints are
\[
\sum_j y_{tj}=\mu_t
\]
and
\[
\sum_t y_{tj}\left(\sigma+\frac{\lambda q_t}{f_{tj}}\right)\le |I_j|
\]
for every cell \(I_j\), with the usual convention that a cell with \(f_{tj}=0\) cannot serve positive benchmark mass. This is the fluid analogue of the paper’s LP-based computation of maximin partitions.
I would expect this mirror to be Class A: tractable. The population multiplicity disappears into the variables \(y_{tj}\), while all genuine combinatorics remain in the finitely many valuation cells and types. The original authors should recognize it as their problem: the cake remains an interval, every individual receives one connected piece, separation remains present, and the fairness target is still maximin share. Only the population representation changes.
This mirror deliberately covers the paper’s explicit-input branch, especially Corollary 3.11 and the machinery of Theorem 3.10. I would not use Theorem 3.2 or Theorem 5.8 as anchors here: their “no finite algorithm” conclusions concern Robertson–Webb oracle access, even with only two agents, rather than finite-input complexity. The paper contains no ordinary NP-hardness anchor.
The weakest point is the scaling \(s_n=\sigma/n\) and the need to rescale utility by \(n\). That is a genuine modelling choice, not a theorem in the paper. If fixed physical separation is non-negotiable, there is no meaningful high-multiplicity limit on a fixed cake. But under the programme’s permitted per-capita rescaling, this is a natural fluid limit rather than a change of subject. It also raises worthwhile follow-up questions: whether the Class A formulation extends to piecewise-linear densities, whether exact output can be obtained with rational data, and what survives under Robertson–Webb oracle access.
I cannot make a convincing universal negative case against this anchor. The proponent has identified a genuine high-multiplicity regime, and Corollary 3.11 is an explicit computational result that survives population continuization.
The strongest objection is that the proposed limit is not automatic. With a fixed separation \(s>0\) on a unit cake, the number of positive-length pieces is bounded, so no large-population limit exists. The proponent therefore changes the regime to \(s_n=\sigma/n\), rescales each agent’s value by \(n\), and replaces the finite MMS benchmark by a fluid benchmark \(q_t\). That is a substantial thermodynamic scaling, not merely replacing named agents by masses. Moreover, the displayed cell constraints are incomplete: separation gaps need not lie in the same valuation cell as the piece they follow, so one needs separate variables for gap mass and piece mass.
But neither point defeats the best mirror. The scaling has a natural interpretation as a fixed physical gap on a cake whose length grows with the population; rescaling utility is harmless because utilities are normalized; and the gap bookkeeping can be repaired with a finite transportation/packing LP. For piecewise-constant types, the limiting MMS benchmark is itself plausibly finitely representable, and agents of identical complete type are a perfectly sensible high-multiplicity population.
Thus the negative case can demand a formal convergence theorem and a corrected fluid formulation, but it cannot honestly argue that no worthwhile mirror exists. The anchor survives; at most, the proposed formulation needs technical repair before being claimed as a theorem.
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.