| paper | d4-conf-wine-2009-0061 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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 the stated exact oracle model, and in polynomial bit time for explicitly given positive rational piecewise-constant densities. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.8
statement extracted from the paper’s text layer
Given \(N\) agents summarized by \(\tau\) complete additive valuation types with rational masses \(\mu_t=n_t/N\), and cut/evaluation oracles for those types, can one produce a type-mass representation of a disjoint cake division that realizes finite assignments giving every type-\(t\) agent a bundle with \(v_t(B)\ge 1/N\), using \(\mathrm{poly}(\tau,L,\log N)\) valuation queries?
A high-multiplicity cake-division model with rational masses over complete valuation types, typewise descriptions of bundles, and finite realizations that preserve disjointness and each agent’s proportional guarantee.
The case gives no compact output representation or query lower bound, and explicit divisions may require \(\Omega(N)\) cut queries even for one valuation type.
fatal: False
The mirror covers Theorem 4.8’s finite-step guarantee for the arbitrary-\(n\) protocol; it does not cover the DGEF guarantees, proportionality and strategy-proofness results, or the surveyed protocols.
The paper has no named NP-hardness, polynomial-time, parameterized-complexity, or approximation result. The only plausible computational anchor is Theorem 4.8, proved here: the protocol in Figure \(n\) terminates after a bounded number of steps, independent of the valuations. Its outer loop runs \((n-4)/2\) times for even \(n\) and \((n-3)/2\) times for odd \(n\); with \(s\) players remaining, the inner loop runs at most \(s-2\) times. The paper bounds its single protocol steps by
\[
7\left\lceil\frac{n-4}{2}\right\rceil
+3\sum_{i=1}^{\lceil(n-4)/2\rceil}(n-2i)+13.
\]
That is a finite-protocol bound, not a standard Turing-machine complexity classification. Theorem 4.9, also proved here, gives the protocol’s DGEF, but that is a fairness guarantee rather than a computational result, so I would not use it as an anchor.
A plausible follow-up is the Type-Mass Proportional Cake Query Problem. Given a population scale \(N\), a support \(T\) of \(\tau\) complete valuation types, rational masses \(\mu_t\), and normalized nonatomic additive valuations \(v_t\) accessible by cut and evaluation queries, find a proportional division for the corresponding high-multiplicity society. A solution must assign cake bundles to the population so that each type-\(t\) member receives a bundle worth at least \(1/N\) under \(v_t\). The computational question is whether a protocol can do this using a number of valuation queries polynomial in \(\tau\), the mass bit length \(L\), and \(\log N\), rather than in the number of people. A continuous output would describe, for each type, the mass assigned to each bundle, with a certificate that it is realizable by ordinary finite divisions in the relevant approximating populations.
The regime is a large cohort with relatively few repeated, fully specified preference profiles: for example, many participants sharing a small set of valuation archetypes for a heterogeneous common resource. This is a property of that regime, not of cake cutting in general. Treating a type as a complete valuation function is faithful to the paper’s assumptions; mass-level bundle assignments are the additional co-modification.
I would tentatively expect a tractability result in this query model: repeated types mean only \(\tau\) distinct valuation oracles need to be queried. Theorem 4.8 gives a finite-protocol starting point, though it does not establish a bound independent of \(N\). Further questions include whether exact masses or additive approximation are needed, whether the DGEF can be expressed as a guaranteed density of envy-free ordered pairs, and how query cost changes when the output must be explicit.
The weak point is substantial: the paper assigns exclusive portions to named players, and the fair-share threshold \(1/N\) vanishes as \(N\) grows. A type-mass allocation description may be only an average over individual bundles; requiring it to correspond to actual divisions could restore an \(N\)-dependent cost or make the continuum limit degenerate. If the authors reject that mass-level output as changing their allocation problem, this mirror fails their recognition test. The positive case is therefore a specific query-compression question, not evidence that the paper’s central results already have continuous-population counterparts.
The strongest anchor is Theorem 4.8, but it proves a bound on the steps of one interactive protocol, not the complexity of a problem whose input is a population distribution. Its operations are valuation marks and choices made by individual players; the proof counts them in terms of \(n\). The proposed Type-Mass Proportional Cake Query Problem is a plausible new question, but it adds an oracle input model and a type-level output that the theorem does not supply.
That output change is where the best version of the mirror runs into trouble. For \(N\) players, the protocol must produce \(N\) disjoint, nonempty portions. Even with one valuation type, writing down an ordinary division has size at least proportional to \(N\); producing \(N\) equal-value portions can require \(N\) distinct cut points. A type-mass summary cannot assign the same bundle to several people, since that would reuse cake. If the summary instead gives a distribution over bundles or a symbolic family of cuts, it no longer outputs the paper’s division, and arbitrary cut-and-evaluation oracles need not provide a compact representation or certificate for that family. The proposed bound in \(\log N\) therefore depends on relaxing the output requirement that gives the protocol its meaning.
There is also a limit issue. The proportional guarantee for each person is \(1/N\) of the cake, which tends to zero as the population grows. In a continuum population, individual agents have zero mass, so individual proportionality becomes vacuous unless the model adds a nontrivial type-level objective. Aggregate guarantees, such as requiring a type’s members collectively to receive a specified value, could be studied, but they describe an aggregate allocation problem rather than the paper’s guarantee to each named player. Scaling the cake with \(N\) would preserve a nonzero per-person allocation, but it changes the fixed-resource setting.
The most favorable regime for the mirror would be a large cohort with a small number of exactly repeated valuation functions. That is conceivable, but it does not remove the central obstacles: the types here are complete valuations over every interval, and the number of people is still tied to the number of portions and cuts in an explicit division. The paper’s step bound does not show that those operations can be compressed by type, and the mass summary that might permit compression needs a different feasibility and fairness definition.
So I would reject this as a strong ChoCo mirror of Theorem 4.8: it is a query-complexity question for a newly aggregated cake-cutting model, not a continuous-population version of the paper’s stated computational result. The negative case is not airtight, though. A type-level allocation model with a carefully chosen aggregate objective might be worth investigating; the case against rests on the fact that the proposed model changes the output and fairness target, while the paper gives no result that establishes the hoped-for compression.
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.