| paper | The computational complexity of truthfulness in combinatorial auctions |
| authors | Shahar Dobzinski, J. Vondrák |
| venue | SIGECOM 2012 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
The paper contains a genuine named computational hardness result, and the proposed two-type mass-allocation problem is a coherent continuous welfare extension with a valid SAT gap. However, Theorem 5.1 concerns MIDR mechanisms, while the stated mirror removes the mechanism and incentive layer; the proponent expressly does not define a corresponding continuum mechanism model. The extension is worthwhile, but its status as a faithful mirror remains unresolved.
fails bit b-changes — the continuum limit changes the question
The proposed welfare problem drops the theorem's valuation-dependent allocation range and strategic mechanism layer, and nonatomic individual deviations may become vacuous.
fatal: False
It is undecided whether a population-level \(\mathrm{MIDR}\) mechanism over mass allocations, with a non-vacuous reporting and payment convention, counts as the same problem as Theorem 5.1; the current question is only aggregate welfare maximization. A precise type-level or nonatomic strategic semantics, together with the corresponding \(1/2+\varepsilon\) impossibility statement, would settle this.
The candidate mirror covers the all-items multi-unit welfare construction and its succinct SAT bonus, but leaves the MIDR restriction, truthfulness, payments, and the other theorems untouched.
The cleanest positive case is Theorem 5.1, and I would make it the lead anchor.
Theorem 5.1, proved in this paper, states:
Let \(A\) be an MIDR algorithm for a multi-unit auction with two bidders that always allocates all \(m\) identical items and runs in time polynomial in \(\log m\). Unless \(RP=NP\), its approximation ratio is no better than \(1/2+\varepsilon\).
The proof uses succinct monotone valuations, including single-minded valuations and the SAT-bonus valuation \(v_\phi(s)=2s+\phi(s)\), where \(s\) encodes an assignment to a formula on \(\log m\) variables.
My continuous mirror is Continuous All-Items Multi-Unit Welfare, \(\mathrm{MU\text{-}Welfare}_\infty\).
An instance consists of:
The variable \(x_{t,r}\) is the mass of type \(t\) receiving exactly \(r\) units. It must satisfy
\[ \sum_{r=0}^{m}x_{t,r}=\mu_t \quad\text{for every }t, \qquad \sum_{t\in T}\sum_{r=0}^{m}r\,x_{t,r}=q. \]
The second equality says that all available units are allocated. The objective is
\[ W(x)=\sum_{t\in T}\sum_{r=0}^{m}x_{t,r}v_t(r). \]
The decision version asks whether \(W(x)\ge B\) for some feasible \(x\); an optimization solution is a sparse rational list of nonzero \(x_{t,r}\)'s. Each individual still receives an integral quantity \(r\); only the aggregate distribution of bundles is continuous.
This is a genuine population mirror. The regime is a large pool of agents—say, millions of recurring customers—with only a few complete valuation types. For example, take two types with \(\mu_1=\mu_2=1/2\), and \(N/2\) agents of each type in a finite realization. The supply is scaled proportionally: \(q=m/2\) means \(Nm/2\) units for \(N\) agents. Thus \(N\) can be arbitrarily large while \(|T|=2\). The type records the entire quantity-value curve, so agents of one type are genuinely interchangeable.
The paper’s SAT construction survives this limit exactly. Let \(q=m/2\), let \(v_2(r)=2r\), and let \(v_1\) be the paper’s SAT-bonus valuation, reindexed harmlessly so that \(v_1(0)=0\). If \(\phi\) is unsatisfiable, every feasible allocation has
\[ W(x)=2q=m. \]
If \(\phi\) has a satisfying assignment encoded by \(a\), assign type \(1\) quantity \(a+1\) and type \(2\) quantity \(m-a-1\). Then
\[ W(x)=m+\frac12. \]
Consequently, deciding whether the optimum is at least \(m+\frac14\) decides SAT, even with exactly two types and rational masses. The expected classification is therefore Class B: hardness transfers. The hard combinatorics live in the succinct quantity domain and in the valuation description, not in the number of named agents. The continuum does not dissolve the SAT gap.
The original authors should recognize this as their problem: the item domain, integral per-agent bundles, monotone valuation curves, exact all-items constraint, and welfare objective are unchanged. What changes is that the two named bidders become two high-multiplicity populations, and the allocation \((s,m-s)\) becomes a type-mass allocation.
A natural follow-up would retain the theorem’s mechanism layer: ask whether a polynomial-time continuous MIDR mechanism, operating on reported type masses and outputting lotteries over feasible \(x\)'s, can beat \(1/2+\varepsilon\). I would not claim that Theorem 5.1 automatically proves this version, because truthfulness in a nonatomic population requires a careful definition of deviations and payments.
That is the weakest point of the mirror. The welfare problem is unmistakably continuous-population and computationally faithful, but the theorem’s precise impossibility concerns MIDR mechanisms. Also, the succinct \(\log m\) encoding is essential: if all \(m\) quantities were explicitly listed, enumeration could remove this particular hardness.
The strongest negative is that the proponent has changed the anchor. Theorem 5.1 is not a theorem about welfare maximization alone. It is about MIDR allocation algorithms—hence about valuation-dependent allocation ranges and the mechanism-design structure that makes those ranges relevant. The proposed \(\mathrm{MU\text{-}Welfare}_\infty\) removes the range and incentive layer and asks only for
\[ \max_x \sum_{t,r} x_{t,r}v_t(r). \]
That is a sensible new high-multiplicity welfare problem, but it is not yet a mirror of Theorem 5.1. The paper never proves a hardness theorem for this aggregate optimization problem.
The SAT calculation itself is sound. With two types of mass \(1/2\), \(q=m/2\), \(v_2(r)=2r\), and \(v_1(r)=2r+\phi(r)\), the unsatisfiable case has welfare \(m\), while a satisfying assignment gives welfare \(m+\tfrac12\). Thus I would not object that the construction fails, nor that the continuous problem is mathematically meaningless. Clearing denominators produces many interchangeable agents with integral individual bundles.
The difficulty appears when one repairs the missing mechanism layer. If the continuum consists of nonatomic individual bidders, a unilateral report changes the reported population distribution by measure zero. Any anonymous mechanism whose outcome is determined by type masses therefore makes individual deviations vacuous. Truthfulness survives only as a formal shell: a bidder cannot affect the aggregate allocation.
If instead a report changes that bidder’s own bundle or payment, the type-mass vector is no longer a sufficient description. One needs identities, measurable allocation functions, or a rule specifying how null-set changes affect outcomes. That reintroduces precisely the individual information that continuization was meant to remove. Treating an entire positive-mass type as one strategic reporter avoids this problem, but then the strategic actors are just two type-level bidders; the “continuum” is an exogenous coefficient, not the population object of the mechanism.
A stronger aggregate formulation could define MIDR over a range of population configurations, with welfare-maximizing mass allocations and perhaps cohort-level reports. That would be worth studying as a new mechanism-design extension. But cohort deviations are coalitional deviations, and aggregate MIDR is not the individual-truthfulness problem proved in the paper. The necessary semantic repair is therefore substantive, not a routine limiting convention.
So the best negative verdict is conditional: under a strict source-fidelity rule, the proposed anchor should not be credited as a continuous mirror of Theorem 5.1. It is a valid, potentially interesting high-multiplicity welfare extension, but the paper’s central computational mechanism result has either been discarded or becomes vacuous in the atomless limit.
The universal “no worthwhile mirror in any scenario” claim is nevertheless too strong. The welfare mirror survives as a legitimate population problem, and its SAT gap is nontrivial. I would reject it only as a direct mirror of the theorem, not as a potentially worthwhile ChoCo extension.
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.