| paper | d4-conf-aaai-2004-0046 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given two paths with resource categories \(I\), a finite support \(T\) of bid types with rational masses \(\mu_t>0\) summing to \(1\), packages \(S_t\subseteq I\) that are unions of at most one interval from each path, prices \(p_t\), per-capita supplies \(\sigma_i\), and a revenue threshold \(R\), decide whether accepted masses \(y_t\) exist such that \(0\le y_t\le\mu_t\), \(\sum_{t:i\in S_t}y_t\le\sigma_i\) for every \(i\in I\), and \(\sum_{t\in T}p_ty_t\ge R\). Each individual receives the whole package or nothing; \(y_t\) is the accepted mass of type \(t\).
Buyer types \(t=(S_t,p_t)\) carry mass \(\mu_t\); resource categories on the two paths have per-capita capacities \(\sigma_i\). Choose accepted masses \(y_t\) to maximize revenue \(\sum_{t\in T}p_ty_t\), subject to type-mass and resource-capacity constraints.
Covers Theorem 4's revenue-threshold clearing result for two paths and bids using at most one interval from each path; leaves Theorems 1–3, Theorem 5, and the graph-construction results unmirrored.
The lead mirror I believe in is the two-path continuum clearing problem, anchored on Theorem 4, proved in this paper by reduction from VERTEXCOVER. Theorem 4 says that, when the item graph consists of two disjoint paths and each bid may combine at most one interval from each path, deciding whether an allocation can achieve revenue at least \(r\) is NP-complete.
A plausible regime is a replicated procurement market with many buyers but relatively few bid archetypes: \(n\gg\tau\), where each type specifies a package and a bid value, and \(\mu_t\) is its population share. The items are resource categories arranged along two paths, and each package uses at most one contiguous interval from each path. As the market grows, stock of each resource category scales with the population; let \(\sigma_i\) be its per-capita supply. This co-modification gives the market a meaningful large-population limit.
Here is the question I would hand to a prover. Given the two paths, a finite support of bid types \(t\) with rational masses \(\mu_t>0\) summing to \(1\), package \(S_t\), bid value \(p_t\), per-capita supplies \(\sigma_i\), and threshold \(R\), can the auctioneer obtain revenue at least \(R\) per capita? A solution is a vector \(y_t\), where \(y_t\) is the mass of type \(t\) whose bid is accepted, satisfying
\[
0\le y_t\le\mu_t,\qquad
\sum_{t:\,i\in S_t}y_t\le\sigma_i\quad\text{for every item }i,\qquad
\sum_t p_t y_t\ge R.
\]
Each individual receives either the whole package or nothing; \(y_t\) records the accepted share of an indistinguishable cohort. The instance is finite and rational, with running time measured in the number of item categories, support size \(\tau\), and input bit length.
I expect this mirror to be tractable: it is a linear program with one variable per bid type and one capacity constraint per item. The bridge is direct for replicated markets: finite counts of bidders and item copies normalize to \(\mu_t\) and \(\sigma_i\), and scaling rational masses and supplies clears denominators. The result is therefore a fluid clearing question for the same package geometry and revenue objective, while allowing a cohort to split across winning and losing agents.
The soft spot is the supply co-modification. The paper’s theorem concerns distinct, indivisible items; this mirror treats them as resource categories whose stocks grow with the market. That is a real modeling choice, though it keeps each agent’s bundle indivisible and preserves the theorem’s two-path package structure and winner-determination question. If the authors regard replicated-resource clearing as their problem, this is a strong population mirror. If they require a fixed stock of named items, the case weakens sharply.
This covers Theorem 4’s clearing result and its two-path setting. It does not mirror the paper’s graph-construction results. Further questions include how well the LP can be rounded for large finite markets, what changes with multiple bids per agent or XOR constraints, and whether similar fluid algorithms apply to broader item graphs.
I can’t make a persuasive case against the Theorem 4 mirror. The strongest objection is that the paper has distinct, indivisible items, while the proposed version gives item categories per-capita supplies. But that is a natural co-modification for a replicated market, and the paper studies clearing, not an objective that tracks the identity of who receives each item.
The improved mirror survives that objection: replicate buyers of each package-and-price type and scale supplies along the two paths. Each buyer still receives the whole package or nothing; \(y_t\) records the accepted mass of indistinguishable buyers. For rational masses and supplies, scaling gives finite instances of the same market, and rounding accepted counts down by type loses only a bounded amount of revenue when the support is fixed. The normalized loss vanishes as the market grows. The resulting per-capita clearing question is a well-defined fluid limit of the paper’s problem, with an LP over the listed bid types.
One can object that this changes unique goods into scalable stock, or that the LP may make the answer easy. Neither defeats the mirror: the first is the permitted supply co-modification, and the second concerns the answer rather than whether the question is worth asking. The negative case is therefore weak. This anchor survives, so I cannot honestly support the claim that no worthwhile continuous mirror exists for this paper.
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.