| paper | d4-conf-wine-2023-0009 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→split discrete result → its continuous mirror
Answer: No everywhere-terminating exact Robertson–Webb protocol exists, so worst-case query complexity has no finite bound. Explicit rational piecewise-constant densities admit polynomial-time feasibility testing and an output-polynomial allocation construction using zero Robertson–Webb queries. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
Given a distinguished root with a valuation oracle, a finite support \(\Theta\) of branch types with rational masses \(\mu_\theta\), and a specified cake-capacity measure \(\sigma\) that accounts for per-capita branch supply and the root’s bundle, compute a locally envy-free allocation. A type records its manager’s valuation and whether it has a leaf, including that leaf’s valuation. The output is a root bundle and, for each type, a finite-support distribution over deterministic manager–leaf bundle assignments; every realized assignment must satisfy the paper’s local envy inequalities, and total mass-weighted cake use plus the root’s use must respect \(\sigma\). What is the Robertson–Webb query complexity in \(\tau=|\Theta|\), the input bit length \(L\), and output size \(S\)?
A distinguished root is connected to a continuum of branches with types \(\theta\) and masses \(\mu_\theta\). Each branch has a manager and at most one leaf. Type valuations are complete additive nonatomic valuation oracles; a mass distribution over deterministic bundle assignments preserves each individual envy comparison. A specified capacity measure \(\sigma\) makes aggregate resource use meaningful, and the objective is to minimize cut and evaluation queries needed to produce a finite-description locally envy-free allocation.
The proposed per-capita supply is not specified as a precise capacity measure, including how the distinguished root’s consumption scales; this leaves feasibility and nontriviality to formalize.
fatal: False
The mirror covers Theorem 4 on \(2\)-Stars and Theorem 3 on depth-two trees; it leaves the general-tree query bound and fixed-agent demonstrations aside.
There is a credible, narrow positive case. The paper already makes the cake divisible; the mirror’s contribution would be to make the population mass-valued while keeping the local envy constraints and Robertson–Webb query question.
The strongest anchor is Theorem 4, proved in the paper: for \(n\) agents on a \(2\)-Star—one root, with each other agent connected to the root and to at most one leaf—the paper gives a discrete protocol that finds a locally envy-free allocation using \(O(n^2)\) cut queries and \(O(n^3)\) evaluation queries. The broader Theorem 3, also proved here, gives \(O(n^3\log n)\) cut queries and \(O(n^4\log n)\) evaluation queries for any tree of depth at most two. These are oracle-query bounds, not Turing-time classifications; the paper supplies algorithmic anchors, not hardness results. [The paper](https://arxiv.org/abs/2211.06458)
A plausible regime is a large network of resource-sharing offices: one central coordinator, many branch managers, and at most one directly connected representative per branch. Many branches may share the same valuation and structural profile. The population size \(N\) can then be much larger than the number \(\tau\) of distinct complete branch types. A type records the manager’s valuation, whether the branch has a leaf, and that leaf’s valuation if present. Mass \(\mu_\theta\) is the fraction of branches of type \(\theta\). The center remains a distinguished agent. This is a scenario-specific high-multiplicity claim, not a claim that all organizational networks have few types.
My lead problem would be the Mass-\(2\)-Star Local-Envy-Free RW Problem. Its input is a finite support of branch types with binary-rational masses summing to one, a root with its own valuation, and nonnegative additive nonatomic valuations for each type, accessed through cut and evaluation oracles. It also specifies a per-capita supply density over the cake, scaled with population size so that the aggregate resource constraint remains meaningful as \(N\) grows. A solution consists of the root’s bundle and a finite-description allocation rule assigning each branch an actual manager bundle and, when present, an actual leaf bundle. The rule may assign different bundles to different members of a type; its support records the mass receiving each bundle pair. It must respect aggregate supply and be locally envy-free for every realized branch assignment: the root weakly prefers its bundle to every manager bundle, each manager weakly prefers its own to the root’s and its paired leaf’s, and each leaf weakly prefers its own to its manager’s. Each person still receives a deterministic bundle; the mass distribution describes how many people receive each one.
The computational question is whether a protocol can produce such an allocation for every admissible typed \(2\)-Star instance with query complexity polynomial in \(\tau\), the mass and supply bit length \(L\), and the output description size \(S\), rather than in \(N\). I would expect a tractability result—Class A—for this restricted model. The paper’s trimming and residue arguments give a concrete starting point, and identical complete types let the model reuse oracle information. But Theorem 4’s \(O(n^2)\) and \(O(n^3)\) bounds do not themselves imply a bound in \(\tau\): adapting the protocol to mass-weighted branches and proving a compact output representation are the research questions.
Theorem 3 motivates a separate, broader Mass-Depth-2 Local-Envy-Free RW Problem: the same input and solution format, but each branch may contain a manager and any explicitly described finite set of leaves, with the branch type preserving their valuations and adjacency. Its question is the support-sensitive query complexity in \(\tau\), \(L\), and the type-incidence description. I would also expect tractability when that description is controlled, though less confidently than for the \(2\)-Star case. Further questions include whether the allocation always has a polynomial-size mass description, how complexity depends on leaf multiplicities, and whether the \(2\)-Star bound extends to arbitrary depth-two profiles.
The authors should recognize these as their problems: the same locally envy-free inequalities, cake bundles, graph roles, and RW information access remain central. The mirror covers the \(2\)-Star and depth-two results, not the paper’s general-tree bound or its small fixed-agent demonstrations. It does not claim the cake’s divisibility as a novelty; the new object is a high-multiplicity population and the complexity of allocating to it.
The soft spot is that local envy is inherently about individual neighbors. A mass model must preserve branch pairings and require envy-freeness for each realized bundle assignment, rather than compare averages and call that fairness. Types therefore need to include the relevant neighborhood profile, which may make \(\tau\) large. The root also remains a distinguished agent as its population share tends to zero. These are real modeling choices, but they do not make the mirror incoherent: they identify exactly what the continuous formulation must retain.
The strongest case against a mirror is that the results are computational, but their population is not a dispensable multiplicity parameter. Theorem 4’s \(2\)-Star protocol and Theorem 3’s depth-two protocol answer Robertson–Webb query questions about partitioning one cake among finitely many named people. The cake is already divisible; the difficulty is assigning its pieces so the envy inequalities hold.
The type issue is sharper here than in voting. Each agent’s type must include their entire normalized, nonatomic valuation function over the cake. The paper assumes no finite catalogue of such functions. For generic valuations, exact types are all distinct, so \(\tau=n\); making \(\tau\ll n\) requires an added assumption that many people have precisely the same valuation. Repeated profiles could be plausible in a standardized institution, but they are not a regime supplied by this paper’s model.
More fundamentally, keep the paper’s fixed cake and let a positive mass of agents share one valuation \(v\). Their bundles must be pairwise disjoint. Since \(v([0,1])=1\), at most countably many disjoint bundles can have positive \(v\)-value: for each \(k\), only finitely many can have value at least \(1/k\). Thus almost every member of that type receives a zero-value bundle. If the root gets a bundle of positive value to them, those members envy the root. If the limit instead gives everyone zero-value bundles, the envy inequalities can become vacuous. The fixed-resource limit therefore loses the meaningful allocation guarantee that Theorems 3 and 4 establish.
The proposed remedy—scale supply with population and let each type receive a distribution over bundle pairs—can avoid that degeneration, but it changes the resource model. The paper partitions one cake; the new model allocates per-capita supply to a continuum of consumers. If that supply gives everyone a full copy, local envy is trivial. If it is scarce enough to keep allocation nontrivial, its density and constraints become new input primitives, and the resulting problem is a continuum exchange economy with local envy constraints. That may be worth studying, but the paper’s query bounds do not establish that this is a natural or useful continuization of their protocol problem.
The \(2\)-Star anchor also has a singular graph feature: one root is adjacent to every branch. Its population share tends to zero while its degree grows with the population. An ordinary type distribution or graphon loses those edges. Keeping the root as a special agent preserves the question, as the proponent suggests, but leaves a continuum of branches attached to an exceptional atom rather than a fully continuous population. The depth-two anchor has the same issue, with more branch structure to encode.
These points defeat a direct mirror of both named results, but they do not prove that no worthwhile mirror exists. A restricted setting with repeated valuation profiles and a deliberately specified, nontrivial per-capita supply could preserve the local envy constraints and ask a genuine support-sensitive query-complexity question. I cannot honestly rule that out: the case against is strong against the paper’s fixed-cake problem, but weak against that carefully re-modeled \(2\)-Star problem.
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.