| paper | d4-journals-jet-2007-0043 |
| 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\), with an exact rational optimal allocation. · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 1
statement extracted from the paper’s text layer
Given goods \(G\), complete valuation types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_g\), and explicit monotone valuation tables \(v_t(S)\), find an exact rational allocation \(x_{t,S}\) maximizing \(\sum_{t\in T}\sum_{S\subseteq G}x_{t,S}v_t(S)\), subject to \(\sum_{S\subseteq G}x_{t,S}=\mu_t\), \(\sum_{t\in T,\,S\ni g}x_{t,S}\le q_g\), and \(x_{t,S}\ge0\). Each unit of mass receives an integral bundle \(S\).
A distribution over complete valuation types, with mass \(x_{t,S}\) of type \(t\) assigned integral bundle \(S\); maximize total welfare subject to type-mass and per-capita supply constraints.
Covers Corollary 1’s efficient-allocation output for a population with valuation types; leaves the finite auction’s price path and the VCG payment results in Theorems 3–7 unaddressed.
The strongest honest mirror is the paper’s efficient allocation problem. The setting I find convincing is a large repeated procurement or licensing market: many firms receive bundles of standardized compute-capacity blocks, but their complete bundle valuation schedules fall into a relatively small number of classes. A type is the full valuation function \(v_t(S)\) over bundles \(S\); firms sharing a type are indistinguishable for the model. With \(n\) firms and \(\tau\) types, the regime is \(n\gg\tau\). The supply of each block category scales with the market, so \(q_g\) denotes units of good \(g\) available per participant. Each participant still receives an integral bundle; mass is the fraction of a type assigned each bundle.
My lead anchor is Corollary 1, proved in this paper from Theorems 1 and 2. Under the paper’s assumptions—finitely many bidders and goods, finite nonnegative integer monotone valuations, and the specified PD auction—every PD auction weakly increases all bundle prices \(p_j(S)\), terminates after finitely many steps, and yields an efficient assignment. This is an algorithmic result, not a P-time bound: the corollary says nothing about how many steps are needed as a function of input size. The paper gives no named NP-hardness or standard complexity-class result to use as an anchor.
The continuous problem I would hand to a prover is Continuous Efficient Bundle Allocation. An instance consists of a finite set of goods \(G\), a finite type set \(T\) with \(|T|=\tau\), rational masses \(\mu_t\geq 0\) summing to \(1\), rational per-capita supplies \(q_g\), and explicit valuation tables \(v_t:2^G\to\mathbb{Z}_{\geq0}\) satisfying the paper’s monotonicity and empty-bundle assumptions. Find an allocation \(x_{t,S}\) maximizing
\[ \sum_{t\in T}\sum_{S\subseteq G} x_{t,S}v_t(S) \]
subject to
\[ \sum_{S\subseteq G}x_{t,S}=\mu_t \quad(t\in T),\qquad \sum_{\substack{t\in T,\ S\subseteq G\\g\in S}}x_{t,S}\leq q_g \quad(g\in G),\qquad x_{t,S}\geq0. \]
Here \(x_{t,S}\) is the mass of type \(t\) receiving the integral bundle \(S\). A solution is an exact rational maximizing allocation and its welfare. The discrete high-multiplicity bridge is direct: with \(n\) participants, type \(t\) has \(n\mu_t\) members and good \(g\) has \(nq_g\) copies when the quantities align.
I expect this mirror problem to be Class A when valuations are given explicitly. It is a linear program with \(\tau 2^m\) allocation variables and a number of constraints linear in \(\tau+m\), so it is solvable in time polynomial in the explicit input length, including the valuation tables. That is polynomial in \(\tau 2^m\) and the rational data’s bit length; it is not a claim of polynomial time in \(m,\tau\) for succinctly represented valuations. For succinct valuations, the pricing problem over bundles becomes a natural further question.
The scope is deliberately the efficient-assignment result behind Corollary 1. A natural next question is whether type-level bundle prices can support an efficient solution through a finite nondecreasing demand-based process when the undersupplied coalition is a mass profile. Another is whether an appropriate submodularity condition yields meaningful cohort-level VCG transfers. Those would extend the mirror toward the auction and payment results, but they require their own definitions and are not part of this anchor.
The soft spot is that the paper’s distinctive theorem concerns a finite PD auction, while the stated continuous problem asks for an efficient allocation. The corollary’s finite price adjustments do not themselves prove a polynomial bound, and this mirror does not preserve the auction’s price path or its VCG-payment guarantees. Scaling supply with population is also a model co-modification. I think it is defensible here because it describes a replicated market of the same bundle-allocation problem, and because efficient assignment is exactly what the PD auction computes.
The strongest objection to the proposed anchor is that Corollary 1 establishes correctness and finite termination of a particular primal-dual auction; it gives no running-time bound. Its proof relies on integral prices, finite valuations, and successive unit price increases. The proposed Continuous Efficient Bundle Allocation drops that price process, its undersupplied coalitions, and its payment outcomes. It asks for an optimal allocation instead. That is a valid continuous allocation problem, but Corollary 1 does not establish its tractability.
A closer mirror would give each valuation type a mass, scale supply per capita, and ask whether a type-level ascending auction reaches an efficient allocation. The paper’s notion of a minimally undersupplied coalition does not transfer directly: in a nonatomic population, a positive-mass coalition can generally be divided into smaller positive-mass subsets, so inclusion-minimal coalitions may not exist. The unit price increase and the proof’s use of coalition cardinality also need new definitions. VCG results pose a separate difficulty: removing one member of a continuum changes the population measure by zero, so the paper’s leave-one-bidder-out payment needs a carefully scaled limit or a different cohort-level concept.
Those objections narrow the mirror, but they do not rule it out. With finitely many complete valuation types, an aggregate type-level model may replace individual coalitions with mass constraints and derive new price adjustments. The proponent’s LP is a plausible formulation of that population model, and the paper’s efficient-allocation objective gives it a genuine connection to the auction. Repeated markets with a few valuation classes and supply that scales with the market are credible scenarios.
So the negative case is weak. It shows that the proposed LP is not itself a continuization of Corollary 1’s finite auction, and that a faithful auction mirror needs fresh work on coalitions, prices, and payments. It does not show that no worthwhile continuous mirror exists. I would treat the auction-process mirror as underdeveloped, while recognizing the efficient-allocation mirror as a viable candidate.
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.