| paper | d4-conf-aaai-2011-0006 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), using at most \(\tau+1\) rational linear programs. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given \(m\) goods, a finite set \(T\) of bidder types with bundle \(x_t\in\{0,1\}^m\setminus\{0\}\), value \(v_t\in\mathbb{Q}_{\ge 0}\), and rational mass \(\mu_t\ge 0\) summing to \(1\), together with per-capita supply \(b\in\mathbb{Q}_{\ge 0}^m\), decide whether there exist served masses \(\alpha_t\in[0,\mu_t]\) and a uniform per-item price \(\lambda\ge 0\) such that \(\alpha\) maximizes \(\sum_{t\in T}\alpha_t v_t\) subject to \(\sum_{t\in T}\alpha_t x_t\le b\), every served type demands its bundle at price \(p(x)=\lambda|x|\), every unserved type demands the empty bundle, and the allocation maximizes seller revenue at those prices.
A nonatomic market with type masses \(\mu_t\); each unit of mass receives its whole desired bundle or nothing, while supply scales per capita. The decision variables are served masses \(\alpha_t\) and a uniform item price \(\lambda\); the objective is to determine whether an efficient allocation and seller revenue-maximizing supply are supported at that price.
Fractional type mass makes integrality valid at the aggregate level, so Proposition 1’s test and the adaptive kernel-upgrade trigger disappear; the proponent acknowledges this, but the proposed question covers only support under uniform prices.
fatal: False
The mirror covers efficient allocation and competitive price support for a fixed uniform price structure. It leaves out the integrality equivalence itself, adaptive kernel upgrades, richer price structures, and the paper’s empirical comparisons.
There is one credible, but deliberately narrow, anchor. The paper has no numbered result asserting a complexity class such as P or NP-hardness. Its relevant formal result is Proposition 1, proved in this paper: for a fixed feature map (kernel), the global efficient-allocation primal has an integer solution if and only if the final restricted primal has an integer solution. The restricted primal is built from the buyers’ current demand sets and the seller’s current revenue-maximizing allocation. The auction uses this equivalence to test whether its current price structure suffices, and to trigger a richer kernel when the restricted solution is fractional. I take Proposition 1 as an algorithmic characterization of price-structure adequacy, not as a complexity bound.
My lead mirror is Continuous Uniform-Price Market Clearing. A high-volume market has \(m\) resource types and a finite support \(T\) of \(\tau\) bidder types. A type \(t\) specifies a nonempty bundle \(x_t\in\{0,1\}^m\) and value \(v_t\); its rational mass \(\mu_t\) is the fraction of the population with exactly that bundle and value, with \(\sum_t\mu_t=1\). The market has per-capita supply \(b\in\mathbb{Q}_{\ge0}^m\), scaling with population size. Each agent still receives either their whole desired bundle or nothing. The decision variable \(\alpha_t\in[0,\mu_t]\) is the mass of type \(t\) served, with \(\sum_t\alpha_t x_t\le b\). Welfare is \(\sum_t\alpha_t v_t\).
The question is: given \((m,T,\mu,v,b)\), does there exist an efficient allocation \(\alpha\) and a uniform per-item price \(\lambda\ge0\), with bundle price \(p(x)=\lambda|x|\), that competitively support one another? A solution is \((\alpha,\lambda)\) such that \(\alpha\) maximizes welfare, every positive mass served demands its bundle, every positive mass left unserved demands the empty bundle, and \(\alpha\) maximizes seller revenue over feasible mass allocations at those prices. If no such pair exists, the answer is no. The mass variable lets a fraction of indistinguishable agents receive a whole bundle; it does not split bundles.
A plausible regime is a large recurring procurement or assignment market with standardized bundle-and-value bid tiers and inventories replenished in proportion to market size: millions of bidders but tens or hundreds of distinct types. Exact shared values are most convincing where bids come from a standardized schedule. Scaling supply per capita is a real co-modification of the paper’s one-copy inventory model, but it preserves the scarce-resource allocation question and is expressly within this programme’s scope.
I expect this mirror problem to be tractable. First compute optimal welfare by a linear program over the \(\tau\) type masses and \(m\) resource constraints. For a proposed uniform price, demand changes only when \(\lambda=v_t/|x_t|\). Check those \(O(\tau)\) breakpoints and one rational price from each interval between them. At a fixed price, buyer-demand restrictions give bounds on \(\alpha_t\); seller revenue maximization and the requirement that welfare equal the optimum can also be checked with linear programs. This gives a polynomial-size procedure in \(m,\tau,L\). There is no discrete hardness anchor here to transfer.
This is a continuous counterpart to Proposition 1’s *question of whether a price structure can support an efficient clear*, rather than a literal translation of its integer-feasibility statement. Its further questions include how well finite high-multiplicity instances approximate the supported mass allocation, and what changes for richer bidder types such as budgets or non-single-minded values.
The weak point is that this relaxation removes the phenomenon Proposition 1 detects. With divisible type mass and per-capita supply, ordinary linear item prices support an efficient allocation by LP duality. So the paper’s adaptive move to higher-degree prices—and its empirical finding that quadratic prices sometimes help—does not carry over to this mirror. The authors should recognize the underlying problem: efficient allocation of single-minded bundles and competitive prices over the same resource system. They may reasonably object that the continuous version makes their price-expressivity problem much easier. That limits the claim to a genuine mirror of their market-clearing problem, not a mirror of the full adaptive-kernel contribution.
The best objection is that the paper has no named complexity result to continuize. Proposition 1 is an integrality characterization for a fixed kernel; the paper’s computational claims are an auction algorithm and empirical comparisons. With the original one-copy inventory, the population limit also degenerates: because every desired bundle is nonempty, at most \(m\) buyers can receive anything, so their share vanishes as the population grows.
Scaling inventory with population avoids that degeneration, and the proposed standardized bundle-and-value tiers are a plausible high-multiplicity regime. But it changes the object Proposition 1 characterizes. The continuous allocation allows a fractional mass of each type to be served, making fractional solutions legitimate. The proposition’s integrality test—and the kernel-upgrade trigger built on it—then has no direct counterpart. One could ask whether a restricted price family, such as uniform prices, supports an efficient mass allocation. That is a sensible computational question, but it is a new restriction imposed on the continuous model, rather than a continuization of the paper’s integrality result.
This does not defeat the uniform-price mirror outright. Per-capita supply is an admissible co-modification, and the resulting market-clearing question is well-posed. I can’t honestly make a strong universal case that it is not worth studying; the negative case rests on the gap between that question and the paper’s central computational contribution.
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.