| paper | d4-conf-atal-2014-0376 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 14
statement extracted from the paper’s text layer
Given goods \(U\), rational per-capita supplies \(q_e\), and a finite set of types \(T\) with rational masses \(\mu_t\) and public menus \(D_t\) of at most two whole bundles, determine the best worst-case welfare approximation ratio achievable in polynomial time by a truthful-in-expectation mechanism with the paper’s verification rule. The mechanism specifies a lottery \(\pi_r(S\mid\mu)\) for each reported type \(r\), with aggregate assignment masses \(x_{t,S}=\mu_t\pi_t(S\mid\mu)\); feasibility requires each type’s mass to be assigned and total use of each good to be at most \(q_e\). Truthfulness requires that, for each true type \(t\) and permissible report \(r\), the expected value under \(\pi_t(\cdot\mid\mu)\) is at least that under \(\pi_r(\cdot\mid\mu)\). Compare welfare with the optimum feasible mass allocation, or prove a lower bound on the achievable ratio.
A society is a distribution \(\mu\) over complete bidder types, each specifying a valuation profile and a public menu of whole bundles. The mechanism assigns lottery probabilities to a tagged agent’s reported type while allocating mass \(x_{t,S}\) to whole-bundle outcomes, subject to per-capita supply limits; it maximizes total welfare subject to individual truthful-in-expectation constraints and verification.
The mirror covers the truthful-in-expectation approximation question anchored by Theorem 14. It leaves the paper’s characterizations, upper bounds, other lower bounds, and priority-algorithm results unaddressed.
The strongest anchor I would use is Theorem 14, proved in this paper. It says that no randomized mechanism truthful in expectation can achieve approximation ratio at most \(1.09\) for combinatorial auctions with known \(2\)-minded bidders, even with just \(n=2\) bidders and \(m=2\) goods. The proof uses goods \(a,b\): bidder 1’s public menu is \(\{\{a,b\},\{b\}\}\), bidder 2’s is \(\{\{a\}\}\), and bidder 2 values \(\{a\}\) at \(1\). Bidder 1 values \(\{a,b\}\) at \(\varphi=(1+\sqrt5)/2\), and values \(\{b\}\) at either \(0\) or \(1\) in two instances. Truthfulness in expectation links the mechanism’s behavior across those instances tightly enough to rule out ratio \(1.09\) or better. This is an approximation impossibility, not an NP-hardness result.
A plausible high-multiplicity setting is a government issuing business licences across cities. Many firms may have the same public menu of licence packages and the same verifiable stock or valuation profile. A firm’s full type includes its package menu and valuation data; firms with identical data belong to the same type. The number of applicants can be very large while the number \(\tau\) of distinct types stays moderate. Licence capacity per city can scale with the applicant population, as the paper already allows for goods with multiple copies. The objective remains total bidder welfare, and each firm still receives at most one whole package.
I would ask the authors to study HM-TIE-CA-V(2). An instance has goods \(U\), public menus \(D_t\) containing at most two bundles for each type \(t\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_e\), and rational valuations \(v_t(S)\). The decision variable \(x_{t,S}\) is the mass of type \(t\) assigned the *integral* bundle \(S\), or nothing. Feasibility and welfare are
\[ \sum_{S\in D_t\cup\{\varnothing\}} x_{t,S}=\mu_t,\qquad \sum_{t,S:e\in S}x_{t,S}\le q_e,\qquad W(x)=\sum_{t,S}x_{t,S}v_t(S). \]
Thus fractional quantities describe fractions of people receiving whole bundles, not people receiving fractional bundles.
The question is to determine the best approximation ratio achievable in polynomial time, in \(m,\tau\), and the input bit length, by a direct mechanism that outputs such a mass allocation and is truthful in expectation without money, with the paper’s verification rule. More precisely, the mechanism must specify a lottery \(\pi_t(S\mid\mu)\) for the allocation to a representative agent reporting type \(t\), with \(x_{t,S}=\mu_t\pi_t(S\mid\mu)\). A report is permissible when it does not overstate the true value of any bundle the mechanism may assign under that report. For every true type \(t\) and permissible alternative report \(r\), the mechanism must satisfy
\[ \sum_S \pi_t(S\mid\mu)v_t(S) \;\ge\; \sum_S \pi_r(S\mid\mu)v_t(S). \]
These conditional allocation policies should be understood as tagged-agent limits of finite-population mechanisms, so the individual incentive constraint does not disappear simply because one person has zero mass. A solution is a polynomial-time mechanism with a proved welfare guarantee against the optimum feasible mass allocation—or a lower bound showing that no such mechanism can attain a better ratio.
This is a natural question for these authors: it keeps their public menus, private valuations, whole-bundle allocations, no-money objective, and verification assumption. Only the population becomes a type distribution, with per-capita supply scaling as part of the model. The specific witness in Theorem 14 has menus and values that can recur across large cohorts, so the continuous question is still recognizably about their auction problem.
My tentative prediction is tractability (Class A) for this mirror. The unconstrained welfare benchmark is a finite linear program over type-to-bundle mass assignments, and high multiplicity lets cohorts split among whole-bundle outcomes. The paper’s two-bidder obstruction may therefore weaken substantially. That is a hypothesis, not a consequence of Theorem 14: the incentive constraints range over reports and population profiles, so the welfare LP alone does not produce a truthful mechanism. The central follow-up is whether the \(1.09\) barrier persists asymptotically, or whether the best truthful-in-expectation ratio approaches \(1\).
The weakest point is the gap between the anchor and the proposed regime. Theorem 14 uses two bidders and one copy of each good; the mirror has large cohorts and supplies growing with population. Splitting a type’s mass across bundles may remove the very conflict used in the finite lower bound. The theorem motivates the question, but it does not establish that its lower bound transfers. My case is for the mirror being a credible problem the authors would recognize, not for the finite impossibility already answering it.
The only anchor is Theorem 14. The strongest objection is that its lower bound depends on a finite bidder being pivotal. Its two instances differ in bidder 1’s value for \(\{b\}\), from \(0\) to \(1\). The incentive argument connects the mechanism’s choices across those instances because one bidder’s report changes the whole input.
That connection does not carry over directly to the proposed population model. If one bidder is replicated into a cohort, changing the report of one member changes the type distribution by only \(1/N\). In the limit, that member’s deviation leaves \(\mu\) unchanged, so the incentive constraint compares \(\pi_t(\cdot\mid\mu)\) with \(\pi_r(\cdot\mid\mu)\). Switching the whole cohort from one valuation type to another changes \(\mu\) by a positive mass, and individual truthfulness does not link the mechanism’s choices at those two populations. Scaling supply with the population avoids vanishing per-capita capacity, but leaves a nonatomic mechanism-design problem whose incentive constraints differ from the ones driving Theorem 14.
A stronger mirror could still ask for the best truthful-in-expectation welfare ratio over these mass populations. That is a coherent question, and a plausible setting is repeated auctions with many firms sharing the same menu and valuation profile. The fixed-menu welfare benchmark is a small linear program over type-to-bundle masses. The unresolved part is incentive compatibility across reports, so the paper’s \(1.09\) bound would motivate the problem without establishing that its obstruction survives.
That leaves the negative case weak. The proposed model is sufficiently specific to be studied, the scenario is plausible, and neither scaling supplies nor preserving whole bundles defeats it. The best objection is that the mirror changes the strategic structure so much that Theorem 14 is a poor anchor, and that the proposed problem may test mechanism design more than continuous-optimization methods. Those points weaken the claimed connection to this result; they do not support the universal claim that no worthwhile continuous mirror exists.
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.