| paper | d4-conf-ijcai-2009-0325 |
| 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\). A rational allocation attaining \(W^*\) and common rational item-linear prices giving exact utility and profit maximization can be computed. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given rational masses of buyer types \(t\) and seller types \(s\), with complete bundle-value functions \(v_t\) and bundle-cost functions \(c_s\) on \(X=\{0,1\}^m\), find fractions \(q_{t,x}\) and \(r_{s,x}\) of each type assigned integral bundles, together with a price function \(p\). Require each type's fractions to sum to one, aggregate item demand to equal supply, and every bundle assigned positive mass to be within \(\varepsilon\) of that type's utility or profit maximum at \(p\); maximize welfare to within \(\varepsilon\) of the optimum. The permitted price class includes item-linear tariffs.
A distribution over complete buyer and seller types, with rational masses; decision variables assign fractions of each type's mass to whole bundles, and prices support approximately utility-maximizing demand and profit-maximizing supply while aggregate item demand equals supply. The objective is maximum total surplus.
The proposed configuration LP changes the common-bundle intersection problem into fractional allocation across types, and its item-linear supporting prices sidestep the paper's distinctive nonlinear kernel-price elicitation.
fatal: False
The mirror covers Proposition 2's approximate clearing objective for a market with type masses; it does not establish a population analogue of the paper's incremental kernel procedure, its sampled-bundle extraction result, or its empirical sparsity findings.
The best positive case is a high-multiplicity version of the paper’s market-clearing problem. The paper explicitly motivates its one-buyer/one-seller model as representing aggregate demand and supply, so a market with many repeated buyer and seller types is a plausible extension of the authors’ own setup.
The anchor is Proposition 2, stated as the paper’s own result, not attributed to prior work. It says Algorithm 1 terminates in finitely many rounds; upon successful convergence, its bundle \(y\) is \(\delta\)-optimal, and maximizes the buyer’s utility and seller’s profit at the returned prices \(p\) to within additive errors \(\delta_b\) and \(\delta_s\), where \(\delta=\delta_b+\delta_s\). This is a termination-and-correctness result, not a claim that the algorithm is polynomial. The paper gives no named P, NP-hardness, FPT, or comparable complexity-class result.
My lead mirror is High-Multiplicity Kernel Market Clearing. Consider a large procurement market with many buyers and suppliers, but relatively few complete buyer valuation types and supplier cost types. A type specifies the agent’s entire value or cost function over bundles, along with every other feature that affects its decisions. Let \(\mu_t\) and \(\nu_s\) be the rational masses of buyer type \(t\) and seller type \(s\), each side normalized to total mass one. This could describe a large consortium whose purchasing units share a modest number of procurement profiles and whose suppliers share a modest number of production profiles.
For each type and bundle \(x\in\{0,1\}^m\), let \(q_{t,x}\) and \(r_{s,x}\) be the fractions of that type’s mass assigned the integral bundle \(x\). Thus people receive whole bundles; only cohort mass is split. The decision is to find these assignments and a bundle-price function \(p\), represented by a finite kernel expansion \(p(x)=\sum_{\ell=1}^h a_\ell\kappa(z_\ell,x)\). Take the allowed price class to include item-linear tariffs. The objective is to maximize total surplus,
\[
W=\sum_t\mu_t\sum_x q_{t,x}v_t(x)-\sum_s\nu_s\sum_x r_{s,x}c_s(x),
\]
subject to each type’s assignments summing to one and aggregate item demand equalling supply:
\[
\sum_t\mu_t\sum_xq_{t,x}x=\sum_s\nu_s\sum_xr_{s,x}x.
\]
For an \(\varepsilon\)-solution, every bundle assigned positive mass to a buyer type must be within \(\varepsilon\) of that type’s maximum \(v_t(x)-p(x)\); the analogous condition applies to sellers’ \(p(x)-c_s(x)\). Require welfare at least \(\mathrm{OPT}-\varepsilon\). This asks for a price-supported, approximately welfare-maximizing market allocation—the population version of clearing demand against supply.
I expect this version to be Class A in the demand-oracle model. The allocation problem is a configuration LP with exponentially many type-bundle variables but only \(O(m+\tau)\) balance constraints. Its dual separation calls for maximizing \(v_t(x)-\lambda\cdot x\) for each buyer type and \(\lambda\cdot x-c_s(x)\) for each seller type: precisely type-level demand and supply queries. Thus the expected complexity is polynomially many oracle calls in \(m,\tau,L\), plus the time taken by those oracles. This is an inference about the proposed mirror, not a result proved in the paper. With discrete type counts \(n_t\), the connection is \(\mu_t=n_t/N\); rounding fractional cohort assignments back to a finite population is a separate question.
The soft spot is substantial: Proposition 2 proves finite termination, not a polynomial bound, and the paper itself notes that its query problem can require exponential revelation in the worst case, citing Nisan and Segal. Also, fractional assignments across a continuum can make a linear supporting price sufficient, so this mirror may dissolve the paper’s particular need for nonlinear prices. I think it survives as a research question because it keeps the same bundle choices, utility and profit maximization, and clearing goal, while making the population’s type distribution explicit—something the paper’s motivation invites but its formal model does not analyze. The resulting questions are whether fixed nonlinear kernels can still give sparse, efficiently elicited prices, and when succinct descriptions of type utilities make the per-type pricing queries hard.
Proposition 2 is the only strong anchor, but its result is finite termination and approximate correctness—not a running-time or complexity bound. Its progress comes from adding bundles from the finite set \(X=\{0,1\}^m\); the population’s mass plays no part. A literal mirror therefore has little to say about continuization: the paper already describes its buyer and seller as representatives of aggregate demand and supply. Once a large market has been compressed into those representatives’ \(v\) and \(c\), its type distribution is absent from the problem. The paper also warns that elicitation can require exponentially many queries.
To make population mass matter, the proponent introduces assignments of whole bundles across buyer and seller types. That is a plausible market model, but it changes the task from finding a bundle in \(D(p)\cap S(p)\) to finding a welfare-maximizing allocation across types. With fractional mass assignments and aggregate item balance, this is a configuration LP. Its dual supplies item-linear prices \(\lambda\in\mathbb{R}^m\), and the LP’s optimality conditions support the assigned bundles at those prices. The model’s population feature thus changes the allocation problem, while the paper’s distinctive search for nonlinear kernel prices largely drops out.
There is a fork here. Preserve the paper’s representative buyer and seller, and multiplicity is already compressed away. Give a continuum of agents distinct bundle assignments, and the mirror becomes a different allocation problem whose basic price support is linear. One could insist on sparse kernel prices and type-specific elicitation, but those restrictions are not required by continuization; they create a new algorithmic question rather than extending Proposition 2’s result. The type masses do not supply the missing complexity bound for the paper’s procedure.
This is a serious objection to the proposed anchor, not proof that no useful extension exists. The paper explicitly invites a multiple-agent interpretation, so a high-multiplicity allocation study could be worthwhile on its own. That invitation is also why the negative case is weak on the universal claim: the proponent’s scenario is credible, even if its central computational question is not a close mirror of the result they anchored it on.
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.