| paper | d4-conf-sagt-2018-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A Robertson–Webb protocol always produces the required bundles using at most \(61\) cut queries and \(110\) evaluation queries; indeed, the literal overlap-permitting formulation admits a zero-query solution. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given four types \(T\), rational masses \(\mu_t>0\) summing to \(1\), and one normalized, additive, divisible valuation oracle \(v_t\) per type over \([0,1]\), can a Robertson–Webb protocol output bundles \(X_t\) that are finite unions of intervals, satisfy \(v_t(X_t)\ge v_t(X_s)\) for all \(t,s\), and meet \(\sum_t \mu_t \mathbf{1}_{X_t}(x)\le 1\) almost everywhere, using at most \(61\) cut queries and \(110\) evaluation queries? Theorem 1’s protocol answers this: its four output bundles partition the cake.
A unit-mass society with exactly four valuation types of masses \(\mu_t\), where each member of type \(t\) has valuation \(v_t\) and receives the same per-person bundle \(X_t\). Cake supply scales with population, giving pointwise capacity one after normalization: \(\sum_t\mu_t\mathbf{1}_{X_t}(x)\le1\). One valuation oracle per type suffices, and the paper’s four-agent protocol returns a partition satisfying envy-freeness across types.
Covers Theorem 1’s fixed four-agent bounded-query guarantee as a four-type cohort problem. It does not establish a variable-number-of-types result or population-dependent complexity; CORE and CORRECTION support the protocol rather than supplying separate population-level questions.
The best positive case is narrow: Four-Type High-Multiplicity Envy-Free Cake Cutting. Take a society of mass \(1\) with exactly four positive-mass types, \(\mu_t\in\mathbb{Q}_{>0}\), \(\sum_t\mu_t=1\). A type is a complete description of its members for this problem: they share the same normalized, additive, divisible valuation \(v_t\). Give the society a cake-like stock that scales with population—one copy of the cake per unit of population mass—and require each member of type \(t\) to receive the same per-person bundle \(X_t\). With capacity one per unit mass at each cake location, feasibility requires
\[
\sum_t \mu_t\,\mathbf{1}_{X_t}(x)\le 1
\quad\text{for almost every }x.
\]
The task is to produce bundles satisfying \(v_t(X_t)\ge v_t(X_s)\) for every pair of types \(t,s\). A solution is the four bundles, along with a protocol that produces them through Robertson–Webb cut and evaluation queries to the type valuation oracles. This is a bulk-allocation regime: the number of people can be very large while the number of distinct types remains four. The mass-scaled supply and type-constant bundles make the continuum population operational; the co-modification is part of the proposed mirror.
The anchor is Theorem 1, proved in this paper. It says that MAIN PROTOCOL returns an envy-free allocation for four agents and makes at most \(61\) cut queries and \(110\) evaluation queries. In the mirror, the four agents stand for the four valuation types, and their returned pieces become the per-person bundles for their respective populations. The pieces form a partition, so the proposed weighted capacity constraint is satisfied. The query count is independent of the population size and the binary encoding length of the masses; here \(\tau=4\). The article’s Theorems 2 and 3 establish properties and query bounds for the CORE and CORRECTION subroutines, but I would not count them as separate anchors: they support the main result rather than provide distinct mirror questions. The paper’s cited \(\Omega(n^2)\) lower bound is not a numbered result proved here, so it is not an anchor under the requested standard.
I expect this mirror to be tractable in the bounded-query sense of Theorem 1: the protocol can operate on one valuation oracle per type, regardless of how many members that type contains. The authors would recognize the valuation model, envy comparisons, and query model. The plausible scenario is a large population arranged into four genuinely homogeneous cohorts, each receiving a common per-person package from population-scaled stock. This mirrors only the paper’s four-agent protocol, not a general-\(n\) result or its cited lower bounds.
The weakest point is that the theorem never uses the masses: it gives four representative agents four pieces, and the masses enter only when interpreting those pieces as cohort bundles and checking resource capacity. The model also permits unused stock in the replicated supply. So this is a credible high-multiplicity reading of the four-agent problem, but it does not show that population continuization unlocks the query bound. The next questions are whether the protocol extends to a variable number \(\tau\) of types with a useful query bound, and whether an analogue remains possible with a fixed, genuinely shared cake supply and individual-level envy guarantees.
Theorem 1 is a real computational result: it gives a bounded Robertson–Webb query protocol, so “there is nothing computational to mirror” is not a defensible objection.
The strongest mirror is the proposed four-type society. Give each type a common valuation and bundle, and require envy-freeness between types. With population-weighted resource capacity, the paper’s four bundles are feasible because they partition the cake. A query to one valuation oracle per type is enough to run the protocol. Many people in each type therefore make a plausible high-multiplicity scenario; mass-scaled supply is a reasonable co-modification, not a formal flaw.
The negative case is that this mirror adds almost no new computational structure. Its input still reduces immediately to four valuation functions, and its output is still four bundles. The masses do not shape the protocol; because its bundles are disjoint, they impose no additional capacity conflict. That makes the continuous population look more like a bulk interpretation of the four-agent problem than a new problem over distributions. But this is a thinness argument, not a decisive objection: a well-posed mirror need not produce a different algorithm or answer.
A version where the masses substantially affect feasibility or the algorithm would be more distinctive, but the paper’s theorem does not establish such a result. Extending the question to a variable number of types would also go beyond this paper’s four-agent theorem. The CORE and CORRECTION query bounds have the same limitation: they operate on the same four roles and do not supply a separate population-level problem.
So the best case against is modest: this is a low-yield mirror, since the population axis contributes little to the theorem’s computational content. I cannot honestly make the stronger case that no worthwhile mirror exists. The four-type cohort scenario survives as a credible, if narrow, interpretation of Theorem 1.
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.