| paper | d4-conf-aaai-2002-0121 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 15
statement extracted from the paper’s text layer
Given goods \(C\), a finite support \(T\) of valuation types with rational masses \(\mu_t\), rational per-capita supplies \(q_j\), and oracle access to each type’s utility \(u_t(S)\), characterize the deterministic worst-case number of distinct type-bundle queries needed to return a welfare-maximizing feasible mass allocation \(x_{t,S}\), when queries are allowed only for type-bundle pairs used by some feasible allocation. Does a fractional analogue of MPAR attain a matching no-uniform-improvement guarantee?
A large market with a continuum mass distribution \(\mu\) over homogeneous valuation types, shared per-capita supplies, mass allocation variables \(x_{t,S}\), welfare maximization, and adaptive queries to type-level bundle values.
Theorem 15 counts queries to aggregate rank combinations, so it supplies no lower bound for queries to type-level bundle values; the proposed analogue needs its own query model and result.
fatal: False
The mirror covers Theorem 15’s feasible-only valuation-elicitation question as a proposed query-complexity problem for mass allocations \(x_{t,S}\). It leaves aside the feasibility-check bound, Vickrey-payment results, and incentive-compatible RANK mechanism.
The strongest honest mirror is the paper’s elicitation problem for welfare-maximizing allocation, not its full Vickrey mechanism. A plausible regime is a large procurement market with many buyers following a small number of standardized valuation schedules. A type \(t\) is a complete bundle-utility function \(u_t:2^C\to\mathbb{Q}_{\ge 0}\), including its induced ranking; \(\mu_t\) is the fraction of buyers of that type. The number of buyers can be enormous while the support size \(\tau\) stays modest. To keep the goods market large with the population, let \(q_j\) be the per-buyer supply of each good category \(j\). Each buyer still receives an integral bundle, but a type’s mass can be split among bundles.
For mass variables \(x_{t,S}\), feasibility and welfare are
\[ \sum_{S\subseteq C}x_{t,S}=\mu_t,\qquad \sum_{t,S:\,j\in S}x_{t,S}\le q_j,\qquad x_{t,S}\ge 0, \]
\[ W(x)=\sum_{t,S}x_{t,S}u_t(S). \]
The mirror retains the paper’s central task: find an efficient allocation while eliciting as little utility information as possible. The fractional type-level allocation is the natural aggregate of integral bundles assigned to individual buyers.
My lead anchor is Theorem 15, proved in this paper. It says that no deterministic, admissible, “admissibly equipped” algorithm restricted to valuation calls on feasible combinations requires fewer calls than MPAR. MPAR uses PAR to find Pareto-optimal allocations, then selects one with maximum value. This is a lower bound on valuation calls in the paper’s stated oracle model; it is not a polynomial-time result or an NP-hardness theorem.
The continuous question I would hand to a prover is Continuous Feasible-Only Elicitation. The input is \(C\), a finite type support \(T\), rational masses \(\mu\), rational per-buyer supplies \(q\), and query access to the type utility schedules. A charged query asks for \(u_t(S)\); it reveals that value for the whole homogeneous type. The task is to return a welfare-maximizing feasible mass allocation \(x\) while minimizing the number of charged queries. In the feasible-only variant, an algorithm may query \(u_t(S)\) only if some feasible allocation assigns positive mass of type \(t\) to \(S\). The precise question is to characterize the deterministic query complexity and establish whether a fractional analogue of MPAR achieves a comparable no-uniform-improvement guarantee. Its solution is an exact optimal allocation together with a query strategy and a matching lower bound.
This would be recognizable to the authors as a continuation of their partial-revelation question: it preserves welfare maximization, limited valuation elicitation, and the distinction between bundle information and value information. But Theorem 15 does not itself transfer. Its objects are rank combinations for individual agents, whereas the mirror has a continuum of feasible mixtures. Defining and analyzing the fractional counterpart of MPAR is part of the proposed problem, not an established result.
For the underlying allocation problem, I expect Class A when utilities are supplied explicitly: the configuration LP has variables \(x_{t,S}\) and is polynomial in the explicit table size, roughly \(\tau 2^m\). That is not a claim of polynomial time in \(m\) for succinct valuations; there, bundle pricing may retain the item-driven difficulty. The query-minimization question is separate from this LP tractability and remains open.
The mirror covers Theorem 15’s valuation-elicitation claim, not the paper’s feasibility-check bound, Vickrey-payment result, or incentive-compatible RANK mechanism. The weakest point is the query model: a type-level utility query presumes the type cohort can answer for itself, and the paper’s aggregate valuation calls do not map one-for-one to those queries. That leaves room to reject this as a literal theorem analogue, but the underlying allocation-and-elicitation problem remains the same kind of question.
The strongest case against is about the anchor, not the market story. Theorem 15 counts calls to the paper’s global valuation function \(v(c)\), where \(c\) is a tuple of individual rank positions. Its lower bound depends on searching a finite rank lattice and asking whether each combination is feasible. It does not bound the number of times bidders must be asked for a bundle value, or the running time of winner determination. Those are different resources.
The procurement version is a plausible high-multiplicity setting, and scaling supplies with the population is a reasonable co-modification. But the natural query there is \(u_t(S)\): it reveals one type’s value for a bundle and can be reused across every mass allocation. A query to \(v(c)\), by contrast, concerns one rank combination. If the mass model instead charges for queries to whole allocations, the oracle has no natural elicitation counterpart: obtaining that allocation’s welfare requires eliciting the underlying type-bundle values. The fractional allocation problem may be worthwhile, but its query lower bound would be a new result about an LP with unknown coefficients, not a continuous version of Theorem 15.
There is also a modeling tension. If the society is supplied as a distribution over complete utility types, as in the programme’s central model, its utility schedules are already part of the input and there is nothing to elicit. If those schedules are hidden behind queries, the task can still be defined, but it adds an oracle model and a type-level query cost absent from the stated population input. Neither choice carries over the paper’s lower bound.
This is not enough to establish that no worthwhile mirror exists. Theorem 15 is a genuine query-complexity result, and type-level partial revelation in a large replicated market is close enough to the paper’s concern that its authors might recognize it as a continuation. The negative case is therefore weak: it defeats the claim that Theorem 15’s bound directly supports the proposed continuous problem, but it does not defeat the new elicitation problem itself.
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.