Answer: Achievable: a strategyproof rule guarantees \(W(A)\geq0.67776W^*\) for every input society.
Theorem 6 — class: algorithmic
Given a finite support \(\mathcal P\) of bilateral utility-pair types \(p=(u_1^p,u_2^p)\), with rational masses \(\mu_p\) summing to one, and \(m\) divisible items in each cell, output a strategyproof rule and feasible allocations for each supported type such that aggregate welfare is at least \(0.67776\) times \(\sum_{p\in\mathcal P}\mu_p\sum_{j=1}^m\max\{u_{1j}^p,u_{2j}^p\}\).
A society is given by its support: a list \(\mathcal P\) of \(\tau\) bilateral types with positive binary-rational masses \(\mu_p\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type comprises two nonnegative rational utility vectors \(u_i^p\) satisfying \(\sum_{j=1}^m u_{ij}^p=1\), with \(m\geq2\). Let \(L\) be the total input bit length; measure running times in \(m,\tau,L\).
Each cell has its own unit supply of each divisible item. Utilities are linear, payments are forbidden, and unallocated fractions are allowed.
A single rule \(A\) maps pairs of reports in \(\Delta_m=\{v\in\mathbb R_{\geq0}^m:\sum_jv_j=1\}\) to allocations satisfying \(A_{ij}\geq0\) and \(A_{1j}+A_{2j}\leq1\). Strategyproofness is dominant-strategy truthfulness throughout \(\Delta_m\), including reports outside the support; the society is held fixed during deviations.
Output a description of such a rule and its allocations at every supported type. Define \(W(A)=\sum_{p\in\mathcal P}\mu_p\sum_{i=1}^2\sum_{j=1}^m u_{ij}^pA_{ij}(u_1^p,u_2^p)\) and \(W^*=\sum_{p\in\mathcal P}\mu_p\sum_{j=1}^m\max\{u_{1j}^p,u_{2j}^p\}\).
Is the approximation guarantee \(W(A)\geq0.67776W^*\) achievable by a strategyproof rule for every input society, or is it impossible?
Known results: a strategyproof mechanism already guarantees the ratio \(0.67776\) at every normalized bilateral utility profile for every \(m\geq2\). [Cheung’s verified result](https://arxiv.org/html/1604.05243#S7) therefore also establishes the stated distributional guarantee; this target is settled.
The guarantee is achievable for every input society. We use the pointwise guarantee supplied in the task; the passage to a society is an exact weighted-sum argument.
Here is an explicit description of the rule. For reports \(b_1,b_2\in\Delta_m\), write \(b_i(x_i)=\sum_j b_{ij}x_{ij}\). For each \(c>0\), choose a feasible allocation \(a^c\) maximizing
\(b_1(a_1^c)b_2(a_2^c)^c\), with deterministic tie-breaking, and define
\[
P^c_{1j}(b_1,b_2)=b_2(a_2^c)^c a_{1j}^c,\qquad
P^c_{2j}(b_1,b_2)=b_1(a_1^c)^{1/c}a_{2j}^c.
\]
Let \(E_{ij}=1/2\), and let \(Q\) choose whichever of \(P^1\) and \(E\) has greater reported welfare, choosing \(P^1\) on a tie. Set
\[
A=\frac{1029}{4000}P^{421/1000}
+\frac{1029}{4000}P^{1000/421}
+\frac{971}{2000}Q.
\]
This is precisely the mechanism in [Cheung’s Theorem 6](https://arxiv.org/html/1604.05243#S7), which establishes strategyproofness and a pointwise competitive ratio of at least \(0.67776\).
For each supported type \(p\), output the allocation with coordinates \(A_{ij}(u_1^p,u_2^p)\), evaluated by these formulas. The same formula defines the rule on all reports outside the support.
These properties also have direct proofs.
The feasible allocation set is compact. The product maximized in the definition of \(P^c\) is continuous, so a maximizer exists. Giving each agent half of every item yields product \(2^{-(1+c)}>0\); hence both utilities at a maximizer are positive. Normalization and feasibility imply \(b_i(a_i^c)\leq1\). Consequently each scaling factor belongs to \((0,1]\), so \(P^c\) is feasible. Both alternatives defining \(Q\) are feasible, and the coefficients defining \(A\) are nonnegative and sum to \(1\). Thus \(A\) is feasible and requires no payments.
Fix agent \(1\)’s true utility \(u_1\) and an arbitrary report \(b_2\). Under truthful reporting, her utility from \(P^c\) equals
\[
Z=\max_{a\text{ feasible}}u_1(a_1)b_2(a_2)^c.
\]
If a deviation selects some feasible allocation \(a\), her actual utility is \(u_1(a_1)b_2(a_2)^c\leq Z\). Thus agent \(1\) cannot benefit from deviating.
For agent \(2\), with an arbitrary fixed report \(b_1\), truthful reporting maximizes
\[
b_1(a_1)^{1/c}u_2(a_2)
=\bigl(b_1(a_1)u_2(a_2)^c\bigr)^{1/c}.
\]
Since taking the positive \(c\)-th root preserves order, the same argument proves truthfulness for agent \(2\).
For \(P^1\), both agents’ reported utilities equal
\(Z(b_1,b_2)=\max_a b_1(a_1)b_2(a_2)\).
Its reported welfare is therefore \(2Z(b_1,b_2)\), whereas \(E\) has welfare \(1\). Fixing either agent’s true utility and the other report, let \(Z_0\) be that agent’s truthful utility under \(P^1\). Her truthful utility under \(Q\) is \(\max\{Z_0,1/2\}\). A deviation that selects \(P^1\) gives utility at most \(Z_0\); one that selects \(E\) gives exactly \(1/2\). Hence \(Q\) is strategyproof.
Finally, utilities under \(A\) are the corresponding weighted sums. Multiplying each component’s truthfulness inequality by its nonnegative coefficient and adding proves truthfulness of \(A\).
All these arguments allow arbitrary true utilities and opposing reports in \(\Delta_m\). In particular, they cover deviations outside the support while the society remains fixed.
We apply Cheung’s verified pointwise theorem, as permitted by the given premises. Its hypotheses match the task: two agents, any \(m\geq2\), nonnegative normalized linear utilities, unit item supplies, and permission to leave fractions unallocated.
Define
\[
S_p=\sum_{i=1}^2\sum_{j=1}^m u_{ij}^pA_{ij}(u_1^p,u_2^p),
\qquad
O_p=\sum_{j=1}^m\max\{u_{1j}^p,u_{2j}^p\}.
\]
The theorem gives \(S_p\geq0.67776\,O_p\) for every supported type. Since \(\mu_p>0\), multiplication by \(\mu_p\) preserves each inequality. Summing yields
\[
W(A)=\sum_{p\in\mathcal P}\mu_pS_p
\geq0.67776\sum_{p\in\mathcal P}\mu_pO_p
=0.67776\,W^*.
\]
The rule is independent of the masses and support, so no additional distributional incentive argument is needed.
For completeness, the supported allocations admit exact descriptions computable in time polynomial in \(m,\tau,L\).
Consider one product maximization with rational reports. Because utilities are nonnegative, some maximizer allocates every item completely. Write agent \(1\)’s share as \(t_j\in[0,1]\), and put
\(x=\sum_jb_{1j}t_j\) and \(y=\sum_jb_{2j}(1-t_j)\).
At a maximizer, \(x,y>0\), so maximizing the product is equivalent to maximizing \(\log x+c\log y\). Its derivative with respect to \(t_j\) is
\[
\frac{b_{1j}}x-\frac{cb_{2j}}y.
\]
A positive derivative forces \(t_j=1\), and a negative derivative forces \(t_j=0\), since otherwise a sufficiently small feasible movement would increase the objective.
Order items by decreasing \(b_{1j}/b_{2j}\), putting positive-over-zero ratios first and items valued by neither agent last. Only items at the threshold ratio \(cx/y\) can be split. Within a tied threshold group, preserving agent \(1\)’s total \(b_2\)-weighted share also preserves both \(x\) and \(y\). Allocating that share successively through the group therefore produces a maximizer with a prefix assigned to agent \(1\), a suffix assigned to agent \(2\), and at most one split item.
Enumerate all prefix allocations and all possible split positions. For a split item with values \(a,b>0\), its interval has utilities
\(x=X+at\) and \(y=Y+b(1-t)\), where \(X,Y\) are the contributions from the other items. The derivative vanishes only at
\[
t=\frac{a(Y+b)-cbX}{(1+c)ab}.
\]
Thus the endpoints and this value, when it lies in \([0,1]\), suffice. If either \(a\) or \(b\) is zero, the objective is monotone or constant on the interval, so endpoints suffice.
There are \(O(m)\) candidates after sorting. For \(c=d/e\), comparing positive products \(xy^c\) is equivalent to comparing the rational quantities \(x^ey^d\). Here \(d,e\leq1000\) are fixed constants. All candidate shares are rational, and the final allocation coordinates can be output as finite expressions using rational numbers and fixed rational powers. No numerical rounding is required.
Each supported profile therefore requires \(O(m\log m)\) rational operations and fixed integer powers, on numbers of polynomial bit length. Across the support, the total bit running time and exact output length are polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The guarantee is established in substance. The construction matches the theorem supplied in the task, and the direct proofs of feasibility and global strategyproofness are correct. The weighted-sum argument establishes the requested society guarantee. The exact-computation argument also supports polynomial running time with symbolic output.
There is one minor issue: the deterministic tie-breaking rule is not specified, and its relationship to the supported-allocation algorithm is left implicit.
The definitions of \(P^c\) and \(Q\), and the coefficients and parameters defining \(A\), match [Cheung’s Theorem 6](https://arxiv.org/html/1604.05243#S7). In particular, the decimal parameter is exactly \(421/1000\), its reciprocal is \(1000/421\), and the mixture coefficients are correct.
The cited theorem states strategyproofness and the pointwise competitive ratio claimed by the prover. Its setting includes two agents, normalized nonnegative linear utilities, arbitrary numbers of divisible items, unit supplies, and partial allocations. These hypotheses match the task, including utility vectors with zero coordinates.
The task expressly supplies this theorem as a verified premise. The prover therefore need not reproduce its numerical certification. There is no unverified theorem application here.
The existence argument is correct:
Consequently, both scaling factors lie in \((0,1]\). Scaling each agent’s original allocation down preserves nonnegativity and the item supply inequalities.
Both alternatives defining \(Q\) are feasible. The mixture coefficients are positive and sum to \(1\), so \(A\) is feasible. The construction introduces no payments.
Finding: Correct.
The truthful utility equals the maximum of the true first-agent utility multiplied by the fixed opposing reported utility raised to \(c\).
After a deviation, the selected underlying allocation remains feasible. The deviating agent’s actual utility is the same objective evaluated at that allocation, so it cannot exceed the truthful maximum. The argument does not assume that the deviation belongs to the support.
Finding: Correct.
The objective relevant to agent 2 is the positive \(c\)-th root of the product maximized under truthful reporting. This root is strictly increasing on nonnegative values, so the maximizers coincide. The same feasible-allocation comparison therefore applies.
Finding: Correct for every \(c>0\).
For \(P^1\), both reported utilities equal the maximum product \(Z\). Thus comparing reported welfare against the equal allocation is exactly comparing \(Z\) against \(1/2\).
With either agent’s true utility and the opposing report fixed:
The specified tie convention causes no difficulty.
Finding: Correct. This justifies this particular welfare selector; the prover does not assume a general closure property for welfare-based selection.
Linearity makes utility under the allocation mixture equal to the corresponding mixture of utilities. Adding the component strategyproofness inequalities with the fixed nonnegative coefficients proves the claim.
Finding: Correct throughout \(\Delta_m\), with the society fixed during deviations.
The quantities \(S_p\) and \(O_p\) agree with the task’s profile welfare and first-best welfare.
The pointwise theorem applies separately to every supported profile. Multiplication by each positive mass preserves the inequality, and summation gives the stated guarantee. No independence assumption or distributional incentive condition is needed.
The rule does not depend on the support or masses. The argument therefore handles the support representation exactly as required.
Finding: Correct.
The computational argument is sound in substance.
The claim concerns exact symbolic output; it does not claim that final coordinates are rational. This is consistent with the task’s unrestricted allocation description.
Finding: Correct, subject to the tie-breaking clarification below.
Where: “with deterministic tie-breaking,” together with the supported-allocation algorithm.
Issue: The text does not specify which maximizer is selected when several allocations attain the maximum. The computational section finds a maximizer, but does not explicitly make its selection procedure the tie-breaking convention defining the rule.
This affects allocation coordinates. For example, with identical two-item reports \((1/2,1/2)\) and \(c=1\), assigning the first item to agent 1 and the second to agent 2, or reversing those assignments, gives distinct maximizing allocations.
This is minor: the truthfulness arguments permit any selected maximizer, and the welfare guarantee survives the choice.
Minimum clarification: Specify a fixed deterministic convention for ordering tied items and choosing among maximizing candidates, and state that this same convention defines the rule and produces the supported allocations. No new mathematical argument is required.
⟨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.