| paper | Computing socially-efficient cake divisions |
| authors | Y. Aumann, Yair Dombb, Avinatan Hassidim |
| venue | ATAL 2013 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational mass vector \(\mu\), population scale \(N\), explicit piecewise-uniform valuation densities \(\nu_t\) on a cake interval \([0,N]\), and threshold \(B\), decide whether there are assignment measures \(\xi_t\) over connected intervals \(I\) such that \(\xi_t(\mathcal I)=N\mu_t\), each mass unit receives one interval, \(\sum_t\int \mathbf{1}_{x\in I}\,d\xi_t(I)\leq 1\) almost everywhere, and \(v_t(I)=\int_I\nu_t(x)\,dx\geq B\) for \(\xi_t\)-almost every assigned interval.
A high-multiplicity configuration model in which types \(t\in T\) carry mass \(N\mu_t\), variables \(\xi_t(I)\) assign that mass to one connected interval, pointwise cake capacity is \(1\), and the egalitarian objective maximizes \(B\).
The proposed pointwise-capacity assignment measure and the claimed polynomial pricing procedure have not been shown to encode and solve the continuous connected-division problem exactly; dual location-dependent prices may make separation subtler than scanning valuation prefix sums.
fatal: False
The mirror covers Theorem 6's connected egalitarian result and Theorem 7's connected utilitarian result. It leaves the approximation algorithms, non-connected LP result, oracle lower bound, discrete formulations, and strategic or two-dimensional extensions untouched.
The strongest positive case is a high-multiplicity version of the paper’s connected cake-division problems. The cake remains one-dimensional, valuations remain additive, and every individual still receives one connected interval. What changes is only the finite list of players: it becomes a distribution over complete valuation types.
A plausible regime is large-scale event scheduling. A municipality has \(N\) event requests for a hall over a horizon of length \(N\). Each event needs one contiguous reservation. Many events share one of a finite set \(T\) of valuation templates: for example, evening classes, weekend conferences, clinics, or recurring community meetings. A type includes the entire piecewise-uniform valuation function and any eligibility restrictions. If type \(t\) has population fraction \(\mu_t\), then there are \(N\mu_t\) such requests, with \(|T|=\tau\ll N\). The horizon scales with the population, which is the natural per-capita-supply modification needed to prevent every individual’s share from collapsing to zero.
My lead anchor is Theorem 6, proved in this paper. It states that \({\sc CEO}\) and \({\sc Discrete\text{-}CEO}\) are strongly NP-complete; moreover, for every \(\epsilon>0\), neither admits a \((2-\epsilon)\)-approximation unless \(\mathrm{P}=\mathrm{NP}\). This remains true when valuations are piecewise-uniform and explicitly given. Here \({\sc CEO}\) asks whether a connected division of the cake exists in which every player receives value at least \(B\), while \({\sc Discrete\text{-}CEO}\) imposes the analogous restriction on a sequence of indivisible items. The theorem is proved here, by reduction from 3-dimensional matching.
The corresponding continuous-population problem is Mass-CEO\(_\infty\). An instance consists of a population distribution \(\mu\), a population scale \(N\), piecewise-uniform valuation densities \(\nu_t\) for \(t\in T\), and a threshold \(B\). A connected bundle is an interval \(I=[a,b]\). Let \(v_t(I)=\int_I\nu_t(x)\,dx\).
A solution is a finite-support assignment measure \(\xi_t\) over intervals, where \(\xi_t(I)\) is the mass of type-\(t\) agents assigned interval \(I\). It must satisfy \(\xi_t(\mathcal I)=N\mu_t\), and the total mass occupying any point of the cake is at most one: \(\sum_t\int \mathbf{1}_{x\in I}\,d\xi_t(I)\le 1\). Unused cake can be filled by a null type, so this is equivalent to a full division. Every unit of population mass is assigned one interval; if a type appears on several intervals, those are different agents of that type, not one agent receiving disconnected pieces.
The question is whether there is a feasible \(\xi\) such that \(v_t(I)\ge B\) for \(\xi_t\)-almost every assigned interval. Equivalently, maximize the essential infimum of assigned-agent utilities. For rational masses, this is the high-multiplicity encoding of \(N\mu_t\) individual players; the continuous object replaces their explicit enumeration by mass variables.
I expect Mass-CEO\(_\infty\) to be Class A in the explicit piecewise-uniform model. Its natural formulation is a configuration LP: variables \(x_{t,I}\) represent mass of type \(t\) assigned to interval \(I\), with type-mass constraints and pointwise capacity constraints. For a fixed \(B\), simply discard interval columns with \(v_t(I)<B\). After refining at valuation breakpoints, the relevant pricing problem is a maximum-weight admissible subinterval, solvable by scanning prefix sums; equivalently, one can use column generation or separation. Thus the paper’s finite-player \(2-\epsilon\) hardness may dissolve because its exact packing of named players becomes fractional mass conservation. This is precisely the kind of population-multiplicity effect the programme is meant to test.
My second anchor is Theorem 7, also proved in this paper. It states that \({\sc CUO}\) and \({\sc Discrete\text{-}CUO}\) are strongly NP-complete, even when valuations are piecewise-uniform and explicitly given. \({\sc CUO}\) asks whether a connected division has total utilitarian welfare at least \(B\), and the discrete version asks the same for consecutive subsequences of indivisible items. The proof reduces from the paper’s Multiple-Choice Segment Packing problem.
The corresponding problem is Mass-CUO\(_\infty\). It has the same population, valuation, interval, and capacity data, but asks for a feasible assignment maximizing \(W(\xi)=N^{-1}\sum_t\int v_t(I)\,d\xi_t(I)\), or, in decision form, whether \(W(\xi)\ge B\). The factor \(N^{-1}\) only changes the normalization: maximizing average welfare is equivalent to maximizing the utilitarian sum of the \(N\) finite agents.
This problem is also plausibly Class A. Its configuration LP uses the same interval columns, but now gives each column its welfare coefficient \(v_t(I)\). The pricing problem is again a maximum-weight interval. The question remains recognisably the authors’ problem: each demand receives one contiguous piece, the objective is still utilitarian welfare, and the only new ingredient is that identical demands are represented by mass rather than by a list of names.
This is not a novelty collision. The paper makes the cake continuous, but its society is still a finite tuple \(v_1,\ldots,v_n\). It does not study a distribution \(\mu\) over valuation types, nor the high-multiplicity assignment LP above. The mirror therefore continuizes the population, not the outcome. The paper’s non-connected Theorem 9 is not the mirror I am relying on; dropping connectedness would change the underlying problem.
The weakest point is the fluid interpretation of connectedness. With an atomless population and a fixed single cake, literal positive-length intervals cannot be assigned to every infinitesimal individual. The mirror therefore needs the permitted co-modification: population-scaled resource supply and an assignment measure whose atoms represent masses of distinct agents, each receiving one interval. If the authors insist on one fixed physical cake, integral agents, and no per-capita scaling, this mirror may be rejected or reduced to a different type-block problem. But for recurring scheduling, repeated service capacity, or a long horizon whose supply grows with demand, the modification is natural. It preserves the paper’s central computational question closely enough that Theorems 6 and 7 generate precise, nontrivial continuous-population problems, with a credible expectation that their discrete hardness may disappear through the very high-multiplicity relaxation ChoCo is designed to study.
The strongest negative case is that neither Theorem 6 nor Theorem 7 supplies a genuinely high-multiplicity family.
Theorem 6’s reduction is built from spatially unique agents. Each separation player is tied to one particular gap; each triplet player has a particular incidence pattern; and the ground-set players are duplicated only within one \(x\)- or \(y\)-role. Since a type includes the complete valuation function, players tied to different sections are different types. Thus the reduction has \(\tau=\Theta(|E|)\) essentially location-coded types, rather than many copies of a small type set. Repeating the agents does not fix this: it merely increases the mass of each location-specific type. If one instead makes players in different sections genuinely identical, they can exchange sections and the exact 3-dimensional-matching gadget disappears.
Theorem 7 is even less compatible with high multiplicity. The segment player \(p_i^j\) is identified by one particular segment and one particular compensation slot, while each separation player \(q_i^j\) has a unique desired interval. Those identities are not incidental bookkeeping; they enforce the multiple-choice packing constraint. Grouping them into common types destroys precisely the combinatorial structure being reduced.
So the proponent cannot claim that these theorems themselves establish a continuous-population hardness or tractability result. Their proposed configuration LP is also only a sketch. It has infinitely many interval columns and pointwise capacity constraints. The pricing problem is not automatically “a maximum-weight interval”: the dual must choose an interval satisfying \(v_t(I)\ge B\) against location-dependent dual prices, and the finite refinement and separation argument still need to be proved. The same gap applies to Mass-CUO\(_\infty\).
That is the full force of the negative case—but it is not enough to support the universal verdict requested. The missing reduction is evidence against these particular anchors, not evidence that no worthwhile mirror exists. A repaired model with a horizon of length \(N\), rational type masses, normalized type valuations, and an assignment measure in which each agent receives one interval is a legitimate high-multiplicity version of the authors’ problem. Event scheduling with many recurring requests of a few valuation templates is a credible regime, and the objectives depend only on valuations and obtained utility, not on personal identity. The programme expressly permits the resource to scale per capita.
If the matching hardness disappears in that model, that is not a defect: it is exactly the population-multiplicity phenomenon ChoCo is meant to study. Consequently, the honest negative conclusion is only that the proposed argument has not yet proved the claimed LP tractability, and that the paper’s reductions do not transfer automatically. It does not defeat either continuous question. The universal “no worthwhile mirror” case is therefore weak.
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.