| paper | d4-conf-ijcai-2020-0072 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorems 2 and 3 have credible population mirrors: customers at the same location can be grouped into rational masses while preserving their service costs and the facilities’ incentives. But these theorems rule out mechanisms with bounded approximation, independent of computation; the rubric excludes impossibility theorems about rules as computational anchors. Theorem 7 states an algorithmic result, but the proponent supplied no continuous question for it.
fails bit a — no named computational result to mirror
The proposed questions establish a truthfulness-and-budget impossibility, not a result about computing a mechanism; the proponent acknowledges this limitation but does not answer the computational-character requirement.
fatal: True
The proposed mirror covers only Theorems 2 and 3, the unbounded approximation results for the cost objectives. It leaves the social-utility and minimum-utility results, including Theorem 7’s 2-approximate mechanism, outside its questions.
The strongest honest mirror is a high multiplicity version of the customers, while keeping the candidate facilities and their strategic cost reports discrete. Picture a city with many residents represented by a small number \(\tau\) of neighborhood locations, and a finite set of possible facility sites, each controlled by an owner with a private opening cost. A customer type is a location \(x\in[0,1]\): residents at the same location are identical for every purpose in the paper, since their costs and utilities depend only on that location and the opened facilities. Their masses \(\mu_x\) are nonnegative binary rationals summing to \(1\). The regime is \(N\gg\tau\), with \(N\) residents represented by \(\tau\) location types.
For a set \(S\) of facilities, the continuous social cost and maximum cost are
\[
SC_\mu(S)=\sum_x\mu_x\min_{j\in S}|x-\ell_j|,
\qquad
MC_\mu(S)=\max_{x:\mu_x>0}\min_{j\in S}|x-\ell_j|.
\]
Here \(\ell_j\) is facility \(j\)’s location. Replacing the paper’s sum of customer costs by the average \(SC_\mu\) only divides by \(N\), so approximation ratios are unchanged; the maximum cost is unchanged. The benchmark is
\[
OPT_G(\mu,\ell,c,B)=\min_{\sum_{j\in S}c_j\le B}G_\mu(S),
\quad G\in\{SC,MC\}.
\]
A mechanism sees the public distribution, facility locations, budget, and reported costs \(b\); it chooses a nonempty \(S(b)\) and payments \(p(b)\). The facilities remain the strategic players, with utility \(p_j-\mathbf{1}[j\in S]c_j\). Thus truthfulness, individual rationality, and the payment budget still have exactly their original meaning. Only the customer population becomes a mass distribution; neither facilities nor outcomes become fractional.
My lead is theorem 2, proved in this paper: for both minimizing social cost and minimizing maximum cost, no deterministic truthful budget-feasible mechanism has a bounded approximation ratio, even when its payment budget is augmented to \(kB\) for any fixed constant \(k\ge1\). The continuous problem I would hand to a prover is: for fixed \(k\) and either objective \(G\), determine the best worst-case approximation ratio achievable over all finite-support rational customer distributions, facility locations, budgets, and true costs \(c_j\le B\), by a direct mechanism that is truthful and pays at most \(kB\). A solution is an allocation-and-payment rule on reported cost vectors, with the stated properties; theorem 2 predicts that no such rule has finite worst-case ratio.
The transfer is exact, including in a high-multiplicity regime. Set \(q=\lceil k\rceil\), put facilities and equal customer masses at \(0,1/q,\ldots,1\), and replicate each location into an arbitrarily large cohort. Opening all facilities gives zero service cost. Omitting any facility leaves positive mass at a positive distance. The paper’s cost profiles—one cost \(B-q\varepsilon\), the rest \(\varepsilon\), and then the all-\(\varepsilon\) profile—therefore force the same allocations in the mass model. Truthfulness makes the threshold payment for each facility in the all-low profile at least \(B-q\varepsilon\); with \(q+1\) facilities, those payments exceed \(kB\) for sufficiently small \(\varepsilon\). The lower bound is not an artifact of having only a few individual customers: the same distribution represents arbitrarily large cohorts with fixed support.
A second, distinct anchor is theorem 3, also proved here: for the same two cost objectives, no randomized universally truthful budget-feasible mechanism has bounded approximation ratio, even with budget \(kB\) for any fixed constant \(k\ge1\). Its continuous counterpart asks for the best worst-case expected approximation ratio over that same distributional input domain, where the mechanism is a distribution over deterministic truthful mechanisms and each realized mechanism respects the augmented payment budget. Theorem 3 predicts that this ratio is unbounded. Its proof uses Yao’s principle and a distribution over opening-cost profiles; the location cohorts and zero-optimum reasoning carry over unchanged.
For both anchors the expected direction is hardness transfers: the paper’s impossibility for truthful mechanisms survives rational mass representation. This is a lower bound on achievable mechanism approximation, not an NP-hardness result or a claim that continuous optimization is computationally intractable. The continuous questions also invite follow-up work: does the obstruction persist under additive-error guarantees or a promise that \(OPT_G>0\), and what changes if the budget augmentation grows with the support size rather than remaining constant?
The mirror’s weakest point is also its limit: these theorems expose a truthfulness-and-budget obstruction, not a computational bottleneck that continuous optimization might remove. Their zero-optimum examples make any positive service cost infinitely bad, so this is a narrow but faithful mirror of the paper’s cost-objective results. It covers those two results only; it does not claim to continuize the paper’s utility-objective results or to classify the runtime of mechanism computation.
The strongest case against these anchors is about fit with ChoCo’s computational brief, not about whether their population mirrors are well posed. Theorems 2 and 3 bound what truthful, budget-feasible mechanisms can achieve; they do not analyze the running time or complexity of computing a mechanism. The proponent’s questions ask for the best achievable approximation ratio over continuous customer distributions. That is a legitimate mechanism-design question, but it does not expose the algorithmic bottleneck that ChoCo’s continuous-optimization programme is meant to study.
That objection does not defeat the mirrors themselves. For rational masses, both theorems transfer directly: expand each type of mass \(a/N\) into \(a\) customers, and the paper’s social cost changes only by the normalization factor \(N\), which leaves approximation ratios unchanged. The maximum cost is unchanged outright. The threshold-payment and budget arguments in Theorems 2 and 3 still apply.
Nor does the zero-optimum construction provide a sound objection. A stronger version can spread each cohort over a narrow band around its facility location, using finitely many rational location types. Opening every facility then has small positive cost, while omitting one leaves a cohort a fixed distance from its nearest facility. As the bands narrow, the ratio grows without bound. This preserves the deterministic and randomized arguments without relying on a zero denominator.
So I cannot honestly defeat either anchor as a continuous-population mirror. The negative case is that both mirrors appear to carry over by replication or a small perturbation, without creating a new computational question. But that is a case against their yield for this programme, not a fundamental reason the mirrors fail. On the modelling merits, Theorems 2 and 3 survive; the case against is weak.
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.