| paper | The Complexity of Cake Cutting with Unequal Shares |
| authors | Ágnes Cseh, T. Fleiner |
| venue | SAGT 2018 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), with \(O(\tau)\) arithmetic and output operations and exactly zero type queries. The proposed \(2(\tau-1)\lceil\log_2 D\rceil\) upper bound holds, but the proposed \(\Omega(\tau\log D)\) lower bound is false. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.3
statement extracted from the paper’s text layer
Given a finite type set \(T\), masses \(\mu_t\) with \(\sum_t\mu_t=1\), aggregate demands \(w_t\in\mathbb{Z}_{>0}\), atomless valuation oracles \(v_t\) on a cake \(X\) with \(v_t(X)=D=\sum_t w_t\), and type-level cut/evaluation access, compute measurable allocation densities \(a_t:X\to[0,1]\) satisfying \(\sum_t a_t(x)=1\) and \(\int_X a_t\,dv_t\ge w_t\) for every \(t\), while determining the worst-case number of type queries; in particular, whether \(2(\tau-1)\lceil\log_2D\rceil\) queries suffice and whether \(\Omega(\tau\log D)\) are necessary.
A high-multiplicity unequal-entitlement cake-cutting model with \(\tau\) valuation-entitlement types, mass \(\mu_t\), common atomless valuation \(v_t\), aggregate entitlement \(w_t=\mu_t d_t\), type-level allocation density \(a_t\), and type-oracle cut/evaluation queries.
The proposed protocol outputs type-level pieces, while the continuum interpretation guarantees only type-average value; the case does not fully formalize an individual allocation or the corresponding type-query implementation.
fatal: False
The mirror covers the type-level versions of Theorems 4.3, 5.4, 6.3, and 7.4, while leaving individual-player truthfulness, prior-protocol comparisons, and uniform bit-complexity for irrational inputs unresolved.
The strongest honest case is a high-multiplicity mirror of the paper’s proportional cake-cutting problem, not a claim that cake cutting itself is newly continuous. The cake is already divisible in the paper; the new continuous object is the population of agents valuing it.
Let \(T=\{1,\ldots,\tau\}\) be valuation types. Type \(t\) has mass \(\lambda_t\), normalized mass \(\mu_t=\lambda_t/M\), entitlement \(d_t\) per unit of mass, and an atomless valuation measure \(v_t\) on the cake \(X\). Every agent of that type has exactly the same \(v_t\) and \(d_t\). Set \(w_t=\lambda_t d_t\) and \(D=\sum_t w_t\), and normalize \(v_t(X)=D\), as in the paper.
A solution is a measurable allocation of the cake among types, represented either by a partition \(\{X_t\}_{t\in T}\) or by allocation densities \(a_t(x)\in[0,1]\) satisfying \(\sum_t a_t(x)=1\). It must satisfy \(v_t(X_t)\ge w_t\), equivalently \(\frac{v_t(X_t)}{\lambda_t}\ge d_t\): the type receives enough total value for every unit of its mass. Within a type, the allocation can be shared measurably among the continuum of identical agents. In the finite case, atomlessness lets \(X_t\) be divided into individual pieces.
This is exactly the high-multiplicity dictionary. If a finite population has \(n_t\) copies of type \(t\), then \(\lambda_t=n_t\), \(\mu_t=n_t/n\), and \(w_t=n_td_t\). A type-level bundle satisfying \(v_t(X_t)\ge n_td_t\) can be divided among the \(n_t\) identical agents. Conversely, rational masses can be multiplied by a common denominator to recover a finite high-multiplicity instance. The computational resource is the number of valuation-type queries, not the number \(M\) of represented agents. A query to \(v_t\) is the paper’s cut or evaluation query, but asked once to the type oracle rather than separately to every copy.
My lead mirror is \(\mathsf{Continuous\text{-}UnequalCake}_{\mathbb Z}\). Its input consists of a finite type set \(T\), rational masses \(\mu_t\), integer aggregate entitlements \(w_t>0\), atomless type valuation oracles \(v_t\) with \(v_t(X)=D=\sum_t w_t\), and the cake-query model from the paper. The task is to output a proportional type allocation satisfying \(v_t(X_t)\ge w_t\) for every type, while minimizing the worst-case number of type queries.
The anchor is Theorem 4.3, proved in this paper. It states that, for \(2\le n<D\), the authors’ protocol for proportional division with unequal shares terminates with a proportional division using at most \(2(n-1)\lceil\log_2 D\rceil\) queries. The continuous question is whether the same bound becomes \(2(\tau-1)\lceil\log_2 D\rceil\) when \(n\) is replaced by the number \(\tau\) of distinct valuation types. The expected answer is yes: run the paper’s recursive near-halves protocol on types, using \(w_t\) as the type’s aggregate demand. When the protocol splits a boundary player into two recursive subinstances, it splits that type’s mass and aggregate entitlement; the valuation oracle remains the same. Thus a population with millions of agents but, say, twenty valuation-entitlement types is handled through roughly twenty type interfaces rather than millions of individual ones.
This is plausibly the authors’ problem. It preserves their cake, valuation measures, unequal entitlements, proportionality requirement, cut/evaluation oracle, and query-complexity objective. The only substantive change is precisely the high-multiplicity assumption that many agents are indistinguishable. A natural regime is a large population of households, firms, or service users falling into a small number of stable valuation-entitlement classes for a heterogeneous divisible resource such as land, time, bandwidth, or public-service capacity.
A second, independent mirror is \(\mathsf{Continuous\text{-}UnequalCake\text{-}LowerBound}\). It has the same input and output, but asks for the minimum worst-case number of type queries over deterministic protocols, even when arbitrary generalized cut/evaluation queries are allowed. Its proposed statement is that some family with \(\tau\) types and aggregate demand \(D\) requires \(\Omega(\tau\log D)\) type queries, even though every type may represent an arbitrarily large mass of identical agents.
The anchor is Theorem 6.3, proved here. It states that constructing a proportional division in an \(n\)-player unequal-shares cake-cutting problem with demands summing to \(D\) requires \(\Omega(n\log D)\) queries. The paper’s surrounding argument establishes this for its generalized cake and query settings as well as the standard interval setting. In the mirror, take \(\tau-1\) humble types with small aggregate demands and one greedy type with the remaining demand, while giving each type a large repeated mass. The adversary argument then concerns the \(\tau\) distinct valuation oracles, not the number of agents represented by each oracle.
This second problem is expected to have a matching lower bound, not NP-hardness. The paper contains no named NP-hardness result; its computational anchors are query upper and lower bounds. The resulting continuous mirror would therefore be Class A with a tight information/query boundary: tractable in the number of types, but not query-free.
A useful real-demand extension is \(\mathsf{Continuous\text{-}UnequalCake}_{\mathbb R}\). Here masses and per-unit entitlements may make the aggregate demands \(w_t=\lambda_t d_t\) irrational. The task is to produce a proportional allocation by a finite sequence of type queries, or equivalently to reduce the instance to finitely many rational-demand type instances.
The anchor is Theorem 7.4, proved here. It states that any \(n\)-player proportional cake-cutting instance with irrational demands can be transformed into at most \(n-1\) proportional cake-cutting instances with rational demands, and therefore solved using finitely many queries. The paper explicitly warns that this gives no uniform query bound, because the rationalized instances may have arbitrarily large total demand \(D\). The continuous analogue replaces \(n\) by \(\tau\): irrational type masses and aggregate entitlements are reduced to at most \(\tau-1\) rational type problems. I would expect finite solvability, but not yet a polynomial bound in a standard bit model. This is precisely the sort of precision question that a continuous population makes natural.
The weakest part of the case is that the lead result transfers almost immediately by grouping identical players. An opponent can fairly say that the paper already contains the divisible cake and that the mirror may look like “run the same theorem with \(\tau\) players.” I would concede that. The defence is that the paper never studies the population distribution, type-oracle complexity, or the high-multiplicity interpretation of its query bounds. The meaningful question is not whether the cake is divisible, but whether a continuum of agents with finitely many complete valuation types admits a precise type-level protocol, tight lower bound, and real-mass extension. That is a genuine population continuization, even though the underlying resource was already continuous.
The strongest negative case is that this paper has no genuinely population-level object left after the complete-type requirement is applied.
A cake-cutting player is completely described, for the purposes of every theorem here, by her valuation oracle and entitlement. Thus a type is exactly a player together with a multiplicity. If type \(t\) has mass \(\lambda_t\), the only constraint that survives aggregation is
\[ v_t(X_t)\ge \lambda_t d_t=:w_t. \]
After fixing the normalization of \(v_t\), the instance depends on \(w_t\), not on \(\lambda_t\) and \(d_t\) separately. It is therefore exactly the finite cake-cutting problem with \(\tau\) players having demands \(w_t\). Conversely, every finite \(\tau\)-player instance can be inflated to arbitrarily many identical agents. This is not the mistaken objection that high multiplicity is illegitimate; it is the consequence of taking high multiplicity seriously. Here the population coordinate is completely eliminable.
There is also a genuine allocation problem hidden by the proposed formulation. The paper allocates disjoint measurable pieces to individual players. If a positive-mass continuum of identical agents must each receive a piece of positive value, this is impossible: a finite atomless measure has at most countably many disjoint positive-measure pieces. The proposed density allocation \(a_t(x)\) repairs this by introducing fractional allocations or lotteries, but then the requirement is a type-average guarantee, not the paper’s guarantee to every player. That may be a sensible new fair-division model, but it is an outcome-space modification whose query model and implementation have to be supplied from scratch. If one insists on the paper’s deterministic pieces, the continuum is infeasible; if one allows fractional pieces, the problem is no longer the named cake-cutting problem.
This defeats the proposed reading of Theorem 4.3. With integer aggregate demands \(w_t\), the protocol really can be run with \(\tau\) type players, but that is merely the paper’s theorem after merging identical players. No continuous population enters its input, transcript, or output. With genuinely normalized real masses, the integer parameter \(D\) and the bound \(2(\tau-1)\lceil\log_2D\rceil\) cease to be intrinsic. Rescaling all valuations and demands preserves every allocation and every query transcript while changing \(D\). A real-demand version could certainly be formulated, but it would be a new scalar-demand cake-cutting problem, not a population continuization of this result.
Theorem 6.3 does not rescue the mirror. Its adversary needs one independent unknown valuation measure per humble player. Repeating a type gives no new hidden information: all copies share one oracle. The resulting lower bound is therefore exactly a lower bound for \(\tau\) finite valuation oracles. If demands are normalized as population masses, \(D\) no longer records multiplicity; if demands scale with the number of copies, the result is simply the finite \(\tau\)-player problem with large numerical demands. In neither case does the adversary establish a new phenomenon caused by a continuous society. The proponent’s claim that every type may have arbitrarily large mass is compatible with the construction, but irrelevant to the proof.
Theorem 7.4 is weaker still as a continuous anchor. Irrational type masses merely produce irrational aggregate demands \(w_t\) in a finite \(\tau\)-player instance—the very scalar irrationality that the theorem already treats. If arbitrary exact irrationals are part of the input, there is no ordinary finite encoding or bit-complexity model; if they are supplied by ideal real oracles, the claimed finite-query reduction is just the paper’s reduction applied after aggregation. A genuinely non-atomic space of valuation types would avoid the quotient, but then there are infinitely many independent valuation oracles and the paper’s finite recursive protocol no longer gives a finite type-level computation.
So the best negative verdict is that every proposed anchor has the same fate: integer masses collapse to the original finite problem with \(\tau\) players; real masses turn into an unmodelled exact-real problem; and a true continuum of distinct valuation types destroys finite query complexity. This is a strong case against spending programme-level effort on this paper.
It is not airtight. If ChoCo regards the lossless replacement of \(n\) identical players by one type with aggregate entitlement as a worthwhile high-multiplicity result in its own right, then Theorem 4.3 gives a legitimate mirror, and no honest negative argument can make it disappear. The defensible conclusion is therefore “low novelty and weakly population-specific,” not a proof that no worthwhile mirror can be designed.
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.