| paper | d4-conf-aaai-2002-0143 |
| 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: Yes. A deterministic truthful mechanism computable in polynomial time achieves \(\mathrm{OPT}\) exactly, and therefore at least \(\mathrm{OPT}/(m+1)\), with polynomial-time individual allocation and payment evaluation. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given \(m\) resource types, per-capita supplies \(b\in\mathbb{Q}_{\ge 0}^m\), and an atomless population with a finite-support distribution \(\mu\) over reported types \((q,v)\in\mathbb{Z}_{\ge 0}^m\times\mathbb{Q}_{\ge 0}\), compute a truthful mechanism assigning each individual either their whole requested bundle or nothing, subject to \(\sum_t q_i^t x_t\le b_i\) for every resource \(i\), that maximizes reported welfare \(\sum_t v^t x_t\). Here \(x_t\in[0,\mu_t]\) is the mass served from type \(t\), demand vectors are known or verifiable, and truthfulness is evaluated against an individual’s unilateral value-report deviation.
A finite-support mass allocation LP over reported demand-value types, with integral bundles for each served individual and dual resource prices defining truthful value thresholds; mass may be rationed among agents tied at a threshold.
The continuous mechanism uses aggregate prices that an individual cannot affect, so the finite-bidder critical-value argument and approximation guarantee do not transfer; the proponent acknowledges the guarantee change but leaves the connection to finite-agent incentive semantics as an open question.
fatal: False
The mirror covers Theorem 7’s known-demand, single-parameter multi-unit combinatorial auction setting. It leaves the paper’s other approximation mechanisms and its broader algorithmic techniques unmirrored.
My lead is Theorem 7, proved in this paper. It says that for multi-unit combinatorial auctions with \(m\) types of goods and known per-bidder demand vectors, the \((m+1)\)-Apx-MUCA allocation rule, paired with critical-value payments, is a truthful \((m+1)\)-approximation to maximum social welfare. The rule finds an optimal basic solution \(x\) to the LP relaxation and the largest bid \(v_h\). If the LP’s welfare is below \((m+1)v_h\), it awards the requested bundle to the highest bidder; otherwise, it awards bundles to exactly those bidders with \(x_j=1\). The paper also discusses NP-hard allocation problems, but those hardness claims are not numbered results, so I do not use them as an anchor.
A plausible regime is a large network allocating standardized capacity bundles to many small customers. A request’s route, and thus its vector of required link capacities, is known or verifiable; its value for the whole bundle is private. Many customers may share the same demand vector and one of a limited set of bid values. Here \(N\), the number of customers, is large while the number \(\tau\) of distinct \((q,v)\) types is much smaller. The paper’s multi-unit goods are not themselves the continuous population: the mirror continuizes the bidders. To keep the capacity question meaningful as \(N\) grows, let each link’s supply grow proportionally with the customer population.
The continuous question is: given \(m\) resource types, a finite support \(T\subseteq\mathbb Z_{\ge0}^m\times\mathbb Q_{\ge0}\), rational masses \(\mu_t\) summing to \(1\), and per-capita supplies \(b\in\mathbb Q_{\ge0}^m\), design a polynomial-time truthful mechanism for allocating capacity. A type \(t=(q^t,v^t)\) has known demand \(q^t\) and private value \(v^t\) for receiving that entire bundle. The mechanism chooses a served mass \(x_t\) for each type, where \(0\le x_t\le\mu_t\), and must satisfy
\[
\sum_{t\in T}q^t_i x_t\le b_i\quad\text{for each }i.
\]
Every served person gets their whole integral bundle; \(x_t\) is the mass served from that type, not a fractional bundle. The objective is to maximize \(\sum_{t\in T}v^t x_t\). Truthfulness means truthful value reporting is a dominant strategy for each individual, with critical-value payments. An atomless population lets the mechanism serve an exact fraction of a tied type cohort; a public priority rule can choose which individuals receive the bundles.
I expect this mirror to be Class A. Its welfare problem is an LP with \(\tau\) allocation variables, and the dual resource prices give a natural value threshold for each demand vector. Allocate when the reported value exceeds the threshold, ration at equality, and charge the critical value. In the nonatomic regime an individual’s report does not move the aggregate prices, so the cutoff rule can remain truthful while achieving the LP optimum. This is a genuine population continuization: although the paper already uses fractional LP variables, its bidders remain discrete and its rule ultimately awards whole bundles to selected bidders. The mirror makes the population a mass distribution and interprets the type-level fraction served as a subset of people each receiving an integral bundle.
The scope is specifically Theorem 7’s known-demand, single-parameter multi-unit combinatorial auction. I am not claiming that the paper’s \((m+1)\) guarantee carries over unchanged: the continuous benchmark is fractional mass allocation, so the natural target is exact optimization of that benchmark. This does not mirror all the paper’s general combinatorial-auction results or its mechanisms for privately described bundles.
The weakest point is the low-support assumption on complete types. If nearly every customer has a distinct private value, then \(\tau\) may be close to \(N\), and the high-multiplicity advantage largely disappears. The case is strongest for standardized requests and a small set of bid levels. The further questions are how tightly the finite auction approximates this continuum as \(N\) grows, what additive rounding loss depends on \(\tau\), and whether the truthful cutoff implementation remains exact under the paper’s finite-agent incentive semantics.
The only anchor is Theorem 7: a polynomial-time truthful \((m+1)\)-approximation for multi-unit combinatorial auctions with known demand vectors and private values. The proposed mirror has a real information problem. A distribution over types \((q,v)\) includes the bidders’ true private values, which the mechanism cannot observe. Read instead as a distribution over reported values, it is a legitimate direct-mechanism input—but in an atomless population, one bidder’s report changes that distribution by zero. The theorem’s finite-bidder incentive problem, where a bid can change the allocation and its critical value, has disappeared at the aggregate level.
That leaves a choice of interpretation. If the mechanism returns only served masses, it does not say which individuals receive bundles or define their individual incentives. If it is lifted to pointwise allocations, the natural rule is to compute resource prices from the aggregate reports, serve a bidder when their value exceeds the price of their demand bundle, and charge that price. This can give an exact LP optimum and truthful price-taking behavior. But that is a nonatomic market mechanism, not a continuization of Theorem 7’s particular algorithm: its LP branch, largest-bid fallback, approximation guarantee, and finite-agent critical-value argument no longer do the work.
Still, that distinction does not defeat the best mirror. The price-taking mechanism is a coherent continuous-population question, and the paper’s authors could reasonably recognize it as theirs. Its LP is over the explicit type support, and scaling capacity with population size makes the resource constraint meaningful. Calling the incentive condition vacuous would overstate the objection: individual reports still determine whether individuals cross the posted threshold, even though they do not move the aggregate price.
So the strongest negative case is that the proponent has shifted from the paper’s finite-agent truthful-approximation problem to an aggregate-information, price-taking allocation problem. That exposes a substantive change in what is being studied, but it does not show the new question is unworthy or unrecognizable. I cannot honestly defeat this anchor outright; the negative case is weak here.
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.