| paper | d4-conf-aaai-2021-1417 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: NP-complete. The candidate statistic suffices. Tight uniform worst-case history memory is \(\Theta(\log s)\) with an external round counter, and \(\Theta(\log s+\log k)\) when execution position must also be retained. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) indivisible item types, a finite support \(T\) of unit-demand valuation types, per-capita supplies \(q_j\), and a finite rational prior over latent states \(\omega\) specifying type masses \(\mu^\omega_{g,t}\) in each of finitely many public cohorts \(g\), find an expected-welfare-maximizing sequential cohort pricing policy. Each round visits an unvisited cohort, posts item prices, allocates each buyer an integral utility-maximizing bundle subject to remaining supply, and observes only aggregate bundle masses. Determine whether the posterior over \(\omega\), aggregate allocations, remaining cohort masses, and supplies suffice for optimal continuation, and give tight policy-state bounds in \(m\), \(\tau=|T|\), the number of cohorts, the number of latent states, and input bit length \(L\).
An atomless buyer population with finitely many complete valuation types and publicly addressable cohorts, under a finite prior over correlated type-mass profiles. The mechanism chooses cohort order and price vectors; individual bundles remain integral, stocks scale per capita, and observations are aggregate purchases. The computational target is an optimal welfare policy and the memory needed to choose its next action.
Exact aggregate responses from a cohort may identify a finite latent composition after a negligible welfare-cost probe, unlike the paper’s one-agent-at-a-time observations.
fatal: False
The mirror covers Theorem 1’s policy-state sufficiency and memory question for correlated, unit-demand welfare maximization; it leaves the other propositions, experiments, and external revenue-hardness results aside.
The strongest defensible mirror is narrow: the information needed to design an optimal welfare-maximizing SPM for a correlated, high-multiplicity population. The paper does not give a numbered polynomial-time or hardness result for its main policy-design problem. Its best computational anchor is a memory-space result.
Theorem 1, proved in this paper, says that under correlated valuations, the allocation matrix together with the agents who have not yet received an offer is sufficient to determine an optimal policy, for any design objective. It also proves that, in some unit-demand setting with correlated valuations, an optimal policy needs information of size \(\Omega(\min\{n,m\}\log(\max\{n,m\}))\). The theorem is about the state information an optimal policy needs, not a runtime classification.
A continuous question I would hand to a prover is Correlated Fluid-SPM Policy Synthesis. An instance has \(m\) item types and a finite set \(T\) of complete unit-demand valuation types, with \(|T|=\tau\); each type specifies its value for every item. A normalized population has mass \(1\). A finite rational prior describes possible realized society distributions \(\mu^\omega\) over those types, where \(\omega\) is a latent market state. The mechanism knows the prior but not the realized state or agents’ private types. Item stocks are rational quantities \(q_j\) per unit of population, so each individual still receives at most one indivisible item even though aggregate allocations are fractional. In each infinitesimal round, the SPM selects an observable cohort with remaining mass and posts item prices; agents in the slice choose utility-maximizing bundles, and the mechanism observes the aggregate purchases and updates its information.
The task is to compute a welfare-maximizing policy and determine whether its optimal continuation can be represented by aggregate allocation masses \(A_{g,j}\), remaining cohort masses \(r_g\), and residual supplies. A solution is an exact policy in those state variables, together with an optimality certificate and a tight bound on the state description in \(m,\tau\), the prior size, and the input bit length; if those variables do not suffice, the solution gives an instance requiring more information and a corresponding lower bound. This mirrors the paper’s question about policy state, while making the population a mass distribution.
The regime is a large market with many buyers sharing a small menu of exact valuation profiles—for example, standardized buyer roles in a replenishment market—with an economy-wide latent demand regime correlating the type masses. Then \(N\) can be far larger than \(\tau\), while the mechanism still has to infer useful information from purchases. Treating the valuation vector as part of the type matters: agents of the same type have the same preferences, and the population can contain large masses of each type.
For this restricted finite-support version, I expect Class A: finitely many valuation types and price-response patterns make a finite-dimensional continuous-control formulation plausible. That is a conjecture, not a consequence of Theorem 1; the paper shows that nonlinear policies can be necessary, so a simple LP is not assured. Hardness transfer is not supported by this anchor.
This mirror covers the paper’s state-information result for correlated valuations and unit-demand welfare optimization. It does not claim a mirror for the RL experiments, the other objectives, or the external revenue-hardness results cited in the introduction.
The weak point is that Theorem 1’s lower-bound construction uses many structurally distinct agents. Its \(\Omega(n\log m)\) information bound does not automatically survive when repeated agents collapse into a fixed number of types. The continuous question is whether the information requirement compresses to a bound in \(\tau\), or whether correlated mass states preserve a comparable lower bound. If the authors do not regard the prior over hidden society distributions and the mass-round SPM as their policy-design problem, the mirror will not hold.
Theorem 1 is the proponent’s strongest anchor, but its lower bound comes from remembering a matching among named agents and items. In the proof, the valuation pattern of each agent encodes which item was assigned to that agent; the right price for a later offer depends on that matching. With a fixed small set of complete types, those distinct identities collapse into interchangeable mass, so the matching information—and the \(\Omega(\min\{n,m\}\log(\max\{n,m\}))\) bound it supports—does not carry over. Preserving the construction by giving each role its own type makes the support grow with the population, removing the high-multiplicity premise.
The proposed finite-prior version does not restore that result. It adds uncertainty over latent societies, which is a reasonable way to model the paper’s correlated valuations, but it changes what the policy learns. Offer a menu to a positive-mass cohort and its aggregate response reveals exact type proportions in that cohort; for finitely many latent states, a separating offer can identify the state after probing an arbitrarily small mass. The welfare cost of the probe can then approach zero. If offers instead go to infinitesimal individuals to preserve the paper’s noisy, one-agent-at-a-time observations, the model needs a continuous-time control process rather than the paper’s finite sequence of rounds. And if the mirror preserves the matching correlations that drive Theorem 1, it again needs identity-level distinctions or a support that grows with the population.
So the proposed state-sufficiency problem may be interesting as a new fluid-control or Bayesian POMDP question, but its central computational issue is no longer the named result in Theorem 1. I cannot honestly rule out every worthwhile continuous SPM model: large markets with repeated buyer roles are plausible, and the paper’s adaptive design objective could transfer. The negative case is therefore strongest against this anchor, not a proof that no scenario could justify study.
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.