Answer: \(\alpha^*=0<0.828\)
Theorem 2 — class: algorithmic
Given a finite type set \(T\subseteq\Delta_2\), rational masses \(\mu\), and scarce per-capita item supplies \(q_j\in(0,1)\), compute the maximum ratio of aggregate truthful welfare to the first-best over anonymous, no-transfer direct mechanisms. Each type report receives a lottery over integral bundles, with expected allocation \(x_r\); require \(\sum_t\mu_t x_{t,j}\le q_j\) and \(v_t\cdot x_t\ge v_t\cdot x_r\) for every \(t,r\). The mechanism observes \(\mu\) as the aggregate report distribution, which is unchanged by one nonatomic deviation.
There are \(m=2\) item kinds. A society is given by its support: a nonempty list \(T\) of \(\tau\) rational types \(v_t\in\mathbb{Q}_{\ge0}^{2}\) with \(v_{t,1}+v_{t,2}=1\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Supplies \(q_j\in(0,1)\) are binary rationals; \(L\) is the total input bit length.
Agents have additive, risk-neutral utilities. Reports range over \(T\); an anonymous direct mechanism assigns each report \(r\) a lottery over bundles \(b\in\{0,1\}^{2}\), including the empty bundle, with expectation \(x_r\). There are no transfers or bundle-size restrictions.
The mechanism observes the aggregate report distribution \(\mu\), unchanged by any single nonatomic deviation. Feasibility means \(\sum_t\mu_t x_{t,j}\le q_j\); truthfulness means \(v_t\cdot x_t\ge v_t\cdot x_r\) for all \(t,r\in T\). Utility ties are allowed.
Let \(W(x)=\sum_t\mu_t v_t\cdot x_t\), and let \(\mathrm{FB}(T,\mu,q)\) be the maximum of \(W\) over the same bundle lotteries and supply constraints without truthfulness. Define \(R^*(T,\mu,q)=\sup_{x\text{ feasible and truthful}}W(x)/\mathrm{FB}(T,\mu,q)\). State any running times in \(m,\tau,L\) and any accuracy parameter.
What is the sharp uniform first-best approximation guarantee \(\alpha^*=\inf_{T,\mu,q}R^*(T,\mu,q)\)? In particular, is \(\alpha^*\ge0.828\), or is \(\alpha^*<0.828\)?
For two finite agents and two items with normalized additive valuations, a particular strategy-proof mechanism has worst-case first-best ratio between \(0.828\) and \(0.829\). [Guo–Conitzer](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/18_04_FP_0251.pdf)
Subsequent work improves mechanisms and upper bounds in the two-agent model; no result settling the exact nonatomic guarantee above was located. [Cheung](https://arxiv.org/abs/1604.05243)
1. Result. The sharp uniform guarantee is \(\boxed{\alpha^*=0}\). In particular, \(\alpha^*<0.828\).
This holds even with exactly two distinct types, strictly positive valuation coordinates, and strictly positive supplies. Thus the conclusion does not rely on allowing a zero supply or a zero valuation.
2. Reduction to expectations. Every vector \(x_t\in[0,1]^2\) is implementable by a bundle lottery: include each item independently with its prescribed probability. Conversely, every bundle lottery has its expectation in this square. Additive, risk-neutral utilities therefore make the stated feasibility and truthfulness inequalities an exact description of the problem.
For every admissible instance, assigning \(x_t=(q_1,q_2)\) to every type is feasible and truthful. Its welfare is at least \(\min\{q_1,q_2\}>0\), because each valuation sums to one. Consequently, \(\mathrm{FB}>0\) and \(R^*>0\) on each individual instance. In particular, \(\alpha^*\ge 0\).
We now construct instances whose optimal ratios converge to zero.
3. An admissible two-type family. Let \(s=2^{-k}\), where \(k\ge 2\). Define types, masses, and supplies by
\[ v_H=(1-s,s),\qquad v_L=(s,1-s), \]
\[ \mu_H=s,\qquad \mu_L=1-s,\qquad q_1=s,\qquad q_2=s^3. \]
All input numbers are binary rationals. Both masses are positive and sum to one; both supplies lie strictly between zero and one. Both types have strictly positive coordinates and are distinct.
Each valuation coordinate is at most \(1-s\). Hence any feasible allocation satisfies
\[ W\le (1-s)(q_1+q_2)=(1-s)(s+s^3). \]
Without truthfulness, this bound is attained by assigning
\[ x_H=(1,0),\qquad x_L=\left(0,\frac{s^3}{1-s}\right). \]
These expectations belong to \([0,1]^2\), since \(s^3<1-s\), and use both supplies exactly. Therefore
\[ \mathrm{FB}=(1-s)(s+s^3). \]
4. Exact optimal truthful welfare. Write the expectations of an arbitrary feasible truthful mechanism as
\[ x_H=(a,b),\qquad x_L=(c,d). \]
Define aggregate item allocations by
\[ S_1=sa+(1-s)c\le s,\qquad S_2=sb+(1-s)d\le s^3. \]
Truthfulness for type \(L\) requires
\[ sc+(1-s)d\ge sa+(1-s)b. \]
Since \(b\ge 0\), this implies
\[ s(a-c)\le (1-s)(d-b)\le (1-s)d\le s^3, \]
and therefore \(a-c\le s^2\). It follows that
\[ S_1\ge sa+(1-s)(a-s^2)=a-(1-s)s^2. \]
Combining this with \(S_1\le s\) gives
\[ a\le s+(1-s)s^2. \]
The welfare can be rewritten exactly as
\[ W=sS_1+s(1-2s)a+(1-s)S_2-s(1-2s)b. \]
Because \(s<1/2\), the coefficient \(s(1-2s)\) is positive. Substituting the bounds above and using \(b\ge 0\) yields
\[ W\le s^2+s(1-2s)\bigl(s+(1-s)s^2\bigr)+(1-s)s^3 =2s^2(1-s)\bigl(1+s(1-s)\bigr). \]
This upper bound is attained. Set
\[ a=s+(1-s)s^2,\qquad b=0,\qquad c=s-s^3,\qquad d=\frac{s^3}{1-s}. \]
All four coordinates belong to \([0,1]\): in particular,
\(a<s+s^2<3/4\), \(0<c<s\), and \(0<d<1/4\).
Direct substitution gives \(S_1=s\) and \(S_2=s^3\).
Type \(L\)'s truthfulness inequality holds with equality:
\[ v_L\cdot x_L-v_L\cdot x_H =s(c-a)+(1-s)(d-b) =-s^3+s^3=0. \]
Type \(H\)'s truthfulness inequality holds strictly:
\[ v_H\cdot x_H-v_H\cdot x_L =(1-s)(a-c)+s(b-d) =(1-s)s^2-\frac{s^4}{1-s} =\frac{s^2(1-2s)}{1-s}>0. \]
Thus this allocation is feasible and truthful. It attains every inequality in the welfare bound, proving that
\[ W^*=2s^2(1-s)\bigl(1+s(1-s)\bigr). \]
Consequently, the exact optimal ratio for this family is
\[ \boxed{ R^*(s)=\frac{2s\bigl(1+s(1-s)\bigr)}{1+s^2}. } \]
For the concrete choice \(s=1/4\), the types are
\((3/4,1/4)\) and \((1/4,3/4)\), their masses are \(1/4\) and \(3/4\), and the supplies are \((1/4,1/64)\). The formula gives
\[ R^*=\frac{19}{34}<0.828. \]
5. Sharpness, interpretation, and computation. As \(k\) tends to infinity, \(s=2^{-k}\) tends to zero, and the exact ratio above tends to zero. Together with \(\alpha^*\ge 0\), this proves \(\alpha^*=0\).
The binding obstruction is type \(L\)'s incentive constraint. The scarce second item cannot compensate this large population enough to permit substantially preferential allocation of the first item to the small population of type \(H\).
The cited [Guo–Conitzer paper](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/18_04_FP_0251.pdf) and [Cheung paper](https://arxiv.org/abs/1604.05243) concern allocation between two finite agents. Their guarantees do not establish a guarantee for the population masses and supplies allowed here; the calculation above directly settles the stated nonatomic problem.
For completeness, an individual instance can be solved exactly by rational linear programming. The expectation formulation has \(m\tau\) variables and \(\tau(\tau-1)+m+2m\tau\) inequalities, including coordinate bounds. Its feasible region is nonempty and bounded, and its coefficients are rational with encoding length polynomial in \(m,\tau,L\). The standard polynomial-time theorem for rational linear programming therefore computes optimal truthful welfare and first-best welfare in time polynomial in \(m,\tau,L\), with no accuracy parameter required.
The counterexample family has \(m=\tau=2\) and input length \(L=\Theta(k)\). Since \(s(1-s)\le 1/4\), its ratio satisfies \(R^*(s)\le (5/2)s\). Thus, for any \(0<\varepsilon<1\), choosing
\[ k=\max\left\{2,\left\lceil\log_2\frac{3}{\varepsilon}\right\rceil\right\} \]
produces a witness with \(R^*<\varepsilon\), using input length \(O(\log(1/\varepsilon))\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed sharp guarantee, \(\alpha^*=0<0.828\). Its counterexample family, exact welfare calculation, and polynomial-time computation claim are correct. I found no major or minor mathematical issues.
Independent inclusion of the two items implements any expectation vector in \([0,1]^2\), including lotteries that assign both items or neither. Additivity and risk neutrality make expected utility equal to \(v_t\cdot x_r\). Consequently, the stated expectation constraints capture precisely the permitted mechanisms.
Assigning every report \((q_1,q_2)\) uses each supply exactly and satisfies every incentive constraint with equality. Normalization gives welfare at least \(\min\{q_1,q_2\}>0\). Thus the first-best denominator is positive on every admissible instance, and the claimed nonnegative lower bound on \(\alpha^*\) is justified.
For integer \(k\ge2\), \(s=2^{-k}\) satisfies \(0<s\le1/4\). The types are distinct, normalized, and strictly positive in both coordinates. Both masses are positive and sum to one. The supplies \(s\) and \(s^3\) lie in \((0,1)\). All input quantities are binary rationals.
The family therefore addresses the intended problem without relying on zero supplies, zero valuations, or an inadmissible limiting instance.
Every valuation coordinate is at most \(1-s\), so feasibility implies
\(W\le(1-s)(q_1+q_2)\).
The proposed first-best allocation gives item one exclusively to its highest-valuing type and item two exclusively to its highest-valuing type. Its expectations lie in the permitted square because \(s^3<1-s\), and it uses both supplies exactly. Hence
\(\mathrm{FB}=(1-s)(s+s^3)\)
is established.
Type \(L\)'s incentive constraint gives
\(s(a-c)\le(1-s)(d-b)\).
Nonnegativity of \(b\), together with the second supply constraint, yields
\((1-s)(d-b)\le(1-s)d\le s^3\).
Thus \(a-c\le s^2\).
Substitution into the first aggregate allocation gives
\(S_1\ge a-(1-s)s^2\), and therefore
\(a\le s+(1-s)s^2\).
This reasoning remains valid even when \(a-c\) is negative; no unstated ordering assumption is used.
The displayed welfare identity expands to
\(s(1-s)a+s^2b+s(1-s)c+(1-s)^2d\),
which is exactly the original welfare objective.
Since \(s(1-2s)>0\), all substitutions into that identity have the correct inequality direction. The resulting expression simplifies correctly to
\(2s^2(1-s)(1+s(1-s))\).
Using only type \(L\)'s incentive constraint for this upper bound is legitimate: every truthful mechanism must satisfy it.
Its coordinate bounds are valid throughout \(0<s\le1/4\). Direct substitution confirms \(S_1=s\), \(S_2=s^3\), and \(a-c=s^2\).
Type \(L\)'s utility difference is exactly zero. Type \(H\)'s utility difference simplifies correctly to
\(\frac{s^2(1-2s)}{1-s}>0\).
These are the only nontrivial incentive constraints for two reports; self-report comparisons are identities.
The allocation also attains every bound used in the welfare estimate. Therefore the claimed value of \(W^*\) is an attained optimum, rather than merely an upper bound.
Dividing the verified truthful optimum by the verified first-best value gives
\(R^*(s)=\frac{2s(1+s(1-s))}{1+s^2}\).
At \(s=1/4\), this equals \(19/34\), which is strictly below \(0.828\).
Along the admissible sequence \(s=2^{-k}\), the ratio tends to zero. Together with nonnegativity, this establishes \(\alpha^*=0\). There is no inconsistency between strictly positive ratios on individual instances and a zero infimum.
The truthful linear program has \(m\tau\) variables and exactly the stated number of inequalities: ordered distinct-report incentive constraints, supply constraints, and two coordinate bounds per variable. Removing incentive constraints gives the first-best program.
Both programs are nonempty, bounded, and have rational objectives and coefficients of polynomial encoding length. These satisfy the hypotheses of the invoked polynomial-time theorem for exact rational linear programming. Thus the polynomial-time claim requires no accuracy parameter.
The family has input length \(L=\Theta(k)\). The bound \(s(1-s)\le1/4\) gives \(R^*(s)\le(5/2)s\). The proposed choice of \(k\) ensures \(s\le\varepsilon/3\), hence \(R^*(s)\le5\varepsilon/6<\varepsilon\). The claimed witness length follows.
Both cited papers concern allocation between two finite agents, consistent with the prover's description. No theorem from either paper is used to establish the nonatomic conclusion. [Guo–Conitzer](https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/18_04_FP_0251.pdf), [Cheung](https://arxiv.org/abs/1604.05243).
Required clarification or repair: None.
⟨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.