Answer: Yes. A truthful mechanism retaining the full factor \(\alpha\) is computable in \(\operatorname{poly}(m,\tau,L)\) time using one black-box call.
Theorem 1 — class: algorithmic
Given item categories \(\mathcal J\), a public function \(f:2^{\mathcal J}\to\mathbb R\), a finite set \(V\) of private values, a rational mass distribution \(\mu\) on \(V\) with support size \(\tau\), and rational per-capita supplies \(q_j\), can a direct truthful mechanism be constructed from an \(\alpha\)-approximation to the aggregate welfare problem? Aggregate assignments \(x_{v,S}\) must satisfy \(\sum_S x_{v,S}=\mu_v\) and \(\sum_{v,S:j\in S}x_{v,S}=q_j\); the benchmark is \(\operatorname{OPT}(\mu)=\max_x\sum_{v,S}v f(S)x_{v,S}\). The mechanism must specify expected bundle values and payments for a tagged agent's reports, satisfy \(v z_v-p_v\ge v z_w-p_w\) for all \(v,w\in V\), achieve welfare at least \(\frac{3\alpha}{4ab}\operatorname{OPT}(\mu)\), and run in \(\operatorname{poly}(m,\tau,L)\) time for fixed \(a,b>1\).
Let \(\mathcal J\) contain \(m\geq1\) item categories, let \(f:2^{\mathcal J}\to\mathbb Q_{\geq0}\) be public and accessible through a value oracle, and let \(V\subseteq\mathbb Q_{\geq0}\) be a nonempty finite report domain. No monotonicity or empty-bundle normalization is imposed on \(f\).
A society is given by its support: the list of its \(\tau\) types \(v\in V\) with positive binary-rational masses \(\mu_v\), summing to \(1\); here \(V\) is precisely this support. Thus \(\tau\) is the support size, not the number of possible bundles or types. Supplies satisfy \(q_j\in\mathbb Q\cap[0,1]\).
An aggregate assignment consists of nonnegative masses \(x_{v,S}\), for \(v\in V\) and \(S\subseteq\mathcal J\), satisfying \(\sum_Sx_{v,S}=\mu_v\) and \(\sum_{v,S:j\in S}x_{v,S}=q_j\). Define \(W(x)=\sum_{v,S}v f(S)x_{v,S}\) and \(\operatorname{OPT}(\mu)=\max_x W(x)\).
Given \(\alpha\in\mathbb Q\cap(0,1]\), assume black-box access to a deterministic polynomial-time algorithm that returns a feasible \(\alpha\)-approximate aggregate assignment as a list of its nonzero entries for every rational society on \(V\), with the same public function and supplies.
A direct mechanism returns such a feasible assignment and rational expected payments \(p_v\). A tagged agent reporting \(v\) receives bundle \(S\) with probability \(x_{v,S}/\mu_v\), giving expected bundle value \(z_v=\mu_v^{-1}\sum_S f(S)x_{v,S}\). The tagged agent is infinitesimal, so changing its report leaves the society unchanged.
Truthfulness means \(v z_v-p_v\geq v z_w-p_w\) for all \(v,w\in V\), at every input society. Payments may have either sign. Let \(L\) include the binary input length and a bound on the bit length of oracle answers; count oracle queries and black-box calls as well as bit operations.
For every fixed rational \(a,b>1\), can an arbitrary such \(\alpha\)-approximation algorithm be converted into a direct truthful mechanism with \(W(x)\geq\frac{3\alpha}{4ab}\operatorname{OPT}(\mu)\) in \(\operatorname{poly}(m,\tau,L)\) time?
For finite societies of \(n\) agents, a [known conversion](https://arxiv.org/pdf/1007.3539) achieves factor \(\frac{3\alpha}{4ab}\) in time \(O((\log_a n)^{\log_b n}\operatorname{poly}(m,n))\); fixed \(a,b\) give quasi-polynomial time, while suitable varying parameters give factor \(\Omega(\alpha/\log n)\) in polynomial time.
No result settling this precise mass-based conversion problem was located.
Yes. In the stated infinitesimal-agent model, the full factor \(\alpha\) can be retained in polynomial time. One black-box call and one polynomial-size rational linear program suffice.
The key is that truthfulness is checked within a fixed society. We can rearrange bundle masses among types to make expected bundle values nondecreasing, preserving every supply and weakly increasing welfare.
Write the types as \(v_1<\cdots<v_\tau\), with masses \(\mu_1,\ldots,\mu_\tau>0\).
Let \(x^A\) be the black-box assignment. List its distinct supported bundles as \(S_1,\ldots,S_K\), ordered so that their oracle values satisfy \(f_1\leq\cdots\leq f_K\), where \(f_k=f(S_k)\). Define their aggregate masses by
\(y_k=\sum_{i=1}^{\tau}x^A_{i,S_k}\).
Thus \(y_k>0\) and \(\sum_k y_k=1\). Set
\(M_0=Y_0=0,\qquad M_i=\sum_{r=1}^{i}\mu_r,\qquad Y_k=\sum_{\ell=1}^{k}y_\ell.\)
Define the rearranged assignment by interval intersection:
\(\widehat x_{i,S_k}=\max\{0,\min(M_i,Y_k)-\max(M_{i-1},Y_{k-1})\}.\)
This assigns the lowest bundle values to the lowest types, allowing bundles to split across type boundaries.
The intervals \((M_{i-1},M_i]\) partition \((0,1]\), as do \((Y_{k-1},Y_k]\). Consequently,
\(\sum_k\widehat x_{i,S_k}=\mu_i,\qquad \sum_i\widehat x_{i,S_k}=y_k.\)
In particular, each item’s aggregate allocation remains unchanged:
\(\sum_{i,k:j\in S_k}\widehat x_{i,S_k}=\sum_{k:j\in S_k}y_k=q_j.\)
Moreover, if \(i<j\), \(\widehat x_{i,S_k}>0\), and \(\widehat x_{j,S_\ell}>0\), then \(k\leq\ell\): the type intervals and bundle intervals have the same left-to-right order. Hence \(f_k\leq f_\ell\).
Define \(\widehat z_i=\mu_i^{-1}\sum_k f_k\widehat x_{i,S_k}\). For \(i<j\),
\(\widehat z_j-\widehat z_i=\sum_{k,\ell}\frac{\widehat x_{i,S_k}\widehat x_{j,S_\ell}}{\mu_i\mu_j}(f_\ell-f_k)\geq0.\)
Thus the expected bundle values are nondecreasing across types.
We prove this explicitly for unequal type masses.
For each \(h\in\{2,\ldots,\tau\}\), let
\(a_{h,k}=\sum_{i=h}^{\tau}x^A_{i,S_k},\qquad b_{h,k}=\sum_{i=h}^{\tau}\widehat x_{i,S_k}.\)
Both vectors allocate bundle masses to the upper-type tail, so
\(0\leq a_{h,k},b_{h,k}\leq y_k,\qquad \sum_k a_{h,k}=\sum_k b_{h,k}=1-M_{h-1}.\)
Choose \(k_h\) with \(Y_{k_h-1}\leq M_{h-1}\leq Y_{k_h}\). By construction, \(b_{h,k}=0\) for \(k<k_h\), and \(b_{h,k}=y_k\) for \(k>k_h\). Therefore:
Since \(\sum_k(b_{h,k}-a_{h,k})=0\), it follows that
\(\sum_k f_k(b_{h,k}-a_{h,k})=\sum_k(f_k-f_{k_h})(b_{h,k}-a_{h,k})\geq0.\)
Finally, use the identity
\(v_i=v_1+\sum_{h=2}^{\tau}(v_h-v_{h-1})\mathbf 1_{\{i\geq h\}}.\)
The aggregate bundle masses agree between the two assignments, so the contribution involving \(v_1\) cancels. Consequently,
\(W(\widehat x)-W(x^A)=\sum_{h=2}^{\tau}(v_h-v_{h-1})\sum_k f_k(b_{h,k}-a_{h,k})\geq0.\)
When \(\tau=1\), the assignments coincide and the same conclusion holds.
This proves that the black-box support admits a feasible, monotone assignment with welfare at least \(W(x^A)\). No monotonicity or normalization of \(f\) was used.
If the black box returns rational masses, the rearrangement above is directly computable by rational arithmetic. Alternatively, the following construction uses only its bundle support and guarantees rational output.
Call the black box on the input society, collect its \(K\) distinct supported bundles, and query their values. Solve the linear program with variables \(X_{i,k}\), maximizing
\(\sum_{i=1}^{\tau}\sum_{k=1}^{K}v_i f_kX_{i,k},\)
subject to:
The last constraints are exactly the inequalities \(z_i\leq z_{i+1}\), because all type masses are positive.
The rearrangement proved above witnesses feasibility and has welfare at least \(W(x^A)\). Therefore an optimal solution \(X^*\) satisfies
\(W(X^*)\geq W(x^A)\geq\alpha\operatorname{OPT}(\mu).\)
Here are the hypotheses needed for polynomial-time rational linear programming:
The standard polynomial-time theorem for rational linear programming therefore returns an exact rational optimum with polynomial encoding length. Output its positive entries as the assignment.
This construction makes one black-box call and at most \(K\) additional value-oracle queries.
For the resulting assignment, calculate
\(z_i=\mu_i^{-1}\sum_k f_kX^*_{i,k}.\)
These are rational and satisfy \(z_1\leq\cdots\leq z_\tau\). Set
\(p_1=0,\qquad p_i=\sum_{h=1}^{i-1}v_h(z_{h+1}-z_h)\quad\text{for }i\geq2.\)
We verify every reporting inequality.
If \(i>j\), then \(v_h\leq v_i\) for \(j\leq h<i\), and each allocation difference is nonnegative. Hence
\(p_i-p_j=\sum_{h=j}^{i-1}v_h(z_{h+1}-z_h)\leq v_i(z_i-z_j).\)
Rearranging gives \(v_i z_i-p_i\geq v_i z_j-p_j\).
If \(i<j\), then \(v_h\geq v_i\) for \(i\leq h<j\). Thus
\(p_j-p_i=\sum_{h=i}^{j-1}v_h(z_{h+1}-z_h)\geq v_i(z_j-z_i),\)
which gives the same truthfulness inequality. The case \(i=j\) is equality.
The payments have polynomial bit length and are computable in polynomial time. Applying this construction independently at every input society establishes exactly the truthfulness condition in the question.
Since \(a,b>1\) and \(\operatorname{OPT}(\mu)\geq0\),
\(W(X^*)\geq\alpha\operatorname{OPT}(\mu)\geq\frac{3\alpha}{4ab}\operatorname{OPT}(\mu).\)
The decisive difference from the [referenced finite-agent model](https://arxiv.org/pdf/1007.3539) is the fixed-society incentive condition: here a tagged deviation compares entries of one monotone allocation menu, whereas a finite agent’s deviation changes the input profile.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved under the stated infinitesimal-agent model. The construction preserves the full approximation factor \(\alpha\), satisfies every required incentive inequality, and runs in polynomial time. No major or minor issues were found.
The proof uses exactly the truthfulness condition in USER_TASK: deviations compare reports within one fixed society. Consequently, establishing a nondecreasing allocation menu and suitable payments separately at each society is sufficient. No consistency between the menus constructed at different societies is required.
The final comparison with the finite-agent model is accurate: the [referenced paper](https://arxiv.org/pdf/1007.3539) defines allocation rules on agents’ reported private multipliers, so changing one agent’s report changes the mechanism’s input. This comparison is explanatory; the proof does not depend on a theorem from that paper.
Collecting distinct supported bundles loses no allocation information relevant to the argument. Their aggregate masses satisfy \(y_k>0\) and \(\sum_k y_k=1\).
The interval-intersection formula is correct. Both interval families partition \((0,1]\), so its row sums equal \(\mu_i\) and its column sums equal \(y_k\). Preserving the aggregate mass of every supported bundle preserves each item’s supply exactly.
Bundles outside this support implicitly receive zero mass. Empty bundles, zero supplies, and unit supplies require no exceptional treatment.
The ordering assertion is valid: a positive intersection for an earlier type interval cannot involve a strictly later bundle interval than a positive intersection for a later type interval. Boundary intersections of zero length cause no problem because the assertion requires positive mass.
The displayed expression for \(\widehat z_j-\widehat z_i\) is an exact identity, using the row-sum equalities. Every summand with positive weight has \(f_\ell-f_k\geq0\). Thus \(\widehat z_i\leq\widehat z_j\).
Equal bundle values are harmless, and no inclusion-based monotonicity of \(f\) is used.
For each upper-type tail, the vectors \(a_{h,k}\) and \(b_{h,k}\) have the stated bounds and equal total mass. A cutoff \(k_h\) exists because the cumulative bundle masses cover \([0,1]\).
The claimed behavior of \(b_{h,k}\) on either side of the cutoff follows from the interval construction. It remains correct when \(M_{h-1}\) equals a bundle boundary; either allowable cutoff gives the required sign argument.
All three sign cases are correct. Subtracting the cutoff value is justified by \(\sum_k(b_{h,k}-a_{h,k})=0\), yielding a nonnegative change in total bundle value for each upper-type tail.
The decomposition of \(v_i\) is exact. Its constant contribution cancels because aggregate bundle masses are preserved, and every remaining coefficient \(v_h-v_{h-1}\) is positive. Hence the displayed welfare difference is nonnegative.
The case \(\tau=1\) is explicitly and correctly handled: both assignments allocate \(y_k\) to the sole type.
The linear program’s monotonicity constraints have the correct orientation and scaling. Since the masses are positive,
\[
\mu_{i+1}\sum_k f_kX_{i,k}\leq
\mu_i\sum_k f_kX_{i+1,k}
\]
is equivalent to \(z_i\leq z_{i+1}\).
The rearrangement supplies a feasible point with objective at least \(W(x^A)\). The row constraints and nonnegativity bound every variable, so an optimum exists.
The stated application of polynomial-time rational linear programming is justified:
Therefore an exact rational optimum with polynomial encoding length can be obtained in polynomial time. The linear-program construction needs only the black box’s supported bundles, so the conditional wording about rational black-box masses does not leave a gap.
One black-box call and at most \(K\) additional oracle queries suffice. These bounds depend on support size and encoding length, not on expanding binary-rational masses into individual agents.
The resulting \(z_i\) are rational and nondecreasing. The payment formula is well-defined, including when \(\tau=1\).
For \(i>j\), the proof correctly bounds each coefficient \(v_h\) above by \(v_i\), giving
\[
p_i-p_j\leq v_i(z_i-z_j).
\]
This is exactly the required incentive inequality after rearrangement.
For \(i<j\), the proof correctly bounds each coefficient \(v_h\) below by \(v_i\), giving
\[
p_j-p_i\geq v_i(z_j-z_i).
\]
This also rearranges to the required inequality. The case \(i=j\) is equality.
Polynomially many rational arithmetic operations on polynomial-length inputs give polynomial-length expected values and payments. Zero types, equal expected values, and zero bundle values do not invalidate any step.
The linear-program optimum satisfies \(W(X^*)\geq\alpha\operatorname{OPT}(\mu)\). Nonnegative types and bundle values ensure \(\operatorname{OPT}(\mu)\geq0\). Since \(a,b>1\), the requested weaker factor follows.
The established polynomial-time result is the conditional black-box conversion requested in USER_TASK; it does not assert unconditional polynomial-time exact welfare optimization for arbitrary value oracles.
No repair or additional clarification is needed.
⟨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.