Answer: A uniform deterministic direct mechanism exists, is exactly evaluable in polynomial time, and achieves the required \(2\)-approximation.
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePRUNE-&-ASSIGN is a truthful, individually rational, budget-feasible 2-approximation mechanism for instances of the divisible agent model with linear valuation functions, and runs in time polynomial in n.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a total seller mass \(N\), budget \(B\), and a rational distribution \(\mu\) over \(\tau\) truthful types \((v_t,c_t)\), does there exist a deterministic direct mechanism, evaluable in time polynomial in \(\tau\) and the input bit length, that assigns each infinitesimal seller with public value \(v\), true cost \(c\), and report \(b\) an allocation \(x(v,b;\nu)\in[0,1]\) and payment \(p(v,b;\nu)\), where \(\nu\) is the fixed distribution of other sellers’ reports? Require dominant-strategy truthfulness and individual rationality for each seller, aggregate payments at most \(B\) for every report profile, and truthful aggregate value at least half of \(\max\{N\sum_t\mu_t v_t x_t: N\sum_t\mu_t c_t x_t\le B,\ x_t\in[0,1]\}\).
An atomless seller society has total mass \(N>0\), budget \(B>0\), public values \(v_t\geq0\), and private unit costs \(0<c_t\leq B\); all input numbers are binary rationals.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Write its normalized distribution as \(\mu\), with \(\sum_t\mu_t=1\), and let \(m\) count distinct public values.
Each seller may report any rational cost \(b\in[0,B]\). Admissible report distributions \(\nu\) have finite rational support and the same public-value marginal as the society; sellers of one truthful type may submit different reports.
A deterministic direct mechanism returns allocation and payment densities \(x(v,b;\nu)\in[0,1]\) and \(p(v,b;\nu)\geq0\), with utility density \(p-cx\). An individual seller's deviation leaves \(\nu\) fixed. The mechanism receives public information and reported costs, without separate access to truthful costs.
Require dominant-strategy truthfulness and individual rationality at truthful reporting for every seller and every admissible distribution of others' reports, and \(N\sum_{(v,b)\in\operatorname{supp}(\nu)}\nu(v,b)p(v,b;\nu)\leq B\) for every admissible report distribution.
Define \(\operatorname{OPT}(\mu)=\max\{N\sum_t\mu_t v_t y_t:N\sum_t\mu_t c_t y_t\leq B,\ 0\leq y_t\leq1\}\). Let \(L\) be the total binary encoding length of the public data, distribution being evaluated, and queried report; running times are measured in \(m,\tau,L\).
Does a uniform deterministic direct mechanism satisfying these requirements exist, evaluable in time polynomial in \(m,\tau,L\), with \(N\sum_t\mu_t v_t x(v_t,c_t;\mu)\geq\operatorname{OPT}(\mu)/2\) for every admissible truthful society, or is this guarantee unattainable by such a mechanism?
For finitely many sellers with fractional allocations, linear values, and each full-service cost bounded by the budget, a polynomial-time deterministic truthful, individually rational, budget-feasible \(2\)-approximation exists ([Amanatidis et al.](https://arxiv.org/html/2307.07385v3)).
For finite sellers under an asymptotic small-bidder assumption, the optimal approximation ratio is \(e/(e-1)\) ([Anari et al.](https://afshin-nikzad.com/pdfs/Procurement.pdf)); this concerns a different model. No result settling exactly the rational-support atomless problem was located.
The guarantee is attainable. We construct a uniform deterministic mechanism and prove truthfulness, individual rationality, budget feasibility, and the required approximation. The construction uses the reported distribution and public data only.
Throughout, write \(w_t=N\nu_t\) for the actual mass of a reported type. Ignore types with public value zero by assigning them allocation and payment zero.
Let \(M=N\sum_{t:v_t>0}\nu_t\) be the total mass with positive public value. This quantity depends only on the public-value marginal.
If \(M\leq1\), assign every positive-value seller allocation \(1\) and payment density \(B\), independently of their report. This branch will be verified below.
Suppose henceforth that \(M>1\). For \(r\geq0\), define
\[ F(r)=\sum_{t:v_t>0}w_t\min\{rv_t,B\}\mathbf{1}_{\{b_t\leq rv_t\}}. \]
Here and below, the mathematics uses the specified inline delimiters; equivalently, the defining expression is \(F(r)=\sum_{t:v_t>0}w_t\min\{rv_t,B\}\mathbf{1}_{\{b_t\leq rv_t\}}\).
The function \(F\) is nondecreasing and right-continuous. Indeed, each summand is zero before \(b_t/v_t\), jumps there if \(b_t>0\), subsequently increases linearly, and becomes constant at \(B/v_t\). The ordering of these two breakpoints follows from \(b_t\leq B\).
Moreover, \(F(0)=0\), and for all sufficiently large \(r\), \(F(r)=BM>B\). Define
\(r_*=\inf\{r\geq0:F(r)\geq B\}\).
This threshold is finite and strictly positive: with \(K=\sum_{t:v_t>0}w_tv_t>0\), we have \(F(r)\leq rK\), so \(r_*\geq B/K>0\).
Define
\(F_-=\sum_{t:v_t>0,\ b_t<r_*v_t}w_t\min\{r_*v_t,B\}\),
and
\(E=\sum_{t:v_t>0,\ b_t=r_*v_t}w_tb_t\).
The first expression is the left limit of \(F\) at \(r_*\), and \(F(r_*)=F_-+E\). Right-continuity and the definition of the first crossing imply
\(F_-\leq B\leq F_-+E\).
Set \(\alpha=(B-F_-)/E\) if \(E>0\), and set \(\alpha=1\) if \(E=0\). Consequently, \(0\leq\alpha\leq1\), and in both cases \(F_-+\alpha E=B\).
For any queried positive public value \(v\) and rational report \(b\in[0,B]\), define the allocation as follows:
Define the payment density by
\(p(v,b;\nu)=\min\{r_*v,B\}\,x(v,b;\nu)\).
These rules also define the mechanism at reports absent from the support of \(\nu\). All fractional allocations are deterministic allocation densities, as permitted in the question.
Fix any admissible distribution \(\nu\), any public value \(v\), and any true cost \(c\in(0,B]\). By atomlessness, an individual deviation leaves \(\nu\), and hence \(r_*\) and \(\alpha\), fixed. We therefore compare reports within one fixed menu.
The zero-value menu always gives utility zero. In the branch \(M\leq1\), every report by a positive-value seller gives utility \(B-c\geq0\), so truthfulness and individual rationality hold.
Consider the branch \(M>1\), and put \(s=r_*v\).
If \(s>B\), every admissible report satisfies \(b<s\). Every report therefore gives allocation \(1\), payment \(B\), and utility \(B-c\geq0\).
Suppose \(s\leq B\). Reports below \(s\) give utility \(s-c\); the report equal to \(s\) gives utility \(\alpha(s-c)\); and reports above \(s\) give utility zero.
There are three cases:
Thus truthful reporting maximizes utility and gives nonnegative utility for every possible true cost and every fixed admissible distribution. This includes the endpoint \(s=B\).
If \(M\leq1\), total payments equal \(BM\leq B\).
If \(M>1\), the positive-value support types with \(b_t<r_*v_t\) contribute exactly \(F_-\) to total payments. Types with \(b_t=r_*v_t\) contribute exactly \(\alpha E\), because their offered price satisfies \(r_*v_t=b_t\leq B\). All other types receive zero.
Hence total payments are
\(N\sum_t\nu_t p(v_t,b_t;\nu)=F_-+\alpha E=B\).
Budget feasibility therefore holds for every admissible report distribution, including distributions containing zero reports.
Evaluate the mechanism at a truthful society, so \(\nu=\mu\) and \(b_t=c_t\).
If \(M\leq1\), purchasing every positive-value seller fully costs at most \(BM\leq B\). This allocation attains the maximum possible value, so the mechanism attains \(\operatorname{OPT}(\mu)\).
Now suppose \(M>1\). Write \(w_t=N\mu_t\), and define
\(A=\{t:v_t>0,\ c_t<r_*v_t\}\),
\(T=\{t:v_t>0,\ c_t=r_*v_t\}\).
The mechanism’s value is
\(V=\sum_{t\in A}w_tv_t+\alpha\sum_{t\in T}w_tv_t\).
Let \(V_A=\sum_{t\in A}w_tv_t\). Since the mechanism spends exactly \(B\), and each payment density is at most \(r_*v_t\) times the corresponding allocation density,
\(B=\sum_t w_t p(v_t,c_t;\mu)\leq r_*V\).
Consequently, \(B/r_*\leq V\).
Next, take any feasible benchmark allocation \(y\). For every positive-value type outside \(A\), its cost satisfies \(c_t\geq r_*v_t\). Since \(0\leq y_t\leq1\),
\(\sum_t w_tv_ty_t\leq V_A+\sum_{t\notin A,\ v_t>0}w_tv_ty_t\).
Using the cost inequality for these remaining types and then benchmark budget feasibility gives
\(\sum_{t\notin A,\ v_t>0}w_tv_ty_t\leq \frac{1}{r_*}\sum_{t\notin A,\ v_t>0}w_tc_ty_t\leq B/r_*\).
It follows that every feasible benchmark allocation has value at most
\(V_A+B/r_*\leq V+V=2V\).
Taking the maximum over benchmark allocations proves
\(N\sum_t\mu_tv_tx(v_t,c_t;\mu)\geq\operatorname{OPT}(\mu)/2\).
The argument includes ties at the threshold and types whose offered prices are capped at \(B\).
We finally verify computational uniformity and rational output.
For each positive-value support type, form the rational breakpoints \(b_t/v_t\) and \(B/v_t\), together with zero. There are at most \(2\tau+1\) breakpoints.
Sort these breakpoints. On every open interval between consecutive distinct breakpoints, \(F\) has the affine form \(F(r)=ar+d\), with rational coefficients. Its endpoint values and jumps are also rational.
Scan the intervals and breakpoints in increasing order:
This scan necessarily finds the crossing, because at the largest breakpoint every positive-value type is active and capped, giving \(F=BM>B\).
The coefficients, threshold, and \(\alpha\) are obtained using sums, products, comparisons, and divisions of input rationals. A direct implementation uses polynomially many such operations; even recomputing the coefficients on each interval takes only polynomial time in \(\tau\). Their binary encoding lengths remain polynomial in \(L\), since they involve sums of at most \(\tau\) products of input rationals and a bounded number of subsequent arithmetic operations.
Once \(r_*\) and \(\alpha\) are computed, a queried allocation and payment require only rational arithmetic and comparison. Thus evaluation is polynomial in \(m,\tau,L\), and all outputs are exact rationals.
The mechanism uses no separately supplied truthful costs: it performs this construction on whichever admissible report distribution it receives.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target. The construction is correct under the task’s explicit convention that an individual deviation leaves the reported distribution fixed. The incentive argument, budget calculation, approximation bound, and polynomial-time evaluation all hold. I found no major or minor mathematical issues.
The actual masses \(w_t=N\nu_t\) are used consistently. Discarding zero-value types by assigning allocation and payment zero preserves the relevant objective and does not compromise truthfulness or individual rationality.
The quantity \(M\) depends only on the public-value marginal, so its branch selection is unchanged by cost reports.
For \(M>1\), the stated behavior of each summand of \(F\) is correct, including reports \(b_t=0\) and \(b_t=B\). The assumption \(b_t\leq B\) ensures that activation occurs no later than the price cap. Thus \(F\) is nondecreasing and right-continuous.
The eventual value \(BM>B\) ensures that the crossing set is nonempty. The inequality \(F(r)\leq rK\), with finite positive \(K\), correctly establishes that \(r_*\) is strictly positive.
At this positive threshold, the expression \(F_-\) is indeed the left limit. Types satisfying \(b_t=r_*v_t\) contribute their activation jump \(w_tb_t\), since their reports satisfy \(b_t\leq B\). Consequently,
\[
F(r_*)=F_-+E
\]
is correct. The first-crossing property and right-continuity justify \(F_-\leq B\leq F_-+E\).
The definition of \(\alpha\) therefore gives an allocation fraction in \([0,1]\). When \(E=0\), the same inequalities force \(F_-=B\), so the stated identity \(F_-+\alpha E=B\) also holds in that case.
The allocation and payment rules cover every permitted report, including reports absent from the support. All allocations lie in \([0,1]\), and all payments are nonnegative.
Once the reported distribution is fixed, the threshold and tie fraction are fixed. The construction therefore supplies exactly the fixed menu needed for the task’s individual-deviation model. It uses reported costs rather than separately supplied truthful costs.
The zero-value menu gives zero utility at every report.
In the branch \(M\leq1\), allocation and payment are report-independent, and truthful utility is \(B-c\geq0\).
For \(M>1\), the case \(s=r_*v>B\) is handled correctly: every permitted report receives full allocation and payment \(B\).
When \(s\leq B\), the three possible utility expressions are correctly calculated. The comparisons for \(c<s\), \(c=s\), and \(c>s\) establish that truthful reporting maximizes utility. They also establish nonnegative truthful utility.
The boundary \(s=B\) causes no problem: although reports above \(s\) are unavailable, removing those alternatives cannot invalidate the comparisons. The argument applies to every true cost in the specified domain and every fixed admissible report distribution.
For \(M\leq1\), total payments are exactly \(BM\leq B\).
For \(M>1\), the strict-threshold types contribute exactly \(F_-\). The equality types contribute exactly \(\alpha E\), because their threshold prices equal their reports and do not exceed \(B\). All remaining types contribute zero.
Thus total payment is exactly \(B\). This calculation remains valid for distributions containing zero reports and does not assume truthful reporting.
For \(M\leq1\), full service to every positive-value type is feasible because each truthful unit cost is at most \(B\). Its value is the maximum possible value, so this branch attains the benchmark.
For \(M>1\), the expression for the mechanism’s value \(V\) correctly includes full allocation on \(A\) and fractional allocation on \(T\).
The inequality \(B\leq r_*V\) follows from exact budget expenditure and the pointwise payment cap. Its direction is correct, yielding \(B/r_*\leq V\).
Every positive-value type outside \(A\), including threshold ties, satisfies \(c_t\geq r_*v_t\). The benchmark contribution on \(A\) is at most \(V_A\), using \(y_t\leq1\). Its contribution outside \(A\) is at most \(B/r_*\), using the stated cost inequality and benchmark feasibility.
Finally, \(V_A\leq V\), so the displayed upper bound on every feasible benchmark allocation is at most \(2V\). Maximizing over feasible allocations gives the required guarantee. Price caps and threshold ties are both covered by these inequalities.
The listed breakpoints include every change in activation or capped-price behavior. Between consecutive distinct breakpoints, \(F\) has the stated rational affine form.
The scan covers crossings at jumps, inside intervals, and at endpoints. The largest breakpoint guarantees termination because \(F=BM>B\) there.
The rational arithmetic claim is justified by the structure described: coefficients are sums of polynomially many products of input rationals, and computing the threshold, tie fraction, and queried output requires only a bounded number of further arithmetic layers. Their encoding lengths remain polynomial in the total input length. Sorting, scanning, and even recomputing coefficients on each interval require polynomially many operations.
Accordingly, the mechanism is uniform, outputs exact rationals, and is evaluable within the requested polynomial bound.
No external theorem is invoked in the proof, and no additional lemma or clarification is needed to verify its conclusion.
⟨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.