Answer: Yes. Exact welfare \(W=W_{\mathrm{full}}\) is attained by finite rational intensities and can be constructed in time polynomial in \(m,\tau,L\), independently of \(\varepsilon\).
Theorem 5.5 — class: algorithmic
Given a finite type set \(T=H\times V\), rational masses \(\mu_{h,v}\) summing to one, and a public priority order on \(H\), consider a single indivisible item and one-bit reports. In the limit of finite replications of these types, represent the winner lottery by per-unit-mass intensities \(\lambda_{h,b}\), with total winning probability \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}=1\), where \(x_{h,v,b}\) is the mass of type \((h,v)\) reporting \(b\). Among mechanisms satisfying the limiting, per-capita-scaled incentive and ex-post individual-rationality constraints, maximize expected winner value \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}v\); determine whether the optimum is attained or only approached.
A society is supplied by its support: \(\tau\) types \((h,v)\in H\times V\) with positive binary-rational masses \(\mu_{h,v}\) summing to one; \(\tau\) is the support size, not the number of possible types. Here \(H\) consists of publicly observable classes with a given priority order, \(m=|H|\), and \(V\subseteq[0,1]\cap\mathbb Q\) is finite and nonempty. Let \(L\) be the total input bit length.
There is one indivisible item, seller value zero, and simultaneous reports \(b\in\{0,1\}\). The designer chooses reporting masses \(x_{h,v,b}\ge0\), finite intensities \(\lambda_{h,b}\ge0\), and real conditional winner payments \(c_{h,b}\), with \(\sum_bx_{h,v,b}=\mu_{h,v}\) and \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}=1\); losers pay zero. Randomized allocations are permitted.
In a replication of size \(n\), intensity means winning probability \(\lambda_{h,b}/n\) and expected payment \(\lambda_{h,b}c_{h,b}/n\). An infinitesimal unilateral deviation leaves the aggregate report profile and these menus fixed.
The limiting incentive constraints are \(x_{h,v,b}>0\Rightarrow\lambda_{h,b}(v-c_{h,b})\ge\lambda_{h,1-b}(v-c_{h,1-b})\). Ex-post individual rationality requires \(c_{h,b}\le v\) whenever \(x_{h,v,b}\lambda_{h,b}>0\). Indifferent types may split their mass between reports.
Expected welfare is \(W=\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}v\); the full-communication benchmark is \(W_{\mathrm{full}}=\max\{v:\mu_{h,v}>0\}\).
For every rational \(\varepsilon>0\), can a feasible one-bit mass mechanism with \(W\ge W_{\mathrm{full}}-\varepsilon\) be constructed in time polynomial in \(m,\tau,L,\varepsilon^{-1}\)?
If arbitrarily small welfare loss is achievable, is zero loss attained by finite intensities or only approached?
For finitely many bidders with independent uniform valuations on \([0,1]\), one-bit priority mechanisms achieve additive welfare and profit losses at most \(9/n\), with dominant strategies and ex-post individual rationality ([source](https://kylewoodward.com/blog-data/pdfs/references/blumrosen%2Bnisan%2Bsegal-journal-of-artificial-intelligence-research-2007A.pdf)).
The literature search identified no result settling this specific finite-support mass-menu formulation.
Yes. Exact welfare is attainable with finite rational intensities, and an exact mechanism can be constructed in polynomial time.
I use the stated mass-menu constraints. The supplied priority order imposes no additional displayed restriction on the menus. The construction below handles arbitrary finite support, including multiple classes and distinct valuations.
Let \(S=\{(h,v):\mu_{h,v}>0\}\), and define
\(M=\max\{v:(h,v)\in S\}=W_{\mathrm{full}}\), \(q=\sum_{(h,M)\in S}\mu_{h,M}\).
The nonempty finite support and positive masses imply \(0<q\leq 1\).
If there is a supported valuation below \(M\), define
\(s=\max\{v:(h,v)\in S,\ v<M\}\), \(p=(s+M)/2\).
Then \(s<p<M\). If all supported valuations equal \(M\), set \(p=M\).
For every \(h\in H\), choose the menus
\(\lambda_{h,0}=0,\quad c_{h,0}=0,\qquad \lambda_{h,1}=1/q,\quad c_{h,1}=p.\)
Assign every supported type with valuation \(M\) entirely to report \(1\), and every other supported type entirely to report \(0\). Thus, for each \((h,v)\in S\),
\(x_{h,v,1}=\mu_{h,v}\) if \(v=M\), and \(x_{h,v,1}=0\) otherwise; set \(x_{h,v,0}=\mu_{h,v}-x_{h,v,1}\).
Unsupported types have zero reporting masses.
The reporting masses are nonnegative and satisfy \(x_{h,v,0}+x_{h,v,1}=\mu_{h,v}\).
Report \(0\) has zero intensity. The total mass assigned to report \(1\) is \(q\), so
\(\displaystyle \sum_{h,v,b}x_{h,v,b}\lambda_{h,b}=\frac{q}{q}=1.\)
All intensities are finite because \(q>0\).
For a type with valuation \(v\), the two menu utilities are
\(u_0(v)=\lambda_{h,0}(v-c_{h,0})=0,\qquad u_1(v)=\lambda_{h,1}(v-c_{h,1})=(v-p)/q.\)
If \(v=M\), then \(M\geq p\), hence \(u_1(M)\geq u_0(M)\). Its assigned report \(1\) satisfies the incentive constraint.
If \(v<M\), the lower-value case defining \(s\) applies. Consequently, \(v\leq s<p\), and therefore \(u_1(v)<0=u_0(v)\). Its assigned report \(0\) satisfies the incentive constraint strictly.
When at least two distinct valuations are supported, the maximum-value types also strictly prefer their assigned report, since \(p<M\). When all valuations equal \(M\), the types are indifferent, and the stipulated permission to assign indifferent types applies.
Whenever \(x_{h,v,b}\lambda_{h,b}>0\), necessarily \(b=1\) and \(v=M\). For those winners,
\(c_{h,1}=p\leq M=v.\)
All other types have zero winning intensity. Thus the stated ex-post individual rationality condition holds.
For any feasible mechanism, nonnegativity and normalization give
\(\displaystyle M-W=\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}(M-v)\geq 0.\)
Thus \(M\) is an upper bound on feasible welfare.
In the constructed mechanism, every positive allocation weight belongs to a maximum-value type. Hence
\(\displaystyle W=\sum_{(h,M)\in S}\mu_{h,M}\frac{M}{q}=\frac{qM}{q}=M=W_{\mathrm{full}}.\)
Therefore, for every rational \(\varepsilon>0\), the construction satisfies \(W\geq W_{\mathrm{full}}-\varepsilon\). Zero loss is attained; no limiting sequence of intensities is needed.
The required intensity magnitude can nevertheless be large. Indeed, in any exact-welfare mechanism, the nonnegative terms in the displayed expression for \(M-W\) must all vanish. Consequently, types below \(M\) receive no positive allocation weight. Writing \(\Lambda=\max_{h,b}\lambda_{h,b}\), normalization then implies
\(\displaystyle 1=\sum_{(h,M)\in S,b}x_{h,M,b}\lambda_{h,b}\leq \Lambda\sum_{(h,M)\in S,b}x_{h,M,b}=\Lambda q.\)
Thus every exact mechanism has \(\Lambda\geq 1/q\). Our construction attains this bound.
Scan the supported types to compute \(M\), the largest supported value below \(M\) when present, and \(q\). These operations require polynomially many exact rational comparisons and additions.
To check encoding size explicitly, write the masses contributing to \(q\) as \(a_i/b_i\), and take \(B=\prod_i b_i\). Its binary length is at most the sum of the input denominator lengths, up to a constant. Then
\(\displaystyle q=A/B,\qquad A=\sum_i a_i(B/b_i).\)
Since \(0<q\leq 1\), we have \(0<A\leq B\). Therefore both \(q\) and \(1/q=B/A\) have binary encodings of length \(O(L)\). The midpoint price \(p\) also has encoding length \(O(L)\).
The output consists of the reporting masses for the \(\tau\) supported types and two menus for each of the \(m\) classes. Its size and construction time are polynomial in \(m,\tau,L\), independently of \(\varepsilon\), and hence polynomial in the requested parameters.
The supplied [finite-bidder auction comparison](https://kylewoodward.com/blog-data/pdfs/references/blumrosen%2Bnisan%2Bsegal-journal-of-artificial-intelligence-research-2007A.pdf) is not needed for this proof. The decisive properties here are positive mass at the largest supported valuation and permission to use the finite intensity \(1/q\).
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly. The construction satisfies the displayed mass-menu constraints, attains exact welfare with finite rational intensities, and has polynomial construction time and output size. No mathematical gaps were found.
The prover correctly treats the displayed constraints as defining feasibility. The given priority order introduces no additional restriction on allocations or menus in the task.
The construction addresses the finite-support mass formulation directly. It does not rely on the cited finite-bidder result, so no external theorem requires verification.
The support is finite and nonempty, so its largest valuation \(M\) exists. At least one supported type has valuation \(M\) and positive mass. Consequently, the defined mass \(q\) satisfies \(0<q\leq 1\).
If lower supported valuations exist, their maximum \(s\) exists and satisfies \(s<M\). The midpoint price therefore satisfies \(s<p<M\). Otherwise, the choice \(p=M\) is valid.
The reporting assignments are defined for every supported type, and unsupported types receive zero mass. Both menu intensities are nonnegative and finite because \(q>0\). The payments are rational and hence permitted real conditional payments.
For each supported type, the construction assigns its entire mass to exactly one report. Thus nonnegativity and mass conservation hold.
Exactly total mass \(q\) receives intensity \(1/q\); every other reporting mass receives intensity zero. The normalization computation \(q(1/q)=1\) is correct.
The computed utilities are correct: report \(0\) gives utility zero, and report \(1\) gives utility \((v-p)/q\).
Every maximum-value type is assigned report \(1\), and \(M\geq p\) ensures that this report is weakly optimal.
Every supported lower-value type satisfies \(v\leq s<p\), so report \(1\) gives strictly negative utility. Its assigned report \(0\) is therefore strictly optimal.
When all supported valuations equal \(M\), both reports give utility zero. The task explicitly permits indifferent types to split their mass, which includes assigning their entire mass to report \(1\).
These checks cover every type-report pair with positive reporting mass.
A positive allocation weight requires report \(1\) and valuation \(M\). Such winners pay \(p\leq M\), exactly as required.
Types assigned report \(0\) have zero allocation weight, so the stated individual-rationality condition imposes no further requirement on them.
The identity expressing \(M-W\) follows from normalization. Its nonnegativity is valid: every supported valuation is at most \(M\), and unsupported types have zero reporting mass.
The constructed mechanism places all allocation weight on valuation \(M\), and the calculation \(W=qM/q=M\) is correct. Thus it satisfies the requested approximation for every positive rational \(\varepsilon\), with zero loss already attained.
The additional intensity lower bound is also valid. Exact welfare forces every nonnegative contribution from a lower supported valuation to vanish. Normalization and mass conservation then imply \(1\leq\Lambda q\). The construction attains the resulting bound \(\Lambda\geq1/q\).
The rational arithmetic argument correctly bounds representation size. The product of the relevant input denominators has binary length \(O(L)\). The numerator \(A\) satisfies \(0<A\leq B\), so both \(q=A/B\) and \(1/q=B/A\) have \(O(L)\)-length representations. The midpoint price also has polynomial encoding length.
Computing these quantities uses polynomially many operations on integers of polynomial bit length. The support-based output requires reporting masses for \(\tau\) types and menus for \(m\) classes; zero masses outside the support can be specified implicitly.
Large numerical intensity does not invalidate polynomial bit complexity. The construction is independent of \(\varepsilon\) and therefore meets the requested parameter bound.
The all-equal valuation case, a singleton support, \(M=0\), and classes with no supported types are covered by the definitions and feasibility checks. None causes a failure.
No corrective feedback or additional clarification is necessary.
⟨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.