d4-journals-mss-2019-0017 (d4-journals-mss-2019-0017)

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 society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here total mass is \(1\), with \(\tau=2\) and masses \(1/2,1/2\).
The cake is \([0,1]\). Types have nonatomic probability valuations \(v_i([a,b])=F_i(b)-F_i(a)\), where \(F_1(x)=x\) and \(F_2(x)=x^d\). The integer \(d\geq5\) is even, or odd with \(d\not\equiv2\pmod3\), or prime with \(d\equiv2\pmod3\).
Type \(1\) receives \([0,t]\) and type \(2\) receives \([t,1]\); the shared endpoint has zero value. Equality means equal unweighted type utilities, \(v_1([0,t])=v_2([t,1])\).
A BSSRW protocol starts with rational constants only, performs exact arithmetic \((+,-,\times,\div)\) and comparisons, and adaptively queries type representatives. Evaluation returns \(v_i([x,y])\) for \(0\leq x\leq y\leq1\); a cut query with \(x\in[0,1]\) and \(0\leq a\leq1-F_i(x)\) returns the unique \(y\in[x,1]\) satisfying \(v_i([x,y])=a\). Output must be an exact real register value after finitely many operations and queries.
Complexity parameters are \(d\), support size \(\tau\), and total binary input length \(L\), including the binary encoding of \(d\); there is no candidate-count parameter \(m\).

For each allowed \(d\), does a finite BSSRW protocol output such an exact \(t\in[0,1]\), or is this impossible?

For two individual agents with these valuations, [Chèze’s impossibility result](https://www.math.univ-toulouse.fr/~cheze/BSS_RW_hal.pdf) excludes every finite BSSRW protocol computing an equitable connected division for every allowed \(d\).
The mass formulation specifies exactly the same oracle operations and output condition; consequently, this result already settles the stated question.

Conclusion

For every allowed \(d\), exact output is impossible for any finite BSSRW protocol with rational constants. This holds for each fixed \(d\), even if the protocol is designed specifically for that degree.

The equitable cut exists and is unique

The prescribed allocation has utilities \(t\) and \(1-t^d\). Thus equality is equivalent to

\(p_d(t)=t^d+t-1=0.\)

The polynomial \(p_d\) is continuous, with \(p_d(0)=-1\) and \(p_d(1)=1\). Moreover, if \(0\leq s<t\leq1\), then

\(p_d(t)-p_d(s)=(t^d-s^d)+(t-s)>0.\)

The intermediate value theorem and strict monotonicity therefore give exactly one equitable cut \(t_d\in(0,1)\). The obstruction concerns its exact computation, not its existence.

Applicable impossibility theorem

Chèze’s Theorem 2 states that, for two nonatomic probability measures with cumulative functions \(x\) and \(x^d\), no BSSRW algorithm outputs an equitable division into connected intervals whenever \(d\geq5\) is even, odd with \(d\not\equiv2\pmod3\), or prime with \(d\equiv2\pmod3\). Section 1 specifies rational constants, exact arithmetic and comparisons, and Robertson–Webb evaluation and cut queries. The obstruction applies separately to each such degree. [Chèze, *Cake cutting: explicit examples for impossibility results*, Theorem 2 and Section 1](https://www.math.univ-toulouse.fr/~cheze/BSS_RW_hal.pdf).

All measure hypotheses hold here. Indeed, \(F_1(x)=x\) and \(F_2(x)=x^d\) are continuous, strictly increasing cumulative functions with endpoint values \(0\) and \(1\). They define nonatomic probability measures, and strict increase makes every admissible cut query unique.

Reduction from the mass formulation

Fix an allowed \(d\), and suppose a protocol for the stated society terminates with the exact equitable cut \(t_d\).

Construct a protocol for two individual agents with these same valuations as follows:

• Supply the society protocol with its fixed rational data: support size \(2\), masses \(1/2,1/2\), and the binary encoding of \(d\).
• Redirect every query to type \(i\) to individual agent \(i\). Evaluation answers coincide because both return \(F_i(y)-F_i(x)\). Cut answers coincide because both solve the same equation with the same unique admissible solution.
• Perform the same arithmetic and comparisons, and output the division \([0,t_d]\), \([t_d,1]\).

Inductively, every register value, oracle answer, and branch decision in this simulation agrees with the supposed society execution. Hence it terminates after finitely many operations and queries. Its constants remain rational; in particular, fixing \(d\) introduces no nonrational constant.

Its output is connected and equitable because \(t_d=1-t_d^d\). Shared endpoints have zero value by nonatomicity. This contradicts Chèze’s theorem.

Consequently, the mass formulation has the same impossibility for every allowed \(d\). Neither the support encoding nor the parameters \(d,\tau,L\) alter this conclusion: the obstruction excludes every finite exact computation, irrespective of its running time.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned question correctly. No major or minor mathematical issues were found. Its conclusion applies to each fixed allowed degree, including protocols designed specifically for that degree.

• Equality condition. For the prescribed allocation, the utilities are \(t\) and \(1-t^d\). Thus equality is exactly \(t^d+t-1=0\). The masses do not enter this equation because the task explicitly requires unweighted type utilities.

• Existence and uniqueness. The endpoint computations \(p_d(0)=-1\) and \(p_d(1)=1\) are correct. Polynomial continuity satisfies the hypotheses of the intermediate value theorem. For \(0\leq s<t\leq1\), both \(t^d-s^d>0\) and \(t-s>0\), so the stated difference is positive. Consequently, there is exactly one root in \((0,1)\), and neither endpoint is equitable.

• The cited theorem matches the target. Chèze’s Theorem 2 explicitly covers the cumulative functions \(x\) and \(x^d\) and precisely the three degree classes listed in the task. Section 1 specifies rational constants, arithmetic, comparisons, evaluation queries, cut queries, and exact output cutpoints. The theorem excludes computation on these specified valuation instances; it is stronger than merely excluding one uniform protocol for all degrees. The prover’s citation and fixed-degree interpretation are accurate. [Chèze, Theorem 2 and Section 1](https://www.math.univ-toulouse.fr/~cheze/BSS_RW_hal.pdf).

• Measure and query hypotheses. The stated cumulative functions are continuous and strictly increasing on \([0,1]\), with endpoint values \(0\) and \(1\). The nonatomic probability-measure hypotheses are therefore satisfied. For every admissible cut query, continuity guarantees existence and strict increase guarantees uniqueness, including the boundary cases \(a=0\), \(a=1-F_i(x)\), and \(x=1\). The theorem’s model supplies the same query answers as the task’s model.

• Simulation of the society protocol. Fixing an allowed \(d\) makes every supplied input datum rational: the support size, masses, and finitely many binary digits encoding \(d\). These can be supplied within a protocol with rational constants. Redirecting type queries to the corresponding individual agents preserves their arguments, admissibility, and answers. Identical arithmetic and comparisons then preserve register values and adaptive branch choices. The claimed induction is valid, and termination of the assumed execution is preserved.

• Output and contradiction. The simulated output consists of connected intervals with equal utilities by the already verified equation. Nonatomicity makes their common endpoint immaterial. Thus the assumed society protocol would produce exactly the division forbidden by the cited theorem. This establishes impossibility for every allowed fixed \(d\), irrespective of running time.

• Scope and feedback. The output addresses the support formulation and the parameters \(d,\tau,L\) without introducing a candidate-count parameter. No repair or additional clarification is required. The established result is exact-computation impossibility in the specified model; it is not a claim of completeness or hardness for a named complexity class.

⟨structured verdict parsed — rendered above⟩