Budget Feasible Mechanisms: A Survey

The paper's only numbered result, Theorem 1, is a truthfulness characterization rather than a complexity, algorithmic, or approximation result. The additive high-multiplicity formulation is sensible and author-recognizable, but it is not attached to an eligible named result in this survey. The opponent therefore wins on the mandatory computational-anchor gate.

The objection that survived

The clone-lift is indexed by \(N\), and unilateral deviations may become vacuous in the atomless limit; exact threshold payments and budget feasibility need not pass to a mechanism defined only on \(\mu\).

What the mirror covers

The conditional mirror covers only the offline additive valuation material in Section 2.3, leaving the submodular, XOS, subadditive, online, Bayesian, multi-unit, two-sided, graph, fairness, sybil, and other settings aside.

Open questions for a prover

The case FOR (proponent)

The strongest honest positive case is conditional: this survey fails the programme’s named-anchor gate.

The only numbered theorem is Theorem 1, attributed to Myerson (1981) and not proved here. It characterizes truthfulness in a single-parameter domain through monotone allocation and threshold payments. It is not a complexity, approximation, or algorithmic theorem. Definitions 1–6, the benchmark in Eq. (2), and the approximation definition in Eq. (3) are likewise not computational results. The approximation ratios in Tables 1 and 2 are unnumbered summaries of results from other papers. Thus this paper has no eligible anchor, and formally there is no per-anchor continuous problem to certify.

If the source gate were relaxed, the strongest mirror would be the survey’s additive procurement setting, which I would call Additive Clone-Procurement\(_\infty\).

Take many unit-supply sellers in crowdsensing, crowdsourcing, or federated learning. A type \(t\) records the seller’s publicly relevant value \(v_t\) and private cost \(c_t\); \(\mu_t\in\mathbb Q_{\ge 0}\) is the fraction of sellers of that type, with \(\sum_t\mu_t=1\). The buyer has per-capita budget \(\beta\). A mass allocation \(x_t\) satisfies \(0\le x_t\le\mu_t\), and its value and cost are

\[ V(x)=\sum_t v_t x_t, \qquad C(x)=\sum_t c_t x_t. \]

The continuous benchmark is

\[ \operatorname{OPT}_\infty = \max \left\{ \sum_t v_t x_t: 0\le x_t\le\mu_t,\; \sum_t c_t x_t\le\beta \right\}. \]

The mechanism-design version asks for a symmetric direct-revelation rule which, on reported costs, returns selected mass \(x_t\) and payment mass \(P_t\), satisfies \(\sum_tP_t\le\beta\), is individually rational and truthful under its finite rational-clone lift, and achieves

\[ \sum_t v_t x_t \ge \frac{1}{\alpha}\operatorname{OPT}_\infty. \]

The clone lift takes \(N\mu_t\) identical unit sellers of each type and total budget \(N\beta\). Truthfulness is required there through the same monotonicity and critical-payment conditions as Theorem 1; this avoids the atomless-continuum problem in which one individual has zero influence. Mass is therefore not divisible goods: it is the fraction of identical unit sellers selected. With rational data, clearing denominators recovers the finite high-multiplicity instance, up to the usual rounding error when the number of clones is insufficient.

This is author-recognizable: it preserves the single buyer, private seller costs, budget constraint, additive valuation, truthful allocation, threshold payments, and approximation objective. The regime is plausible in repeated sensing or service markets with many workers sharing a small number of cost–value profiles, so \(N\gg\tau\). The continuous benchmark is a one-constraint LP, equivalently continuous knapsack, and should be Class A. The surveyed additive mechanisms of Singer, Chen–Gravin–Lu, and Gravin et al. are natural sources for threshold rules, although none is a numbered result of this survey.

The mirror covers only the additive, offline procurement results. Extending it to submodular, XOS, online, Bayesian, or two-sided settings would require additional modelling choices. In particular, “divisible agents” in Klumper and Schäfer is outcome-space continuity, not by itself population continuization; it is supporting evidence, not a novelty collision.

The weakest point is decisive: the mechanism’s strategic semantics do not survive literal atomlessness. The clone-lift condition is a principled high-multiplicity extension, but it is not stated in the survey, and a strict evaluator could regard it as changing individual deviations into cohort deviations. More fundamentally, because the paper supplies no eligible numbered computational anchor, this is a promising mirror of the survey’s subject matter, not a valid anchored positive case under the ChoCo protocol.

The case AGAINST (opponent, writing after the proponent)

The decisive negative point is procedural but substantive: this paper contains no eligible computational anchor.

It is a survey. Its only numbered result, Theorem 1, is Myerson’s characterization of truthfulness; it asserts neither a complexity bound nor an approximation or algorithmic result. Definitions 1–6 and equations (2)–(3) are setup. The approximation ratios in Tables 1 and 2 summarize results proved in other papers; they are not numbered results of this paper. Thus the proposed “Additive Clone-Procurement\(_\infty\)” is not a continuous question attached to a named computational result in the source. Under ChoCo’s anchor rule, the positive case stops there.

Even relaxing that gate, the proposed mirror does not yet preserve the paper’s central object. The original mechanism is a map

\[ (b_1,\ldots,b_n)\longmapsto (x(b),p(b)), \]

with individual truthfulness required against unilateral deviations. The proposed continuum instead receives a mass distribution over cost–value types and returns selected mass and payment mass. If the distribution contains true costs, the mechanism has been given the private information it was supposed to elicit. If it contains only reports, an individual seller changes the histogram by \(1/N\), which disappears in the atomless limit. Individual incentive constraints then become vacuous.

The clone lift repairs this only by reintroducing a finite population. One obtains a sequence of mechanisms indexed by \(N\), not a mechanism defined on \(\mu\) alone. Exact threshold payments, tie-breaking, indivisibility, and ex-post budget feasibility can depend on \(N\); “usual rounding” does not automatically preserve truthfulness or exact budget feasibility. Alternatively, allowing genuine mass deviations or fractional seller allocations changes the strategic and allocation model into a divisible-agent or cohort mechanism. That may be a legitimate new problem, but it is no longer a continuous version of Theorem 1 or of the surveyed finite-agent mechanisms.

The same problem becomes worse for the survey’s richer settings. An arbitrary submodular valuation is a function of named subsets, not merely seller types; compressing sellers by cost and value loses the objective unless a type encodes an essentially exponential marginal-value profile. Online mechanisms depend on arrival order and individual timing, which a population measure does not retain. Network, sybil, and two-sided variants likewise depend on identity or relational structure. These could be rebuilt under strong symmetry assumptions, but each repair defines a new model rather than a canonical mirror of a result in this survey.

The honest weakness is that the universal substantive claim is not airtight. A large market of many interchangeable sellers with finitely many cost–value profiles and a budget scaling as \(N\beta\) is a sensible high-multiplicity regime. Its fractional-knapsack benchmark could be worth studying. But that is a plausible new ChoCo problem, not an anchored mirror of this paper. The strongest defensible verdict is therefore: no worthwhile continuous mirror is established for this paper under the programme’s rules; the broader claim that no meaningful high-multiplicity procurement model exists would be overstated.

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.