Answer: Yes. A randomized algorithm using \(\operatorname{poly}(m,\tau,L)\) bit operations and demand-oracle calls returns a feasible allocation with \(\mathbb{E}[W(x)]\geq\mathrm{OPT}/(C D\log\log D/\log D)\) for a universal constant \(C>0\).
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor CA with bidder conflicts, suppose that the bidders have fractionally sub-additive (FSA) valuations. If there is a demand oracle for each bidder (we shall define this in Section \ref{subsect:CP-CA-noconflict}), then there exists an $\bigO\left((\Delta \log\log \Delta)/\log \Delta\right)$-approximation algorithm of social welfare that runs in \polymn-time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given items \(I\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(b_k\), a directed type-conflict graph \(H\), and fractionally sub-additive valuations \(v_t\) with demand oracles, choose masses \(x_{t,S}\ge 0\) satisfying \(\sum_{S\subseteq I}x_{t,S}=\mu_t\) and \(\sum_{t\in T}\sum_{S\ni k}x_{t,S}\le b_k\). Let \(A(x)=\{t:\sum_{S\ne\emptyset}x_{t,S}>0\}\), and count type \(t\)’s welfare only when \(N_H^+(t)\cap A(x)=\emptyset\). Does there exist an algorithm returning feasible \(x\) with welfare at least \(\mathrm{OPT}/O((\Delta_H\log\log\Delta_H)/\log\Delta_H)\), in time polynomial in \(m,\tau,L\) and the demand-oracle calls?
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
There are \(m\geq1\) items \(I\), nonnegative binary-rational per-capita supplies \(b_k\), and a loopless directed graph \(H=(T,E)\). Write \(N_H^+(t)=\{u:(t,u)\in E\}\), \(\Delta_H=\max_t|N_H^+(t)|\), and \(D=\max\{4,\Delta_H\}\).
Each type has a monotone fractionally sub-additive valuation \(v_t:2^I\to\mathbb{Q}_{\geq0}\), with \(v_t(\emptyset)=0\). An exact demand oracle, at nonnegative rational item prices \(p\), returns any maximizing bundle \(S\in\arg\max_{R\subseteq I}(v_t(R)-\sum_{k\in R}p_k)\) and its value.
Let \(L\) include the explicit input bit length and a uniform bound on the bit lengths of valuation values; oracle calls are charged separately.
An allocation assigns nonnegative real masses \(x_{t,S}\) to bundles, satisfying \(\sum_{S\subseteq I}x_{t,S}=\mu_t\) for every \(t\), and \(\sum_t\sum_{S\ni k}x_{t,S}\leq b_k\) for every \(k\); empty bundles represent unallocated mass.
Define \(A(x)=\{t:\sum_{S\neq\emptyset}x_{t,S}>0\}\) and \(W(x)=\sum_{t:N_H^+(t)\cap A(x)=\emptyset}\sum_{S\subseteq I}x_{t,S}v_t(S)\). Set \(\mathrm{OPT}=\max_{x\text{ feasible}}W(x)\); positive allocated mass of a conflicting type suppresses the entire type's welfare.
Does there exist a possibly randomized algorithm returning a feasible allocation \(x\) with \(\mathbb{E}[W(x)]\geq\mathrm{OPT}/(C D\log\log D/\log D)\) for a universal constant \(C>0\), using \(\operatorname{poly}(m,\tau,L)\) bit operations and demand-oracle calls?
For finite bidders and indivisible items, an approximation algorithm with this asymptotic ratio and expected-welfare guarantee is known for fractionally sub-additive valuations with demand oracles ([Cheung et al.](https://arxiv.org/pdf/1509.09147)).
No result settling the approximation guarantee for exactly the mass-allocation model above was located.
Yes. The stated mass-allocation model admits a randomized algorithm with the requested guarantee and polynomial bit complexity and demand-oracle complexity.
The crucial additional constraint in the relaxation is that a type’s use of each item must be bounded by its activation variable times that item’s supply. This makes the type’s allocation feasible by itself after amplification. Capacity violations among sampled types can then be resolved by splitting bundle masses.
The proof below uses Gaussian rounding related to the finite-bidder argument of [Cheung et al.](https://arxiv.org/pdf/1509.09147), but establishes the mass-allocation rounding directly.
Throughout, logarithms are natural.
Call a subset of types independent if it contains no two endpoints of any directed edge.
For a feasible allocation \(x\), let
\(\displaystyle P(x)=\{t\in A(x):N_H^+(t)\cap A(x)=\emptyset\}.\)
The set \(P(x)\) is independent: if \(t,u\in P(x)\) and \((t,u)\in E\), then \(u\in A(x)\) contradicts the defining condition for \(t\).
Construct \(x'\) by retaining all nonempty-bundle masses of types in \(P(x)\), and assigning every other type entirely to the empty bundle. Then \(x'\) is feasible, its active support is independent, and
\(\displaystyle W(x')=\sum_{t\in P(x)}\sum_{S\ne\emptyset}x_{t,S}v_t(S)=W(x).\)
Consequently, \(\mathrm{OPT}\) equals the maximum ordinary welfare obtainable with independent active support. This maximum exists: there are finitely many independent subsets, and the allocation problem restricted to each subset is a finite, compact linear program.
We make two harmless preprocessing changes.
Deleted types will receive empty bundles. Restricting a valuation to the remaining items preserves fractional subadditivity. A restricted demand query is implemented by assigning deleted items a price larger than every valuation value; such a bound is also obtainable from zero-price demand queries on the original item set.
Write \(n\leq\tau\) for the number of remaining types, and retain the original parameter \(D\). If no items or types remain, the empty allocation is optimal. Otherwise all supplies and all full-set values are positive.
Since a positive rational with bit length at most \(L\) is at least \(2^{-L}\), allocating a sufficiently small mass of the full remaining item set to one remaining type shows that
\(\displaystyle \mathrm{OPT}\geq 2^{-2L}.\)
Indeed, the mass \(\min\{\mu_t,\min_k b_k\}\) is feasible for that type and is at least \(2^{-L}\).
For a remaining type \(t\), a scalar \(a\in[0,1]\), and nonnegative item capacities \(d=(d_k)_k\), define
\(\displaystyle F_t(a,d)=\max_{y\geq0}\left\{\sum_{S\ne\emptyset}y_Sv_t(S):\sum_{S\ne\emptyset}y_S\leq\mu_ta,\quad \sum_{S\ni k}y_S\leq d_k\ \text{for every }k\right\}.\)
Its dual is
\(\displaystyle F_t(a,d)=\min_{\alpha,p\geq0}\left\{\mu_ta\alpha+\sum_k d_kp_k:\alpha+\sum_{k\in S}p_k\geq v_t(S)\ \text{for every }S\ne\emptyset\right\}.\)
A demand query at prices \(p\) separates the bundle inequalities: it returns a bundle maximizing \(v_t(S)-\sum_{k\in S}p_k\), which is compared with \(\alpha\). If the returned bundle is empty, its utility is zero, and no inequality is violated because \(\alpha\geq0\).
We use the standard rational LP optimization–separation theorem, including primal recovery. Its hypotheses hold here:
Thus \(F_t(a,d)\), an optimal dual solution, and an optimal primal allocation can be obtained with polynomial bit operations and oracle calls. A primal optimum can be chosen with at most \(m+1\) positive bundle variables, by choosing an optimal basic solution.
The dual formula also shows that \(F_t\) is concave. Its hypograph has a strong separation oracle: if \(z>F_t(a,d)\), an optimal dual solution gives the separating inequality
\(\displaystyle z\leq\mu_t\alpha a+\sum_k p_kd_k.\)
These are applications of the rational oracle optimization framework of [Grötschel, Lovász and Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf).
Introduce activation variables \(a_t\), item-capacity variables \(d_{t,k}\), welfare variables \(z_t\), and a symmetric matrix \(M\) indexed by the types together with an auxiliary index \(0\).
Maximize \(\sum_t z_t\), subject to
\(\displaystyle 0\leq a_t\leq1,\qquad d_{t,k}\geq0,\qquad z_t\geq0,\)
\(\displaystyle \sum_t d_{t,k}\leq b_k,\qquad d_{t,k}\leq b_ka_t,\qquad z_t\leq F_t(a_t,d_t),\)
\(\displaystyle M\succeq0,\qquad M_{00}=M_{tt}=1,\qquad M_{0t}=2a_t-1,\)
and, whenever either orientation of an edge joins \(t\) and \(u\),
\(\displaystyle M_{tu}=1-2a_t-2a_u.\)
Denote its optimum by \(Z^*\).
This is a relaxation of the independent-support problem. To check this, take any feasible allocation with independent active support and put \(a_t=1\) on that support and \(a_t=0\) elsewhere. Let \(d_{t,k}\) be its actual item consumption, and let \(z_t\) be its ordinary welfare contribution.
Set \(s_0=1\), \(s_t=2a_t-1\), and \(M=ss^{\mathsf T}\). For an edge, independence gives \(a_ta_u=0\), so
\(\displaystyle M_{tu}=(2a_t-1)(2a_u-1)=1-2a_t-2a_u.\)
Every constraint holds. Therefore
\(\displaystyle Z^*\geq\mathrm{OPT}.\)
Here the use of convex optimization requires a conditioning check.
Eliminate the matrix equalities, using \(a\), \(d\), \(z\), and the matrix entries corresponding to nonedges as coordinates. The number of coordinates is polynomial in \(m\) and \(n\). All coordinates are bounded: matrix entries have absolute value at most one, \(a_t,d_{t,k}\leq1\), and \(z_t\leq2^L\).
There is also an explicitly known interior point. Put
\(\displaystyle \delta=\frac1{4n},\qquad a_t^0=\delta,\qquad d_{t,k}^0=\frac{\delta b_k}{4n}.\)
Choose \(M^0\) with diagonal entries one, entries \(M^0_{0t}=2\delta-1\), and all distinct type-type entries equal to \(1-4\delta\). Its Schur complement with respect to the auxiliary diagonal entry is
\(\displaystyle 4\delta I-4\delta^2\mathbf1\mathbf1^{\mathsf T}\succeq3\delta I.\)
Moreover, \(M^0\) has smallest eigenvalue at least \(1/(4n^2)\). For completeness, writing \(c=2\delta-1\), its quadratic form is at least
\(\displaystyle (x_0+c\mathbf1^{\mathsf T}x)^2+3\delta\|x\|^2.\)
The inequality
\(\displaystyle x_0^2+\|x\|^2\leq2(x_0+c\mathbf1^{\mathsf T}x)^2+(2n+1)\|x\|^2\)
gives the asserted eigenvalue bound.
For each type choose
\(\displaystyle \eta_t=\frac12\min\{\mu_t\delta,\min_k d_{t,k}^0\},\qquad z_t^0=\frac12\eta_tv_t(I).\)
The allocation placing mass \(\eta_t\) on \(I\) proves \(F_t(a_t^0,d_t^0)\geq2z_t^0>0\). Every scalar inequality is strict.
An explicit radius that works in the eliminated coordinates is
\(\displaystyle r=\frac{2^{-4L}}{2^{12}(n+1)^4(m+1)}.\)
To verify this, a coordinate perturbation of norm at most \(r\) changes the matrix by Frobenius norm at most \(5nr\), preserving positive definiteness. It also preserves all scalar capacity inequalities. Finally,
\(\displaystyle \eta_t\geq\frac{2^{-L}}{32n^2},\qquad z_t^0\geq\frac{2^{-2L}}{64n^2},\)
so the same allocation of mass \(\eta_t\) on \(I\) remains feasible throughout the ball and keeps \(z_t<F_t(a_t,d_t)\).
Thus the feasible set has a known outer radius and a known interior radius whose logarithms have polynomial length. Its strong separation oracle combines rational positive-semidefiniteness testing with the single-type LP oracles.
The well-bounded convex optimization theorem consequently returns a rational feasible point satisfying
\(\displaystyle \sum_tz_t\geq Z^*-2^{-2L-1}\geq\frac{\mathrm{OPT}}2.\)
One may use the usual weak-optimization formulation of that theorem and obtain exact feasibility by mixing the returned point with the known interior point: if a point is within distance \(\xi\) of the feasible set, mixing it with the interior point in proportion at least \(\xi/(r+\xi)\) puts it inside the feasible set. Choosing polynomial-bit precision makes the resulting objective loss smaller than the specified tolerance.
At this rational feasible point, recover an optimal single-type plan \(y_{t,S}\) for every \(F_t(a_t,d_t)\). Define
\(\displaystyle V_t=\sum_{S\ne\emptyset}y_{t,S}v_t(S),\qquad \ell_{t,k}=\sum_{S\ni k}y_{t,S}.\)
The plans have polynomial support and satisfy
\(\displaystyle \sum_Sy_{t,S}\leq\mu_ta_t,\qquad \ell_{t,k}\leq b_ka_t,\qquad \sum_t\ell_{t,k}\leq b_k,\)
and
\(\displaystyle Z:=\sum_tV_t\geq\sum_tz_t\geq\frac{\mathrm{OPT}}2.\)
The remaining task is to round these plans.
We need the following consequence of fractional subadditivity.
Retention lemma. Suppose \(R\) is a random subset of a fixed bundle \(S\), and \(\Pr(k\in R)\geq\gamma>0\) for every \(k\in S\). Then
\(\displaystyle \mathbb E[v_t(R)]\geq\gamma v_t(S).\)
Indeed, give every subset \(Q\subseteq S\) fractional-cover weight \(\Pr(R=Q)/\gamma\). Every item of \(S\) receives total weight at least one. Fractional subadditivity gives the inequality. If the definition restricts cover coefficients to at most one, cap each coefficient at one; this preserves coverage.
We also describe an exact, deterministic trimming operation on bundle masses.
Suppose proposed plans have total item loads \(L_k\). Set
\(\displaystyle r_k=\begin{cases}\min\{1,b_k/L_k\},&L_k>0,\\1,&L_k=0.\end{cases}\)
Replace each proposed bundle \(S\) by the mass distribution of
\(\displaystyle S(\theta)=\{k\in S:\theta\leq r_k\},\qquad \theta\ \text{uniform on }[0,1].\)
This is a description of mass splitting, not an additional sampling step. Sort the finitely many thresholds \(r_k\); their interval lengths determine the output masses exactly.
Every item’s load becomes \(r_kL_k\leq b_k\), and each bundle yields at most \(m+1\) subbundles. All masses are rational when the proposed plans are rational.
Assume \(D\geq2^{64}\). Choose a rational \(\varepsilon\) satisfying
\(\displaystyle \frac{\log\log D}{\log D}\leq\varepsilon\leq2\frac{\log\log D}{\log D}.\)
Such a rational is computable with polynomial precision. In this range, \(\varepsilon<1/4\) and \(\varepsilon D\geq1\).
Partition the types into
\(\displaystyle B_0=\{t:a_t\leq\varepsilon\},\qquad B_1=\{t:\varepsilon<a_t\leq1/2\},\qquad B_2=\{t:a_t>1/2\}.\)
We construct one feasible allocation from each class.
For each \(t\in B_0\) with \(a_t>0\), independently select \(t\) with a dyadic probability \(\widehat p_t\) satisfying
\(\displaystyle \frac{a_t}{8\varepsilon D}\leq\widehat p_t\leq\frac{a_t}{4\varepsilon D}.\)
This is obtained by rounding \(a_t/(4\varepsilon D)\) down to a dyadic rational within a factor of two, using polynomially many bits.
A selected type proposes the amplified plan \(y_{t,S}/a_t\). It respects its population mass and is feasible by itself for every item:
\(\displaystyle \sum_S\frac{y_{t,S}}{a_t}\leq\mu_t,\qquad \frac{\ell_{t,k}}{a_t}\leq b_k.\)
Apply the trimming operation to all proposed plans. Then discard every selected type having a selected out-neighbor. Fill unused population mass with empty bundles. The resulting allocation is feasible and has independent active support.
Fix a type \(t\), and condition on its selection and on the event \(F_t\) that none of its out-neighbors is selected. Since every low-activation selection probability is at most \(1/(4D)\),
\(\displaystyle \Pr(F_t)\geq1-\sum_{u\in N_H^+(t)\cap B_0}\widehat p_u\geq\frac34.\)
Under this conditioning, selections of all other eligible types remain independent with their original probabilities. Let \(O_k\) denote their proposed load of item \(k\). Then
\(\displaystyle \mathbb E[O_k\mid t\text{ selected},F_t]\leq\sum_{u\ne t}\frac{\widehat p_u\ell_{u,k}}{a_u}\leq\frac{b_k}{4\varepsilon D}.\)
The type’s own proposed load is at most \(b_k\). Thus its trimming factor satisfies
\(\displaystyle r_k\geq\frac{b_k}{b_k+O_k}.\)
The function \(s\mapsto b_k/(b_k+s)\) is convex, so Jensen’s inequality yields
\(\displaystyle \mathbb E[r_k\mid t\text{ selected},F_t]\geq\frac1{1+1/(4\varepsilon D)}\geq\frac12.\)
Apply the retention lemma to each original bundle, averaging over the other selections and over the interval used for mass splitting. Conditional retained welfare is at least \(V_t/(2a_t)\). Therefore
\(\displaystyle \mathbb E[W_0]\geq\sum_{t\in B_0}\frac{a_t}{8\varepsilon D}\cdot\frac34\cdot\frac{V_t}{2a_t}=\frac{3}{64\varepsilon D}\sum_{t\in B_0}V_t.\)
Types with \(a_t=0\) have \(V_t=0\) and need not be selected.
Factor \(M\) as a Gram matrix of unit vectors \(w_0,w_t\). Put
\(\displaystyle u_t=\frac{w_0+w_t}{2}.\)
Then \(\|u_t\|^2=a_t\), \(w_0\cdot u_t=a_t\), and an edge implies \(u_t\cdot u_u=0\).
For two adjacent types with positive activation, Bessel’s inequality applied to the orthonormal vectors \(u_t/\sqrt{a_t}\) and \(u_u/\sqrt{a_u}\) gives
\(\displaystyle a_t+a_u\leq\|w_0\|^2=1.\)
Hence \(B_2\) is independent. Retain its original plans and assign all other types empty bundles. This is feasible and has welfare
\(\displaystyle W_2=\sum_{t\in B_2}V_t.\)
For \(t\in B_1\), project \(w_t\) perpendicular to \(w_0\) and normalize:
\(\displaystyle q_t=\frac{w_t-(w_0\cdot w_t)w_0}{\sqrt{1-(w_0\cdot w_t)^2}}.\)
These vectors are well defined. For an edge joining \(t,u\in B_1\),
\(\displaystyle q_t\cdot q_u=-\sqrt{\frac{a_ta_u}{(1-a_t)(1-a_u)}}\leq-\frac{\varepsilon}{1-\varepsilon}.\)
Write \(r_0=\varepsilon/(1-\varepsilon)\), and set
\(\displaystyle h=\sqrt{2(1-2\varepsilon)(\log D+4)}.\)
Take a standard Gaussian vector \(g\). Select \(t\in B_1\) when \(q_t\cdot g\geq h\), and discard every selected type having a selected out-neighbor. Retain the original plans of the survivors.
We now prove a uniform survival bound. Let \(Q(s)\) denote the standard normal upper-tail probability, and put \(q=Q(h)\). For \(s\geq1\),
\(\displaystyle \frac{e^{-3/2}}{\sqrt{2\pi}\,s}e^{-s^2/2}\leq Q(s)\leq\frac1{\sqrt{2\pi}\,s}e^{-s^2/2}.\)
The lower bound follows by integrating the density over the interval from \(s\) to \(s+1/s\); the upper bound follows by integration by parts.
For adjacent types, let \(X=q_t\cdot g\), \(Y=q_u\cdot g\). Their correlation is at most \(-r_0\). Consequently, \(X+Y\) has variance at most \(2(1-r_0)\), and
\(\displaystyle \Pr(X\geq h,Y\geq h)\leq Q\!\left(h\sqrt{\frac2{1-r_0}}\right).\)
Using the tail bounds,
\(\displaystyle \frac{\Pr(X\geq h,Y\geq h)}q\leq\frac{e^{3/2}}{\sqrt2}\exp\!\left(-\frac{h^2(1+r_0)}{2(1-r_0)}\right)=\frac{e^{-5/2}}{\sqrt2\,D}<\frac1{8D}.\)
The equality uses \((1+r_0)/(1-r_0)=1/(1-2\varepsilon)\).
There are at most \(D\) relevant out-neighbors, so a union bound gives
\(\displaystyle \Pr(t\text{ survives})\geq\frac78q.\)
Furthermore, \(h\leq2\sqrt{\log D}\) and \(\varepsilon\log D\geq\log\log D\). Therefore
\(\displaystyle q\geq\frac{e^{-11/2}}{2\sqrt{2\pi}}\frac{(\log D)^{3/2}}D\geq\frac{2^{-16}}{\varepsilon D}.\)
For the last inequality, the constant preceding \((\log D)^{3/2}/D\) exceeds \(2^{-16}\), and \(\varepsilon(\log D)^{3/2}\geq1\) in the stipulated range.
Thus ideal Gaussian rounding gives every middle-activation type survival probability at least
\(\displaystyle \rho=\frac{2^{-17}}{\varepsilon D}.\)
The preceding Gaussian construction has a bounded polynomial-bit implementation with survival probability at least \(\rho/2\).
Here are the details needed for that assertion.
A rational positive-semidefinite matrix admits a rational \(LDL^{\mathsf T}\) factorization, with polynomial coefficient bit lengths. Approximating the square roots of its nonnegative diagonal factors gives approximations to the Gram vectors to any specified accuracy in polynomial time. For middle-activation types, the squared projection norm is
\(\displaystyle 1-(2a_t-1)^2=4a_t(1-a_t)\geq2\varepsilon,\)
so normalization does not require excessive precision.
Approximate the unit vectors and the threshold, and generate independent normal coordinates by applying the inverse normal distribution function to finite-bit uniform variables. Couple these variables to genuine uniform variables lying in the same dyadic intervals. After excluding Gaussian tails beyond a bound of order \(\sqrt{\log(n/\rho)}\), polynomially many bits suffice to make every computed inner product differ from its ideal value by at most any prescribed positive rational tolerance.
To quantify the decision error, choose the tolerance
\(\displaystyle \kappa=\frac{\rho}{8n}.\)
Each ideal inner product is standard normal, so
\(\displaystyle \Pr(|q_t\cdot g-h|\leq\kappa)\leq\frac{2\kappa}{\sqrt{2\pi}}.\)
A union bound, together with a Gaussian-tail failure probability at most \(\rho/4\), makes the probability that *any* candidate-selection flag differs from its ideal flag at most \(\rho/2\). Thus every type’s survival probability decreases by at most \(\rho/2\).
All required precision parameters have polynomial bit length. In particular, \(D\leq\max\{4,\tau-1\}\), and \(\log(1/\rho)\) is polynomially bounded. The inverse normal function and the elementary functions used above can be evaluated to this precision by bounded-interval bisection and standard polynomial-bit evaluation.
Regardless of numerical decision errors, pruning is performed exactly on the explicit graph, so every output remains feasible with independent active support. We have proved for the implemented algorithm that
\(\displaystyle \mathbb E[W_1]\geq\frac{2^{-18}}{\varepsilon D}\sum_{t\in B_1}V_t.\)
For \(4\leq D<2^{64}\), use the globally feasible plans \(y\) from Section 2 without amplification.
Independently select every type with a dyadic probability \(p\) satisfying
\(\displaystyle \frac1{4D}\leq p\leq\frac1{2D}.\)
Discard every selected type having a selected out-neighbor, and retain the original plans of the survivors. Restriction preserves all mass and supply constraints. Each type survives with probability at least
\(\displaystyle p(1-Dp)\geq\frac1{8D}.\)
Therefore
\(\displaystyle \mathbb E[W]\geq\frac Z{8D}\geq\frac{\mathrm{OPT}}{16D}.\)
On the fixed interval from \(4\) to \(2^{64}\), the positive function \(\log D/\log\log D\) is bounded. This is therefore the requested approximation with a universal constant.
For large \(D\), construct the three allocations above and return the one with greatest welfare. Their active supports are independent, so their welfare is ordinary bundle welfare.
This comparison uses only polynomially many additional demand queries: to evaluate a bundle \(S\), assign zero prices on \(S\) and sufficiently large prices outside \(S\). Monotonicity ensures that the returned value equals \(v_t(S)\).
Pointwise, the largest of three nonnegative numbers is at least their average. Since \(\varepsilon D\geq1\), all three bounds imply
\(\displaystyle \mathbb E[W]\geq\frac{2^{-18}}{3\varepsilon D}\sum_tV_t\geq\frac{\mathrm{OPT}}{6\cdot2^{18}\varepsilon D}.\)
Using the upper bound on \(\varepsilon\),
\(\displaystyle \mathbb E[W]\geq\frac{\mathrm{OPT}}{(12\cdot2^{18})D\log\log D/\log D}.\)
Combining this with the bounded-\(D\) case gives a universal constant \(C>0\).
Finally, every recovered type plan has at most \(m+1\) positive bundle variables. Trimming replaces each by at most \(m+1\) subbundles, so the output has polynomial support. Its masses have polynomial bit length: amplification, load summation, threshold formation, and interval splitting involve only polynomially many rational operations on polynomial-bit numbers. Unused mass is assigned to empty bundles.
The convex optimization, its demand-oracle LP separation calls, plan recovery, finite-bit sampling, and welfare comparison all use \(\operatorname{poly}(m,\tau,L)\) bit operations and demand-oracle calls. This proves the requested guarantee for exactly the stated mass-allocation model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with minor gaps. The argument is sound in substance and addresses the stated mass-allocation model directly. I found no false central step or gap requiring new mathematics. The remaining issues concern the precision of the optimization citation, finite-bit sampling details, and one conditional-probability statement.
The established result is a polynomial-time approximation guarantee, not an exact polynomial-time solution of the optimization problem.
The definition of \(P(x)\) correctly identifies the active types contributing welfare. If an edge joins two members of \(P(x)\), its tail has an active out-neighbor, contradicting membership.
Removing all nonempty allocations outside \(P(x)\) preserves feasibility. Every retained type then contributes its original ordinary welfare, while removed types contribute zero because \(v_t(\emptyset)=0\). Thus the displayed equality \(W(x')=W(x)\) is valid.
The existence argument is also correct: for each independent subset, the restricted allocation problem is a finite compact linear program, and there are finitely many such subsets. This appropriately avoids relying on continuity of the original suppression-based objective.
Items with zero supply cannot occur with positive mass in any feasible nonempty allocation. Capping other supplies at one is valid because total population mass is one.
Deleting types whose full remaining-item value is zero is justified by monotonicity. Such types cannot contribute welfare, and their activation can only suppress other contributions.
The proposed implementation of restricted demand queries works: a price exceeding every valuation value excludes every bundle containing a deleted item, since the empty bundle has utility zero.
When a type and an item remain, the proposed single-type full-bundle allocation is feasible. Both its mass and its positive bundle value are at least \(2^{-L}\), giving \(\mathrm{OPT}\geq 2^{-2L}\). The empty residual instance is handled explicitly.
The primal and dual constraints match. Nonnegative-price demand queries provide the stated separation: an empty maximizing bundle cannot conceal a violation because its utility is zero and \(\alpha\geq0\).
The primal is feasible and bounded, and the dual is feasible. Finite-dimensional linear-programming duality therefore applies. The sparse-support bound of at most \(m+1\) positive bundle variables is valid.
Concavity follows from the dual representation as an infimum of affine functions. An optimal dual solution supplies the claimed hypograph inequality.
Minor issue: the output invokes an exact rational optimization–separation theorem “including primal recovery” without identifying a precise theorem or stating its complete oracle and encoding guarantees. The rational constraint structure supplied here supports the application, but the reference should distinguish exact rational LP optimization and primal recovery from weak optimization of general convex bodies. The [GLS treatment](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf) distinguishes these settings.
Minimum clarification: identify the exact result used for rational LP optimization and recovery, including its dependence on constraint encoding length and its guarantee of a polynomial-size primal solution.
For an allocation with independent active support, the proposed binary activations and actual item consumptions satisfy all scalar constraints, including the additional constraint \(d_{t,k}\leq b_ka_t\).
The rank-one matrix construction is positive semidefinite and satisfies every matrix equality. On an edge, independence gives \(a_ta_u=0\), yielding the required entry.
Consequently, \(Z^*\geq\mathrm{OPT}\) is justified. The extra per-type capacity constraint does not exclude any independent-support allocation.
The coordinate bounds are valid after preprocessing. The displayed Schur complement is correct, and the quadratic-form estimate supports the claimed lower eigenvalue bound.
The proposed interior point has strict scalar slack. The lower bounds on \(\eta_t\) and \(z_t^0\) check out. The specified radius is sufficiently small to preserve positive definiteness, capacity slack, positivity, and feasibility of the fixed full-bundle witness.
Thus the relaxation is full-dimensional in the eliminated coordinates and has polynomially encoded inner and outer bounds. Its separation components are appropriate.
The interior-point mixing assertion is valid under the stated distance hypothesis.
Minor issue: the write-up does not state the precise weak-optimization output guarantee or allocate the objective-error budget between weak optimization and subsequent mixing. The claimed accuracy is compatible with the supplied bounds, but “choosing polynomial-bit precision” leaves this application insufficiently explicit.
Minimum clarification: state the optimization theorem’s distance and objective guarantees and specify precision parameters ensuring that the combined objective loss is at most \(2^{-2L-1}\). This is numerical bookkeeping, not an additional mathematical ingredient.
Once the feasible point is obtained, recovery of the single-type plans correctly gives all stated mass and load inequalities and \(Z\geq\mathrm{OPT}/2\).
The fractional-cover construction proves the retention lemma without any independence assumption on item retention. Capping cover coefficients at one preserves coverage and cannot increase the weighted valuation sum.
The trimming operation correctly represents mass splitting. Every item survives in precisely an \(r_k\) fraction of each proposed bundle mass containing it. Hence its final load is \(r_kL_k\leq b_k\).
Sorting the thresholds produces at most \(m+1\) subbundles per original bundle. Rationality and preservation of total bundle mass are justified.
Amplification by \(1/a_t\) respects population mass and each item’s supply for an individual type. The selection probabilities give the stated lower bound on the probability of having no selected out-neighbor.
The conditional expected competing load is bounded as claimed. Jensen’s inequality applies in the correct direction because the displayed function is convex. Combining trimming retention, amplification, selection, and conflict pruning yields the factor \(3/(64\varepsilon D)\).
Types with \(a_t=0\) have zero plans and are handled correctly.
Minor issue: “selections of all other eligible types remain independent with their original probabilities” is imprecise. Under the conditioning, the out-neighbors covered by the event are forced unselected. Only the remaining unconditioned types retain their original probabilities.
This does not invalidate the expected-load upper bound: forced exclusions only reduce load.
Minimum clarification: specify that the unchanged probabilities refer to types outside the conditioned out-neighbor set, and that the conditioned neighbors contribute zero.
The Gram-vector identities are correct. For adjacent positive-activation types, the normalized \(u_t\) vectors are orthogonal, and their squared projections of \(w_0\) are \(a_t\) and \(a_u\).
Bessel’s inequality therefore gives \(a_t+a_u\leq1\). Two types in \(B_2\) cannot be adjacent. Restricting the original plans preserves feasibility and gives the stated welfare exactly.
The normalization is well defined throughout \(B_1\). The edge-correlation formula and its upper bound are correct.
The Gaussian-tail estimates hold in the stated range. Substitution of \(h\) and \(r_0\) gives the displayed joint-selection bound, including the constant \(e^{-5/2}/(\sqrt{2}D)<1/(8D)\).
The union bound uses out-degree, as required; it does not incorrectly assume bounded undirected degree.
The lower bound on \(q\) also checks out. In particular, the exponent yields the stated factor \((\log D)^{3/2}/D\), and the numerical constant exceeds \(2^{-16}\). The claimed ideal survival probability \(\rho\) follows.
Singular Gaussian correlations do not invalidate the argument: the sum-based upper bound remains valid.
Rational positive-semidefinite factorization, approximate square roots, and the projection-norm lower bound support polynomial-precision vector construction.
The anti-concentration estimate is correct. With the stipulated coupling-error and tail budgets, the global flag-disagreement probability is at most \(\rho/2\), so the survival guarantee follows. Exact graph pruning preserves independent support regardless of numerical errors.
Minor issue: the implementation does not specify the representative chosen in each dyadic uniform interval, the tail cutoff, the number of random bits, or the division of \(\kappa\) between vector, normal-coordinate, arithmetic, and threshold errors. Endpoint handling matters because the inverse normal function is undefined at uniform endpoints zero and one.
Minimum clarification: specify these choices and give quantitative precision bounds ensuring total decision error at most \(\kappa\) outside the exceptional event. The supplied conditioning and anti-concentration estimates make this a routine implementation clarification.
The bounded-degree survival estimate \(p(1-Dp)\geq1/(8D)\) is valid. The bounded interval of degree parameters permits absorption into a universal approximation constant.
Returning the greatest-welfare allocation gives the pointwise averaging bound without requiring independence between the three constructions. The final large-degree constant follows correctly from \(Z\geq\mathrm{OPT}/2\) and the upper bound on \(\varepsilon\).
Bundle-value recovery through restricted zero-price demand queries is valid by monotonicity. The support-growth and rational-arithmetic arguments give polynomial output size and bit length.
The genuine contribution is the supply-scaled activation relaxation together with amplification and deterministic mass trimming. Those steps establish the bridge to the continuous allocation model. The remaining requested clarifications make the computational claims fully explicit; they do not require a new rounding argument.
⟨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.