| paper | Dividing a Graphical Cake |
| authors | Xiaohui Bei, 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 |
other→NP-hard discrete result → its continuous mirror
Answer: The existential threshold problem is $\mathrm{NP}$-hard under polynomial-time many-one reductions, already for $\tau=3$ and edgewise constant densities. The optimum $W^*$ is attained, has the exact congestion-price characterization proved above, and $W^*/\kappa$ admits certified finite rational approximation with the stated running-time bounds. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
Given a finite connected graph \(G\), finite valuation-type set \(T\), type distribution \(\mu\), and per-capita capacity \(\kappa\), assign each type-conditioned unit of population mass a connected bundle \(B\subseteq G\) so that \(\ell(x)=\sum_t\mu_t\Pr[B\ni x\mid t]\leq\kappa\) almost everywhere, maximizing \(W=\min_{t:\mu_t>0}\operatorname{ess\,inf}_{B\sim t}v_t(B)\); determine whether \(W\geq w\) and characterize or compute the optimum \(W/\kappa\).
A finite-type, atomless population of complete additive valuation profiles is allocated connected bundles through type-conditioned bundle distributions; \(\kappa\) limits aggregate population mass at every cake point, and the objective is max-min type welfare, with \(W/\kappa\) as the population-scaled guarantee.
The load model permits sub-\(\kappa\) fractional bundles and does not yet prove purification into finite connected bundles, so the claimed exact recovery of finite instances is unsupported.
fatal: False
The mirror covers the general connected-allocation welfare guarantee and the star-graph welfare frontier. It leaves the two-agent graph classification, utility frontiers, multi-piece guarantees, equitability, and chore-division results unformalized.
The strongest honest mirror is a high-multiplicity version of the paper’s graphical-cake problem. The continuous object is the population of agents; the graph remains a physical resource, and connectivity remains a constraint on every individual bundle.
Let \(G\) be a finite connected graph, with each edge an interval. A type \(t\) is a complete additive, divisible, normalized valuation function \(v_t\) over every finite union of edge-intervals. A society is a distribution \(\mu\) over finitely many such types, with \(\mu_t\) the fraction of agents of type \(t\). This describes, for example, a large population of road-maintenance contractors whose valuation densities and equipment constraints fall into a small number of recurring profiles: \(N\gg\tau\), where \(N\) is the number of contractors and \(\tau\) the number of valuation types.
To preserve the paper’s one-cake resource constraint after normalizing population mass to \(1\), introduce \(\kappa\), the amount of normalized population mass that may use any point of the graph. For an \(N\)-agent instance, \(\kappa=1/N\). A continuous allocation assigns each unit of population mass one connected piece \(B\subseteq G\), with the aggregate load constraint
\[
\ell(x)=\sum_t\mu_t\Pr[B\ni x\mid t]\leq\kappa
\]
for almost every point \(x\). Thus each unit of mass receives an integral connected bundle, while the type-level allocation is fractional. The welfare of type \(t\) is the essential infimum of \(v_t(B)\) among its assigned bundles, and the objective is to maximize the minimum type welfare \(W\). The population-scaled welfare is \(W/\kappa\).
For empirical \(\mu_t=n_t/N\), this exactly recovers the finite problem: the load constraint says that no physical point is assigned to more than one of the \(N\) agents. The continuous question is therefore not “make the cake fractional”; the cake was already divisible. It is whether the finite agent index can be replaced by a mass distribution while retaining connected individual bundles and the egalitarian objective.
My lead anchor is Theorem 3.1 of the paper, proved there rather than cited. It states that for every graph \(G\), there is a connected allocation with egalitarian welfare at least \(1/(2n-1)\). It also gives a matching lower-bound construction: for some graph and identical valuations, every connected allocation has egalitarian welfare at most \(1/(2n-1)\). The proof is constructive, using cycle removal, a rooted-tree traversal, and a moving knife. The paper contains no named NP-hardness or polynomial-time theorem, so this is necessarily an algorithmic/existence anchor rather than a hardness anchor. The theorem is stated as Theorem 3.1 in the AAAI version of the paper. ([paper](https://ojs.aaai.org/index.php/AAAI/article/view/16652/16459))
The corresponding continuous problem is:
Continuous Graphical-Cake Egalitarian Allocation. Given \(G\), \(\kappa\), a finite type set \(T\), valuation functions \(v_t\), and society distribution \(\mu\), find a measurable mass allocation into connected pieces satisfying the load bound \(\ell(x)\leq\kappa\), maximizing
\[
W=\min_{t:\mu_t>0}\operatorname{ess\,inf}_{B\sim t}v_t(B).
\]
The decision version asks whether \(W\geq w\).
For an empirical \(N\)-agent society with \(\kappa=1/N\), Theorem 3.1 predicts \(W\geq \kappa/(2-\kappa)\), since
\[
\frac{1}{2N-1}=\frac{\kappa}{2-\kappa}.
\]
The genuinely continuous question is whether this guarantee extends to arbitrary \(\mu\), and whether the scaled limit \(W/\kappa\) tends to \(1/2\) as \(\kappa\to0\). I expect this to be Class A in the natural finite-type, rational piecewise-linear valuation regime. The moving-knife proof already exposes the relevant structure, and a finite encoding should permit a tree-based algorithm or a column-generation formulation. The paper itself does not establish polynomial running time, so that would be a new computational result rather than a claim attributed to the authors.
A strong secondary anchor is Theorem 3.2, also proved in the paper. For \(n\geq2\) agents and a star with \(k\geq3\) edges, it defines
\[
f(n,k)=
\begin{cases}
\dfrac{1}{n+\lceil k/2\rceil-1},&k<2n-1,\\[4pt]
\dfrac{1}{2n-1},&k\geq2n-1,
\end{cases}
\]
and proves that a connected allocation with egalitarian welfare at least \(f(n,k)\) always exists, while this bound is tight.
The corresponding continuous question is:
Continuous Star-Cake Frontier. Given a star \(S_k\), a population distribution \(\mu\), and capacity \(\kappa\), solve the same mass-allocation problem and determine the worst-case scaled welfare \(W/\kappa\). In the high-multiplicity regime \(k\kappa\to\theta\), determine
\[
\Phi(\theta)=\inf \liminf_{\kappa\to0}\frac{W^*(S_k,\mu,\kappa)}{\kappa}.
\]
Theorem 3.2 suggests the exact frontier
\[
\Phi(\theta)=
\begin{cases}
\dfrac{1}{1+\theta/2},&0\leq\theta<2,\\[4pt]
\dfrac12,&\theta\geq2.
\end{cases}
\]
This is especially credible as a continuous mirror because the tight examples use identical valuations: the continuous society can have \(\tau=1\), with all complexity coming from population multiplicity and the number of network branches. The expected classification is again Class A for fixed-type star instances, with the frontier governed by a one-dimensional branch-allocation problem.
The authors should recognise both mirrors as their problem. The graph, additive valuations, connected bundles, moving-knife structure, and egalitarian objective are unchanged. Only the finite list of agents is replaced by a distribution of complete agent types, with the population-normalized capacity \(\kappa\) forced by the requirement that finite \(N\)-agent instances embed exactly into the model.
The weakest point is the capacity scaling. A literal atomless population dividing one fixed cake gives almost every individual zero resource, so taking \(\mu\) continuous while leaving the resource normalization untouched would be meaningless. The parameter \(\kappa\) is therefore essential. An opponent can argue that this changes the problem, but it is a controlled co-modification: \(\kappa=1/N\) recovers the paper’s finite model exactly, and \(\kappa\to0\) is its high-multiplicity limit. The remaining questions—continuum extension of the \(1/(2n-1)\) guarantee, purification of mass allocations, finite algorithms, and possible pricing hardness for general graphs—are precisely the computational questions that make this a worthwhile continuous mirror.
The negative case should begin with the programme’s anchor rule. The paper has no qualifying computational result to continuize. Its §3.1 theorem is an existence and approximation guarantee, proved by a moving-knife protocol; its §3.2 theorem is a tight welfare guarantee for stars. Neither states a complexity classification, running-time bound, approximation algorithm in a finite encoding, or parameterized result. The paper’s “constructive” protocols live in the Robertson–Webb query model, not in the computational-complexity model that ChoCo is meant to develop.
This is not a claim that high multiplicity is unnatural here. It is quite natural: the paper’s identical-valuation lower bounds are already excellent repeated-type instances. Thus the objection cannot be that agents are inherently individuated. The objection is that the proposed continuous problem is not a continuization of a computational contribution made by the paper.
For the general guarantee theorem, the proposed load model introduces a substantial unresolved modelling gap. With \(\mu_t=n_t/N\) and \(\kappa=1/N\), the constraint
\[
\ell(x)\leq \kappa
\]
does not exactly recover \(N\) finite agents. It permits a connected bundle to be assigned to any mass \(a<\kappa\), and permits a type’s mass to be fractionally split among arbitrarily many bundles. Finite agents instead come in indivisible population units of mass \(\kappa\). Turning such a fractional allocation into \(N\) connected bundles requires a purification theorem; connectedness makes that nontrivial, since merging underweight bundles can produce a disconnected bundle.
There are therefore two possible repairs, neither of which is the paper’s problem. If fractional bundle masses are retained, one has created a new infinite-dimensional capacitated packing problem. If every bundle is required to carry exactly one agent-mass, the model becomes a sequence of finite connected-partition problems, with the continuum notation adding little and destroying the convexity that made the proposed formulation attractive. The statement that the model “exactly recovers” the finite problem is consequently unproved and, as written, false.
The parameter \(\kappa\) is defensible as a co-modification, but it also reveals the issue: \(\mu\) alone does not define the continuous problem. One must add a population-scale resource-capacity parameter and decide how individual bundle mass is represented. Those choices are new modelling work, not consequences of Theorem 3.1. Once they are made, the resulting max-min allocation problem may be worth studying independently, but it is not a computational question supplied by the paper.
The star anchor is weaker still. The proposed frontier assumes
\[
k\kappa\to\theta,
\]
so \(k\) must grow together with the population size. For a fixed graph, \(k\kappa\to0\), and the advertised nontrivial \(\theta\)-frontier disappears. The proposal is therefore a joint asymptotic in which both the population and the physical resource grow. That may be interesting, but it is not merely continuizing the population of a fixed graphical-cake instance.
Moreover, the tight star valuations themselves vary with \(N\) and \(k\). The finite theorem therefore supplies a family of worst-case instances, not a fixed finite type distribution whose continuous limit has been identified. Passing from the finite bound \(f(N,k)\) to
\[
\frac{f(N,k)}{\kappa}
\]
does not establish the continuous frontier unless one proves that the fractional mass model and the finite connected-partition model have matching optima. Again, that is precisely the missing purification or rounding theorem.
So the proponent has shown that a coherent high-multiplicity graphical-cake model can be invented. That is the honest weak point in the negative case: I cannot claim that no sensible model exists. But under ChoCo’s stated standard, neither proposed anchor carries a computational result from the paper, and the repaired mirrors require a new capacity model, a new finite encoding, and a new discrete–continuous correspondence. They would be worthwhile fair-division projects in their own right, not worthwhile continuous mirrors of this paper’s contribution.
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.