Answer: A polynomial-time black-box transformation exists, with \(K=3\) for the natural logarithm and no additive error.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven $\epsilon > 0$, black-box access to algorithm~$\alg$ and distribution $\dists$, one can construct a BIC mechanism $\mathcal{M}$ that is cost-recovering in expectation, with $\ex_{\vals}[SC(\mathcal{M})] \leq O(\min\{\log(h), \log(n)\}) \ex_{\vals}[SC(\alg)] + \epsilon$. The mechanism runs in time polynomial in $1/\eps$, $n$, and the runtime of $\alg$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_{g,v}\) over finitely many cohort-value types, a monotone service-cost oracle \(C\) on served-mass vectors, and a black-box baseline allocation rule \(\mathcal A\) for the aggregate population, can one compute in time polynomial in \(1/\epsilon\), support size \(\tau\), input bit length \(L\), and oracle runtime a BIC, individually rational mechanism that recovers expected cost and has expected social cost at most \(O(\log h)\,\mathbb E[SC(\mathcal A)]+\epsilon\)?
A society is given by its support: the list of the \(\tau\) cohort-value types with positive mass, each mass \(\mu_{g,v}\) a binary rational; \(\tau\) is the support size, not the number of possible types. There are \(m\) public cohorts, total mass \(\sum_{g,v}\mu_{g,v}=1\), and rational private values \(v\in[0,1]\), with at least one positive value; set \(h=v_{\max}/v_{\min}\), using the largest and smallest positive supported values.
For cohort \(g\), permitted reports are its supported values and zero. Individuals are nonatomic: a unilateral report changes neither the aggregate society nor the public cohort. Mechanisms treat individuals with the same cohort and report identically in distribution.
A randomized allocation specifies served fractions \(x_{g,v}\in[0,1]\); its served-mass vector is \(z_g=\sum_v\mu_{g,v}x_{g,v}\). An exact oracle returns nonnegative rational \(C(z)\), coordinatewise monotone on \(\prod_g[0,\sum_v\mu_{g,v}]\), with \(C(0)=0\); no continuity or convexity is assumed.
The arbitrary, possibly randomized baseline oracle \(\mathcal A\) accepts rational aggregate report distributions with the same cohort totals and permitted reports, and returns feasible rational served fractions. Both oracles have finite binary outputs; let \(T\) denote their runtime bounds and \(L\) the input bit length.
Let \(p_{g,v}\) be payments per unit mass. BIC requires \(v\bar x_{g,v}-\bar p_{g,v}\geq v\bar x_{g,w}-\bar p_{g,w}\) for every permitted \(v,w\) within a cohort, where bars average all mechanism randomness at the truthful aggregate society. Require individual rationality in every realization: only served individuals pay, with nonnegative charges at most their truthful value.
Define \(SC=C(z)+\sum_{g,v}\mu_{g,v}v(1-x_{g,v})\); expected cost recovery means \(\mathbb E[\sum_{g,v}\mu_{g,v}p_{g,v}]\geq\mathbb E[C(z)]\). Costs are evaluated on realized served masses before taking expectations.
Does a black-box transformation, with construction and execution time polynomial in \(m,\tau,L,1/\epsilon,T\), always produce such a BIC, individually rational, expected-cost-recovering mechanism satisfying \(\mathbb E[SC(\mathcal M)]\leq K(1+\log h)\mathbb E[SC(\mathcal A)]+\epsilon\) for a universal constant \(K\), or is this approximation guarantee unattainable with polynomial oracle access?
For finite independent agents, a polynomial-time black-box transformation achieves BIC, individual rationality, expected cost recovery, and social-cost inflation \(O(1+\min\{\log h,\log n\})\), plus arbitrary additive error ([source](https://www.fuhuthu.com/cost-recovery.pdf)). No result settling this exact nonatomic oracle model was identified in the literature search.
The guarantee is attainable with polynomial oracle access. There is a transformation using one call to \(\mathcal A\) and \(O(L)\) calls to \(C\) that satisfies BIC, individual rationality in every realization, and cost recovery in every realization. It achieves
\(\mathbb E[SC(\mathcal M)]\leq 3(1+\ln h)\mathbb E[SC(\mathcal A)]\).
Thus no additive error is needed.
The key nonatomic feature is that a unilateral report leaves the aggregate distribution unchanged. Consequently, allocation schedules and prices computed from that aggregate remain fixed when checking an individual’s incentive constraints.
Fix one realization of the baseline at the truthful aggregate society. Write its allocations as \(x_{g,v}\), its served masses as \(z_g\), and its cost as \(c=C(z)\).
For each cohort, define
\(b_g=\sum_{v>0}\mu_{g,v},\qquad q_g=\min\{z_g,b_g\}\).
Construct an allocation \(a\) by assigning exactly mass \(q_g\) to the highest positive values in cohort \(g\): serve higher values completely, at most one boundary value fractionally, and lower values not at all. Set \(a_{g,0}=0\), including when zero is a permitted but unsupported report. If \(q_g=0\), set the entire cohort’s schedule to zero.
This gives a nondecreasing allocation schedule on every cohort’s permitted reports. Its served-mass vector is \(q\), so coordinatewise monotonicity of the cost gives
\(C(q)\leq C(z)=c\).
We next verify that this reassignment does not decrease served value.
Fix a cohort with positive supported values \(u_1<\cdots<u_r\). Let \(s_i=\mu_{g,u_i}x_{g,u_i}\), let \(r_g=\sum_i s_i\), and define the tail masses
\(B_i=\sum_{\ell=i}^r\mu_{g,u_\ell},\qquad S_i=\sum_{\ell=i}^r s_\ell\).
Since \(r_g\leq q_g\), we have \(S_i\leq\min\{q_g,B_i\}\). The highest-value-first allocation has served tail mass exactly \(\min\{q_g,B_i\}\). The telescoping identity
\(\sum_{i=1}^r u_i s_i=u_1r_g+\sum_{i=2}^r(u_i-u_{i-1})S_i\)
therefore implies
\(\sum_v\mu_{g,v}v a_{g,v}\geq\sum_v\mu_{g,v}v x_{g,v}\).
The claim is immediate for cohorts with no positive supported values. Summing over cohorts gives
\(U(a)\leq U(x)\),
where \(U(y)=\sum_{g,v}\mu_{g,v}v(1-y_{g,v})\) denotes unserved value.
Consider any nondecreasing allocation schedule \(y\) in a cohort. List its permitted reports as
\(0=u_0<u_1<\cdots<u_r\),
and suppose \(y_0=0\). Define payments per unit mass by
\(p_0=0,\qquad p_i=\sum_{\ell=1}^i u_\ell(y_\ell-y_{\ell-1})\).
These payments satisfy all incentive constraints.
Indeed, if \(i>j\), the truthful utility advantage of type \(u_i\) over report \(u_j\) is
\(u_i(y_i-y_j)-(p_i-p_j)=\sum_{\ell=j+1}^i(u_i-u_\ell)(y_\ell-y_{\ell-1})\geq0\).
If \(i<j\), that advantage is
\((p_j-p_i)-u_i(y_j-y_i)=\sum_{\ell=i+1}^j(u_\ell-u_i)(y_\ell-y_{\ell-1})\geq0\).
Both inequalities follow from monotonicity of \(y\).
Furthermore,
\(0\leq p_i\leq u_i\sum_{\ell=1}^i(y_\ell-y_{\ell-1})=u_i y_i\).
Implement the payment by charging each served individual \(p_i/y_i\) when \(y_i>0\), and charging nothing when unserved. Every truthful served individual then pays a nonnegative amount at most their value. This proves individual rationality in every realization. In the nonatomic fractional-allocation model, the class’s total payment is exactly \(\mu_{g,u_i}p_i\).
We will also use the following consequence: if \(y_i=0\) whenever \(u_i<t\), then
\(p_i\geq t y_i\).
To see this, every nonzero increment \(y_\ell-y_{\ell-1}\) occurs at a report \(u_\ell\geq t\), so the payment formula gives the inequality directly.
Let
\(v_{\min}=\min\{v>0:\mu_{g,v}>0\text{ for some }g\},\qquad J=1+\lfloor\log_2 h\rfloor\).
Define thresholds
\(t_j=2^jv_{\min},\qquad j=0,\ldots,J\).
In particular, \(t_J>v_{\max}\).
After obtaining the baseline realization and constructing \(a\) as above, form, for each threshold,
\(y^j_{g,v}=a_{g,v}\mathbf 1_{\{v\geq t_j\}},\qquad z^j_g=\sum_v\mu_{g,v}y^j_{g,v}\).
Every \(y^j\) is nondecreasing within each cohort and is zero at report zero. Compute its payments \(p^j\) using Section 2, and its revenue
\(R_j=\sum_{g,v}\mu_{g,v}p^j_{g,v}\).
Choose the smallest index \(k\) satisfying
\(R_k\geq C(z^k)\).
Such an index always exists: at \(j=J\), allocation, revenue, and cost are all zero.
Output allocation \(y^k\), charging served individuals \(p^k_{g,v}/y^k_{g,v}\) and unserved individuals zero.
All these computations use exact rational arithmetic.
Fix the truthful aggregate society and condition on a realization of the baseline oracle’s randomness.
A unilateral report changes neither that aggregate nor the individual’s public cohort. Hence it changes none of the computed objects \(a\), \(k\), or the cohort’s allocation and payment schedules. An individual reporting \(w\) receives service probability \(y^k_{g,w}\) and expected payment \(p^k_{g,w}\).
Section 2 proves the incentive inequalities conditional on this baseline realization. Averaging them over the baseline randomness proves precisely the required BIC inequalities.
Section 2 also proves individual rationality in every realization: unserved individuals pay zero, and truthful served individuals pay between zero and their value.
Finally, the selected threshold satisfies
\(\sum_{g,v}\mu_{g,v}p^k_{g,v}=R_k\geq C(z^k)\).
Thus costs are recovered in each realization of the baseline. Taking expectations gives expected cost recovery. The cost here is evaluated at the realized served-mass vector \(z^k\), before averaging.
Continue to fix one baseline realization.
Because \(k\) is the first successful threshold, every \(j<k\) satisfies
\(R_j<C(z^j)\).
Also \(z^j\leq q\leq z\) coordinatewise, so
\(C(z^j)\leq c\).
Let the served value discarded between consecutive thresholds be
\(D_j=\sum_{g,v:\,t_j\leq v<t_{j+1}}\mu_{g,v}v a_{g,v}\).
Since \(t_{j+1}=2t_j\), and Section 2 gives \(p^j_{g,v}\geq t_jy^j_{g,v}\),
\(D_j\leq 2t_j\sum_{g,v:\,t_j\leq v<t_{j+1}}\mu_{g,v}a_{g,v}\leq 2t_j\sum_{g,v}\mu_{g,v}y^j_{g,v}\leq 2R_j\).
For each failed threshold, therefore,
\(D_j\leq2c\).
All positive supported values are at least \(t_0\). Consequently, the service discarded by the chosen threshold is partitioned by these bands:
\(U(y^k)=U(a)+\sum_{j=0}^{k-1}D_j\leq U(x)+2kc\).
Combining this with \(C(z^k)\leq c\) yields
\(SC(\mathcal M)\leq U(x)+(1+2k)c\leq(1+2J)SC(\mathcal A)\).
Finally,
\(1+2J\leq3+2\log_2h=3+\frac{2}{\ln2}\ln h\leq3(1+\ln h)\).
This bound holds separately for every baseline realization. Averaging proves
\(\mathbb E[SC(\mathcal M)]\leq3(1+\ln h)\mathbb E[SC(\mathcal A)]\).
No continuity or convexity assumption was used.
The transformation makes one baseline query and at most \(J+1\) cost queries.
Because the positive rational values are encoded in the input and lie in \([0,1]\), their denominators have at most \(L\) bits. Hence \(v_{\min}\geq2^{-L}\), giving \(h\leq2^L\) and \(J=O(L)\).
Sorting the supported values, computing the allocations and payments, and comparing revenues with costs require polynomially many rational arithmetic operations. Every constructed rational has bit length polynomial in \(m,\tau,L,T\): it is obtained through polynomially many sums, products, and quotients of input rationals and oracle outputs. The resulting construction and execution time is therefore polynomial in \(m,\tau,L,T\), and consequently also in \(m,\tau,L,1/\epsilon,T\).
The support is handled explicitly; the algorithm never enumerates unsupported cohort-value types or computes expectations of the randomized baseline.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested transformation, subject to one minor gap in the explanation of rational bit lengths. The allocation, incentive, cost-recovery, and approximation arguments are correct. No major mathematical issue was found.
The quantities \(z_g\), \(b_g\), and \(q_g=\min\{z_g,b_g\}\) satisfy \(0\leq q_g\leq b_g\), so the prescribed highest-value-first allocation exists. Its served mass is exactly \(q_g\), and \(q\leq z\) coordinatewise. Thus the stated use of cost monotonicity, \(C(q)\leq C(z)\), is justified.
For the positive types in a cohort, \(r_g\leq z_g\) and \(r_g\leq b_g\), hence \(r_g\leq q_g\). Each original served tail satisfies both \(S_i\leq r_g\leq q_g\) and \(S_i\leq B_i\). The reassigned served tail is indeed \(\min\{q_g,B_i\}\).
The telescoping identity is correct. Its coefficients are nonnegative, so the tail comparisons imply the claimed comparison of served values. Zero-valued types contribute no served value. Cohorts without positive supported values are handled correctly. Therefore \(U(a)\leq U(x)\) follows.
For a nondecreasing schedule with \(y_0=0\), the increments \(y_\ell-y_{\ell-1}\) are nonnegative. Both displayed utility-difference identities are correct, and their summands have the stated signs. They cover upward and downward deviations, including deviations involving report zero. The equal-report case is automatic.
The bounds \(0\leq p_i\leq u_i y_i\) follow directly from \(u_\ell\leq u_i\) for \(\ell\leq i\). In particular, \(y_i=0\) implies \(p_i=0\), so the charging rule has no undefined division.
Charging \(p_i/y_i\) only upon service gives expected payment \(p_i\) and a realized charge in \([0,u_i]\). This establishes the required individual rationality for truthful reporting.
The threshold consequence \(p_i\geq t y_i\) is also correct: all nonzero increments occur at reports at least \(t\), and the increments sum to \(y_i\).
The task guarantees at least one positive supported value, so \(v_{\min}>0\) and \(h\geq1\). With \(J=1+\lfloor\log_2 h\rfloor\), one has \(2^J>h\), including when \(h\) is an exact power of two. Consequently \(t_J>v_{\max}\).
Multiplying a nonnegative, nondecreasing schedule by the threshold indicator preserves monotonicity: the schedule is zero below the threshold and follows the original schedule above it. Report zero remains unserved.
At index \(J\), allocation and payments are zero, and \(C(0)=0\). The successful-index set is therefore nonempty, and its smallest member exists. No continuity assumption is needed.
At the truthful aggregate society, a unilateral report leaves the aggregate distribution and cohort unchanged. Consequently, conditional on the baseline randomness, the computed schedule and threshold remain fixed when evaluating a deviation.
Section 2 therefore applies to every permitted report pair conditional on each baseline realization. Averaging these inequalities proves exactly the required BIC inequalities. The proof does not require computing those expectations.
The payment aggregation uses the task’s fractional-allocation interpretation: each class has the specified realized served fraction. Under that interpretation, its total payment is \(\mu_{g,u_i}p_i\). Independently sampling service without preserving the prescribed served masses would require additional justification, but that is not the allocation model specified in the task.
The selection condition is \(R_k\geq C(z^k)\). The output’s total payment is \(R_k\), and its realized served-mass vector is \(z^k\). Thus cost recovery holds conditional on each baseline realization, which implies expected cost recovery.
The argument evaluates \(C(z^k)\) before averaging. It makes no unjustified exchange between cost evaluation and expectation.
Every failed threshold satisfies \(R_j<C(z^j)\leq c\), since \(z^j\leq q\leq z\).
In the band defining \(D_j\), values are less than \(2t_j\). The band’s served mass is no larger than the total served mass under \(y^j\), and the payment lower bound gives \(R_j\geq t_j\sum_{g,v}\mu_{g,v}y^j_{g,v}\). These facts justify all three inequalities leading to \(D_j\leq2R_j\), and hence \(D_j\leq2c\) for failed thresholds.
The half-open bands partition precisely the positive values removed before threshold \(k\). Values equal to a threshold are assigned to the correct band. Thus
\[
U(y^k)=U(a)+\sum_{j=0}^{k-1}D_j
\]
is valid, including the empty sum when \(k=0\).
Combining this identity with the cost and reassignment bounds yields
\[
SC(\mathcal M)\leq U(x)+(1+2k)c\leq(1+2J)SC(\mathcal A).
\]
The final constant conversion is correct because \(\ln h\geq0\) and \(2/\ln2<3\).
The bound holds for each baseline realization, so averaging is justified. It establishes \(K=3\) with no additive error.
There is one baseline query and at most \(J+1\) cost queries. The input encoding gives \(v_{\min}\geq2^{-L}\), while \(v_{\max}\leq1\). Hence \(h\leq2^L\) and \(J=O(L)\). Unsupported types need not be enumerated.
Minor issue: Section 6 justifies polynomial bit lengths by saying the rationals are obtained through polynomially many sums, products, and quotients. That general inference is insufficient: polynomially many arithmetic operations can produce exponentially long numbers, for example through repeated squaring.
This does not undermine the transformation’s substantive runtime claim. The displayed computations have a restricted structure, and the missing justification is routine arithmetic bookkeeping.
Minimum clarification requested: Give a bit-length bound for the actual intermediate quantities—served masses, boundary allocation fractions, thresholds, payments, revenues, and conditional charges—in terms of input bit lengths and baseline-output bit lengths. Explain why these formulas avoid uncontrolled repeated multiplication or division. No new mathematical lemma or change to the mechanism is needed.
Cohorts with no positive supported values receive zero service. Unsupported report zero is explicitly assigned zero allocation and payment. A zero boundary allocation causes no division. The case \(h=1\) still has a terminal threshold strictly above all positive values. If the baseline cost is zero, monotonicity makes the initial threshold successful. These cases create no additional gaps.
The output resolves the continuous oracle model in substance. Its only identified deficiency is the routine bit-complexity explanation in Section 6.
⟨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.