| paper | d4-conf-aaai-2000-0179 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable by exact rational linear programming. Optimization takes \(\operatorname{poly}(m,\tau 2^m,L)=\operatorname{poly}(L)\) time under explicit tabulation; decision takes \(\operatorname{poly}(m,\tau 2^m,L+\ell_K)=\operatorname{poly}(L+\ell_K)\), where \(\ell_K\) is the binary encoding length of \(K\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given finite goods \(G\), types \(T\) with rational masses \(\mu_t\) summing to \(1\), per-type bundle values \(b_t(S)\), and per-capita supplies \(q_g\), take a rational terminal allocation \(x^*_{t,S}\) and price schedule \(p^0_t(S)\) that support a competitive equilibrium. The allocation must satisfy \(\sum_S x^*_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x^*_{t,S}\le q_g\). Find prices \(p_t(S)\) with \(0\le p_t(S)\le p^0_t(S)\) that minimize \(\sum_{t,S}x^*_{t,S}p_t(S)\), subject to every bundle assigned positive mass to type \(t\) maximizing \(b_t(S)-p_t(S)\), and \(x^*\) maximizing auctioneer revenue among feasible mass allocations at those prices.
Many firms share each complete type, including its bundle values and proxy information state. Rational type masses replace headcounts, mass can split across bundles while each firm receives an integral bundle, and resource supplies scale with population. The output is the lowest total payment among prices supporting the fixed terminal allocation as a competitive equilibrium; with explicit bundle tables, primal-dual LP constraints give an algorithm polynomial in table size.
The mirror covers Theorem 8’s minimum competitive-equilibrium price result. It leaves aside the paper’s proxy-agent incentive claims, its conditions for Vickrey prices, its approximation procedures, and its experiments.
The strongest honest positive case is a narrow mirror of the paper’s price-adjustment result. Theorem 8, proved in this paper, says that *iBundle(3), combined with Adjust and myopic best-response proxy agents, computes minimal competitive-equilibrium prices in combinatorial resource-allocation problems*. That is a concrete computational result, though it gives no polynomial-time bound. The paper’s NP-hard winner-determination statement is in the surrounding prose and cites earlier work; it is not a numbered hardness theorem, so I would not present it as an anchor.
A plausible high-multiplicity setting is a large wholesale market for bundles of discrete resources—say, compute capacity or logistics slots—serving many small firms. A firm’s type records its value for every bundle and its proxy’s information state. Many firms share each type, so there are \(N\) firms but only \(\tau\ll N\) types. The supply of each resource scales with the market: if \(q_g\) is the per-firm supply of resource \(g\), the market has about \(Nq_g\) units. This keeps the allocation problem meaningful as the population grows.
I would pose Continuous Minimum-CE Price Adjustment as follows. Let \(G\) be the discrete goods, \(T\) the finite set of types, and \(\mu_t\) the rational mass of type \(t\), with \(\sum_t\mu_t=1\). Each type has a bundle-value table \(b_t(S)\). The terminal allocation is given by rates \(x^*_{t,S}\): mass \(x^*_{t,S}\) receives the *integral* bundle \(S\), with
\[
\sum_S x^*_{t,S}=\mu_t,\qquad
\sum_{t,S:\,g\in S}x^*_{t,S}\le q_g.
\]
Thus a type’s mass may be split across bundles, while each actual firm still receives a discrete bundle. Given the terminal price schedule \(p^0_t(S)\), find a type-level price schedule \(p_t(S)\), with \(0\le p_t(S)\le p^0_t(S)\), that minimizes
\[
\sum_{t,S}x^*_{t,S}p_t(S),
\]
subject to \(x^*\) remaining a competitive-equilibrium allocation at those prices. In particular, every bundle assigned positive mass to type \(t\) must maximize \(b_t(S)-p_t(S)\) for that type, and \(x^*\) must maximize the auctioneer’s revenue among feasible mass allocations at those prices. The output is the minimum-revenue supporting price schedule.
I expect this version to be tractable when bundle values are supplied as explicit tables. Its assignment and equilibrium conditions are linear in the mass and price variables; the revenue-maximization condition has a separation problem that is itself a linear allocation problem over type-by-bundle mass. The resulting runtime is polynomial in the explicit table size, \(\tau\), and the rational input’s bit length. That bound is not polynomial in \(|G|\) for succinctly represented valuation functions: the paper itself notes that second-best winner determination can be NP-hard. Whether a compact valuation representation still permits efficient separation is a natural next question.
This mirror covers Theorem 8’s minimal-CE-price outcome, not the paper’s full dynamic-information advantage or its claims about Vickrey prices and incentives. The main soft spot is that a cohort-level price schedule and the option to split a type’s mass across bundles are real modeling choices. If the authors regard distinct agents’ proxy histories or atomic participation as essential, they may see this as a static population version of Adjust rather than a mirror of the entire iBundle mechanism. I think the case survives because it preserves the result’s central object—the minimum-revenue equilibrium prices—while making the population, rather than the goods or bundles, the continuous part.
The only plausible anchor is Theorem 8, but it supports a much narrower case than the proponent suggests. It says that iBundle(3) with Adjust computes minimal competitive-equilibrium prices under the paper’s assumptions. It gives no running-time bound; the paper says Adjust solves a second-best winner-determination problem that is NP-hard. The empirical fast procedure, Adj-Pivot*, has no worst-case guarantee. So this is a correctness result for a price-adjustment procedure, not a complexity result showing that the underlying auction computation is tractable.
The proposed continuous version also gets its polynomial bound only when every type’s value for every bundle is listed explicitly. That input has \(2^{|G|}\) bundles. With a compact valuation description, the LP’s pricing problem can retain the original winner-determination difficulty. This weakens the claim that the mirror exposes a useful tractability result in the programme’s usual parameters.
But neither point defeats the best version of the mirror. A large market with many firms sharing a small number of valuation and proxy-state types, and resource supplies scaling with population, is coherent. A type-level allocation can split mass among bundles while each firm still receives an integral bundle. The resulting minimum-revenue equilibrium-price question is well-defined, and the LP is a natural way to ask it. The paper’s result is about those prices, so this is not merely a mirror of its motivating story.
There is a sharper limit on extending the mirror to strategic incentives: in a nonatomic population, one firm has zero mass, so its individual effect on the allocation and Vickrey externality vanishes. Making a whole type’s mass act together restores an effect, but then the type behaves like a bloc rather than many independently strategic firms. That undercuts a continuous mirror of the proxy and Vickrey-incentive claims; it does not undercut Theorem 8’s static price result.
My negative case is therefore weak on the decisive question. Theorem 8 is not a complexity theorem, and the proponent’s claimed tractability is representation-dependent, but a sensible high-multiplicity mirror survives both objections. I would argue for lower priority, not that no worthwhile continuous mirror exists.
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.