Answer: A deterministic polynomial-time algorithm attains the \(1-2^{-k}\) welfare approximation guarantee.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe conditional expectation algorithm is truth- ful for the “known” case, and it achieves a (1 −1/2k)- approximation for k-SAT, in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\ell\) Boolean variables and \(\tau\) clause types \((C_j,v_j)\), each with at least \(k\) literals, positive rational per-capita value \(v_j\), and positive rational mass \(\mu_j\) summing to \(1\), return an assignment \(x\) such that \(W_\mu(x)=\sum_{j=1}^{\tau}\mu_jv_j\mathbf{1}[x\models C_j]\ge(1-2^{-k})\max_y W_\mu(y)\). What running time is achievable in \(\ell,\tau\), and the binary input length?
Let \(m=\ell\), with integers \(1\le k\le\ell\). A society is given by its support: an explicit list of \(\tau\) distinct types \((C_j,v_j)\) with positive binary-rational masses \(\mu_j\) satisfying \(\sum_j\mu_j=1\). Here \(\tau\) is the support size, not the number of possible types.
Each \(C_j\) is a disjunctive clause containing at least \(k\) literals, with each variable appearing at most once and never in both polarities; \(v_j\) is a positive binary rational. Let \(L\) be the total binary input length, including clauses, values, masses, and \(k\).
An outcome is one common assignment \(x\in\{0,1\}^{\ell}\), with welfare \(W_\mu(x)=\sum_{j=1}^{\tau}\mu_jv_j\mathbf{1}[x\models C_j]\).
Can an assignment satisfying \(W_\mu(x)\ge(1-2^{-k})\max_{y\in\{0,1\}^{\ell}}W_\mu(y)\) be found deterministically in time polynomial in \(\ell,\tau,k,L\), or is attaining this approximation guarantee NP-hard?
For finitely many agents with positive values and these clause restrictions, a deterministic polynomial-time \((1-2^{-k})\) welfare approximation is known; with public clauses, its allocation rule also admits truthful payments. [Source](https://cdn.aaai.org/AAAI/2005/AAAI05-039.pdf)
No separate published result explicitly using this support-encoded mass formulation was verified.
The approximation guarantee is attainable deterministically in time polynomial in \(\ell,\tau,k,L\). Treating each support entry as a clause with weight \(\mu_jv_j\), conditional expectation gives the stronger guarantee
\[
W_\mu(x)\ge \sum_{j=1}^{\tau}\mu_jv_j\bigl(1-2^{-|C_j|}\bigr)
\ge (1-2^{-k})\sum_{j=1}^{\tau}\mu_jv_j.
\]
Below, the proof includes the bit complexity of handling the encoded masses.
Define \(w_j=\mu_jv_j>0\), \(d_j=|C_j|\), and \(T=\sum_{j=1}^{\tau}w_j\). Since each satisfaction indicator is at most \(1\), every assignment \(y\) satisfies \(W_\mu(y)\le T\). Consequently, \(\mathrm{OPT}:=\max_y W_\mu(y)\le T\).
Let \(X\) assign every variable independently and uniformly from \(\{0,1\}\). Clause \(C_j\) is false precisely when all its literals are false. Its \(d_j\) literals involve distinct variables, so these events are independent, each with probability \(1/2\). Thus \(\Pr[X\models C_j]=1-2^{-d_j}\).
By linearity of expectation and the hypothesis \(d_j\ge k\),
\[
\mathbb E[W_\mu(X)]
=\sum_{j=1}^{\tau}w_j(1-2^{-d_j})
\ge (1-2^{-k})T
\ge (1-2^{-k})\mathrm{OPT}.
\]
Independence between different clauses is unnecessary.
Fix the variable order \(x_1,\ldots,x_\ell\). For a prefix \(s\in\{0,1\}^{t}\), define \(F(s)\) as the expected welfare when the first \(t\) variables equal \(s\) and the remaining variables are independent uniform bits.
For each clause, its conditional satisfaction probability \(p_j(s)\) is computed as follows:
The second formula follows because all fixed literals are false and the remaining literals concern distinct, independent uniform variables. It also covers \(r_j(s)=0\), yielding probability \(0\).
Therefore \(F(s)=\sum_{j=1}^{\tau}w_jp_j(s)\), which can be evaluated by scanning the explicitly listed clauses.
Start with the empty prefix. At a prefix \(s\) of length less than \(\ell\), compute \(F(s0)\) and \(F(s1)\), and append the bit giving the larger value. Break ties by choosing \(0\).
Conditioned on the current prefix, the next uniform bit has either value with probability \(1/2\). Hence \(F(s)=\bigl(F(s0)+F(s1)\bigr)/2\). At least one child therefore has conditional expectation at least \(F(s)\), and the algorithm chooses such a child.
After \(\ell\) steps, the resulting complete assignment \(x\) satisfies \(F(x)=W_\mu(x)\), since no randomness remains. The conditional expectations never decrease, so
\[
W_\mu(x)\ge F(\varnothing)
=\sum_{j=1}^{\tau}w_j(1-2^{-d_j})
\ge (1-2^{-k})\mathrm{OPT}.
\]
This constructs one common assignment for all support entries.
It remains to verify that comparing conditional expectations takes polynomial time in the binary input length.
Write the encoded rationals as \(\mu_j=a_j/b_j\) and \(v_j=c_j/e_j\), with positive integer numerators and denominators. Define \(D=\prod_{j=1}^{\tau}b_je_j\) and \(A_j=a_jc_jD/(b_je_j)\). Each \(A_j\) is a positive integer and \(w_j=A_j/D\).
The total bit length of the input numerators and denominators is at most \(L\). Thus \(D\) and every \(A_j\) have \(O(L)\) bits and can be computed using polynomial-time integer arithmetic.
For any prefix \(s\), compare conditional expectations using the scaled score \(S(s)=D\,2^\ell F(s)\). Each clause contributes:
These are integers because \(0\le r_j(s)\le\ell\). Each contribution has \(O(L+\ell)\) bits, and their sum has \(O(L+\ell+\log\tau)\) bits. Since the scaling factor is the same positive number for every prefix, comparing \(S(s0)\) and \(S(s1)\) is exactly equivalent to comparing \(F(s0)\) and \(F(s1)\).
There are \(2\ell\) candidate-prefix evaluations. Each scans at most \(\tau\ell\) literals and performs polynomially many arithmetic operations on integers of polynomial bit length. The entire algorithm therefore runs in time polynomial in \(\ell,\tau,L\), and hence in \(\ell,\tau,k,L\).
The construction processes the \(\tau\) support entries directly; small masses cause no expansion into repeated agents.
Theorem 2 of [Babaioff, Lavi, and Pavlov, *Mechanism Design for Single-Value Domains*](https://cdn.aaai.org/AAAI/2005/AAAI05-039.pdf) gives the conditional-expectation approximation for the finite-agent setting. The proof above establishes its applicability to the explicit support formulation, including exact polynomial-time computation with binary-rational masses. No separate published result for that formulation is needed.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The deterministic construction, approximation bound, and exact arithmetic analysis are rigorous. No major or minor mathematical issues were found.
Defining \(w_j=\mu_jv_j\) preserves the objective exactly:
\[
W_\mu(x)=\sum_{j=1}^{\tau}w_j\mathbf{1}[x\models C_j].
\]
Every weight is positive by the input hypotheses. Processing one weighted clause per support entry respects the explicit support encoding; no expansion into agents is required.
The bound \(\mathrm{OPT}\le T\), where \(T=\sum_jw_j\), follows directly because each satisfaction indicator lies in \(\{0,1\}\).
The probability calculation is correct. A clause of length \(d_j\) involves \(d_j\) distinct variables, and each literal is false with probability \(1/2\). Independence of those variables gives clause failure probability \(2^{-d_j}\).
Linearity of expectation applies regardless of dependencies between different clauses. Since \(d_j\ge k\), the inequality \(1-2^{-d_j}\ge1-2^{-k}\) has the correct direction. Finally, \(k\ge1\) makes the approximation factor positive, so multiplying \(\mathrm{OPT}\le T\) by that factor preserves the inequality.
The two cases exhaust all possibilities for a prefix:
Conditioning on a fixed prefix leaves the unassigned variables independent and uniform. Thus the second probability is correctly given by \(1-2^{-r_j(s)}\).
The boundary case \(r_j(s)=0\) is explicitly handled and correctly yields probability \(0\) for an unsatisfied clause. Every prefix has positive probability under the uniform distribution, so all conditional expectations used are well-defined.
The identity
\[
F(s)=\frac{F(s0)+F(s1)}{2}
\]
correctly follows by conditioning on the next uniform bit. Choosing the larger child therefore preserves or increases conditional expectation. The fixed tie rule makes the construction deterministic.
After exactly \(\ell\) choices, the prefix is a complete assignment and \(F(x)=W_\mu(x)\). Consequently, the argument establishes the claimed stronger bound
\[
W_\mu(x)\ge\sum_jw_j(1-2^{-d_j}),
\]
and hence the requested approximation relative to \(\mathrm{OPT}\).
All clauses are evaluated against the same completed assignment, as required.
The common denominator construction is valid: each \(b_je_j\) divides \(D\), so every \(A_j\) is an integer and \(w_j=A_j/D\).
The bit length of a product is bounded by the sum of the factor bit lengths. Since the encoded numerators and denominators together occupy at most \(L\) bits, both \(D\) and each \(A_j\) have \(O(L)\) bits. Computing them requires only polynomially many integer operations on numbers of polynomial bit length.
The scaled contributions are correct. For an unsatisfied prefix, multiplying \(1-2^{-r_j(s)}\) by \(A_j2^\ell\) gives
\[
A_j\bigl(2^\ell-2^{\ell-r_j(s)}\bigr).
\]
The exponent \(\ell-r_j(s)\) is nonnegative because each clause contains at most \(\ell\) distinct variables. The case \(r_j(s)=0\) again gives zero.
The contribution bound \(O(L+\ell)\) and sum bound \(O(L+\ell+\log\tau)\) are correct. The common positive scaling factor preserves comparisons exactly.
There are exactly \(2\ell\) candidate-prefix evaluations. Each clause contains at most \(\ell\) literals, so the stated bound of at most \(\tau\ell\) scanned literals per evaluation is valid.
Combining these counts with the established integer bit bounds gives polynomial running time in \(\ell,\tau,L\), and therefore in the requested parameters \(\ell,\tau,k,L\). This includes \(k=1\), \(k=\ell\), unused variables, and arbitrarily small positive encoded masses.
The attribution is accurate: Theorem 2 states polynomial-time conditional-expectation approximation for the finite-agent \(k\)-SAT domain and truthfulness in the known-clause setting. Its clause restrictions and positive-value assumptions match the relevant setting here. [Babaioff, Lavi, and Pavlov, Theorem 2](https://cdn.aaai.org/AAAI/2005/AAAI05-039.pdf)
The support-encoded arithmetic claim is established independently in the submitted proof. The citation does not substitute for any necessary step, and truthful payments are not part of the requested construction.
Repair feedback: None 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.