Answer: Yes. A polynomial-time deterministic anonymous mechanism satisfies every stated requirement and achieves approximation factor \(1\), hence also factor \(2.62\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism DA with α = √ 5−1 √ 5+1 and β = 1 2 √ 5 −1 2 is truthful, individually rational, budget feasible, computationally efficient and has an ap- proximation guarantee of √ 5+1 √ 5−1. Lower Bound. Next we show that no truthful, individually rational, budget feasible and deterministic mechanism exists with an approximation guarantee of ( 5 4 −ǫ1), for some ǫ1 > 0. For contradiction, assume such a mechanism does exist.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational report measure over public supplier classes \(q\) and declared costs \(b\), with per-capita budget \(\bar B\), does there exist a polynomial-time anonymous mechanism with report-indexed allocation and payment schedules \(x_q(r;\nu)\in[0,1]\) and \(p_q(r;\nu)\ge 0\) such that aggregate payments satisfy \(\int p_q(b;\nu)\,d\nu(q,b)\le\bar B\), each supplier is individually rational and truthful against every alternative report \(r\) when tested as a tagged supplier against a fixed measure of the others, and the allocation achieves a \(2.62\) approximation to \(\mathrm{OPT}(\nu)=\max_{z\in[0,1]}\{\int v_qz(q,b)\,d\nu(q,b):\int bz(q,b)\,d\nu(q,b)\le\bar B\}\)?
There are \(m\ge1\) public supplier classes, with binary-rational values \(v_q\ge0\), and a binary-rational per-capita budget \(\bar B>0\). Costs are linear and private, with \(c\in[0,\bar B]\); reports may be any \(r\ge0\), and classes cannot be misreported.
A society is a probability measure \(\nu\) given by its support: the list of the \(\tau\) report types \((q,b)\) with positive mass, each with its mass as a binary rational. Thus \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
A deterministic anonymous mechanism provides measurable schedules \(x_q(r;\nu)\in[0,1]\) and \(p_q(r;\nu)\ge0\). Suppliers with the same class and report receive the same allocation fraction and payment per unit mass.
A tagged supplier has zero mass, so changing its report leaves the measure of others \(\nu\) fixed. For every \(\nu,q,c\in[0,\bar B]\) and \(r\ge0\), require \(p_q(c;\nu)-c x_q(c;\nu)\ge p_q(r;\nu)-c x_q(r;\nu)\); require also \(p_q(r;\nu)\ge r x_q(r;\nu)\).
For every report measure, require \(\int p_q(b;\nu)\,d\nu(q,b)\le\bar B\). On every measure supported on \(b\in[0,\bar B]\), require \(2.62\int v_qx_q(b;\nu)\,d\nu(q,b)\ge\mathrm{OPT}(\nu)\), where \(\mathrm{OPT}(\nu)=\max_{0\le z(q,b)\le1}\{\int v_qz(q,b)\,d\nu(q,b):\int bz(q,b)\,d\nu(q,b)\le\bar B\}\).
Computational efficiency means constructing a finite representation of the schedules in time polynomial in \(m,\tau,L\), with evaluation at rational reports polynomial also in the query bit length.
Does a polynomial-time deterministic anonymous mechanism satisfying these conditions and achieving approximation factor \(2.62\) exist, or is this approximation guarantee unattainable under these requirements?
For finitely many divisible suppliers with costs bounded by the total budget, a polynomial-time deterministic truthful, individually rational, budget-feasible mechanism achieves factor \((3+\sqrt5)/2\), with a deterministic lower bound of \(5/4\) ([Klumper–Schäfer](https://arxiv.org/pdf/2206.13124v2)).
The finite-supplier upper bound was subsequently improved to \(2\) ([Amanatidis et al.](https://ir.cwi.nl/pub/35197/35197.pdf)); neither result treats the zero-mass tagged-supplier model above. No result settling this precise distributional question was located.
Yes. A polynomial-time deterministic anonymous mechanism exists; under the stated assumptions it achieves factor \(1\).
The per-capita normalization makes full procurement feasible: the society has total mass \(1\), and every true unit cost is at most \(\bar B\). I first prove the exact guarantee. I then give a factor-\(2\) construction that also handles the nontrivial extension in which costs may exceed \(\bar B\).
For every society \(\nu\), class \(q\), and report \(r\ge0\), define
\[ x_q(r;\nu)= \begin{cases} 1,&0\le r\le\bar B,\\ 0,&r>\bar B, \end{cases} \qquad p_q(r;\nu)= \begin{cases} \bar B,&0\le r\le\bar B,\\ 0,&r>\bar B. \end{cases} \]
These schedules are measurable, deterministic, and anonymous. They do not depend on \(\nu\).
Truthfulness. Fix \(\nu,q\), and a true cost \(c\in[0,\bar B]\). Truthful utility is \(\bar B-c\). Every report \(r\le\bar B\) gives exactly the same utility; every report \(r>\bar B\) gives utility \(0\). Since \(\bar B-c\ge0\), truthful reporting maximizes utility.
Individual rationality at every report. If \(r\le\bar B\), then \(p_q(r;\nu)=\bar B\ge r=r x_q(r;\nu)\). If \(r>\bar B\), both payment and allocation are zero.
Budget feasibility for every report measure. Because \(\nu\) is a probability measure,
\[ \int p_q(b;\nu)\,d\nu(q,b) =\bar B\,\nu\bigl(\{(q,b):b\le\bar B\}\bigr) \le\bar B. \]
This argument does not require reports to lie within the true-cost bound.
Optimality on every required society. Suppose \(\nu\) is supported on \(b\in[0,\bar B]\). Full allocation is feasible for the benchmark because
\[ \int b\,d\nu(q,b)\le\bar B\int1\,d\nu(q,b)=\bar B. \]
Also, for every feasible allocation \(z\), nonnegativity of the public values and \(z\le1\) imply
\[ \int v_qz(q,b)\,d\nu(q,b)\le\int v_q\,d\nu(q,b). \]
Consequently,
\[ \mathrm{OPT}(\nu)=\int v_q\,d\nu(q,b) =\int v_qx_q(b;\nu)\,d\nu(q,b). \]
Thus the mechanism achieves factor \(1\), including when all values are zero.
Computational efficiency. The finite representation consists of the rational threshold \(\bar B\) and the two constant outcomes. Constructing it and evaluating it at a rational report require only copying input data and an exact rational comparison. Both operations have polynomial bit complexity.
The preceding conclusion follows directly from the stated normalization. Nevertheless, zero-mass truthfulness also permits an efficient constant-factor mechanism when full procurement need not be affordable.
Here is a self-contained construction for finitely supported societies with arbitrary nonnegative costs. It satisfies truthfulness for every true cost \(c\ge0\).
Write the support as \((q_i,b_i)\), with masses \(\mu_i>0\). For entries with \(v_{q_i}>0\), define
\[ w_i=\mu_i v_{q_i}, \qquad d_i=\frac{b_i}{v_{q_i}}, \qquad S=\sum_{i:v_{q_i}>0}w_i. \]
If \(S=0\), use zero allocation and payment everywhere. Its benchmark value is zero. Henceforth assume \(S>0\).
For \(s\ge0\), define
\[ W_{<}(s)=\sum_{i:d_i<s}w_i, \qquad W_{\le}(s)=\sum_{i:d_i\le s}w_i. \]
Choose
\[ t=\inf\{s>0:sW_{\le}(s)\ge\bar B\}. \]
This threshold exists and is positive. Indeed, \(sW_{\le}(s)\le sS\), so every member of the defining set is at least \(\bar B/S>0\). For sufficiently large \(s\), all positive-value support entries are included and \(sW_{\le}(s)=sS\), which eventually exceeds \(\bar B\).
The function \(sW_{\le}(s)\) is nondecreasing and right-continuous. Its left limit at \(t\) is \(tW_{<}(t)\). The definition of \(t\) therefore gives
\[ tW_{<}(t)\le\bar B\le tW_{\le}(t). \]
Put \(\Delta=W_{\le}(t)-W_{<}(t)\). If \(\Delta>0\), set
\[ \alpha=\frac{\bar B/t-W_{<}(t)}{\Delta}. \]
The preceding inequalities imply \(0\le\alpha\le1\). If \(\Delta=0\), those inequalities imply \(W_{<}(t)=\bar B/t\); set \(\alpha=0\).
For a class with \(v_q>0\), define
\[ x_q(r;\nu)= \begin{cases} 1,&r<t v_q,\\ \alpha,&r=t v_q,\\ 0,&r>t v_q, \end{cases} \qquad p_q(r;\nu)=t v_qx_q(r;\nu). \]
For \(v_q=0\), both schedules are zero.
Fix \(\nu\) and a positive-value class \(q\). Zero mass means that changing the tagged supplier’s report leaves \(t\) and \(\alpha\) fixed. Its utility at report \(r\) is
\[ (t v_q-c)x_q(r;\nu). \]
If \(c<t v_q\), truthful reporting gives allocation \(1\), which maximizes this expression. If \(c>t v_q\), truthful reporting gives allocation \(0\), which maximizes it. If \(c=t v_q\), every report gives utility zero. This proves truthfulness, including at the threshold.
A positive allocation occurs only when \(r\le t v_q\), so \(p_q(r;\nu)\ge r x_q(r;\nu)\). Moreover, total payment is exactly
\[ \int p_q(b;\nu)\,d\nu(q,b) =t\bigl(W_{<}(t)+\alpha\Delta\bigr) =\bar B. \]
Thus the mechanism is individually rational and budget feasible.
Let \(V\) be its achieved value. By construction,
\[ V=W_{<}(t)+\alpha\Delta=\frac{\bar B}{t}. \]
Consider any feasible benchmark allocation \(z_i\in[0,1]\). Its value from entries with \(d_i<t\) is at most \(W_{<}(t)\). For entries with \(d_i\ge t\), the inequality \(b_i\ge t v_{q_i}\) gives
\[ \sum_{i:d_i\ge t}\mu_i v_{q_i}z_i \le\frac1t\sum_{i:d_i\ge t}\mu_i b_i z_i \le\frac{\bar B}{t}. \]
Zero-value entries contribute nothing. Therefore every feasible benchmark allocation has value at most
\[ W_{<}(t)+\frac{\bar B}{t} \le\frac{2\bar B}{t} =2V. \]
This proves factor \(2\) even without the original cost bound.
Sort the distinct rational ratios \(d_i\), and compute their cumulative weights. The threshold \(t\) either equals a support ratio or lies between consecutive ratios, where \(W_{\le}(s)\) is a constant positive cumulative weight \(W\). In the latter case, \(t=\bar B/W\).
Thus one can enumerate the support ratios and the numbers \(\bar B/W\) for all positive cumulative weights, and select a candidate satisfying
\[ tW_{<}(t)\le\bar B\le tW_{\le}(t). \]
There are at most \(2\tau\) candidates. Exact rational arithmetic finds \(t\) and \(\alpha\) in polynomial time, with polynomial output bit length. Each schedule is represented by its rational threshold \(t v_q\), its boundary allocation \(\alpha\), and its payment multiplier \(t v_q\); rational-report evaluation is polynomial in the input and query bit lengths.
The factor-\(1\) mechanism completely settles the problem as stated. The factor-\(2\) construction additionally shows that the requested factor \(2.62\) remains achievable in the zero-mass model even after removing the assumption that makes full procurement affordable.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the stated task. The factor-\(1\) mechanism satisfies every requirement, and the additional factor-\(2\) construction is also sound. No major or minor mathematical issues were found.
The full-procurement argument uses the task’s explicit assumptions: society mass is \(1\), every cost relevant to the approximation requirement is at most \(\bar B\), and the available budget is \(\bar B\). It does not depend on an unintended interpretation.
The schedules specify outcomes for every class, every society, and every report \(r\ge0\), including the boundary \(r=\bar B\). Their allocations lie in \([0,1]\), their payments are nonnegative, and both schedules are measurable step functions.
They are deterministic and anonymous: suppliers with the same class and report receive identical outcomes. Independence from \(\nu\) is permitted by the task.
For every permitted true cost \(c\in[0,\bar B]\), truthful utility is \(\bar B-c\).
Every report \(r\le\bar B\) gives the same utility, while every report \(r>\bar B\) gives zero utility. Since \(\bar B-c\ge0\), the required incentive inequality holds for every report. At \(c=\bar B\), all reports give zero utility, so the boundary case also satisfies weak truthfulness.
For \(r\le\bar B\), allocation is \(1\) and payment is \(\bar B\ge r\). For \(r>\bar B\), allocation and payment are both zero. Thus the stronger report-wise requirement \(p_q(r;\nu)\ge r x_q(r;\nu)\) holds throughout the report domain.
The displayed payment integral is correct. The mass receiving payment is at most \(1\), so total payment is at most \(\bar B\).
This verifies budget feasibility even for report measures containing reports above \(\bar B\), as required.
On every society covered by the approximation requirement, full allocation has total cost at most \(\bar B\), because \(b\le\bar B\) throughout the support and total mass is \(1\).
The upper bound on every benchmark allocation is also correct: \(v_q\ge0\) and \(z(q,b)\le1\) imply that its value cannot exceed the value of full allocation. Therefore full allocation attains \(\mathrm{OPT}(\nu)\), and the proposed mechanism implements it on every required society.
This establishes factor \(1\), hence factor \(2.62\). Zero costs, zero values, and the case where all values vanish are covered.
The shared threshold and constant outcomes form a finite representation of all class schedules. The threshold is already a binary rational in the input. Construction and rational-report evaluation require only polynomial-time copying and exact comparison.
The mechanism therefore meets both computational requirements in the task.
This extension is unnecessary to settle the target, but its substantive claims also withstand verification.
The ratios \(d_i\) are defined only for positive-value entries, avoiding division by zero. The subsequent ratio-indexed sums consistently concern those entries.
If \(S=0\), every supported entry has zero value, so the benchmark value is zero. Setting all schedules to zero satisfies truthfulness, individual rationality, and budget feasibility.
For \(S>0\), the defining set is nonempty because sufficiently large \(s\) includes every positive-value entry and makes \(sS\ge\bar B\).
The bound \(sW_{\le}(s)\le sS\) correctly implies \(t\ge\bar B/S>0\). Thus every later division by \(t\) is valid.
For finite support, the stated monotonicity, right-continuity, and left-limit formula are correct. They justify
\[
tW_{<}(t)\le\bar B\le tW_{\le}(t).
\]
When \(\Delta>0\), these inequalities place \(\alpha\) in \([0,1]\). When \(\Delta=0\), they force \(W_{<}(t)=\bar B/t\), so setting \(\alpha=0\) preserves the payment and value identities.
There is no omitted threshold case.
With \(\nu\) fixed, the utility expression \((tv_q-c)x_q(r;\nu)\) is correct.
The proposed truthful allocation maximizes this expression in each of the three cases \(c<tv_q\), \(c>tv_q\), and \(c=tv_q\). Zero-value classes have zero utility at every report.
Positive allocations occur only at reports at most the payment threshold, establishing report-wise individual rationality.
The total-payment identity follows directly from the definition of \(\alpha\) and remains valid when \(\Delta=0\).
The achieved-value identity \(V=\bar B/t\) is correct. The benchmark decomposition also holds:
Since \(W_{<}(t)\le\bar B/t\), the displayed factor-\(2\) bound follows with the stated constant.
The candidate enumeration covers thresholds occurring at support ratios and thresholds occurring between ratios or beyond the largest ratio. The asserted bound of at most \(2\tau\) candidates is valid.
All candidate checks and schedule parameters use rational arithmetic on polynomially many input rationals. Their bit lengths remain polynomial, and rational-report evaluation has the claimed complexity.
None. The exact mechanism independently settles the assigned question, and the extension introduces no mathematical inconsistency.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.