| paper | d4-conf-sagt-2024-0017 |
| 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.1
Given a rational type distribution \(\mu\) over strict rankings of \(K\) item classes, a finite piecewise-constant schedule \(\sigma:[0,1]\to T\) with \(|\{s:\sigma(s)=t\}|=\mu_t\), and rational per-capita supplies \(b_j\) with \(\sum_j b_j=R\), compute the limiting bundle masses \(x_{t,\mathbf{k}}\). The schedule repeats for \(R\) rounds; in each finite approximation, \(q\mu_t\) agents of type \(t\) take turns in schedule order and each item class has \(qb_j\) indivisible copies. Each agent takes her highest-ranked class still available on her turn. Output the limiting mass of each type receiving each integral bundle \(\mathbf{k}\in\mathbb{N}^K\), using noiseless comparison oracles for the type rankings.
A population of ranking types with masses \(\mu_t\), moving through a fixed repeated schedule over \([0,1]\), faces per-capita supplies \(b_j\) of item classes. Each position in the schedule keeps its type and accumulated integral bundle across rounds. The algorithm computes the limit of finite round-robin allocations and reports \(x_{t,\mathbf{k}}\), the mass of each type receiving bundle \(\mathbf{k}\).
The mirror restricts the roster to a fixed piecewise-constant cohort schedule, and its shared type oracles do not preserve Theorem 3.1’s query dependence on separately accessible agents; the proponent acknowledges these limits, and they bound rather than eliminate the proposed question.
fatal: False
Covers Theorem 3.1’s noiseless algorithmic allocation question in a structured cohort regime. It leaves the paper’s random-preference result, query lower bounds, and noisy-query bounds aside; the original query bounds do not transfer to shared type oracles.
The strongest positive case is narrow: the paper’s round-robin *procedure* has a credible high-multiplicity version, even though its individual query bounds do not transfer directly.
My anchor is Theorem 3.1, proved in this paper. It says that with a fixed cyclic order of \(n\) agents, \(m\ge n\) items, strict rankings, and noiseless comparison queries, a deterministic algorithm can output the round-robin allocation using \(O(nm\log(m/n))\) queries and time. [Theorem 3.1](https://arxiv.org/html/2404.19402) is an algorithmic anchor; the paper’s query lower bounds are not conventional NP-hardness results.
A continuous counterpart I would put to the authors is the Cohort Round-Robin Query Problem. Its society is a rational distribution \(\mu\) over \(\tau\) strict ranking types on \(K\) item classes. A public, piecewise-constant turn schedule specifies the order of those types through one round, with type \(t\) appearing for total mass \(\mu_t\); the same schedule repeats each round. Each class \(j\) has rational per-capita stock \(b_j\), with \(\sum_j b_j=R\) for fixed \(R\). In a finite approximation with \(q\) agents, there are \(q\mu_t\) agents of type \(t\) and \(qb_j\) indivisible copies of class \(j\). Each turn, an agent takes her highest-ranked class with a copy remaining. The type rankings are accessed through noiseless comparison queries, one oracle per type.
The requested output is the exact limiting allocation \(x_{t,\mathbf{k}}\): the mass of type \(t\) whose members receive \(\mathbf{k}\in\mathbb{N}^K\) copies across the \(R\) rounds. Each person still receives an integral bundle; for example, the output must satisfy \(\sum_{\mathbf{k}}x_{t,\mathbf{k}}=\mu_t\) and \(\sum_{t,\mathbf{k}}x_{t,\mathbf{k}}k_j=b_j\). The computational question is to produce this allocation from the type-level comparison oracles, with query and arithmetic complexity measured in \(K,\tau\), the schedule size, and the rational input bit length.
This is a plausible regime for a large recurring allocation among cohorts whose members share rankings over standardized goods, with supplies scaling per capita and a fixed public turn order. The number of people \(q\) grows while \(\tau\) remains small. It is a recognizable version of the paper’s problem because every finite approximation runs the ordinary round-robin procedure; the continuous output records the limiting mass of each type receiving each integral bundle. The move to per-capita supplies and fractional type-level averages is the co-modification that makes a population limit possible.
I expect this version to be tractable: elicit each of the \(\tau\) rankings, then simulate the continuous process as stock is depleted. For fixed \(R\), the simulation has finitely many depletion events per schedule segment and round. A further question is whether the paper’s partial-sorting ideas yield a sharper query bound than sorting every type’s full ranking, and how much finite-\(q\) error is needed to approximate the limiting allocation.
The mirror covers Theorem 3.1’s noiseless algorithmic question, not the paper’s noisy-query bounds or its lower bounds. Its weakest point is that it asks for an anonymous type-and-bundle allocation and gives the schedule an explicit continuous representation; Theorem 3.1 instead outputs a named allocation for a finite agent order. A referee could regard the cohort process as a new high-multiplicity variant rather than a direct limit of that theorem. The positive case rests on the fact that the finite approximants preserve the paper’s exact picking rule, while the population and output are aggregated.
The strongest objection to Theorem 3.1’s mirror is that round-robin uses an ordered roster, while a society \(\mu\) over ranking types records no roster positions. Position changes the allocation even when preferences and type masses stay fixed. For example, take types \(A:x\succ y\succ z\succ w\) and \(B:x\succ z\succ y\succ w\), with equal mass and \(1/2\) per-capita supply of each item. With the order \(A,B\) repeated twice, the two-type allocation is \(A:\{x,y\}\), \(B:\{z,w\}\). Reversing the order gives \(B:\{x,z\}\), \(A:\{y,w\}\). The same \(\mu\) and supplies therefore produce different type-level bundle distributions.
A faithful input must carry the turn schedule as well as \(\mu\). For an arbitrary roster, encoding that schedule can take size proportional to the population: the type sequence may alternate at every position. Treating position as part of a complete type has the same problem, since positions then distinguish agents and the support can grow with \(q\). The proponent’s fixed, piecewise-constant schedule avoids that growth only by restricting the problem to specially ordered cohorts. That is a coherent variant, but it is narrower than the paper’s fixed-roster problem.
The query model also shifts. With explicit support, each ranking is part of the type description, so the paper’s preference-query cost disappears. With one oracle per type, the cost is for learning \(\tau\) rankings, rather than the paper’s queries across \(n\) separately accessible agents. This does not make the proposed continuous question ill-posed; it means the theorem’s query bounds are not the computational question being mirrored.
That is the best negative case, but it does not eliminate the block-cohort scenario. Its finite approximants follow the same picking rule, and aggregating their integral bundles is a defensible continuous output. The question may be a useful new variant even if it does not preserve Theorem 3.1’s query-complexity contribution. I cannot honestly claim that no worthwhile mirror exists; the negative case is weak precisely at this plausible cohort construction.
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.