Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

Let $r$ be the smallest power of two that is at least $4c^2+1$. Let $H\in {\{-1,+1\}}^{r\times r}$ be an Hadamard matrix of order $r$, i.e., a $\{-1,+1\}$-matrix whose row vectors are mutually orthogonal. Note that such a matrix can be constructed. Let $J$ denote the all-$1$ matrix of order $r$ and define $H^{\ast }=(H+J)/2$. It is known that for any $u\in {\{-1,+1\}}^r$, we have ${\Vert H^{\ast }u\Vert }_{\mathrm{\infty }}\ge \sqrt{r}/2$ (see, e.g., [1, Section 13.4]).

Consider the instance defined by $N=\{1,2\}$, $M=\{g_1,g_2,\mathrm{\dots },g_r\}$, and $L=[r]$. For every agent $i\in N$, item $g_j\in M$, and dimension $k\in L$, define $v_{ijk}=H_{jk}^{\ast }$. This instance is both binary and identical. Note that the number of dimensions $r$ is at most $2(4c^2+1)=O(c^2)$.

For an allocation $𝐀=(A_1,A_2)$, consider the column vector $u\in {\{-1,+1\}}^r$ defined by $u_j=+1$ if $g_j\in A_1$ and $u_j=-1$ if $g_j\in A_2$. Then, we have ${\max }_{k\in L}|v_1{(A_1)}_k-v_1{(A_2)}_k|={\Vert H^{\ast }u\Vert }_{\mathrm{\infty }}\ge \sqrt{r}/2>c$. This means that we need to remove at least $c+1$ items to eliminate envy. This completes the proof. $◀$

This theorem has a direct consequence for the strong variant. Because any strong sEF$c$ allocation must also satisfy weak sEF$c$, the impossibility of achieving weak sEF$c$ under certain conditions immediately implies that strong sEF$c$ allocations cannot exist under the same conditions. We further strengthen this conclusion by demonstrating that even when the number of dimensions $\mathrm{\ell }$ is exactly $2c+1$, a strong sEF$c$ allocation may fail to exist. Thus, requiring $\mathrm{\ell }\le 2c$, or equivalently $c\ge \lceil \mathrm{\ell }/2\rceil$, is necessary to guarantee the existence of a strong sEF$c$ allocation.

Consider the instance with $N=\{1,2\}$, $M=\{g_1,g_2,\mathrm{\dots },g_{2c+1}\}$, and $L=[2c+1]$. For every agent $i\in N$, item $g_j\in M$, and dimension $k\in L$, define $v_{ijk}$ to be $1$ if $j=k$ and $0$ otherwise. This instance is both binary and identical.

Now, suppose toward a contradiction that there exists a strong sEF$c$ allocation $𝐀=(A_1,A_2)$. Without loss of generality, assume that $|A_1|\le |A_2|$. Since $|A_1|+|A_2|=|M|=2c+1$, it follows that $|A_1|\le c$ and $|A_2|\ge c+1$.

Consider agent $1$’s evaluation of agent $2$’s bundle. By the definition of $v_{ijk}$, only item $g_{j^{\ast }}\in A_2$ contributes a value of 1 in dimension $j^{\ast }$. To eliminate envy in dimension $j^{\ast }$, the item $g_{j^{\ast }}$ must be removed from $A_2$. Therefore, in order to eliminate envy in all dimensions, every item in $A_2$ must be removed. However, since $|A_2|\ge c+1$, at least $c+1$ items must be removed, exceeding the allowable limit of $c$.

This contradiction shows that no strong sEF$c$ allocation exists for this instance. $◀$

Let $(N,M,L,{(v_i)}_{i\in N})$ be a given instance of the MDFA problem. We assume that $N=\{1,2\}$, $M=\{g_1,\mathrm{\dots },g_m\}$, and $L=[\mathrm{\ell }]$. Consider the following linear program:

A solution $x$ with a nonnegative objective yields a simultaneously envy-free fractional allocation, where $x_j$ is interpreted as the fraction of item $g_j$ allocated to agent 1. Note that, since $x=(1/2,1/2,\mathrm{\dots },1/2)$ is a feasible solution, the optimal objective value is nonnegative.

Since the LP has $m$ variables, any basic solution is determined by $m$ linearly independent tight constraints. In particular, at least $m-(2\mathrm{\ell }-1)$ of these tight constraints must be of the form $x_j=0$ or $x_j=1$ (i.e., constraints in (3)). This implies that every basic solution has at least $m-2\mathrm{\ell }+1$ coordinates that are integral (i.e., equal to $0$ or $1$). Equivalently, there can be at most $2\mathrm{\ell }-1$ fractional coordinates.

We now construct an allocation from a basic optimal solution $x^{\ast }$. Note that a basic optimal solution must exist since the feasible region is nonempty and bounded. Define

Then, since all fractional coordinates of $x^{\ast }$ lie in $F_1\cup F_2$, we have $|F_1|+|F_2|\le 2\mathrm{\ell }-1$.

Define the allocation $𝐀=(A_1,A_2)$ by $A_1=I_1\cup F_1$ and $A_2=I_2\cup F_2$. Since $x^{\ast }$ satisfies (1) and the objective value is nonnegative, for every dimension $k\in [\mathrm{\ell }]$ we have

where the second inequality holds since, for the optimal solution $x^{\ast }$, the objective value of LP is nonnegative and inequalities in (1) are satisfied. Similarly, by (2), for every dimension $k\in [\mathrm{\ell }]$ we have

Thus, any envy can be eliminated by removing all the fractional items from the bundle of the other agent. Hence, the allocation is strong sEF$(2\mathrm{\ell }-1)$. Since $c\ge 2\mathrm{\ell }-1$, the allocation is strong sEF$c$ as well.

Finally, since the LP has polynomial number of constraints and variables, a basic optimal solution can be computed in polynomial time via standard linear programming techniques (see, e.g., a textbook [8]). Hence, the resulting allocation $𝐀$ can be found in polynomial time. $◀$

If the valuations of the two agents are identical, we can reduce the requirement of $2\mathrm{\ell }-1$ to $\mathrm{\ell }$. Due to space constraints, the proof is deferred to the Appendix.

When the number of agents is three or more, a direct application of the polytope-based approach presented in Theorem 7 and Theorem 8 fails. Indeed, consider the case with three agents in one dimension, where the valuations are given by

In this case, allocating half of item $g_1$ to agents $1$ and $2$, while assigning all the remaining items to agent $3$ yields an envy-free fractional allocation. A reasonable rounding method in this situation is to assign item $g_1$ to either agent $1$ or $2$. However, the agent who does not receive $g_1$ will envy agent $3$, and this envy cannot be eliminated by removing $m-2$ items.

To overcome this difficulty, we pre-assign certain items before employing the polytope-based approach. This strategy allows us to derive an upper bound on $c$ that guarantees the existence of a strong sEF$c$ allocation independent of the total number of items $m$.

Let $(N,M,L,{(v_i)}_{i\in N})$ be a given instance of the MDFA problem. We assume that $N=[n]$, $M=\{g_1,\mathrm{\dots },g_m\}$, and $L=[\mathrm{\ell }]$. If $m\le n\cdot c$, then simply allocating at most $c$ items to each agent yields a strong EF$c$ allocation. Hence, in what follows, we assume that $m>n\cdot c(\ge n^3{\mathrm{\ell }}^2)$.

For each agent $i\in N$ and dimension $k\in L$, we begin by sequentially allocating the ${(n-1)}^2\mathrm{\ell }$ most desired items in dimension $k$ to agent $i$. Denote by $Z_{i,k}$ the set of items allocated to agent $i$ with respect to dimension $k$. This procedure is described in Algorithm 1. Intuitively, the set $Z_{i,k}$ is used to compensate for the loss of value in the $k$th dimension that occurs when rounding a fractional solution. Let $R≔M\setminus {\bigcup }_{i\in N}{\bigcup }_{k\in L}{Z}_{i,k}$ be the set of remaining items. Note that, for every $g_j\in Z_{i,k}$ and $g_{j^{\prime }}\in R$, we have $v_{ijk}\ge v_{i{j}^{\prime }k}$.

Consider the following polytope $P$ in ${ℝ}^{N\times R}$:

A feasible point $x\in P$ is a simultaneously proportional fractional allocation of $R$, where $x_{ig}$ is interpreted as the fraction of item $g$ allocated to agent $i$. Note that, since the uniform allocation $x={(1/n)}_{i\in N,g\in R}$ is feasible, the polytope $P$ is nonempty.

Let $m^{\prime }=|R|$. Since $P$ is in $m^{\prime }n$-dimensional space, any extreme point is determined by $m^{\prime }n$ linearly independent tight constraints. In particular, at least $m^{\prime }n-m^{\prime }-n(n-1)\mathrm{\ell }$ of these tight constraints must be zero. This implies that every extreme point has at most $m^{\prime }+n(n-1)\mathrm{\ell }$ nonzero coordinates. Consequently, at least $m^{\prime }-n(n-1)\mathrm{\ell }$ items are allocated integrally (i.e., for such an item $g\in R$, there exists some agent $i$ with $x_{ig}=1$).

Now, let $x^{\ast }$ be an extreme point of $P$, and for each agent $i\in N$, define $I_i≔\{g\in R:x_{ig}^{\ast }=1\}$. Let $F≔R\setminus {\bigcup }_{i\in N}{I}_i$ be the set of items that are not allocated integrally. By the above discussion, we have $|F|\le n(n-1)\mathrm{\ell }$. Partition $F$ arbitrary into $n$ subsets $(F_1,\mathrm{\dots },F_n)$ such that $|F_i|\le (n-1)\mathrm{\ell }$ for all $i\in N$. Then, define the allocation $𝐀=(A_1,\mathrm{\dots },A_n)$ by $A_i=\left({\bigcup }_{k\in L}{Z}_{i,k}\right)\cup I_i\cup F_i$ for each $i\in N$. We now show that $𝐀$ is a strong sEF$c$ allocation if $c\ge n^2{\mathrm{\ell }}^2$.

For every $i,i^{\prime }\in N$ and every $k\in L$, we have

where the last inequality follows from the facts that, for every $g_j\in Z_{i,k}$ and $g_{j^{\prime }}\in F\subseteq R$, $v_{ijk}\ge v_{i{j}^{\prime }k}$, and $|F\setminus F_i|\le {(n-1)}^2\mathrm{\ell }\le |Z_{i,k}|$. Therefore, we obtain that $𝐀$ is a strong sEF$c$ when $c=n^2{\mathrm{\ell }}^2$ since

for every $i^{\prime }\in N$.

Finally, since the polytope $P$ has polynomial number of constraints and variables, a basic optimal solution can be computed in polynomial time via standard linear programming techniques. Hence, the resulting allocation $𝐀$ can be found in polynomial time. $◀$

Next, we provide a dynamic programming algorithm that checks existence of a weak sEF$c$ allocation. The key idea is to process the items one by one, gradually building up partial allocations and summarizing their “state” in a way that keeps track of all the information necessary to verify the weak sEF$c$ condition later.

Let $(N,M,L,{(v_i)}_{i\in N})$ be an instance of the MDFA problem. We assume that $N=[n]$, $M=\{g_1,\mathrm{\dots },g_m\}$, $L=[\mathrm{\ell }]$, and that for each agent $i\in N$ and item $g\in M$. For each $j\in \{0,1,\mathrm{\dots },m\}$, let $M_j=\{g_1,g_2,\mathrm{\dots },g_j\}$ denote the prefix of items. Without loss of generality, we assume that $m>n\cdot c$ since otherwise simply allocating at most $c$ items to each agent yields a weak EF$c$ allocation.

For each $j\in \{0,1,\mathrm{\dots },m\}$ and for each allocation $𝐀$ of $M_j$, we summarize its state $(V,T)$ as follows:

• $\mathrm{■}$

  $V\in {\mathbb{Z}}^{N\times N\times L}$ represents the valuation profile. For every $i,i^{\prime }\in N$ and every $k\in L$, $V_{i,i^{\prime },k}=v_i{(A_{i^{\prime }})}_k\in [0,1,\mathrm{\dots },m\cdot v_{\max }]$.

• $\mathrm{■}$

  $T\in {\mathbb{Z}}^{N\times N\times L\times [c]}$ encodes the top $c$ item values. For every $i,i^{\prime }\in N$, every $k\in L$, and $s\in [c]$, let $T_{i,i^{\prime },k,s}$ denote the $s$th largest value in the multiset $\{v_i(g):g\in A_{i^{\prime }}\}$. If , the remaining entries in $T_{i,i^{\prime },k}$ are filled with $0$.

We now describe a dynamic programming algorithm that computes a table $\mathrm{DP}[j][V][T]$, which is a Boolean indicator that is set to true if there exists an allocation of the items in $M_j$ that achieves the state $(V,T)$, and false otherwise. Notice that the size of the DP table is at most

For $j=0$ (i.e., no items are allocated), the table $\mathrm{DP}[0][V][T]$ is true only when the valuations $V$ and the top $c$ item values $T$ are all zero. In other words, the DP table can be filled as follows:

For $j\ge 1$, assume that $\mathrm{DP}[j-1][V][T]=\text{true}$ for some state $(V,T)$ corresponding to an allocation of $M_{j-1}$. We then process item $g_j$. For each agent $i\in N$, consider allocating $g_j$ to $i$. For each such choice, we update the state as follows:

• $\mathrm{■}$

  Update $V$: For every $i^{\prime },i^{\prime \prime }\in N$ and every $k\in L$, define

  $V_{i^{\prime },i^{\prime \prime },k}^{\prime }$

  This corresponds to the valuation profile of the allocation where item $g_j$ is additionally assigned to agent $i$.

• $\mathrm{■}$

  Update $T$: For every $i^{\prime }\in N$ and every $k\in L$, define $T_{i^{\prime },i,k}^{\prime }$ by updating $T_{i^{\prime },i,k}$ by inserting the value $v_{i^{\prime }jk}$ into the multiset $\{T_{i^{\prime },i,k,1},T_{i^{\prime },i,k,2},\mathrm{\dots },T_{i^{\prime },i,k,c}\}$ and retaining only the $c$ highest entries. For every agent $i^{\prime \prime }\ne i$, $T_{i^{\prime },i^{\prime \prime },k}^{\prime }$ is defined to be $T_{i^{\prime },i^{\prime \prime },k}$.

Note that this update can be performed in $O(n^2\cdot \mathrm{\ell }\cdot c)$ time.

After performing these updates for every state $(V,T)$ with $\mathrm{DP}[j-1][V][T]=\text{true}$ and for every choice of agent $i\in N$ who receives $g_j$, we set the corresponding entry $\mathrm{DP}[j][V^{\prime }][T^{\prime }]$ to true. All other cells are set to false.

After processing all items, the table $\mathrm{DP}[m][\cdot ][\cdot ]$ represents possible states corresponding to full allocations of $M$. We then examine each state $(V,T)$ such that $\mathrm{DP}[m][V][T]=\text{true}$ to verify the weak sEF$c$ condition. Specifically, for every pair of distinct agents $i,i^{\prime }\in N$ and for every dimension $k\in L$, weak sEF$c$ requires that there exists a set $X\subseteq A_{i^{\prime }}$, with $|X|\le c$, such that $v_i{(A_i)}_k\ge v_i{(A_{i^{\prime }})}_k-{\sum }_{g\in X}{v}_i{(g)}_k$. Since the list $T_{i,i^{\prime },k}$ contains the $c$ highest values among the multiset $\{v_i{(g)}_k:g\in A_{i^{\prime }}\}$, it suffices to verify that $V_{iik}\ge V_{i{i}^{\prime }k}-{\sum }_{s=1}^c{T}_{i,i^{\prime },k,s}$ for every distinct $i,i^{\prime }\in N$ and every $k\in L$. This condition can be checked in $O(n^2\cdot \mathrm{\ell }\cdot c)$ time. A weak sEF$c$ allocation exists if and only if at least one state $(V,T)$ such that $\mathrm{DP}[m][V][T]=\text{true}$ satisfies this inequality. Finally, the overall running time is

since computing the DP table dominates the running time. This completes the proof. $◀$

Finally, we provide a dynamic programming algorithm that checks the existence of a strong sEF$c$ allocation. Unlike the approach for weak sEF$c$, we first enumerate all possible combinations of subsets used to eliminate envies.

Let $(N,M,L,{(v_i)}_{i\in N})$ be an instance of the MDFA problem. We assume that $N=[n]$, $M=\{g_1,\mathrm{\dots },g_m\}$, $L=[\mathrm{\ell }]$, and that for each agent $i\in N$ and item $g\in M$. Without loss of generality, we assume that $m>n\cdot c$ since otherwise simply allocating at most $c$ items to each agent yields a strong EF$c$ allocation.

We enumerate a collection ${(X_{i{i}^{\prime }})}_{i,i^{\prime }\in N}$ with $|X_{i{i}^{\prime }}|\le c$ for all $i,i^{\prime }\in N$. Each $X_{i{i}^{\prime }}$ represents the subset that is used to eliminate envy from agent $i$ towards agent $i^{\prime }$. We consider allocations $𝐀$ that satisfies $A_i\supseteq {\bigcup }_{i^{\prime }\in N}{X}_{i{i}^{\prime }}$ for all agent $i\in N$. To satisfy consistency, for distinct agents $i$ and $\iota$, the sets of items used for envy elimination must be disjoint, i.e., $\left({\bigcup }_{i^{\prime }\in N}{X}_{i{i}^{\prime }}\right)\cap \left({\bigcup }_{{\iota }^{\prime }\in N}{X}_{\iota {\iota }^{\prime }}\right)=\mathrm{\varnothing }$. Note that the number of possible choices for the collection ${(X_{i{i}^{\prime }})}_{i,i^{\prime }\in N}$ is at most ${\prod }_{i,i^{\prime }\in N}{(1+m)}^c=m^{O(c{n}^2)}$.

Fix some collection ${(X_{i{i}^{\prime }})}_{i,i^{\prime }\in N}$ satisfying $|X_{i{i}^{\prime }}|\le c$ for all $i,i^{\prime }\in N$ and $X_{i{i}^{\prime }}\cap X_{\iota {\iota }^{\prime }}=\mathrm{\varnothing }$ for all $i,i^{\prime },\iota ,{\iota }^{\prime }$ with $i\ne \iota$. Define $X_i={\bigcup }_{i^{\prime }\in N}{X}_{i{i}^{\prime }}$ for each $i\in N$ and $X={\bigcup }_{i\in N}{X}_i$. Let $M^{\prime }=M\setminus X$ be the set of remaining items. Write $M^{\prime }$ as $\{g_{\sigma (1)},\mathrm{\dots },g_{\sigma (m^{\prime })}\}$ and for each $j\in \{0,1,\mathrm{\dots },m^{\prime }\}$, let $M_j^{\prime }=\{g_{\sigma (1)},g_{\sigma (2)},\mathrm{\dots },g_{\sigma (j)}\}$ denote the prefix of items.

For each $j\in \{0,1,\mathrm{\dots },m^{\prime }\}$ and for each allocation $𝐀$ of $X\cup M_j^{\prime }$ with $A_i\supseteq {\bigcup }_{i^{\prime }\in N}{X}_{i{i}^{\prime }}$ for all $i\in N$, we keep the valuation profile $V={(v_i{(A_{i^{\prime }})}_k)}_{i,i^{\prime }\in N,k\in L}$.

We now describe a dynamic programming algorithm that computes a table $\mathrm{DP}[j][V]$, which is a Boolean indicator that is set to true if there exists an allocation of the items in $X\cup M_j^{\prime }$ that achieves the valuation profile $V$, and false otherwise. Notice that the size of the DP table is at most $(m+1)\cdot {(m\cdot v_{\max }+1)}^{n\cdot n\cdot \mathrm{\ell }}=m^{O(n^2\mathrm{\ell })}\cdot {(v_{\max }+1)}^{O(n^2\mathrm{\ell })}$.

For $j=0$ (i.e., no items are allocated), the table $\mathrm{DP}[0][V]$ is true only when the valuation profile $V$ correspond to the allocation $(X_1,\mathrm{\dots },X_n)$. In other words, the DP table can be filled as follows:

For $j\ge 1$, assume that $\mathrm{DP}[j-1][V]=\text{true}$ for some valuation profile $V$ corresponding to an allocation of $X\cup M_{j-1}^{\prime }$. We then process item $g_{\sigma (j)}$. For each agent $i\in N$, consider allocating $g_{\sigma (j)}$ to $i$. For each such choice, we construct an updated valuation profile $V^{\prime }$ as follows:

This corresponds to the valuation profile of the allocation where item $g_{\sigma (j)}$ is additionally assigned to agent $i$. After performing these updates for every valuation profile $V$ with $\mathrm{DP}[j-1][V]=\text{true}$ and for every choice of agent $i\in N$ who receives $g_{\sigma (j)}$, we set the corresponding entry $\mathrm{DP}[j][V^{\prime }]$ to true. All other cells are set to false.

After processing all items, the table $\mathrm{DP}[m][\cdot ]$ represents possible valuation profile corresponding to full allocations of $M$. We then examine each valuation profile $V$ such that $\mathrm{DP}[m][V]=\text{true}$ to verify the strong sEF$c$ condition. Specifically, for every pair of distinct agents $i,i^{\prime }\in N$ and for every dimension $k\in L$, it suffices to verify that $V_{iik}\ge V_{i{i}^{\prime }k}-{\sum }_{j\in g_j\in X_{i,i^{\prime }}}{v}_{ijk}$.

This condition can be checked in $O(n^2\cdot \mathrm{\ell }\cdot c)$ time. A strong sEF$c$ allocation $𝐀$ corresponding to ${(X_{i{i}^{\prime }})}_{i,i^{\prime }\in N}$ exists if and only if at least one state $V$ such that $\mathrm{DP}[m][V]=\text{true}$ satisfies this inequality.

Finally, the overall running time is

This completes the proof. $◀$

The problem is in NP, since we can verify the condition of weak sEF1 for a given allocation in polynomial time.

We prove strong NP-hardness by reduction from the monotone not-all-equal 3-SAT (MNAE3SAT) problem, which is known to be strongly NP-complete [31]. In the problem, we are given $n$ variables $x_1,x_2,\mathrm{\dots },x_n$ and $m$ clauses $C_1,C_2,\mathrm{\dots },C_m$. Each clause $C_k$ is of the form $C_k=(z_{k,1},z_{k,2},z_{k,3})$, where every literal $z_{k,1},z_{k,2},z_{k,3}$ is one of the variables $x_1,x_2,\mathrm{\dots },x_n$. The goal is to decide whether there exists a truth assignment to the variables such that, in each clause, the literals do not all share the same truth value; in other words, each clause must contain at least one true literal and at least one false literal.

From a given instance of the MNAE3SAT problem, we construct an instance of the MDFA problem as follows. Let $N=\{1,2\}$, $M=\{g_1,g_2,\mathrm{\dots },g_n\}$, and $L=\{1,2,\mathrm{\dots },m\}$. For every agent $i\in N$, item $g_j\in M$, and dimension $k\in L$, define

Notice that in every dimension $k$ (which corresponds to clause $C_k$), exactly the three items corresponding to the three variables appearing in $C_k$ are assigned value $1$, and all other items are assigned $0$. Moreover, both agents have the same binary valuation functions.

We now show that the constructed instance has a weak sEF1 alocation if and only if the MNAE3SAT instance is a yes-instance.

($\mathbf{\Rightarrow }$) Suppose that a weak sEF1 allocation $𝐀=(A_1,A_2)$ exists for the reduced instance. In the constructed instance, for each dimension $k\in L$, exactly three items (corresponding to the three variables of clause $C_k$) have value $1$. Observe that if, for some dimension $k$, all these three items are allocated to the same agent, then one agent would have a value of $0$ while the other has a value of $3$ in that dimension. Removing one item (value $1$) from the bundle with three would yield a value of $2$, which would still leave an envy. Thus, to satisfy the weak sEF1 condition, it must be that in every dimension $k$ both agents receive at least one item with value $1$.

Now define a truth assignment for the MNAE3SAT instance by assigning $x_j$ to be true if $g_j\in A_1$ and false otherwise. Since for every clause $C_k$ the corresponding three items (with value $1$ in dimension $k$) are split between the two agents, the clause contains at least one literal that is true and at least one that is false. Hence, the constructed truth assignment satisfies every clause in the MNAE3SAT instance.

($\mathbf{\Leftarrow }$) Conversely, suppose that the given MNAE3SAT instance is a yes-instance. Let $I\subseteq [n]$ be the set of indices of variables assigned true in some satisfying truth assignment, so that in each clause at least one variable is true and at least one is false. We construct an allocation $𝐀=(A_1,A_2)$ by letting $A_1=\{g_j\in M:j\in I\}$ and $A_2=\{g_j\in M:j\notin I\}$. Consider any dimension $k\in L$ (i.e., any clause $C_k$). Since $C_k=(z_{k,1},z_{k,2},z_{k,3})$, the three items with value $1$ in dimension $k$ are precisely those items corresponding to the variables in $C_k$. Because the truth assignment is satisfying in the MNAE3SAT sense, at least one of these variables is true and at least one is false. Hence, in dimension $k$ the items with value $1$ are split between $A_1$ and $A_2$. In particular, one bundle will contain one item valued $1$ on dimension $k$ while the other will contain two.