d4-conf-ecai-2024-0492

Answer: Under the supplied exact equivalence and Robertson–Webb query model, decision and construction query complexities are both \(\Theta(\tau 2^\tau)\).

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given \(\tau\) types of equal mass \(\mu_t=1/\tau\), each with a normalized nonatomic valuation \(V_t\) available through eval and right-mark queries, decide whether the interval can be partitioned into one contiguous interval \(I_t\) per type with \(V_t(I_t)>\mu_t\) for every \(t\), and compute such a partition if it exists.

Packaged proof task (what the prover saw — nothing else)

No faithful open proof task is available: the stated type-mass problem is exactly connected strongly-proportional cake-cutting with \(n=\tau\) and equal entitlements. Its decision and construction query complexities are already \(\Theta(\tau 2^\tau)\). [Verified source](https://arxiv.org/html/2312.15326v4#S4.Thmtheorem7).

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Verified result and scope

The cited result confirms the stated query complexity: Theorem 4.7 of Jankó, Joó, Segal-Halevi, and Yuen gives \(\Theta(n2^n)\) queries for deciding existence and computing a connected strongly-proportional allocation when one exists, including equal entitlements. [Theorem 4.7](https://arxiv.org/html/2312.15326v4#S4.Thmtheorem7)

The hypotheses are normalized, nonnegative, finitely additive valuations on \([0,1]\), with continuous cumulative valuation functions. Access is through Robertson–Webb evaluation and marking queries; the paper specifies rightmost marks. General valuations may assign zero value to intervals. [Section 2](https://arxiv.org/html/2312.15326v4#S2)

Application to the supplied premise

The task supplies the exact equivalence with the type-mass problem; it does not separately define that problem. Accordingly, the equivalence is a given premise, rather than an independently verified conclusion here.

Under that premise, associate type \(i\) with agent \(i\), retain its valuation \(\mu_i\), and set \(n=\tau\) and \(w_i=1/\tau\). Feasibility then means that a connected allocation \((X_1,\ldots,X_\tau)\) satisfies
\[ \mu_i(X_i)>\frac{1}{\tau} \qquad\text{for every }i\in\{1,\ldots,\tau\}. \]
This is precisely strong proportionality with equal entitlements.

Because the supplied equivalence identifies both admissible instances and query access, every query and output can be transferred in either direction without additional oracle queries. Thus an upper bound transfers from cake-cutting to type-mass, and a lower bound transfers in the reverse direction. Substituting \(n=\tau\) into Theorem 4.7 yields \(\Theta(\tau2^\tau)\) for both tasks.

Conclusion

Under the exact equivalence stated in the task, the complexity question is already settled. The general-valuation hypothesis matters: for hungry agents, whose valuations are positive on every interval of positive length, equal entitlements instead give \(\Theta(n^2)\). [Theorem 3.5](https://arxiv.org/html/2312.15326v4#S3.Thmtheorem5)

No new open mathematical claim has been specified.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

The output is correct in substance, with a minor clarification needed about the query model. It accurately reports the cited results and addresses the supplied task, which already states the equivalence and complexity conclusion.

Theorem 4.7 is correctly reported. The theorem gives worst-case query complexity \(\Theta(n2^n)\) for deciding existence and computing a connected strongly-proportional allocation if one exists, including equal entitlements. Thus the prover correctly includes both decision and construction. [Theorem 4.7](https://arxiv.org/html/2312.15326v4#S4.Thmtheorem7)

The valuation hypotheses match the source. Normalization, nonnegativity, finite additivity, and continuity of cumulative valuations are the paper’s assumptions. Valuations are defined on the algebra generated by intervals. General agents may value positive-length intervals at zero. The specified oracle uses evaluation queries and rightmost marking queries, with an infinity response when the requested value is unavailable. The prover’s abbreviated description is accurate. [Section 2](https://arxiv.org/html/2312.15326v4#S2)

The equal-entitlement substitution is valid. Taking \(n=\tau\) and \(w_i=1/\tau\) gives exactly the inequalities written by the prover. Here \(\tau\) is naturally a positive integer counting types. “Connected allocation” must retain the cited definition: a partition of the entire cake into one interval per agent, allowing shared endpoints. The prover’s use of the established term is sufficient; the displayed inequalities are fairness conditions within that definition.

Treating the equivalence as a premise is appropriate. USER_TASK expressly asserts exact equivalence and provides no independent definition of the type-mass problem. The prover correctly distinguishes accepting that premise from independently verifying it.

Minor issue: The sentence “Because the supplied equivalence identifies both admissible instances and query access” makes the oracle interpretation more explicit than USER_TASK does. Mathematical equivalence of feasible allocations alone would not establish query-preserving equivalence. In context, however, USER_TASK already asserts the query complexity, and the prover expressly conditions its conclusion on the Robertson–Webb model.

Minimum clarification: State that “exact equivalence” is being interpreted as including the same admissible valuation class and query access, with the asserted transfer requiring no additional oracle queries. No new proof of equivalence is required against this supplied premise.

The complexity transfer follows under that interpretation. Query-preserving transfer in both directions carries the upper and lower bounds to the corresponding type-mass tasks. Substitution yields \(\Theta(\tau2^\tau)\). This is an asymptotic worst-case statement, not a claim that every instance requires that many queries. The edge case \(\tau=1\), where strict proportionality is impossible under normalization, does not contradict the asymptotic result.

The hungry-agent qualification is correct. Theorem 3.5 gives \(\Theta(n^2)\) for hungry agents with equal entitlements. This correctly identifies why restricting the admissible valuations could change the bound. [Theorem 3.5](https://arxiv.org/html/2312.15326v4#S3.Thmtheorem5)

The output establishes the stated oracle query complexity under the supplied equivalence. It does not establish a classification for finitely encoded inputs or hardness for a complexity class. Accordingly, the continuous-status category below is “other.”