| paper | d4-conf-aaai-2000-0019 |
| 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 in \(m,\tau,L\), with an exact rational revenue-maximizing vector as output. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given an item DAG \(D=(V,E)\), rational per-capita supplies \(q_v\), and a finite support of buyer types \(t\), each with rational mass \(\mu_t\), price \(p_t\), and a bundle \(S_t\) that is a subtree of \(D\), choose accepted masses \(x_t\) maximizing \(\sum_t p_t x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:v\in S_t}x_t\le q_v\) for every \(v\in V\). Each accepted unit of mass receives its type’s whole bundle; determine the revenue-maximizing vector \(x\).
A continuum of buyers represented by bundle-and-price types with masses \(\mu_t\), and item supplies \(q_v\) per unit of population; the decision variable \(x_t\) is accepted mass, the objective is auction revenue, and each accepted buyer receives an indivisible whole bundle.
The mass LP handles arbitrary bundle incidence, so the tree-versus-DAG distinction that separates Propositions 3 and 4 no longer affects its tractability.
fatal: False
The mirror covers Propositions 3 and 4 for tree-subgraph and DAG-subtree bundles under population-scaled supplies; it leaves the paper’s search heuristics and other auction generalizations aside.
My strongest case is a continuous version of the paper’s bundle winner determination problem. A type is a buyer’s complete offer: a bundle \(S_t\) and a price \(p_t\). The society is a rational distribution \(\mu\) over the \(\tau\) offer types. Let \(D\) describe the item structure, and let \(q_v\) be the rational supply of item \(v\) per unit of population. Choose \(x_t\), the mass of type \(t\) whose offer is accepted, to maximize revenue:
\[ \max \sum_t p_t x_t \quad\text{subject to}\quad 0 \le x_t \le \mu_t,\qquad \sum_{t:\,v\in S_t} x_t \le q_v \quad\text{for each item }v. \]
Each accepted buyer still receives their whole bundle; each rejected buyer receives nothing. The fractional quantity is the mass of identical buyers taking each action, not a fraction of a bundle handed to an individual. For a finite market of \(N\) buyers, this corresponds to \(N\mu_t\) buyers of type \(t\) and \(Nq_v\) units of item \(v\), choosing \(N\) to make these counts integral.
A plausible regime is a large recurring procurement or online market: many small buyers use a relatively small collection of standard bundle-and-price templates, while inventories scale with the size of the market. Then \(N\) can be much larger than \(\tau\). The paper itself motivates tree-structured bundles with web shopping and treats auctions with multiple units of items, which helps make this regime recognizable to its authors.
My lead anchor is Proposition 4, an NP-completeness result presented by the authors here, not attributed to outside work. It says that winner determination is NP-complete when items are structured as a directed acyclic graph and every bid is a subtree of that graph. The corresponding continuous question is DAG-Subtree Population Winner Determination: given \(D\), rational supplies \(q_v\), and rational masses \(\mu_t\) of types whose bundles are subtrees of \(D\), find the revenue-maximizing accepted masses \(x_t\) subject to the constraints above. A solution is the vector \(x\). This is a linear program with \(\tau\) variables and a number of constraints linear in the item count, so I expect it to be tractable, in Class A, in \(m,\tau\), and the input bit length \(L\). The discrete hardness may dissolve because the decision for each individual bidder is integral, while a nonatomic mass of identical bidders can be split between acceptance and rejection. Further questions include how closely finite replicated markets approximate this optimum, and what additive revenue loss is needed when rounding \(x\) to whole buyers.
A useful secondary anchor is Proposition 3, also presented as the authors’ result. It says that when the items form a tree and each bid is a connected subgraph, an optimal allocation can be computed in worst-case time \(O(nm)\). Its mirror is Tree-Subgraph Population Winner Determination: use the same input and objective, but require \(D\) to be a tree and each \(S_t\) to be a connected subgraph. The solution is again an accepted-mass vector \(x\); the same LP makes this version polynomial-time solvable. This is a less valuable anchor than Proposition 4, since the discrete problem is already tractable, but it shows that the mirror retains the paper’s actual bundle structure and its tree-versus-DAG distinction. It also raises whether the tree structure permits a faster continuous algorithm than a general-purpose LP, and how the paper’s \(O(nm)\) dynamic program relates to finite-population rounding.
This case covers those two structural winner-determination results, not the paper’s search heuristics or every auction generalization. I think the authors could recognize the mirror: it still asks which whole bundle offers to accept to maximize auction revenue, and its types include the attributes that determine an offer. The paper’s multi-unit setting also makes per-capita supply a plausible co-modification as the market grows.
The weakest point is that Proposition 4’s hardness comes from the combinatorics of overlapping bundles and the item graph, not obviously from having too few bidders. My tractable mirror removes the individual accept/reject integrality while retaining bundle complementarity. A referee might therefore view it as a fractional relaxation rather than the high-multiplicity form of this particular result. The case depends on accepting a nonatomic population with replicated supply as a sensible market regime; if the intended question must preserve indivisible bidder counts, the DAG hardness may well survive.
The strongest objection to both Proposition 3 and Proposition 4 is that their unit is a submitted bid, while a population model needs meaningful multiplicity of agents. In the paper’s single-unit setting, two bids for the same bundle can be reduced to the higher-priced one: at most one can win. Repeating a type \((S,p)\) therefore adds no effective bids. With a fixed stock of items, the share of a growing population whose bids can be accepted also tends to zero. The tree-subgraph and DAG-subtree results both lose their population axis in this limit.
The proponent’s best repair is to scale item supplies with the population. That avoids the collapse, and the paper’s multi-unit model makes the resulting market recognizable to its authors. But it changes the setting of both propositions. The continuous problem is then the explicit LP over accepted masses, which handles arbitrary bundle incidence; the tree-versus-DAG distinction no longer does computational work. That makes this a clean continuous market-clearing model, though its central result appears to be the immediate LP relaxation of a packing problem. This is a reason to doubt the research value, not a decisive reason to reject the mirror: the programme explicitly allows supply to scale when needed and counts tractability as a worthwhile result.
There is a further modeling choice if the mirror is meant to cover the paper’s richer auctions. A bidder’s complete type would need to include their whole bid menu and any XOR or OR constraints. Treating each offer as a separate type can then allow the auctioneer to accept incompatible bids from the same bidder. A faithful model would need bidder-level allocation choices. That may restore a harder pricing problem, but it also means the proposed \((S,p)\)-type LP does not mirror those generalizations.
So the negative case is strongest against the *particular* single-unit anchors: fixed supply makes multiplicity degenerate, while scaled supply yields a materially altered model with a very direct LP. It does not establish that no worthwhile mirror exists. The authors could plausibly recognize the scaled-supply version as their multi-unit winner-determination problem, and the programme’s rules admit exactly that co-modification. I cannot honestly defeat Proposition 4’s anchor on the grounds given; Proposition 3 is weaker as a research target because its discrete problem is already tractable, but that alone does not defeat its 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.