| paper | d4-conf-aaai-2010-0376 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: The continuous allocation-feasibility problem is in \(\mathrm{P}\), with deterministic bit running time \(\bigl((m+\tau)K+L\bigr)^{O(1)}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given item kinds \(X\), a finite set \(T\) of buyer types with rational masses \(\mu_t\), posted prices \(p\), explicitly listed integral-bundle demand families \(D_t(p)\), and rational per-capita supplies \(q_a\), decide whether nonnegative assignment masses \(\lambda_{tB}\) exist such that \(\sum_{B\in D_t(p)}\lambda_{tB}=\mu_t\) for every \(t\), and \(\sum_{t\in T}\sum_{\substack{B\in D_t(p)\a\in B}}\lambda_{tB}=q_a\) for every \(a\in X\).
A high-multiplicity market has a distribution \(\mu\) over complete valuation types; each buyer receives an integral bundle demanded at the posted prices, while \(\lambda_{tB}\) records the mass of type \(t\) assigned bundle \(B\). Item-kind supplies scale per capita, and the question is whether all type mass and supply can be exactly cleared.
The mirror covers Proposition 1's efficient allocation problem at fixed posted prices. It leaves the Lyapunov minimization result, the GSC auction convergence theorem, and the full dynamic procedure aside.
My lead is the paper’s Proposition 1, proved in the paper: the efficient allocation problem (EAP) is \(\mathrm{NP}\)-complete. EAP asks whether the buyers can each receive a bundle they demand at the current prices while every item is allocated. The paper proves membership in \(\mathrm{NP}\) by checking a proposed allocation, and proves hardness by reducing from EXACT COVER: buyers share the same demand family, and choosing demanded bundles that allocate every item corresponds to finding an exact cover.
A natural high-multiplicity setting is a large procurement market: many branches buy bundles of item kinds from replenished stock, and their complete bundle valuations fall into a modest number of purchasing types. A type \(t\) records the full valuation \(u_t\), so agents of that type have the same demands at any given prices. Let \(\mu_t\) be the fraction of the population with type \(t\), and let \(q_a\) be the per-capita supply of item kind \(a\). Stock scales with population: a market of \(N\) branches has \(Nq_a\) copies of item \(a\). Each branch still receives an integral bundle; only the aggregate mass assigned to each bundle is continuous.
I would hand a prover this problem, named Continuous Efficient Allocation (\(\mathrm{EAP}_\infty\)). The input is a finite item set \(X\); supported types \(T\) with positive rational masses \(\mu_t\) summing to \(1\); posted prices and each type’s demand family \(D_t(p)\), given as an explicit list of bundles; and rational per-capita supplies \(q_a\). Decide whether there are nonnegative masses \(\lambda_{tB}\), where \(\lambda_{tB}\) is the fraction of the whole population of type \(t\) assigned bundle \(B\), such that
\[ \sum_{B\in D_t(p)} \lambda_{tB}=\mu_t \quad\text{for every }t\in T, \qquad \sum_{t\in T}\sum_{\substack{B\in D_t(p)\\a\in B}}\lambda_{tB}=q_a \quad\text{for every }a\in X. \]
The solution is such a mass assignment. There is no optimization objective: this is the paper’s feasibility question, with demand bundles still integral for every agent and all stock exactly allocated. With explicitly listed demand families, these constraints form a rational linear program, so I expect this mirror to be tractable—Class A. The exact-cover combinatorics in the discrete proof become fractional mass choices among bundles. If demands are represented implicitly instead, the pricing problem for finding useful bundles may itself be hard; that is a further question, not settled by this LP.
The finite-to-continuous link is direct for replicated markets. Any discrete allocation in a market of \(N\) agents induces masses in multiples of \(1/N\). Conversely, a rational feasible \(\lambda\) is realized exactly by a sufficiently large replication whose size clears the denominators of the type masses, supplies, and assignment masses. The continuous question is therefore a high-multiplicity version of the same demand-and-clearance problem.
The scope here is deliberately narrow: it mirrors Proposition 1’s EAP, not the paper’s GSC price-adjustment theorem or the full dynamic auction. The weakest point is the supply co-modification. Proposition 1 is stated for a finite set of single-copy items; a nondegenerate large-market mirror needs item-kind stocks to scale with population. An author could regard that as a materially different market regime. I think the mirror remains credible because the decision being studied—whether current demands can be assembled into a clearing allocation—is preserved, while repeated, replenished stock is natural in the procurement scenario.
Proposition 1 is the strongest anchor, and I can make a case against the proposed mirror—but it does not defeat the better version. With the paper’s fixed finite stock, increasing the buyer population does not give a nondegenerate limit: at most \(|X|\) buyers can receive nonempty bundles, so the fraction served tends to zero. The per-capita supplies \(q_a\) therefore tend to zero as well. To avoid that collapse, the mirror must scale the stock with the population. That is a meaningful change to the seller’s side of the market: the paper sells a fixed set of indivisible items, while the mirror studies recurring item kinds with replenished stock.
The proposed \(\mathrm{EAP}_\infty\) also makes the demand families explicit. Its question is then fractional feasibility over type–bundle pairs, a generic rational LP; it does not need the paper’s auction procedure, GSC structure, or pricing machinery. The continuous mirror thus gets its tractability by allowing a type’s mass to split across demanded bundles, after changing the supply regime. That gives a skeptic grounds to doubt its contribution to this paper’s computational story.
But those points fall short of showing there is no worthwhile mirror. Scaling stock is precisely the kind of co-modification the programme allows, and repeated buyers served from replenished stock are plausible. Splitting a type’s mass across bundles preserves integral bundles for individuals while making aggregate feasibility continuous. Proposition 1 is a named computational result, and its exact-cover feasibility question has a clear high-multiplicity counterpart. The negative case is therefore weak: it can question whether the authors would see the scaled-stock version as their problem, but it cannot rule out a sensible continuous mirror.
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.