Answer: The approximation guarantee is attainable in polynomial time: $W\geq\mathrm{OPT}/(6\log_2 R)$.
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a mechanism with a polynomial running time4 that achieves an O(log R) approximation to the optimal welfare and is incentive compatible for agents with OR-linear valuations. The description of the shifting mechanism is involved and requires many details. Due to lack of space, we will only mention an outline of this algorithm and of the incentive- compatibility proof. The Shifting mechanism (outline): Divide the rectangles to log n classes according to their heights (e.g., all the rectangles up to height of 2, up to 4, 8 etc.).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many bidder classes \(q\), each with a fixed OR-linear bundle template, a rational mass distribution over private values \(\theta\), rational per-capita spatial supply, and a finite rational description of candidate rectangles, compute a polynomial-time direct menu mechanism. Each bidder must receive an integral feasible bundle and a transfer; aggregate assignments must respect supply, and truthful menu choice must be dominant-strategy optimal. Does such a mechanism guarantee welfare at least \(\mathrm{OPT}/(c\log R)\) for a universal constant \(c\), where \(R\) bounds the ratio of rectangle edge lengths?
There are \(Q\) public bidder classes and \(m\) distinct axis-parallel candidate rectangles with rational coordinates and positive edge lengths. A class \(q\) has a public template \((S_{qj},\alpha_{qj})_j\), where each \(S_{qj}\) is a candidate rectangle and \(\alpha_{qj}\geq0\) is rational; let \(K\) be the total number of template entries.
An integral bundle \(T\) is a union of pairwise disjoint candidate rectangles, including the empty union. Its OR-linear value is \(v_q(\theta,T)=\theta\max\{\sum_{j\in I}\alpha_{qj}: S_{qj}\subseteq T\text{ for all }j\in I,\ S_{qj}\text{ pairwise disjoint}\}\), with the empty index set allowed. Rectangles are half-open, so touching edges do not conflict.
The society is nonatomic and given by its support: the list of the \(\tau\) types \((q,\theta)\) with positive binary-rational masses \(\mu_{q,\theta}\), summing to \(1\), where \(\theta\geq0\) is rational. Here \(\tau\) is the support size, not the number of possible types; class membership is public and only \(\theta\) is private.
Spatial supply \(s(x)\geq0\) is rational and constant on each cell of an explicitly given rational rectilinear partition with \(B\) cells covering all candidate rectangles. Feasibility means that, at every point \(x\), the total mass of agents whose bundles contain \(x\) is at most \(s(x)\).
Within every type, agents have a public label \(u\in[0,1]\), uniformly distributed independently of private value conditional on class. A mechanism specifies finitely many rational label intervals per class, each with a finite menu of integral bundles and signed rational prices; an agent can access only its assigned menu. The empty bundle is available, and menu ties use a specified order independent of reports.
The direct mechanism selects, for reported \(\theta\in[0,\infty)\), a menu entry maximizing \(v_q(\theta,T)-p\). Truthful reporting must be dominant-strategy optimal for every value and label; supply feasibility is required for truthful choices under the given society. Labels permit different integral assignments within one type without making class or identity reportable.
Let \(W\) be aggregate truthful welfare and \(\mathrm{OPT}\) the supremum of aggregate welfare over all feasible assignments of integral bundles, allowing type masses to split and imposing no incentive constraints. The rational input \(R\geq2\) bounds the ratio of any two edge lengths among all candidate rectangles.
Does an algorithm running in time polynomial in \(m,\tau,Q,K,B,L\), where \(L\) is the total binary input length, always compute such a mechanism with \(W\geq\mathrm{OPT}/(c\log R)\) for some universal constant \(c>0\), or is this approximation guarantee unattainable in polynomial time?
For finite societies with explicitly listed OR-linear templates, a polynomial-time dominant-strategy truthful mechanism achieves an \(O(\log R)\) welfare approximation ([Blumrosen](https://blumrosen.weebly.com/uploads/4/7/4/7/47472385/max_aaai.pdf)).
No result settling this precise nonatomic society, spatial-supply, integral-bundle menu problem was located in the literature search.
The approximation guarantee is attainable. I prove that an algorithm running in time polynomial in the stated input parameters computes a mechanism satisfying
$$
W\geq \frac{\mathrm{OPT}}{6\log_2 R}.
$$
Thus, if $\log$ denotes the natural logarithm, one may take $c=6/\ln 2$.
The key additional observation is that an optimal fractional packing solution certifies the actual OR-linear coefficients of the bundles produced by geometric rounding. This closes the computational gap identified in the notes.
For class $q$, let $J_q$ index its template entries, and define
$$
\beta_q(T)=
\max\left\{
\sum_{j\in I}\alpha_{qj}:
I\subseteq J_q,\
S_{qj}\subseteq T\text{ for every }j\in I,\
(S_{qj})_{j\in I}\text{ are pairwise disjoint}
\right\}.
$$
The empty index set is allowed. The template is finite, so this maximum exists, and
$$
v_q(\theta,T)=\theta\beta_q(T).
$$
Overlay all horizontal and vertical boundary coordinates of the candidate rectangles and the given supply partition. Include singleton coordinate sets as well as the intervening open intervals. Their Cartesian products give two-dimensional, one-dimensional, and zero-dimensional atoms.
Retain the atoms lying in the union of the candidate rectangles. On every retained atom, membership in every candidate rectangle and the value of supply are constant, using the input’s conventions on partition boundaries. Consequently, constraints at one representative point per atom are equivalent to constraints at every point. Including the lower-dimensional atoms handles the pointwise requirement.
Let these atoms be indexed by $a\in A$, with rational representative points $x_a$ and supply values $s_a$. Write $H=|A|$. There are polynomially many atoms: if the two coordinate lists have sizes $N_x,N_y$, the number is at most
$$
(2N_x+1)(2N_y+1).
$$
The explicit input bounds both coordinate-list sizes polynomially.
For a template entry, define
$$
\chi_{aj}^q=
\begin{cases}
1,&x_a\in S_{qj},\\
0,&x_a\notin S_{qj}.
\end{cases}
$$
Write $t=(q_t,\theta_t)$ for a supported type, and $\mu_t$ for its mass. Initially assign the empty bundle to every type with $\theta_t=0$. Such types contribute no welfare.
For each supported type with $\theta_t>0$ and each $j\in J_{q_t}$, introduce a variable $f_{tj}\geq0$. Consider the explicit rational linear program
$$
\begin{aligned}
\text{maximize}\quad&
\sum_{t:\,\theta_t>0}\theta_t
\sum_{j\in J_{q_t}}\alpha_{q_tj}f_{tj},\\
\text{subject to}\quad&
\sum_{j\in J_{q_t}}\chi_{aj}^{q_t}f_{tj}\leq\mu_t
&&\text{for every }t\text{ with }\theta_t>0,\ a\in A,\\
&
\sum_{t:\,\theta_t>0}
\sum_{j\in J_{q_t}}\chi_{aj}^{q_t}f_{tj}\leq s_a
&&\text{for every }a\in A,\\
&f_{tj}\geq0.
\end{aligned}
$$
The first family limits the fractional packing load of one type at each point. The second imposes spatial supply.
There are at most $\tau K$ variables and $(\tau+1)H$ constraints. The zero vector is feasible. Every candidate rectangle contains a retained atom, so the first family implies
$$
f_{tj}\leq\mu_t.
$$
Thus the feasible region is bounded. Standard polynomial-time rational linear programming therefore computes an exact rational optimum of polynomial binary length. Fix such an optimum $f$, and let its objective value be $F$.
Consider any feasible assignment of integral bundles. There are finitely many possible bundles, since each is a union of a subset of the $m$ candidates. Let $z_{t,T}$ be the mass of type $t$ receiving bundle $T$.
For every class–bundle pair, choose a template packing $I_{q,T}$ attaining $\beta_q(T)$. Set
$$
f_{tj}^{\,\mathrm{assign}}
=
\sum_T z_{t,T}\,
\mathbf 1\{j\in I_{q_t,T}\}
$$
for positive-value types.
At any point, the certifying rectangles for one bundle are disjoint and contained in that bundle. Their total indicator is therefore at most the bundle’s indicator. It follows that these marginals satisfy both families of LP constraints. Their objective is exactly the assignment’s welfare, since zero-value types contribute zero.
Hence
$$
F\geq\mathrm{OPT}.
$$
This argument applies to every feasible assignment and therefore also to the supremum defining $\mathrm{OPT}$.
If $F=0$, then $\mathrm{OPT}=0$, and offering only the empty bundle at price zero solves the problem. The remaining proof treats $F>0$.
This is the implementation bridge.
Lemma. Fix a type $t$ with $\theta_t>0$. Suppose $I\subseteq J_{q_t}$ is a pairwise disjoint set of template entries and
$$
f_{tj}>0\qquad\text{for every }j\in I.
$$
For
$$
T=\bigcup_{j\in I}S_{q_tj},
$$
one has
$$
\beta_{q_t}(T)=\sum_{j\in I}\alpha_{q_tj}.
$$
Proof. If $I$ is empty, then $T$ is empty and its coefficient is zero, because every candidate rectangle has positive edge lengths.
Otherwise, the packing $I$ certifies
$$
\beta_{q_t}(T)\geq\sum_{j\in I}\alpha_{q_tj}.
$$
Suppose the inequality were strict. Choose a disjoint template packing $J$ contained in $T$ with
$$
\sum_{j\in J}\alpha_{q_tj}>
\sum_{j\in I}\alpha_{q_tj}.
$$
Set
$$
\delta=\min_{j\in I}f_{tj}>0
$$
and modify only type $t$’s variables:
$$
f'_{tj}
=
f_{tj}
+\delta\bigl(\mathbf 1\{j\in J\}-\mathbf 1\{j\in I\}\bigr).
$$
All modified variables remain nonnegative.
At any point $x$, the change in type $t$’s packing load is
$$
\delta\left(
\sum_{j\in J}\mathbf 1\{x\in S_{q_tj}\}
-
\sum_{j\in I}\mathbf 1\{x\in S_{q_tj}\}
\right).
$$
Because both packings are disjoint, the second sum is $\mathbf 1\{x\in T\}$, and the first is at most $\mathbf 1\{x\in T\}$. Thus every local and global spatial load weakly decreases. The modified vector is feasible.
Its objective increases by
$$
\delta\theta_t
\left(
\sum_{j\in J}\alpha_{q_tj}
-
\sum_{j\in I}\alpha_{q_tj}
\right)>0,
$$
contradicting optimality of $f$. This proves the lemma. $\square$
In particular, whenever rounding selects disjoint rectangles from the positive support of $f$ for one type, their weight sum is the actual coefficient of their union. No separate OR-linear valuation optimization is needed.
Let $h_{\min}$ and $h_{\max}$ be the minimum and maximum candidate heights. Partition candidates into height classes
$$
[2^k h_{\min},\,2^{k+1}h_{\min}),
$$
using
$$
d=1+\left\lfloor\log_2(h_{\max}/h_{\min})\right\rfloor
\leq1+\lfloor\log_2R\rfloor
$$
classes.
Within a height class $[h,2h)$, a rectangle with bottom coordinate $y$ has row
$$
r=\lceil y/h\rceil
$$
and color given by the residue of $r$ modulo $3$.
For a row-$r$ rectangle,
$$
(r-1)h<y\leq rh.
$$
Its height is at least $h$, so it contains the horizontal line at height $rh$. Consequently, two rectangles in the same row are disjoint exactly when their horizontal intervals are disjoint.
Its top coordinate is strictly below $(r+2)h$. A row-$(r+3)$ rectangle has bottom coordinate strictly above $(r+2)h$. Therefore rectangles in different rows of the same color are disjoint.
The height classes and colors partition all template entries into $3d$ groups. For a group $G$, define
$$
F_G=
\sum_{t:\,\theta_t>0}\theta_t
\sum_{\substack{j\in J_{q_t}\\S_{q_tj}\in G}}
\alpha_{q_tj}f_{tj}.
$$
Since all summands are nonnegative and the groups partition the entries,
$$
\sum_G F_G=F.
$$
Choose a group maximizing this quantity. Then
$$
F_G\geq\frac{F}{3d}\geq\frac{\mathrm{OPT}}{3d}.
$$
Fix a positive-value type $t$ and an occupied row of the chosen group. Retain its template entries with $f_{tj}>0$. Sort their distinct horizontal endpoints:
$$
x_0<x_1<\cdots<x_n.
$$
Construct a directed acyclic graph with:
Give template arc $j$ flow $f_{tj}$. Give skip arc $k$ flow
$$
g_k=\mu_t-
\sum_{\substack{j:\,
\text{the horizontal interval of }S_{q_tj}\\
\text{contains }(x_k,x_{k+1})}}
f_{tj}.
$$
This is nonnegative. Indeed, at any horizontal position in that open interval, all rectangles in this sum contain the point on the row’s common horizontal line. The local LP constraint bounds their total flow by $\mu_t$.
These arc flows constitute a source-to-sink flow of value $\mu_t$. One way to verify conservation is to start with flow $\mu_t$ along the skip chain. For each template entry, replace flow $f_{tj}$ along the corresponding segment of that chain by flow $f_{tj}$ on its template arc. This preserves conservation and gives exactly the displayed skip flows.
Decompose the flow into weighted source-to-sink paths. Repeatedly subtract the minimum positive arc flow along a positive-flow path. Each subtraction eliminates at least one positive arc, so the decomposition uses at most the number of graph arcs.
Each path selects horizontally disjoint template rectangles and hence a disjoint packing in its row. Realize its path distribution on rational intervals of the label space, with an interval of length equal to the path’s flow divided by $\mu_t$.
Do this for every occupied row of the chosen group and take the common refinement of the row label partitions. At each label, unite the selected row packings. Different rows of this color are disjoint, so the resulting bundle is integral.
The common refinement has at most the sum of the row partition sizes. Thus it yields only polynomially many bundles and rational type–bundle masses.
Each retained template entry has assigned mass exactly $f_{tj}$. At every label the selected rectangles are disjoint. Therefore the total load at atom $a$ is
$$
\sum_{t:\,\theta_t>0}
\sum_{\substack{j\in J_{q_t}\\S_{q_tj}\in G}}
\chi_{aj}^{q_t}f_{tj}
\leq s_a.
$$
All zero-value types initially receive the empty bundle. The assignment is consequently feasible at every point.
Every nonempty output bundle is a disjoint union of entries in the positive LP support of its generating type. The lemma proves that its actual class coefficient equals the sum of its selected template weights. Accordingly, its coefficient is known exactly, and the assignment’s welfare is
$$
W_0=F_G\geq\frac{\mathrm{OPT}}{3d}.
$$
This is a rational assignment with polynomial description size and known actual bundle coefficients. It remains to implement it using menus indexed only by public class and label.
I give the implementation argument in full, including equal coefficients and label endpoints.
Fix a class $q$ with positive total supported mass
$$
M=\sum_{t:\,q_t=q}\mu_t.
$$
List its distinct supported values in increasing order:
$$
\theta_1<\cdots<\theta_n,
\qquad
\pi_i=\mu_{q,\theta_i}/M.
$$
Let $\lambda_T$ be the aggregate class mass assigned bundle $T$ by the rounded assignment, omitting bundles with zero aggregate mass. Define
$$
\gamma_T=\lambda_T/M.
$$
Both $(\pi_i)_i$ and $(\gamma_T)_T$ sum to one. Every coefficient $b_T=\beta_q(T)$ is already known.
Group bundles with equal coefficient and set
$$
\gamma_b=\sum_{T:\,b_T=b}\gamma_T.
$$
Define a nondecreasing step function $g$ on $[0,1)$ that lists the distinct coefficients in increasing order, giving coefficient $b$ an interval of length $\gamma_b$. Use half-open intervals.
Put
$$
a_0=0,\qquad a_i=\sum_{k=1}^i\pi_k.
$$
For $u\in[0,1)$, prescribe type $i$’s coefficient as
$$
b_i(u)=g(a_{i-1}+\pi_i u).
$$
For $i<j$,
$$
a_{i-1}+\pi_i u\leq a_i\leq a_{j-1}
\leq a_{j-1}+\pi_j u.
$$
Thus
$$
b_i(u)\leq b_j(u).
$$
This prescription preserves the aggregate coefficient distribution. Indeed,
$$
\begin{aligned}
\sum_i\pi_i\int_0^1\mathbf 1\{b_i(u)=b\}\,du
&=
\sum_i\int_{a_{i-1}}^{a_i}\mathbf 1\{g(r)=b\}\,dr\\
&=\gamma_b.
\end{aligned}
$$
It also weakly increases class welfare. Here is a direct rearrangement proof. For nonnegative, finitely supported random variables $X,Y$,
$$
\mathbb E[XY]
=
\int_0^\infty\int_0^\infty
\Pr(X>x,\ Y>y)\,dx\,dy.
$$
This follows by averaging the identity
$$
XY=\int_0^\infty\int_0^\infty
\mathbf 1\{X>x,\ Y>y\}\,dx\,dy;
$$
the average is a finite sum.
For any coupling with fixed marginals,
$$
\Pr(X>x,\ Y>y)
\leq
\min\{\Pr(X>x),\Pr(Y>y)\}.
$$
When both variables are nondecreasing functions of one uniform quantile, their upper-tail sets are upper intervals, and their intersection has exactly this minimum measure.
The prescribed joint distribution of supported value and coefficient is such a quantile coupling: conditional on type $i$, the variable
$$
r=a_{i-1}+\pi_i u
$$
is uniform on $[a_{i-1},a_i)$; mixing these intervals with probabilities $\pi_i$ makes $r$ uniform on $[0,1)$. Hence the prescription maximizes welfare among couplings with these marginals, and in particular weakly improves the original assignment.
Equal coefficients must select the same bundle at a fixed label whenever they arise at different supported values.
For each coefficient $b$, define
$$
w_b(u)=\sum_i\pi_i\,\mathbf 1\{b_i(u)=b\}.
$$
This is a rational step function, and
$$
\int_0^1w_b(u)\,du=\gamma_b.
$$
List the bundles with this coefficient as $T_1,\ldots,T_e$. Choose cuts
$$
0=c_0\leq c_1\leq\cdots\leq c_e=1
$$
such that
$$
\int_{c_{\ell-1}}^{c_\ell}w_b(u)\,du=\gamma_{T_\ell}.
$$
These cuts exist because the cumulative integral is continuous, nondecreasing, and has total value $\gamma_b$. They can be chosen rational: its breakpoints, slopes, and requested cumulative values are rational, so each cut is either a rational breakpoint or the solution of an affine equation with rational coefficients and positive slope.
Whenever $b_i(u)=b$, assign bundle $T_\ell$ according to the half-open cut interval containing $u$. This preserves each bundle’s normalized aggregate mass, because
$$
\sum_i\pi_i\int_0^1
\mathbf 1\{\text{type }i\text{ receives }T_\ell\}\,du
=
\int_{c_{\ell-1}}^{c_\ell}w_b(u)\,du
=
\gamma_{T_\ell}.
$$
At a fixed label, all supported values with coefficient $b$ now receive the same bundle.
Take the common refinement of all these cuts and the breakpoints of the functions $b_i$. If $D$ bundles have positive class mass, there are at most $O(nD+D)$ resulting intervals. On each interval, every supported value has a fixed prescribed bundle.
Use intervals closed on the left and open on the right, except that the final interval is also closed at $1$. At $u=1$, use the menu of that final interval. This defines the mechanism for every label; endpoint choices have zero mass and do not affect the preceding distribution calculations.
Fix one resulting label interval. The prescribed coefficients are nondecreasing with supported value. Compress consecutive equal-coefficient blocks. By the previous construction, each block uses one bundle. Write these bundles and coefficients as
$$
T_0,\ldots,T_\ell,
\qquad
b_0<\cdots<b_\ell.
$$
For each transition $r$, choose the threshold $h_r$ as the midpoint between the last supported value assigned $T_{r-1}$ and the first supported value assigned $T_r$. These thresholds are rational and strictly between their respective blocks.
Set
$$
p_0=-1,\qquad
p_r=p_{r-1}+h_r(b_r-b_{r-1}).
$$
Offer these bundle–price pairs. If the empty bundle is not already offered, add it at price zero.
For a supported value $\theta$ assigned $T_r$, comparison with a higher-index bundle $T_k$ gives
$$
(\theta b_r-p_r)-(\theta b_k-p_k)
=
\sum_{v=r+1}^{k}(h_v-\theta)(b_v-b_{v-1})>0.
$$
Every later threshold exceeds $\theta$, and every coefficient difference is positive. For a lower-index bundle $T_k$,
$$
(\theta b_r-p_r)-(\theta b_k-p_k)
=
\sum_{v=k+1}^{r}(\theta-h_v)(b_v-b_{v-1})>0.
$$
Every earlier threshold is below $\theta$.
Thus the prescribed entry is the unique maximizer among these entries. Its utility is at least that of the first entry, namely
$$
\theta b_0+1\geq1.
$$
An additional empty option at price zero therefore does not interfere. Signed prices are permitted by the task.
For every value, including unsupported values, the direct mechanism chooses a utility-maximizing entry from this fixed accessible menu. A misreport can only select another entry from the same menu and therefore cannot improve utility at the true value. Fix any menu-entry order independent of reports for ties. Truthful reporting is dominant-strategy optimal for every value and label.
For every public class with zero supported mass, offer only the empty bundle at price zero on the entire label interval.
The construction preserves the aggregate mass assigned every bundle within each class. Consequently, it preserves the load at every spatial point exactly.
Sorting the coefficients weakly increases welfare, and selecting among equal-coefficient bundles leaves welfare unchanged. Therefore the resulting truthful mechanism is feasible and satisfies
$$
W\geq W_0.
$$
All parts of the construction have polynomial size.
The rational encodings also remain polynomially bounded. The optimal LP coordinates have polynomial binary length. Taking a common denominator for these coordinates and the type masses requires only polynomially many bits. Skip flows and path-decomposition weights are obtained by sums, differences, and minima, so their denominators divide this common denominator.
Normalized path probabilities, class masses, and bundle masses are ratios of polynomial-bit rationals. Quantile breakpoints are ratios of differences of such quantities. The functions $w_b$ have slopes given by sums of normalized type masses; their cumulative integrals are sums of polynomially many products of polynomial-bit rationals. Each bundle cut solves one affine equation using these already computed quantities. Finally, prices are sums of products of rational thresholds and coefficient differences.
At each of these finitely many stages, a product of the polynomially many relevant denominators has polynomial binary length. Hence all interval endpoints and prices have polynomial binary length, and the entire mechanism can be computed and written in polynomial time.
Combining the rounding and implementation bounds gives
$$
W\geq W_0\geq\frac{\mathrm{OPT}}{3d}.
$$
Since $R\geq2$,
$$
d\leq1+\lfloor\log_2R\rfloor
\leq2\log_2R.
$$
Therefore
$$
W\geq\frac{\mathrm{OPT}}{6\log_2R}.
$$
The mechanism has integral bundles, finitely many rational label intervals and menu entries, signed rational prices, report-independent tie-breaking, pointwise supply feasibility under the given society, and dominant-strategy truthfulness for every value and label. This resolves the requested polynomial-time approximation question.
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the stated problem. The LP upper bound, exact-value lemma, geometric rounding, and menu implementation are sound. I found no major or minor gaps requiring repair.
The atom construction correctly reduces pointwise feasibility to finitely many constraints.
On each atom, every candidate rectangle has constant membership. Supply is also constant because the coordinate overlay includes the boundaries of the given supply partition. Including singleton coordinates ensures that points on rectangle or supply boundaries are checked, rather than merely checking almost everywhere.
The atom count
$$
H\leq(2N_x+1)(2N_y+1)
$$
is valid. The coordinate lists, representative points, membership indicators, and supply values have polynomial description size under the explicitly given rational partition representation.
Assessment: Correct, including the pointwise boundary requirement.
The LP is feasible because its zero vector satisfies all constraints. For every variable, its template rectangle contains a retained atom, whose local constraint gives
$$
0\leq f_{tj}\leq\mu_t.
$$
Consequently, the feasible region is bounded.
The invoked rational linear-programming result applies: an explicitly represented rational LP with a nonempty bounded feasible region admits an exact rational optimum of polynomial binary length, computable in polynomial time. The number and encoding size of the LP’s variables and constraints are polynomial here.
For the welfare upper bound, each bundle has a maximizing template packing because its template is finite. At every point, the selected packing’s total indicator is at most the bundle’s indicator. Integrating these indicators against assigned masses therefore gives both:
The constructed LP objective equals the assignment’s welfare. Discarding zero-value types does not change that objective and can only reduce spatial load. Thus
$$
F\geq\mathrm{OPT}
$$
holds for every feasible assignment and hence for the supremum.
The branch $F=0$ is also correct: welfare is nonnegative, so the upper bound implies $\mathrm{OPT}=0$.
Assessment: Correct.
This is the central computational step, and its proof is valid.
For a disjoint set $I$ drawn from the positive support, subtracting
$$
\delta=\min_{j\in I}f_{tj}
$$
from its entries preserves nonnegativity. Entries belonging to both $I$ and the proposed replacement packing $J$ have no net change.
Since $I$ is disjoint and its union is $T$,
$$
\sum_{j\in I}\mathbf 1\{x\in S_{q_tj}\}
=\mathbf 1\{x\in T\}.
$$
Since $J$ is disjoint and contained in $T$,
$$
\sum_{j\in J}\mathbf 1\{x\in S_{q_tj}\}
\leq\mathbf 1\{x\in T\}.
$$
Every local and global load therefore weakly decreases. A strictly larger replacement weight would strictly increase the objective because $\delta>0$ and $\theta_t>0$, contradicting optimality.
The empty-set case is correctly handled: a positive-edge-length rectangle cannot be contained in the empty bundle.
The lemma establishes the actual OR-linear coefficient of every subsequently generated bundle. It does not require an algorithm to find the hypothetical improving packing; that packing is used only in the contradiction argument.
Assessment: Correct. The claimed computational bridge is established.
For a rectangle in row $r$,
$$
(r-1)h<y\leq rh.
$$
Its height is at least $h$, so its top is strictly above $rh$. Thus the line at height $rh$ belongs to the rectangle even under the half-open convention.
Rectangles in the same row therefore intersect precisely when their horizontal intervals intersect. Horizontal intervals touching only at an endpoint remain disjoint.
The top of a row-$r$ rectangle is strictly below $(r+2)h$, whereas the bottom of a row-$(r+3)$ rectangle is strictly above $(r+2)h$. This proves disjointness between different rows of one color, including rows farther apart.
The height classes and colors partition the entries into $3d$ groups. Nonnegative objective contributions then imply
$$
F_G\geq\frac{F}{3d}.
$$
For each consecutive endpoint gap, all retained rectangles spanning that gap contain its points on the common row line. The local LP constraint therefore proves that the displayed skip flow is nonnegative.
The chain-replacement explanation correctly verifies conservation and source-to-sink flow value $\mu_t$. The graph is acyclic because every arc moves strictly rightward. Decomposition into positive-flow paths terminates after at most the number of arcs, since each subtraction eliminates a positive arc.
Each path selects horizontally disjoint rectangles. Its normalized weight gives a rational label interval, and the path decomposition realizes each template marginal exactly.
Refining the row partitions adds their breakpoints; it does not multiply the numbers of intervals. Combining the resulting row selections produces integral bundles because different rows of the chosen color are disjoint.
Exact realization of the retained marginals gives the asserted spatial load. At each label, disjointness makes the sum of selected rectangle indicators equal to the indicator of their union.
The exact-value lemma applies to every generated packing. Consequently,
$$
W_0=F_G\geq\frac{\mathrm{OPT}}{3d}.
$$
Assessment: Correct.
The functions $b_i(u)$ are nondecreasing in supported value at each fixed label. Their arguments occupy consecutively ordered quantile intervals, so the displayed monotonicity inequalities are valid.
The change of variables in the distribution calculation correctly preserves aggregate coefficient masses.
The rearrangement argument also applies as written. Values and coefficients are nonnegative and finitely supported, so the tail-integral identity is valid. The constructed joint distribution is a common-quantile coupling, which attains the stated upper bound on every joint upper-tail probability. Thus sorting weakly increases welfare.
The weighted function $w_b$ correctly measures the aggregate normalized type mass receiving coefficient $b$ at each label.
Its cumulative integral is continuous, nondecreasing, piecewise affine, and rational at its breakpoints. The requested cuts therefore exist and can be chosen rational. They preserve each individual bundle’s aggregate mass and ensure that all supported values with the same coefficient at a fixed label receive the same bundle.
This last property is essential for menu implementation and is explicitly established.
The common refinement has polynomially many intervals. The convention at $u=1$ gives a menu to every label without changing any aggregate mass.
After compressing equal-coefficient blocks, the coefficients strictly increase. Each threshold lies strictly between the adjacent supported-value blocks.
Both displayed utility-difference formulas are correct. For a supported value assigned block $r$, every summand in the relevant comparison is strictly positive. Hence its prescribed entry is the unique maximizer among the prescribed entries.
The first entry gives utility
$$
\theta b_0+1\geq1.
$$
Thus adding the empty bundle at price zero cannot alter supported choices. If the empty bundle is already offered, its assigned signed price is permitted by the task.
For every unsupported value as well, truthful selection maximizes true utility over the fixed accessible menu. A misreport only changes which entry of that same menu is selected. This proves dominant-strategy truthfulness for every value and label.
Preserving each bundle’s aggregate mass within each class preserves its contribution to load at every point. Supply feasibility therefore survives the implementation exactly, while welfare weakly increases.
Assessment: Correct. The mechanism uses only public class and label to determine menu access.
The claimed size bounds are consistent with the construction.
The atom set and LP are polynomially sized. Height classes have polynomial count, and possibly large row indices still have polynomial binary length because they arise from rational input coordinates and heights.
The flow decompositions and partition refinements produce polynomially many bundle records. Their coefficients are computed from the selected template weights using the proved lemma.
For each class, the coefficient breakpoints and equal-coefficient cuts yield the stated polynomial bound on label intervals, with polynomially many entries per menu.
The encoding argument is also sufficient. LP coordinates have polynomial bit length; flow operations use sums, differences, and minima; subsequent normalizations, cuts, and prices use polynomially many rational operations in the specified stages. The common-denominator reasoning bounds their bit lengths polynomially.
Empty templates and classes without supported mass are covered by the existing empty-bundle branches. If height extrema are needed, the branch $F>0$ already guarantees that candidate rectangles exist.
Assessment: Correct.
The final bound follows from
$$
W\geq W_0\geq\frac{\mathrm{OPT}}{3d}
$$
and, for $R\geq2$,
$$
d\leq1+\lfloor\log_2R\rfloor\leq2\log_2R.
$$
Therefore
$$
W\geq\frac{\mathrm{OPT}}{6\log_2R}
=\frac{\mathrm{OPT}}{(6/\ln2)\ln R}.
$$
The stated natural-logarithm constant is correct.
The output establishes a polynomial-time algorithm satisfying the requested approximation guarantee and all specified mechanism requirements. No additional clarification is needed to make the argument verifiable.
⟨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.