\in L}$, where $I_0 = [0, \frac{\epsilon B}{4K})$ and $I_\ell = [\frac{\epsilon B}{4K} (1 + \frac{\epsilon}{4})^{\ell - 1}, \frac{\epsilon B}{4K} (1 + \frac{\epsilon}{4})^\ell)$ for $\ell > 0$ and $L = \{0, \ldots, \lceil \log_{1 + \epsilon/4} \frac{8K}{\epsilon} \rceil\}$ (note that since $B \geq m$, we have $B + m \leq 2B$). Define $\mathcal{B}_{i,j}^\ell$ as the set of partial classifications $y \in \mathcal{X}|_{C_j}$ whose budget occupation $a_i(y)$ lies in the interval $I_\ell$. For ${v}\in L^K$ define the family of classifications $\mathcal{B}_i^{{v}} = \{(y^1, y^2, \ldots, y^K) : y^j \in \mathcal{B}_{i,j}^{{v}_j}\}$. The $\mathcal{B}_i^{{v}}$’s then provide the desired grouping of the classifications. Note that the $\mathcal{B}_i^{{v}}$’s may include classifications not in $\mathcal{X}$ and may not include classifications in $\mathcal{X}$ which have occupation $a_i(.)$ greater than $B + m$.

Now consider a non-empty $\mathcal{B}_i^{{v}}$. Let $\underline{w}_i^{{v}}$ be the inclusion-wise smallest element in $\mathcal{B}_i^{{v}}$. Notice that such unique smallest element exists: since $\mathcal{X}|_{C_j}$ is a chain, so is $\mathcal{B}_{i,j}^{{v}_j}$, and hence $\underline{w}_i^{{v}}$ is the product (over $j$) of the smallest elements in the sets $\{\mathcal{B}_{i,j}^{{v}_j}\}_j$. Similarly, let $\overline{w}_i^{{v}}$ denote the largest element in $\mathcal{B}_i^{{v}}$. Intuitively, $\underline{w}^{{v}}_i$ and $\overline{w}^{{v}}_i$ will serve as witnesses for all the sets in $\mathcal{B}_i^{{v}}$.

Finally, define the witness sets by adding 