| paper | d4-conf-atal-2010-0011 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3 shows that limiting the number of invoked providers can cause an arbitrarily large welfare loss, but it states no running-time bound, computational hardness, or approximation guarantee achieved by an algorithm. The proposed mass-cap comparison is a coherent procurement extension, but it cannot supply the missing computational character of the paper’s anchor.
fails bit a — no named computational result to mirror
Theorem 3 bounds welfare for a restricted allocation range; it does not claim that computing an allocation is easy or hard, and the proposed continuous optimization does not change that.
fatal: True
The proposed extension covers only Theorem 3’s zero-cost, immediate-procurement welfare comparison; it leaves the incentive-compatibility results, execution-contingent payments, and general scheduling problem aside.
The strongest case I see is narrow: a large market for redundant service providers, such as cloud workers or contractors who can each complete the same task. Many providers may share the same cost and service-duration distribution, while their realized durations remain independent, as in the paper. Here a type is a pair \((c,F)\), and \(\mu_t\) is the fraction of available provider capacity of type \(t\). The regime is \(N\) providers but only \(\tau\) distinct cost-duration types, with \(N\gg\tau\).
My anchor is Theorem 3, proved in this paper. It says that for every provider-count limit \(\eta\ge1\) and every \(b\ge1\), there is an instance where the optimal expected social welfare using unrestricted procurement is at least \(b\) times the best welfare achievable by a strategy that invokes at most \(\eta\) providers. The paper’s witness sets every provider’s cost to zero and gives them the same deadline success probability \(1-f\), choosing \(f\) near \(1\) and then taking \(m\) large enough. This is an approximation-performance lower bound, not an NP-hardness result.
A continuous counterpart is the Continuous \(\kappa\)-Cap Service Procurement Gap. Its input is a finite support \(T\), rational masses \(\mu_t\ge0\) summing to \(1\), nonnegative completion intensities \(\lambda_t\), a deadline value \(V>0\), and a mass cap \(\kappa\in(0,1]\). Restrict to the zero-cost, immediate-procurement slice used in Theorem 3. Choose \(x_t\in[0,\mu_t]\), where \(x_t\) is the mass of type \(t\) called. Under an exponential survival interpolation, the probability that no provider completes by the deadline is \(\exp(-\sum_t\lambda_t x_t)\). The task is to return allocations maximizing
\[ W^\star=V\!\left(1-\exp\left(-\sum_t\lambda_t\mu_t\right)\right) \]
without a cap, and
\[ W^\star_\kappa =\max_{\substack{0\le x_t\le\mu_t\\\sum_t x_t\le\kappa}} V\!\left(1-\exp\left(-\sum_t\lambda_t x_t\right)\right) \]
with the cap, together with their ratio. For an \(N\)-provider instance with identical success probability \(1-f\), set \(\mu=1\), \(\lambda=-N\ln f\), and \(\kappa=\eta/N\). The continuous expression then gives exactly the finite-instance ratio \((1-f^N)/(1-f^\eta)\).
This problem is tractable: sort types by \(\lambda_t\) and fill the cap from the highest intensity down. For any fixed \(\kappa>0\), the worst-case ratio has supremum \(1/\kappa\); equal intensities with intensity tending to zero approach it. Thus the unbounded gap in Theorem 3 is consistent with the continuous model when the permitted mass share \(\eta/N\) shrinks toward zero. With a fixed positive share, the gap is bounded. I would class this mirror as tractable, and the capped welfare comparison is my lead question.
The paper’s result supports the mirror because its hard example already uses a homogeneous provider population, and its providers are described by precisely the cost and duration information used to define types. A convincing regime is a large pool of near-identical providers offering redundant attempts at a task with a deadline. The authors could recognize the question as their service-procurement welfare problem with provider capacity and the strategy cap measured continuously.
The weakest point is the survival interpolation: it is a natural way to extend the finite product of independent failure probabilities to fractional provider mass, but the paper does not specify that limit. Also, Theorem 3 gives no complexity lower bound; this mirror concerns the welfare loss from limiting procurement, and the tractable result above is for the zero-cost, immediate-procurement slice. It does not cover the paper’s incentive-compatibility results or establish the complexity of its full mechanism-design problem.
Theorem 3 is a weak ChoCo anchor. It proves a welfare-gap lower bound for strategies that invoke at most \(\eta\) providers; it does not establish the complexity of computing a procurement strategy. The proposed continuous problem is well defined, but its zero-cost, immediate-procurement slice asks about that welfare gap, not a complexity result from the paper.
The scaling needed to match the theorem also matters. With \(N\) identical providers, the proposed mapping sets \(\lambda_N=-N\ln f\) and \(\kappa_N=\eta/N\). So as \(N\) grows, the rate grows while the permitted mass shrinks. Fixing a positive \(\kappa\) instead means allowing a number of providers proportional to \(N\), which changes the theorem’s fixed-\(\eta\) regime. Keeping \(\eta\) fixed sends the permitted mass to zero and retains the finite-count scale in the limiting model. The mirror therefore captures the theorem along a singular scaling, rather than as a stable fixed-mass comparison.
A stronger mirror could include provider types \((c,F)\), start times, and continuous allocations. That may yield a worthwhile procurement problem, but Theorem 3’s witness—zero costs, immediate calls, and a single deadline success probability—does not motivate the additional scheduling or strategic structure. At the witness itself, the proposed model reduces to aggregate success intensity and a mass cap. This narrowness is a reason to doubt the value of this particular anchor, though a simple tractable result would still count as a valid Class A outcome.
I cannot honestly rule out the mirror on the grounds that its population regime is implausible: a large pool of interchangeable service providers is a credible high-multiplicity setting. The negative case is narrower. Theorem 3 contributes a performance bound, and its exact continuous analogue depends on a population-dependent scaling; the most faithful version is consequently a limited welfare comparison, while richer versions become new procurement questions.
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.