| paper | d4-journals-jair-2026-0004 |
| 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. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.7
statement extracted from the paper’s text layer
Given finitely many types \(t\) with rational masses \(\mu_t\) summing to \(1\), and strictly positive normalized rational piecewise-constant densities \(f_{tj}\) on common cake cells \(I_j\) of lengths \(d_j\), decide whether there are masses \(r_{tj}\ge 0\) such that \(\sum_j r_{tj}=\mu_t\), \(\sum_t r_{tj}>0\), and \(\sum_t r_{tj}/f_{tj}<d_j\) for every cell \(j\). This asks whether a unit-mass population of repeated types can receive connected infinitesimal shares whose utility, scaled by population size, is strictly greater than the equal per-capita entitlement.
A unit-mass population with type distribution \(\mu\); each type has a complete valuation description given by its density \(f_t\). Variables \(r_{tj}\) assign type mass to cake cells, and each type-cell cohort receives a contiguous block that can be divided into infinitesimal connected shares with scaled utility above \(1\).
The LP’s cell-by-cell construction is not shown to capture finite allocations where agents cross cell boundaries or vanishingly small cohorts receive large pieces, so the claimed finite-population bridge remains unproved.
fatal: False
The mirror covers the hungry, equal-entitlement cake-allocation decision and construction addressed by Theorem 3.7, using explicit rational type densities; it leaves arbitrary valuation oracles, non-hungry agents, unequal entitlements, and the pie result aside.
The strongest mirror I believe is for the hungry, equal-entitlement case. The anchor is Theorem 3.7, proved in this paper: for \(n\) hungry agents with equal entitlements, deciding whether a connected super-proportional allocation exists—or computing one when it does—requires \(\Theta(n^2)\) Robertson–Webb queries. This is an oracle query bound, not an NP-hardness or ordinary Turing-time result; the paper’s relevant computational lower bound is the one its cake-cutting model actually measures.
Here is a finite-type limit of that problem. Let the types be complete valuation descriptions: everyone of type \(t\) has the same normalized value density \(f_t\) and the same entitlement parameter \(q_t\). The population is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\) and \(\sum_t\mu_tq_t=1\). For the direct mirror of Theorem 3.7, set every \(q_t=1\). Assume each \(f_t\) is a strictly positive, rational, piecewise-constant density on the cake, specified on a common partition \(I_1,\ldots,I_K\); write \(d_j=|I_j|\) and let \(f_{tj}\) be type \(t\)’s density on cell \(I_j\).
Call the decision problem Finite-Type Connected Super-Proportionality. In a population of size \(N\), type \(t\) represents \(N\mu_t\) agents, each with entitlement \(q_t/N\). The question is whether the population can be allocated the whole cake in connected pieces so every agent gets value strictly above their entitlement. A continuous solution is a mass allocation \(r_{tj}\): the fraction of the whole population of type \(t\) assigned within cell \(j\). It must satisfy \(\sum_j r_{tj}=\mu_t\). In each cell, the cake is split into blocks for its assigned type cohorts, and each block is divided into connected pieces for the agents in that cohort.
This decision has a compact LP certificate. Maximize \(\epsilon\), subject to \(r_{tj}\ge 0\), \(\sum_j r_{tj}=\mu_t\), and, for each cell \(j\),
\[
\sum_t \frac{q_t}{f_{tj}}r_{tj}+\epsilon\le d_j,
\qquad
\sum_t r_{tj}\ge\epsilon.
\]
The answer is yes exactly when the optimum is positive. The first cell constraint leaves enough cake to give every assigned cohort strictly more than its entitlement; the second ensures that every cell is assigned to population mass. With positive slack, split the remaining cell length among its active cohorts. A type-\(t\) cohort of mass \(r_{tj}\) then gets a block of length \(\ell_{tj}>q_t r_{tj}/f_{tj}\). Each of its \(Nr_{tj}\) agents can receive a connected subinterval worth \(f_{tj}\ell_{tj}/(Nr_{tj})>q_t/N\). For rational inputs this is an LP of size polynomial in \(\tau\), \(K\), and the input bit length. So my prediction for this stated, explicit-input problem is Class A.
The regime is a large population of users or teams dividing a time-based resource, where people with the same usage pattern and entitlement recur many times. For example, many service users might value different periods according to a small catalogue of schedules, and each needs one uninterrupted time slot. Here \(N\) grows while the number \(\tau\) of distinct types stays moderate. The finite population is replaced by type masses; the cake remains divisible, as it already is in the paper. The per-capita entitlement \(q_t/N\) and infinitesimal connected slices are the scaling forced by that population limit.
This is recognizably the authors’ allocation question: do all agents get connected pieces worth more than their proportional entitlements? In a cohort block, the individuals still receive separate contiguous pieces; mass describes how many agents of a type there are, not a fractional outcome for an agent. The LP predicts when the quadratic query burden in Theorem 3.7 can collapse to dependence on the number and description of types in this high-multiplicity regime. A useful bridge theorem would show that positive LP slack gives finite connected allocations for all sufficiently large compatible \(N\), and then characterize what happens when the slack tends to zero.
The weak point is real: Theorem 3.7 allows arbitrary individual valuation oracles, while this mirror groups identical agents and gives each type’s piecewise-constant density explicitly. Its lower bound therefore does not imply an LP lower bound—or its dissolution—in this representation. Nor does the LP claim to cover arbitrary valuation functions or every finite allocation pattern. I consider that a fair limit on scope: the question is whether the authors’ connected super-proportionality problem becomes tractable in a clear, large-population regime with finite type support. The paper’s pie result is outside this case; its impossibility is tied to pie topology and oracle access, rather than to population multiplicity.
Theorem 3.7 is a genuine computational result, and repeated valuation types are plausible here. The strongest negative case is that the proposed LP does not mirror the theorem’s computational question.
The theorem measures Robertson–Webb queries to learn arbitrary valuation functions. Its lower bound uses the freedom to hide changes in an individual’s valuation between queried points. The proposed problem supplies each type’s full, explicit density table instead. Once agents are grouped by identical types, the input and information model have changed: the theorem’s \(n\)-dependent query lower bound says nothing about the LP’s running time in \(\tau\), \(K\), and \(L\). Keeping oracle access per type would preserve the paper’s information model, but would leave the continuous problem without the proposed finite binary input or LP.
There is also a gap between the LP and the paper’s allocation problem. The LP assigns each agent to one cell, so their entire piece lies within that cell. The paper permits a piece to cross cell boundaries. Positive LP slack gives a sufficient cellwise construction, but the paper’s theorem does not show that every feasible connected allocation has such a construction. The parameter \(\epsilon>0\) also asks for positive aggregate slack; finite instances require strict improvement for every agent, with no uniform lower bound on the size of that improvement. A bridge from the LP to exact finite feasibility would need to address both differences.
A stronger formulation could retain cross-cell pieces by representing the left-to-right order of agents along the cake. If \(a\) is population rank and \(x(a)\) is the corresponding cake position, the scaled value of a small piece for type \(t\) is locally described by \(f_t(x(a))x'(a)\). This could yield a coherent continuum model, but it requires an ordering variable and pointwise local constraints. The type masses alone do not give the LP’s claimed characterization, and the resulting problem no longer inherits the theorem’s query-complexity bound.
So I would reject the stated LP as an exact mirror of Theorem 3.7. The honest negative case is weaker against the broader claim: an ordered, scaled-utility model could still be worthwhile if the authors recognize it as their problem and establish a finite-population bridge. The main concern is that the proponent has presented a tractable restricted construction, while the paper’s result concerns the cost of discovering arbitrary valuations.
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.