| paper | d4-journals-mss-2019-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: No finite BSSRW protocol with rational constants can output the exact equitable cut for any allowed \(d\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
For an allowed \(d\) from Theorem 2, let a society of unit mass have two valuation types with \(\mu_{t_1}=\mu_{t_2}=1/2\), \(F_{t_1}(x)=x\), and \(F_{t_2}(x)=x^d\). Given Robertson–Webb evaluation and cut queries to representatives of those types, is there a finite BSSRW protocol that outputs an exact \(t\in[0,1]\) such that type \(t_1\) receives \([0,t]\), type \(t_2\) receives \([t,1]\), and their utilities are equal?
A unit mass of two complete valuation types, each receiving one common connected interval, with per-capita cake supply scaled to the population. The decision variable is the exact cutpoint \(t\); the feasibility condition is \(F_{t_1}(t)=1-F_{t_2}(t)\), and the computation model is BSSRW access to the two type representatives.
The mirror covers Theorem 2’s explicit family of simple equitable divisions, including the \(d=5\) instance, and leaves the utilitarian-welfare impossibility and divisions with non-connected parts aside.
The strongest mirror I believe is a narrow, type-uniform version of equitable cake division. Its society is a unit mass split equally between two complete valuation types: \(\mu_{t_1}=\mu_{t_2}=1/2\), with cumulative utilities \(F_{t_1}(x)=x\) and \(F_{t_2}(x)=x^d\). A natural regime is a large population with \(n/2\) agents of each type, so \(n\gg\tau=2\). Every agent in a type receives the same connected interval as the rest of that type. To keep individual bundles from vanishing as the population grows, the available stock of each cake location scales with population: in the finite version, there are \(n/2\) copies of each location. The two cohorts receive complementary intervals, so this allocation uses that stock.
My anchor is Theorem 2, proved in this paper. It says that in the BSSRW model there are pairs of measures for which no algorithm returns a simple equitable division; specifically, this holds for \(F_1(x)=x\) and \(F_2(x)=x^d\) when \(d\ge5\) is even, when \(d\ge5\) is odd with \(d\not\equiv2\pmod 3\), or when \(d\ge5\) is prime with \(d\equiv2\pmod 3\). The obstruction is exact computation in the paper’s query model, not a claim of NP-hardness.
The corresponding continuous problem is Type-Uniform Equitable Cake Division. Given one of those values of \(d\), the two-type society above, and Robertson–Webb evaluation and cut queries to its type representatives, can a finite BSSRW protocol output an exact \(t\in[0,1]\) such that type \(t_1\) receives \([0,t]\), type \(t_2\) receives \([t,1]\), and every agent gets the same utility? A solution is the exact cutpoint and those two intervals. Equitability requires
\[
F_{t_1}(t)=1-F_{t_2}(t),
\]
so \(t\) must satisfy \(t^d+t-1=0\).
I expect the BSSRW impossibility to transfer. Evaluation queries add no new field elements; cut queries for the \(x^d\) type can adjoin \(d\)-th roots, while cuts for the uniform type add none. Thus the same field-extension obstruction used in the paper applies to the cutpoint required by the mirror. This is persistence from the two-agent core, not a new hardness caused by population multiplicity. In ChoCo’s trichotomy, “hardness transfers” is the closest label, with the qualification that the result is model-specific computability, not standard complexity hardness.
The mirror covers Theorem 2’s simple equitable divisions, and nothing here claims to mirror the paper’s utilitarian-welfare result. It raises useful follow-up questions: does allowing a type’s mass to split across different intervals remove the obstruction? What changes if the output can encode an algebraic number by a polynomial and isolating interval, or need only approximate the cutpoint? Those are different output or allocation models and should be stated as such.
The weakest point is the resource and symmetry extension. The paper divides one cake among finitely many named players; this mirror scales supply with population and requires identical agents of a type to receive a common interval. If the authors or a referee require one fixed cake, this does not work as a population limit: almost all agents’ connected pieces would have zero size. The scaled-stock version is author-recognizable as equitable connected cake allocation, but it is an extension, and its exact BSSRW obstruction says little about whether population continuization creates the broader complexity landscape ChoCo seeks.
Theorem 2 is the proponent’s strongest anchor, and its exact BSSRW obstruction really does carry over to their two-type construction: the required cutpoint still solves \(t^d+t-1=0\), and repeating each type does not change the field argument. I would not dispute that this is a formal continuous-population mirror.
My objection is that it mirrors a different computational question from the one ChoCo is meant to chart. The theorem concerns whether a finite Robertson–Webb protocol, restricted to BSS arithmetic and exact real comparisons, can produce a real endpoint from valuation-oracle answers. It does not give a running-time classification in population size, support size, or input bit length. The society’s masses can be encoded as rationals, but that does not encode the valuation or settle how an algorithm must represent its output. Preserve the paper’s oracle and raw-real-output model, and the mass duplication leaves the same two-agent field obstruction in place. Give the valuations finite descriptions and allow algebraic-number output, and the cutpoint can at least be *named* by its polynomial and an isolating interval; that changes the question from BSSRW computability. Neither formulation supplies the complexity landscape the programme is seeking.
The population also does no computational work in this anchor. Equitability compares each type’s per-agent utility, and the equation for \(t\) contains no type masses. Under the proposed scaling, the large society is a replication of the same two-type allocation across copies of the cake. A more general continuum allocation that lets members of a type receive different bundles might make mass matter, but Theorem 2 gives no result about that problem; its algebraic obstruction need not apply.
So I would not prioritize this as a ChoCo mirror: it transports an exact-real computability barrier into a replicated population, rather than opening a population-dependent complexity question. That is a case against the proposed anchor’s value, not a proof that no worthwhile cake-cutting mirror exists. The authors’ multi-agent resource-allocation framing makes a high-multiplicity regime plausible, and I cannot honestly rule out a different, useful mirror.
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.