$u_{l_{1}}(\pi)=u_{l_{2}}(\pi)=u_{l_{3}}(\pi)=u_{l_{4}}(\pi)=2$. Since
$u_{l_{1}}(\\{l_{3},l_{4}\\})=2$ and $u_{l_{2}}(\\{l_{3},l_{4}\\})=2$, neither
$l_{1}$ nor $l_{2}$ has j-envy for $\alpha_{k_{1}}$, so
$\alpha_{j}\notin\\{l_{1},l_{2}\\}$. Similarly, since
$u_{l_{3}}(\\{l_{1},l_{2}\\})=2$ and $u_{l_{4}}(\\{l_{1},l_{2}\\})=2$ neither
$l_{3}$ nor $l_{4}$ has j-envy for $\alpha_{k_{1}}$, so
$\alpha_{j}\notin\\{l_{3},l_{4}\\}$. Since $u_{c_{i}}(\pi)=3$,
$u_{c_{i}}(\\{l_{1},l_{2}\\})=0$, and $u_{c_{i}}(\\{l_{1},l_{2}\\})=2$ for any
$i$ where $1\leq i\leq 3q$, it must be no agent in $C$ has j-envy for
$\alpha_{k_{1}}$, so $\alpha_{j}\notin C$. It remains that $\alpha_{j}\in H$.
Since this implies
$v_{l_{1}}(\alpha_{j})=v_{l_{2}}(\alpha_{j})=v_{l_{3}}(\alpha_{j})=v_{l_{4}}(\alpha_{j})=0$
it follows that $\alpha_{j}$ does not have j-envy for $\alpha_{k_{1}}$ and
thus that $\alpha_{k_{1}}\notin\\{h_{4},h_{5}\\}$.

    * –

Suppose then that $\alpha_{k_{1}}\in\\{h_{1},h_{2},h_{3}\\}$. Since
$\alpha_{j}$ has j-envy for $\alpha_{k_{1}}$ it must be that
$v_{\alpha_{j}}(\alpha_{k_{2}})\geq 1$ so it follows that
$\alpha_{j}\in\\{h_{4},h_{5}\\}$. If $\alpha_{k_{1}}=h_{1}$ and
$\alpha_{j}=h_{4}$ then we reach a contradiction since $h_{4}$ has j-envy for
$h_{1}$ but $v_{h_{3}}(h_{1})=1=v_{h_{3}}(h_{4})$. Similarly, if
$\alpha_{k_{1}}=h_{1}$ and $\alpha_{j}=h_{5}$ then we reach a contradiction
since $v_{h_{2}}(h_{1})=1=v_{h_{2}}(h_{5})$. If $\alpha_{k_{1}}=h_{2}$ or
$\alpha_{k_{1}}=h_{3}$ then we also reach a contradiction since
$v_{h_{1}}(h_{4})=v_{h_{1}}(h_{5})=1=v_{h_{1}}(h_{2})<2=v_{h_{1}}(h_{3})$.

  * •

Suppose $\alpha_{k_{1}}\in C$. By the construction of $\pi$ it must be that
$\alpha_{k_{2}}\in C$ and $\alpha_{k_{3}}\in C$ so we label
$\alpha_{k_{1}}=c_{i_{1}}$, $\alpha_{k_{2}}=c_{i_{2}}$, and
$\alpha_{k_{3}}=c_{i_{3}}$. By the construction of $(N,V)$ in the reduction it
follows that $v_{c_{i_{2}}}(c_{i_{1}})\geq 1$ and
$v_{c_{i_{3}}}(c_{i_{1}})\geq 1$. Since $\alpha_{j}$ has j-envy for
$c_{i_{1}}$ it follows then that $v_{c_{i_{2}}}(\alpha_{j})=2$ and
$v_{c_{i_{3}}}(\alpha_{j})=2$. By the construction of the instance there are
two possibilities: either $\alpha_{j}=l_{4}$ or $\alpha_{j}\in C$. If
$\alpha_{j}=l_{4}$ then $u_{l_{4}}(\\{c_{i_{2}},c_{i_{3}}\\})=2$ which is a
contradiction since by assumption $l_{4}$ has j-envy for $c_{i_{1}}$ but
$u_{l_{4}}(\pi)=2$. If $\alpha_{j}\in C$ then label $\alpha_{j}=c_{i_{4}}$.
Since $v_{c_{i_{2}}}(c_{i_{4}})=2$ and $v_{c_{i_{3}}}(c_{i_{4}})=2$, by the
construction of $C$ it must be that $(w_{i_{2}},w_{i_{4}})\in A$ and
$(w_{i_{3}},w_{i_{4}})\in A$, where the vertices
$w_{i_{2}},w_{i_{3}},w_{i_{4}}$ are the vertices in $W$ that correspond
respectively to the agents $c_{i_{2}},c_{i_{3}},c_{i_{4}}$ in $C$. Since $G$
is antisymmetric, it follows that $(w_{i_{4}},w_{i_{2}})\notin A$ and
$(w_{i_{4}},w_{i_{3}})\notin A$ so it must be that
$v_{c_{i_{4}}}(c_{i_{2}})=v_{c_{i_{4}}}(c_{i_{3}})=1$. This is also a
contradiction since by assumption $c_{i_{4}}$ has j-envy for $c_{i_{1}}$ but
$u_{c_{i_{4}}}(\\{c_{i_{2}},c_{i_{3}}\\})=2$ and by the construction of $\pi$
it must be that $u_{c_{i_{4}}}(\pi)=3$.

  * •

Suppose $\alpha_{k_{1}}\in L$. It must be that $\alpha_{k_{1}}=l_{i_{1}}$,
$\alpha_{k_{2}}=l_{i_{2}}$, and $\alpha_{k_{3}}=h_{i_{3}}$, for some
$i_{1},i_{2}$ where $1\leq i_{1},i_{2}\leq 4$ and $i_{3}\in\\{4,5\\}$. If
$\alpha_{j}\in H$ then it must be that $v_{l_{i_{2}}}(\alpha_{j})=0$ which
contradicts the supposition that $\alpha_{j}$ has j-envy for $l_{i_{1}}$.
Otherwise, if $\alpha_{j}\notin H$ then $v_{h_{i_{3}}}(\alpha_{j})=0$, which
also contradicts the supposition that $\alpha_{j}$ has j-envy for
$l_{i_{1}}$.∎

We now show that if the ASHG $(N,V)$ contains a j-envy-free partition into
triples then the DTC instance $G$ contains a directed triangle cover.

######  Lemma 36.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then
$\sigma(H,\pi)\geq 3$.

###### Proof.

Since $|H|=5$ it must be that $\sigma(H,\pi)\geq 2$. Suppose for a
contradiction that $\sigma(H,\pi)=2$. It must be that one triple in $\pi$
contains three agents in $H$ and one triple in $\pi$ contains two agents in
$H$. Suppose the former triple is $\\{h_{i_{1}},h_{i_{2}},h_{i_{3}}\\}$ and
the latter triple is $\\{h_{i_{4}},h_{i_{5}},\alpha_{j}\\}$, where $1\leq
i_{1},i_{2},\dots,i_{5}\leq 5$ and $\alpha_{j}\in N\setminus H$. There are
five symmetries in $H$ and $\binom{5}{2}=10$ possible assignments of
$\\{h_{i_{4}},h_{i_{5}}\\}$ to two agents in $H$, so we need only consider the
two assignments $i_{4}=1$, $i_{5}=2$ and $i_{4}=1$, $i_{5}=3$, which are not
symmetric. If $i_{4}=1$ and $i_{5}=2$ then it remains that
$\\{i_{1},i_{2},i_{3}\\}=\\{3,4,5\\}$. In this case, $h_{5}$ has j-envy for
$\alpha_{j}$ since $u_{h_{5}}(\pi)=2<3\leq u_{h_{5}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<1=v_{h_{1}}(h_{5})$, and
$v_{h_{2}}(\alpha_{j})=0<1=v_{h_{2}}(h_{5})$. If $i_{4}=1$ and $i_{5}=3$ then
it remains that $\\{i_{1},i_{2},i_{3}\\}=\\{2,4,5\\}$. In this case, $h_{4}$
has j-envy for $\alpha_{j}$ since $u_{h_{4}}(\pi)=2<3\leq
u_{h_{4}}(\\{h_{1},h_{3}\\})$, $v_{h_{1}}(\alpha_{j})=0<1=v_{h_{1}}(h_{4})$,
and $v_{h_{3}}(\alpha_{j})=0<1=v_{h_{3}}(h_{4})$. ∎

######  Lemma 37.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then at least
two triples in $\pi$ each contain exactly one agent in $H$.

###### Proof.

By Lemma 36, $\sigma(H,\pi)\geq 3$. If, contrary to the lemma statement, at
most one triple in $\pi$ contains exactly one agent in $H$ then it must be
that two triples in $\pi$ each contain two agents in $H$ and one triple in
$\pi$ contains exactly one agent in $H$. Suppose one of the two former triples
is $\\{h_{i_{1}},h_{i_{2}},\alpha_{j_{1}}\\}$ and the latter triple is
$\\{h_{i_{3}},\alpha_{j_{2}},\alpha_{j_{3}}\\}$, where $1\leq
i_{1},i_{2},i_{3}\leq 5$ and $\alpha_{j_{1}},\alpha_{j_{2}},\alpha_{j_{3}}\in
N\setminus H$. By the construction of the instance it must be that
$v_{h_{i_{1}}}(\alpha_{j_{1}})=v_{h_{i_{2}}}(\alpha_{j_{1}})=0$,
$v_{h_{i_{1}}}(h_{i_{3}})\geq 1$ and $v_{h_{i_{2}}}(h_{i_{3}})\geq 1$. It
follows that $h_{i_{3}}$ has j-envy for $\alpha_{j_{1}}$ since
$u_{h_{i_{3}}}(\pi)=0<2\leq u_{h_{i_{3}}}(\\{h_{i_{1}},h_{i_{2}}\\})$,
$v_{h_{i_{1}}}(\alpha_{j})=0<1\leq v_{h_{i_{1}}}(h_{i_{3}})$, and
$v_{h_{i_{2}}}(\alpha_{j})=0<1\leq v_{h_{i_{2}}}(h_{i_{3}})$. This contradicts
the supposition that $\pi$ is j-envy-free. ∎

We have shown in Lemma 37 that if $(N,V)$ contains a j-envy-free partition
into triples $\pi$ then at least two triples in $\pi$ each contain exactly one
agent in $H$. Suppose $t_{\beta},t_{\gamma}\in M$ are two such triples and
$t_{\beta}=\\{h_{a_{1}},\alpha_{b_{1}},\alpha_{b_{2}}\\}$ and
$t_{\gamma}=\\{h_{a_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}$.

######  Lemma 38.

If $(N,V)$ contains a j-envy-free partition into triples then
$\\{\alpha_{b_{1}},\allowbreak\alpha_{b_{2}},\alpha_{b_{3}},\allowbreak\alpha_{b_{4}}\\}=L$.

###### Proof.

Suppose for a contradiction that
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\neq L$.

By definition,
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\cap
H=\varnothing$ and
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\neq L$ it
must be that at least one agent in
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}$ belongs to
$C$. Assume without loss of generality that $\alpha_{b_{1}}\in C$.

Note that by construction of the instance, the valuation of any agent not in
$H$ for any other agent not in $H$ is at least $1$.

Since $\alpha_{b_{2}}\notin H$, it must be that
$u_{\alpha_{b_{2}}}(\pi)=v_{\alpha_{b_{2}}}(\alpha_{b_{1}})$. By the design of
the instance, since $\alpha_{b_{2}}\notin H$ and $\alpha_{b_{1}}\notin H$ it
must be that $v_{\alpha_{b_{2}}}(\alpha_{b_{1}})\in\\{1,2\\}$. We consider
each possibility of
$u_{\alpha_{b_{2}}}(\pi)=v_{\alpha_{b_{2}}}(\alpha_{b_{1}})$.

Firstly, suppose $u_{\alpha_{b_{2}}}(\pi)=1$. As noted earlier in this proof,
since $\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\in N\setminus H$ it must
be that $v_{\alpha_{b_{2}}}(\alpha_{b_{3}})\geq 1$ and
$v_{\alpha_{b_{2}}}(\alpha_{b_{4}})\geq 1$. It follows that $\alpha_{b_{2}}$
has j-envy for $h_{a_{2}}$, since $u_{\alpha_{b_{2}}}(\pi)=1<2\leq
u_{\alpha_{b_{2}}}(\\{\alpha_{b_{3}},\alpha_{b_{4}}\\})$,
$v_{\alpha_{b_{3}}}(h_{a_{2}})=0<1\leq v_{\alpha_{b_{3}}}(\alpha_{b_{2}})$,
and $v_{\alpha_{b_{4}}}(h_{a_{2}})=0<1\leq
v_{\alpha_{b_{4}}}(\alpha_{b_{2}})$. This contradicts the supposition that
$\pi$ is j-envy-free.

Suppose then that $u_{\alpha_{b_{2}}}(\pi)=2$, so
$v_{\alpha_{b_{2}}}(\alpha_{b_{1}})=2$. Since $\alpha_{b_{1}}\in C$ by
assumption, by the design of the instance it must be $\alpha_{b_{2}}\in C$.
For the remainder of this lemma only, label $\alpha_{b_{1}}=c_{i_{1}}$ and
$\alpha_{b_{2}}=c_{i_{2}}$. Since $v_{c_{i_{2}}}(c_{i_{1}})=2$ it follows that
$(w_{i_{2}},w_{i_{1}})\in A$. Since $G$ is antisymmetric it must be that
$(w_{i_{1}},w_{i_{2}})\notin A$ and thus that $v_{c_{i_{1}}}(c_{i_{2}})=1$.
Since $\pi(c_{i_{1}})=\\{c_{i_{1}},c_{i_{2}},h_{a_{1}}\\}$ it follows that
$u_{c_{i_{1}}}(\pi)=v_{c_{i_{1}}}(c_{i_{2}})=1$. Now $\alpha_{b_{1}}$ has
j-envy for $h_{a_{2}}$, since $u_{\alpha_{b_{1}}}(\pi)=1<2\leq
u_{\alpha_{b_{1}}}(\\{\alpha_{b_{3}},\alpha_{b_{4}}\\})$,
$v_{\alpha_{b_{3}}}(h_{a_{2}})=0<1\leq v_{\alpha_{b_{3}}}(\alpha_{b_{1}})$,
and $v_{\alpha_{b_{4}}}(h_{a_{2}})=0<1\leq
v_{\alpha_{b_{4}}}(\alpha_{b_{1}})$. This contradicts the supposition that
$\pi$ is j-envy-free. ∎

######  Lemma 39.

If $(N,V)$ contains a j-envy-free partition into triples then
$\\{\\{\alpha_{b_{1}},\allowbreak\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\allowbreak\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},\allowbreak
l_{2}\\},\\{l_{3},\allowbreak l_{4}\\}\\}$.

###### Proof.

By Lemma 38,
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}=L$. There
are now three possibilities: first that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{3}\\},\\{l_{2},l_{4}\\}\\}$,
second that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{4}\\},\\{l_{2},l_{3}\\}\\}$,
and third that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{2}\\},\\{l_{3},l_{4}\\}\\}$.

First suppose
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{3}\\},\\{l_{2},l_{4}\\}\\}$.
Without loss of generality assume that $\alpha_{b_{1}}=l_{1}$. Now $l_{1}$ has
j-envy for $h_{a_{2}}$ since
$u_{l_{1}}(\\{h_{a_{1}},l_{3}\\})=1<3=u_{l_{1}}(\\{l_{2},l_{4}\\})$,
$v_{l_{2}}(h_{a_{2}})=0<2=v_{l_{2}}(l_{1})$, and
$v_{l_{4}}(h_{a_{2}})=0<1=v_{l_{4}}(l_{1})$.

Second suppose
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{4}\\},\\{l_{2},l_{3}\\}\\}$.
Without loss of generality assume that $\alpha_{b_{1}}=l_{1}$. As before,
$l_{1}$ has j-envy for $h_{a_{2}}$ since
$u_{l_{1}}(\\{h_{a_{1}},l_{4}\\})=1<3=u_{l_{1}}(\\{l_{2},l_{3}\\})$,
$v_{l_{2}}(h_{a_{2}})=0<2=v_{l_{2}}(l_{1})$, and
$v_{l_{3}}(h_{a_{2}})=0<1=v_{l_{3}}(l_{1})$.

It remains that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{2}\\},\\{l_{3},l_{4}\\}\\}$.
∎

By Lemma 39, either $\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{1},l_{2}\\}$ or
$\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{3},l_{4}\\}$. Without loss of
generality assume that
$\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{3},l_{4}\\}$.

######  Lemma 40.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then
$u_{c_{i}}(\pi)\geq 3$ for each $i$ where $1\leq i\leq 3q$.

###### Proof.

Suppose to the contrary that some $1\leq i\leq 3q$ exists where
$u_{c_{i}}(\pi)<3$. Then $c_{i}$ has j-envy for $h_{a_{1}}$ since
$u_{c_{i}}(\pi)\leq 2<3=u_{c_{i}}(\\{l_{3},l_{4}\\})$,
$v_{l_{3}}(h_{a_{1}})=0<1=v_{l_{3}}(c_{i})$, and
$v_{l_{4}}(h_{a_{1}})=0<1=v_{l_{4}}(c_{i})$. This contradicts our supposition
that $\pi$ is j-envy-free. ∎

######  Lemma 41.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then $G$
contains a directed triangle cover.

###### Proof.

Suppose $(N,V)$ contains a j-envy-free partition into triples $\pi$. Lemma 40
shows that $u_{c_{i}}(\pi)\geq 3$ for each $i$ where $1\leq i\leq 3q$. By
construction, it follows that $\pi(c_{i})$ contains two agents $c_{j},c_{k}$
such that $v_{c_{i}}(c_{j})\geq 1$ and $v_{c_{i}}(c_{k})=2$. Hence $c_{k}$
corresponds to a vertex $w_{k}\in W$ where $(w_{i},w_{k})\in A$ and, since $G$
is antisymmetric, $(w_{k},w_{i})\notin A$. Since $c_{i}$ was chosen
arbitrarily it follows that $\\{w_{i},w_{j},w_{k}\\}$ is a directed $3$-cycle
in $G$. It follows thus that there are exactly $q$ triples in $\pi$ each
containing three agents $\\{c_{i},c_{j},c_{k}\\}$ where the three
corresponding vertices $\\{w_{i},w_{j},w_{k}\\}$ form a directed $3$-cycle in
$G$. From these triples a directed triangle cover $X$ can be easily
constructed. ∎

We have now shown that the ASHG $(N,V)$ contains a j-envy-free partition into
triples if and only if the DTC instance $G$ contains a directed triangle
cover. This shows that the reduction is correct.

######  Theorem 6.

Deciding if a given ASHG contains a j-envy-free partition into triples is
$\NP$-complete, even when preferences are ternary.

###### Proof.

It is straightforward to show that this decision problem belongs to $\NP$,
since for any two agents $\alpha_{i},\alpha_{j}\in N$ we can test if
$\alpha_{i}$ j-envies $\alpha_{j}$ in constant time.

We have presented a polynomial-time reduction from a restricted version of
Directed Triangle Cover (DTC), which is $\NP$-complete [29]. Given a directed
antisymmetric graph $G$, the reduction constructs an ASHG $(N,V)$ with ternary
preferences. Lemmas 35 and 41 show that $(N,V)$ contains a j-envy-free
partition into triples if and only if $G$ contains a directed triangle cover
and thus that this decision problem is $\NP$-hard. ∎

###  5.4 Symmetric non-binary preferences

From Theorems 5 and 6, a natural question arises: is it the symmetry of
agents’ preferences that guarantees the existence of a j-envy-free partition
into triples? In this section we show that this is not the case, and a j-envy-
free partition into triples may not exist even when agents’ preferences are
symmetric, and the associated existence problem is $\NP$-complete. We remark,
however, that the instances shown that do not contain j-envy-free partitions
into triples are relatively contrived and involve non-negative integer
valuations up to $6$. We leave open the case in which preferences are
symmetric and the maximum valuation is strictly less than $6$.

To show that this existence problem is $\NP$-complete, we present a
polynomial-time reduction from PIT. This reduction is similar to the reduction
we presented in Section 5.3 for the analogous problem involving ternary
preferences that are not (necessarily) symmetric. In that section we reduced
from Directed Triangle Packing (DTC) but here we reduce from Partition Into
Triangles (PIT, Problem 3).

######  Problem 3 (Partition Into Triangles (PIT))

Input: a simple undirected graph $G=(W,E)$ where $|W|=3q$ for some integer $q$

Question: Can the vertices of $G$ be partitioned into $q$ disjoint sets
$X=\\{X_{1},X_{2},\dots,X_{q}\\}$, each set containing exactly three vertices,
such that each $X_{p}=\\{w_{i},w_{j},w_{k}\\}\in W$ where $1\leq p\leq q$ is a
triangle? We describe the reduction in detail and then provide some intuition
with respect to its design. The reduction, illustrated in Figure 6, is as
follows. Suppose $G$ is an arbitrary instance of PIT. We shall construct an
ASHG $(N,V)$ of with symmetric preferences and maximum valuation $6$. Since
valuations are symmetric in $(N,V)$, we shall usually specify valuations in
one direction only. For example, instead of writing “let
$v_{\alpha_{i}}(\alpha_{j})=v_{\alpha_{j}}(\alpha_{i})=1$” we write “let
$v_{\alpha_{i}}(\alpha_{j})=1$”. Unless otherwise specified assume that
$v_{\alpha_{i}}(\alpha_{j})=0$ for any $\alpha_{i},\alpha_{j}\in N$. To
simplify the description of the valuations in the reduction, in this section
we write $i\oplus y$ to denote $((i+y-2)\bmod 10)+2$. First, construct a set
of eleven agents $H=\\{h_{1},h_{2},\dots,h_{11}\\}$. For each $i$ where $2\leq
i\leq 11$ let $v_{h_{1}}(h_{i})=2$. For each $i$ where $2\leq i\leq 11$, let:

  * •

$v_{h_{i}}(h_{i\oplus 1})=4$ if $i$ is even otherwise $5$

  * •

$v_{h_{i}}(h_{i\oplus 2})=6$ if $i$ is even otherwise $3$

  * •

$v_{h_{i}}(h_{i\oplus 3})=1$

  * •

$v_{h_{i}}(h_{i\oplus 4})=1$

  * •

$v_{h_{i}}(h_{i\oplus 5})=3$.

Next, construct a set of four agents $L=\\{l_{1},l_{2},l_{3},l_{4}\\}$. Let
$v_{l_{1}}(l_{2})=v_{l_{3}}(l_{4})=2$ and
$v_{l_{1}}(l_{3})=v_{l_{1}}(l_{4})=v_{l_{2}}(l_{3})=v_{l_{2}}(l_{4})=1$. Next,
construct a set of $3q$ agents $C=\\{c_{1},c_{2},\dots,c_{3q}\\}$. Let
$v_{c_{i}}(l_{r})=3$ for each $i$ and $r$ where $1\leq i\leq 3q$ and $1\leq
r\leq 4$. For each $i$ and $j$ where $1\leq i,j\leq 3q$ let
$v_{c_{i}}(c_{j})=3$ if $\\{w_{i},w_{j}\\}\in E$ otherwise $2$. This completes
the construction of $(N,V)$. Note that the structure of the valuations among
the agents in $C$ reflects the graph $G$. We make some remarks on the design
of the constructed instance. Like before, in the reduction presented in
Section 5.3, the design of $H$ is derived from a particular instance that
admits no j-envy-free partition into triples. This instance comprises $H$ as
well as a single isolated agent $\alpha_{z}$, where $v_{\alpha_{z}}(h_{i})=0$
for each $i$ where $1\leq i\leq 11$. In fact, the proof that this instance
contains no j-envy-free partition into triples can be directly derived from
the proofs of lemmas appearing later in this section (Lemmas 44–48). It is
straightforward to show that the reduction runs in polynomial time. To prove
that the reduction is correct we show that the ASHG $(N,V)$ contains a j-envy-
free partition into triples if and only if the PIT instance $G$ contains a
partition into triangles.
$h_{1}$$h_{3}$$h_{2}$$h_{11}$$h_{10}$$h_{9}$$h_{8}$$h_{7}$$h_{6}$$h_{5}$$h_{4}$$c_{1},c_{2},\dots,c_{3q}$$l_{1}$$l_{2}$$l_{3}$$l_{4}$
Figure 6: The reduction from PIT to the problem of deciding if an ASHG with
symmetric preferences contains a j-envy-free partition into triples. Valuation
colour key: red \- 6, green \- 5, blue \- 4, black \- 3, purple \- 2, grey \-
1. We first show that if the PIT instance $G$ contains a partition into
triangles then the ASHG $(N,V)$ contains a j-envy-free partition into triples.

######  Lemma 42.

If $G$ contains a partition into triangles then $(N,V)$ contains a j-envy-free
partition into triples.

###### Proof.

Suppose $G$ contains a partition into triangles
$X=\\{X_{1},X_{2},\dots,X_{q}\\}$. We shall construct a partition into triples
$\pi$ in $(N,V)$ that is j-envy-free. First, add $\\{h_{2},h_{10},h_{11}\\}$,
$\\{h_{5},h_{6},h_{8}\\}$, $\\{h_{1},h_{9},h_{4}\\}$,
$\\{h_{3},l_{1},l_{2}\\}$ and $\\{h_{7},l_{3},l_{4}\\}$ to $\pi$. Next, for
each triangle $X_{p}=\\{w_{i},w_{j},w_{k}\\}$ in $X$, add
$\\{c_{i},c_{j},c_{k}\\}$ to $\pi$.

Suppose for a contradiction that some agent $\alpha_{j}$ exists where
$\alpha_{j}$ has j-envy for some other agent $\alpha_{k_{1}}$ where
$\pi(\alpha_{k_{1}})=\\{\alpha_{k_{1}},\alpha_{k_{2}},\alpha_{k_{3}}\\}$.
Since $N=H\cup L\cup C$ it must be that either $\alpha_{k_{1}}\in H$,
$\alpha_{k_{1}}\in L$, or $\alpha_{k_{1}}\in C$. We show that each case leads
to a contradiction. It follows that no such $\alpha_{j}$ exists and thus that
$\pi$ is j-envy-free.

  * •

Suppose $\alpha_{k_{1}}\in H$. Either $\alpha_{k_{1}}\in\\{h_{3},h_{7}\\}$ or
$\alpha_{k_{1}}\in H\setminus\\{h_{3},h_{7}\\}$.

    * –

Suppose $\alpha_{k_{1}}\in\\{h_{3},h_{7}\\}$. Then it must be that either
$\\{\alpha_{k_{2}},\alpha_{k_{3}}\\}=\\{l_{1},l_{2}\\}$ or
$\\{\alpha_{k_{2}},\alpha_{k_{3}}\\}=\\{l_{3},l_{4}\\}$. Suppose firstly that
$\\{\alpha_{k_{2}},\alpha_{k_{3}}\\}=\\{l_{1},l_{2}\\}$. We can see
immediately that $\alpha_{j}\notin H$ since otherwise
$u_{\alpha_{j}}(\\{l_{1},l_{2}\\})=0$. It must also be that $\alpha_{j}\notin
C$, since $u_{c_{a}}(\\{l_{1},l_{2}\\})=6=u_{c_{a}}(\pi)$ for any $c_{a}\in
C$. Similarly, $u_{l_{3}}(\\{l_{1},l_{2}\\})=2=u_{l_{3}}(\pi)$ and
$u_{l_{4}}(\\{l_{1},l_{2}\\})=2=u_{l_{4}}(\pi)$ so $\alpha_{j}\neq l_{3}$ and
$\alpha_{j}\neq l_{4}$. This shows $\alpha_{j}\notin L$. We have shown that
$\alpha_{j}\notin H$, $\alpha_{j}\notin C$, and $\alpha_{j}\notin L$, which is
a contradiction. The proof for the case in which
$\\{\alpha_{k_{2}},\alpha_{k_{3}}\\}=\\{l_{3},l_{4}\\}$ is symmetric and also
leads to a contradiction.

    * –

Suppose $\alpha_{k_{1}}\in H\setminus\\{h_{3},h_{7}\\}$. If
$\alpha_{k_{1}}=h_{1}$ then
$\\{\alpha_{k_{2}},\alpha_{k_{3}}\\}=\\{h_{4},h_{9}\\}$ so it must be that
$v_{h_{4}}(\alpha_{j})>2=v_{h_{4}}(h_{1})$ and
$v_{h_{9}}(\alpha_{j})>2=v_{h_{9}}(h_{1})$, which is impossible by the design
of $H$. The proof for every other assignment of $\alpha_{k_{1}}$ is similar:
if $\alpha_{k_{1}}=h_{2}$ then $v_{h_{11}}(\alpha_{j})>5$, which is
impossible. If $\alpha_{k_{1}}=h_{4}$ then $v_{h_{1}}(\alpha_{j})>2$, which is
impossible. If $\alpha_{k_{1}}=h_{5}$ then $v_{h_{6}}(\alpha_{j})>5$ and
$v_{h_{8}}(\alpha_{j})>1$, which is impossible. If $\alpha_{k_{1}}=h_{6}$ then
$v_{h_{8}}(\alpha_{j})>6$, which is impossible. If $\alpha_{k_{1}}=h_{8}$ then
$v_{h_{6}}(\alpha_{j})>6$, which is impossible. If $\alpha_{k_{1}}=h_{9}$ then
$v_{h_{1}}(\alpha_{j})>2$, which is impossible. If $\alpha_{k_{1}}=h_{10}$
then $v_{h_{2}}(\alpha_{j})>6$, which is impossible. If
$\alpha_{k_{1}}=h_{11}$ then $v_{h_{2}}(\alpha_{j})>5$ and
$v_{h_{10}}(\alpha_{j})>4$, which is impossible.

  * •

Suppose $\alpha_{k_{1}}\in C$. By construction, it must be that
$\alpha_{k_{1}}=c_{i_{1}}$, $\alpha_{k_{2}}=c_{i_{2}}$, and
$\alpha_{k_{3}}=c_{i_{3}}$ where $\\{c_{i_{1}},c_{i_{2}},c_{i_{3}}\\}\subseteq
C$, where the corresponding vertices $\\{w_{i_{1}},w_{i_{2}},w_{i_{3}}\\}$ in
$G$ are a triangle. It follows that $v_{c_{i_{2}}}(c_{i_{1}})=3$. By
assumption, $\alpha_{j}$ has j-envy for $c_{i_{1}}$ so it must be that
$v_{c_{i_{2}}}(\alpha_{j})>v_{c_{i_{2}}}(c_{i_{1}})=3$, which is impossible by
the design of $C$.

  * •

Suppose $\alpha_{k_{1}}\in L$. It must be that $\alpha_{k_{1}}=l_{i_{1}}$ for
some $i_{1}$ where $1\leq i_{1}\leq 4$, $\alpha_{k_{2}}=l_{i_{2}}$ for some
$i_{2}$ where $1\leq i_{2}\leq 4$ and $\alpha_{k_{3}}=h_{i_{3}}$ where
$i_{3}\in\\{3,7\\}$. If $\alpha_{j}\in H$ then $v_{l_{i_{2}}}(\alpha_{j})=0$
which contradicts the supposition that $\alpha_{j}$ has j-envy for
$l_{i_{1}}$. Otherwise, if $\alpha_{j}\notin H$ then
$v_{h_{i_{3}}}(\alpha_{j})=0$, which also contradicts the supposition that
$\alpha_{j}$ has j-envy for $l_{i_{1}}$.∎

We now show that if the ASHG $(N,V)$ contains a j-envy-free partition into
triples then the PIT instance $G$ contains a partition into triangles. In the
first part of this proof (up to and including Lemma 48) we focus on $H$. To
begin, we define two possible configurations of $H$ in an arbitrary j-envy-
free partition into triples $\pi$. If some triple $t\in\pi$ contains exactly
one agent in $H$ then we say that $H$ has an _open configuration in $\pi$_.
Otherwise, we say that $H$ has a _closed configuration in $\pi$_. We shall
eventually show, in Lemma 48, that the only possible configuration of $H$ in
$\pi$ is an open configuration. In Lemmas 43–47 we prove a sequence of
intermediary results.

######  Lemma 43.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then no triples
$t_{1},t_{2}$ in $\pi$ exist such that $t_{1}$ contains exactly two agents in
$H$ and $t_{2}$ contains exactly one agent in $H$.

###### Proof.

Suppose for a contradiction that some such $t_{1},t_{2}\in\pi$ exist. Suppose
$t_{1}=\\{h_{i_{1}},h_{i_{2}},\alpha_{j_{1}}\\}$ and
$t_{2}=\\{h_{i_{3}},\alpha_{j_{2}},\alpha_{j_{3}}\\}$ where $1\leq
i_{1},i_{2},i_{3}\leq 11$ and $\alpha_{j_{1}},\alpha_{j_{2}},\alpha_{j_{3}}\in
N\setminus H$. Now $h_{i_{3}}$ has j-envy for $\alpha_{j_{1}}$ since
$u_{h_{i_{3}}}(\pi)=0<2\leq u_{h_{i_{3}}}(\\{h_{i_{1}},h_{i_{2}}\\})$,
$v_{h_{i_{1}}}(\alpha_{j_{1}})=0<1\leq v_{h_{i_{1}}}(h_{i_{3}})$ and
$v_{h_{i_{2}}}(\alpha_{j_{1}})=0<1\leq v_{h_{i_{2}}}(h_{i_{3}})$. This
contradicts our supposition that $\pi$ is j-envy-free. ∎

######  Lemma 44.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$,
$\sigma(H,\pi)=4$, and $u_{h_{1}}(\pi)<4$ then $H$ has an open configuration
in $\pi$.

###### Proof.

Suppose to the contrary that $\sigma(H,\pi)=4$, $u_{h_{1}}(\pi)<4$, and $H$
has a closed configuration in $\pi$. Since $\sigma(H,\pi)=4$ it must be that
three triples in $\pi$ each contain exactly three agents in $H$ and one triple
in $\pi$ contains exactly two agents in $H$. Suppose then that
$t_{1},t_{2},t_{3}\in\pi$ each contain exactly three agents in $H$ and
$t_{4}\in\pi$ contains exactly two agents in $H$. Since $u_{h_{1}}(\pi)<4$ by
assumption, by the design of $H$ it follows that $\pi(h_{1})$ contains at most
one agent in $H\setminus\\{h_{1}\\}$ and therefore $h_{1}\in t_{4}$. It
follows that $t_{4}=\\{h_{1},h_{i_{1}},\alpha_{j}\\}$ where $2\leq i_{1}\leq
11$ and $\alpha_{j}\in N\setminus H$. We use a case analysis to prove a
contradiction occurs for each possible assignment of $i_{1}$.

  * •

Suppose first $i_{1}=2$. If $u_{h_{4}}(\pi)\leq 7$ then $h_{4}$ has j-envy for
$\alpha_{j}$, since $u_{h_{4}}(\pi)\leq 7<8=u_{h_{4}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{4})$, and
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 8$. By the assumptions regarding the structure of $\pi$,
it must be that $\pi(h_{4})$ contains three agents in $H$. Since
$t_{4}=\\{h_{1},h_{2},\alpha_{j}\\}$ it must be that
$\pi(h_{4})=\\{h_{4},h_{i_{2}},h_{i_{3}}\\}$ where
$\\{i_{2},i_{3}\\}\subset\\{3,5,6,7,8,9,10,11\\}$. Recall that
$v_{h_{4}}(h_{3})=5$, $v_{h_{4}}(h_{5})=4$, $v_{h_{4}}(h_{6})=6$,
$v_{h_{4}}(h_{7})=1$, $v_{h_{4}}(h_{8})=1$, $v_{h_{4}}(h_{9})=3$,
$v_{h_{4}}(h_{10})=1$, and $v_{h_{4}}(h_{11})=1$. Since we established
$u_{h_{4}}(\pi)\geq 8$ it follows that there are 5 possibilities:
$\\{i_{2},i_{3}\\}=\\{3,9\\}$, $\\{i_{2},i_{3}\\}=\\{3,5\\}$,
$\\{i_{2},i_{3}\\}=\\{3,6\\}$, $\\{i_{2},i_{3}\\}=\\{5,6\\}$, and
$\\{i_{2},i_{3}\\}=\\{6,9\\}$, which we shall now consider.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{3,9\\}$. It follows that $h_{2}$ has j-envy for
$h_{9}$, since $u_{h_{2}}(\pi)=2<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(h_{9})=1<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(h_{9})=3<6=v_{h_{4}}(h_{2})$. This contradicts the supposition that
$\pi$ is j-envy-free.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{3,5\\}$. It follows that $h_{2}$ has j-envy for
$h_{5}$, since $u_{h_{2}}(\pi)=2<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(h_{5})=3<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(h_{5})=4<6=v_{h_{4}}(h_{2})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{3,6\\}$. Consider $h_{11}$. If
$u_{h_{11}}(\pi)\leq 6$ then $h_{11}$ has j-envy for $\alpha_{j}$, since
$u_{h_{11}}(\pi)\leq 6<7=u_{h_{11}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{11})$, and
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$. It follows that
$u_{h_{11}}(\pi)\geq 7$. We have established that $h_{2}\notin\pi(h_{11})$,
$h_{3}\notin\pi(h_{11})$, and $h_{6}\notin\pi(h_{11})$ so, by the design of
$H$, it must be that $\pi(h_{11})=\\{h_{9},h_{10},h_{11}\\}$. Now $h_{2}$ has
j-envy for $h_{9}$, since
$u_{h_{2}}(\pi)=2<11=u_{h_{2}}(\\{h_{10},h_{11}\\})$,
$v_{h_{10}}(h_{9})=5<6=v_{h_{10}}(h_{2})$, and
$v_{h_{11}}(h_{9})=3<5=v_{h_{11}}(h_{2})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{5,6\\}$. Consider $h_{3}$. If
$u_{h_{3}}(\pi)\leq 5$ then $h_{3}$ has j-envy for $\alpha_{j}$, since
$u_{h_{3}}(\pi)\leq 5<6=u_{h_{3}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{3})$, and
$v_{h_{2}}(\alpha_{j})=0<4=v_{h_{2}}(h_{3})$. It follows that
$u_{h_{3}}(\pi)\geq 6$. We have established that $h_{2}\notin\pi(h_{3})$,
$h_{4}\notin\pi(h_{3})$, and $h_{5}\notin\pi(h_{3})$ so, by the design of $H$,
it must be that $\pi(h_{3})=\\{h_{3},h_{8},h_{11}\\}$. Now $h_{11}$ has j-envy
for $\alpha_{j}$, since $u_{h_{11}}(\pi)=4<7=u_{h_{11}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{11})$, and
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,9\\}$. Consider $h_{11}$. If
$u_{h_{11}}(\pi)\leq 6$ then $h_{11}$ has j-envy for $\alpha_{j}$, since
$u_{h_{11}}(\pi)\leq 6<7=u_{h_{11}}(\\{h_{1},h_{2}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{11})$, and
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$. It follows that
$u_{h_{11}}(\pi)\geq 7$. We have established that $h_{2}\notin\pi(h_{11})$,
$h_{6}\notin\pi(h_{11})$, and $h_{9}\notin\pi(h_{11})$ so, by the design of
$H$, it must be that $\pi(h_{11})=\\{h_{3},h_{10},h_{11}\\}$. Now $h_{2}$ has
j-envy for $h_{10}$, since $u_{h_{2}}(\pi)=2<9=u_{h_{2}}(\\{h_{3},h_{11}\\})$,
$v_{h_{3}}(h_{10})=1<4=v_{h_{3}}(h_{2})$, and
$v_{h_{11}}(h_{10})=4<5=v_{h_{11}}(h_{2})$.

  * •

Suppose next $i_{1}=3$. If $u_{h_{4}}(\pi)\leq 6$ then $h_{4}$ has j-envy for
$\alpha_{j}$, since $u_{h_{4}}(\pi)\leq 6<7=u_{h_{4}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{4})$, and
$v_{h_{3}}(\alpha_{j})=0<5=v_{h_{3}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 7$. Since $\pi(h_{4})\neq t_{4}$ it must be that
$\pi(h_{4})=\\{h_{4},h_{i_{2}},h_{i_{3}}\\}$ where
$\\{i_{2},i_{3}\\}\subset\\{2,5,6,7,8,9,10,11\\}$. Recall that
$v_{h_{4}}(h_{2})=6$, $v_{h_{4}}(h_{5})=4$, $v_{h_{4}}(h_{6})=6$,
$v_{h_{4}}(h_{7})=1$, $v_{h_{4}}(h_{8})=1$, $v_{h_{4}}(h_{9})=3$,
$v_{h_{4}}(h_{10})=1$, and $v_{h_{4}}(h_{11})=1$. Since we established
$u_{h_{4}}(\pi)\geq 7$ it follows that there are $14$ possibilities:
$\\{i_{2},i_{3}\\}=\\{2,5\\}$, $\\{i_{2},i_{3}\\}=\\{2,6\\}$,
$\\{i_{2},i_{3}\\}=\\{2,7\\}$, $\\{i_{2},i_{3}\\}=\\{2,8\\}$,
$\\{i_{2},i_{3}\\}=\\{2,9\\}$, $\\{i_{2},i_{3}\\}=\\{2,10\\}$,
$\\{i_{2},i_{3}\\}=\\{2,11\\}$, $\\{i_{2},i_{3}\\}=\\{5,6\\}$,
$\\{i_{2},i_{3}\\}=\\{5,9\\}$, $\\{i_{2},i_{3}\\}=\\{6,7\\}$,
$\\{i_{2},i_{3}\\}=\\{6,8\\}$, $\\{i_{2},i_{3}\\}=\\{6,9\\}$,
$\\{i_{2},i_{3}\\}=\\{6,10\\}$, and $\\{i_{2},i_{3}\\}=\\{6,11\\}$, which we
shall now consider.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,5\\}$. It follows that $h_{3}$ has j-envy for
$h_{5}$, since $u_{h_{3}}(\pi)=2<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{5})=1<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{5})=4<5=v_{h_{4}}(h_{3})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,6\\}$. If $u_{h_{5}}(\pi)\leq 4$ then $h_{5}$
has j-envy for $\alpha_{j}$, since $u_{h_{5}}(\pi)\leq
4<5=u_{h_{5}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{5})$, and
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{5})$. It follows that
$u_{h_{5}}(\pi)\geq 5$. We have established that $h_{3}\notin\pi(h_{5})$,
$h_{4}\notin\pi(h_{5})$, and $h_{6}\notin\pi(h_{5})$ so, by the design of $H$,
it must be that $\pi(h_{5})=\\{h_{5},h_{7},h_{10}\\}$. It remains that
$\pi(h_{11})=\\{h_{8},h_{9},h_{11}\\}$. Now $h_{11}$ has j-envy for
$\alpha_{j}$, since $u_{h_{11}}(\pi)=4<5=u_{h_{11}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{11})$, and
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{11})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,7\\}$. It follows that $h_{3}$ has j-envy for
$h_{7}$, since $u_{h_{3}}(\pi)=2<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{7})=3<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{7})=1<5=v_{h_{4}}(h_{3})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,8\\}$. It follows that $h_{3}$ has j-envy for
$h_{8}$, since $u_{h_{3}}(\pi)=2<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{8})=1<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{8})=1<5=v_{h_{4}}(h_{3})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,9\\}$. It follows that $h_{3}$ has j-envy for
$h_{9}$, since $u_{h_{3}}(\pi)=2<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{9})=1<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{9})=3<5=v_{h_{4}}(h_{3})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,10\\}$. If $u_{h_{11}}(\pi)\leq 4$ then
$h_{11}$ has j-envy for $\alpha_{j}$, since $u_{h_{11}}(\pi)\leq
4<5=u_{h_{5}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{11})$, and
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{11})$. It follows that
$u_{h_{11}}(\pi)\geq 5$. We have established that $h_{2}\notin\pi(h_{11})$,
$h_{3}\notin\pi(h_{11})$, and $h_{10}\notin\pi(h_{11})$ so, by the design of
$H$, it must be that $\pi(h_{11})=\\{h_{6},h_{9},h_{11}\\}$. Since
$h_{5}\notin t_{4}$, it must be that $\pi(h_{5})$ contains three agents in $H$
and thus $\pi(h_{5})=\\{h_{5},h_{7},h_{8}\\}$. Now $h_{6}$ has j-envy for
$h_{5}$, since $u_{h_{6}}(\pi)=4<10=u_{h_{6}}(\\{h_{7},h_{8}\\})$,
$v_{h_{7}}(h_{5})=3<4=v_{h_{7}}(h_{6})$, and
$v_{h_{8}}(h_{5})=1<6=v_{h_{8}}(h_{6})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{2,11\\}$. If $u_{h_{5}}(\pi)\leq 4$ then $h_{5}$
has j-envy for $\alpha_{j}$, since $u_{h_{5}}(\pi)\leq
4<5=u_{h_{5}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{5})$, and
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{5})$. It follows that
$u_{h_{5}}(\pi)\geq 5$. We have established that $h_{3}\notin\pi(h_{5})$ and
$h_{4}\notin\pi(h_{5})$ so, by the design of $H$, there are three
possibilities: either $\pi(h_{5})=\\{h_{5},h_{6},h_{7}\\}$,
$\pi(h_{5})=\\{h_{5},h_{6},h_{10}\\}$, or
$\pi(h_{5})=\\{h_{5},h_{7},h_{10}\\}$.

      * *

If $\pi(h_{5})=\\{h_{5},h_{6},h_{7}\\}$ then $h_{4}$ has j-envy for $h_{7}$,
since $u_{h_{4}}(\pi)=7<10=u_{h_{4}}(\\{h_{5},h_{6}\\})$,
$v_{h_{5}}(h_{7})=3<4=v_{h_{5}}(h_{4})$, and
$v_{h_{6}}(h_{7})=4<6=v_{h_{6}}(h_{4})$.

      * *

If $\pi(h_{5})=\\{h_{5},h_{6},h_{10}\\}$ then $h_{4}$ has j-envy for $h_{10}$,
since $u_{h_{4}}(\pi)=7<10=u_{h_{4}}(\\{h_{5},h_{6}\\})$,
$v_{h_{5}}(h_{10})=3<4=v_{h_{5}}(h_{4})$, and
$v_{h_{6}}(h_{10})=1<6=v_{h_{6}}(h_{4})$.

      * *

If $\pi(h_{5})=\\{h_{5},h_{7},h_{10}\\}$ then it remains that
$\pi(h_{6})=\\{h_{6},h_{8},h_{9}\\}$. Now $h_{6}$ has j-envy for $h_{10}$,
since $u_{h_{6}}(\pi)=7<9=u_{h_{6}}(\\{h_{5},h_{7}\\})$,
$v_{h_{5}}(h_{10})=3<5=v_{h_{5}}(h_{6})$, and
$v_{h_{7}}(h_{10})=1<4=v_{h_{7}}(h_{6})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{5,6\\}$. If $u_{h_{2}}(\pi)\leq 5$ then $h_{2}$
has j-envy for $\alpha_{j}$, since $u_{h_{2}}(\pi)\leq
5<6=u_{h_{2}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{2})$, and
$v_{h_{3}}(\alpha_{j})=0<4=v_{h_{3}}(h_{2})$. It follows that
$u_{h_{2}}(\pi)\geq 6$. Since $h_{2}\notin t_{4}$ it must be that $\pi(h_{2})$
contains three agents in $H$. Since $t_{4}=\\{h_{1},h_{3},\alpha_{j}\\}$ and
$\pi(h_{4})=\\{h_{4},h_{5},h_{6}\\}$ it follows that
$\pi(h_{2})=\\{h_{2},h_{i_{4}},h_{i_{5}}\\}$ where
$\\{i_{4},i_{5}\\}\subset\\{7,8,9,10,11\\}$. Recall that $v_{h_{2}}(h_{7})=3$,
$v_{h_{2}}(h_{8})=1$, $v_{h_{2}}(h_{9})=1$, $v_{h_{2}}(h_{10})=6$, and
$v_{h_{2}}(h_{11})=5$. Since we established $u_{h_{2}}(\pi)\geq 6$ it follows
that there are $7$ possibilities: $\\{h_{i_{4}},h_{i_{5}}\\}=\\{7,10\\}$,
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{7,11\\}$,
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{8,10\\}$,
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{8,11\\}$,
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{9,10\\}$,
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{9,11\\}$, and
$\\{h_{i_{4}},h_{i_{5}}\\}=\\{10,11\\}$, which we shall now consider.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{7,10\\}$ then it remains that
$\pi(h_{11})=\\{h_{8},h_{9},h_{11}\\}$. Now $h_{11}$ has j-envy for $h_{7}$,
since $u_{h_{11}}(\pi)=4<9=u_{h_{11}}(\\{h_{2},h_{10}\\})$,
$v_{h_{2}}(h_{7})=3<5=v_{h_{2}}(h_{11})$, and
$v_{h_{10}}(h_{7})=1<4=v_{h_{10}}(h_{11})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{7,11\\}$ then $h_{3}$ has j-envy for $h_{7}$,
since $u_{h_{3}}(\pi)=2<7=u_{h_{3}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{7})=3<4=v_{h_{2}}(h_{3})$, and
$v_{h_{11}}(h_{7})=1<3=v_{h_{11}}(h_{3})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{8,10\\}$ then it remains that
$\pi(h_{7})=\\{h_{7},h_{9},h_{11}\\}$. Now $h_{8}$ has j-envy for $h_{11}$,
since $u_{h_{8}}(\pi)=7<9=u_{h_{8}}(\\{h_{7},h_{9}\\})$,
$v_{h_{7}}(h_{11})=1<5=v_{h_{7}}(h_{8})$, and
$v_{h_{9}}(h_{11})=3<4=v_{h_{9}}(h_{8})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{8,11\\}$ then $h_{3}$ has j-envy for $h_{8}$,
since $u_{h_{3}}(\pi)=2<7=u_{h_{3}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{8})=1<4=v_{h_{2}}(h_{3})$, and
$v_{h_{11}}(h_{8})=1<3=v_{h_{11}}(h_{3})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{9,10\\}$ then it remains that
$\pi(h_{7})=\\{h_{7},h_{8},h_{11}\\}$. Now $h_{9}$ has j-envy for $h_{11}$,
since $u_{h_{9}}(\pi)=6<7=u_{h_{9}}(\\{h_{7},h_{8}\\})$,
$v_{h_{7}}(h_{11})=1<3=v_{h_{7}}(h_{9})$, and
$v_{h_{8}}(h_{11})=1<4=v_{h_{8}}(h_{9})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{9,11\\}$ then it remains that
$\pi(h_{10})=\\{h_{7},h_{8},h_{10}\\}$. Now $h_{10}$ has j-envy for $h_{9}$,
since $u_{h_{10}}(\pi)=7<10=u_{h_{10}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{9})=1<6=v_{h_{2}}(h_{10})$, and
$v_{h_{11}}(h_{9})=3<4=v_{h_{11}}(h_{10})$.

      * *

If $\\{h_{i_{4}},h_{i_{5}}\\}=\\{10,11\\}$ then it remains that
$\pi(h_{7})=\\{h_{7},h_{8},h_{9}\\}$. Now $h_{10}$ has j-envy for $h_{7}$,
since $u_{h_{10}}(\pi)=10<11=u_{h_{10}}(\\{h_{8},h_{9}\\})$,
$v_{h_{8}}(h_{7})=5<6=v_{h_{8}}(h_{10})$, and
$v_{h_{9}}(h_{7})=3<5=v_{h_{9}}(h_{10})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{5,9\\}$. It follows that $h_{3}$ has j-envy for
$h_{9}$, since $u_{h_{3}}(\pi)=2<8=u_{h_{3}}(\\{h_{4},h_{5}\\})$,
$v_{h_{4}}(h_{9})=3<5=v_{h_{4}}(h_{3})$, and
$v_{h_{5}}(h_{9})=1<3=v_{h_{5}}(h_{3})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,7\\}$. Consider $h_{5}$. Since
$h_{3}\notin\pi(h_{5})$, $h_{4}\notin\pi(h_{5})$, $h_{6}\notin\pi(h_{5})$, and
$h_{7}\notin\pi(h_{5})$ by the design of $H$ it must be that
$u_{h_{5}}(\pi)\leq 4$. It follows that $h_{5}$ has j-envy for $h_{7}$, since
$u_{h_{5}}(\pi)\leq 4<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{7})=1<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{7})=4<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,8\\}$. Consider $h_{5}$. If
$u_{h_{5}}(\pi)\leq 4$ then $h_{5}$ has j-envy for $\alpha_{j}$, since
$u_{h_{5}}(\pi)\leq 4<5=u_{h_{2}}(\\{h_{1},h_{3}\\})$,
$v_{h_{1}}(\alpha_{j})=0<2=v_{h_{1}}(h_{5})$, and
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{5})$. It follows that
$u_{h_{5}}(\pi)\geq 5$. Since $h_{3}\notin\pi(h_{5})$,
$h_{4}\notin\pi(h_{5})$, and $h_{6}\notin\pi(h_{5})$, the only possibility is
that $\pi(h_{5})=\\{h_{5},h_{7},h_{10}\\}$. It remains that
$\pi(h_{2})=\\{h_{2},h_{9},h_{11}\\}$. Now $h_{10}$ has j-envy for $h_{9}$,
since $u_{h_{10}}(\pi)=4<10=u_{h_{10}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{9})=1<6=v_{h_{2}}(h_{10})$, and
$v_{h_{11}}(h_{9})=3<4=v_{h_{11}}(h_{10})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,9\\}$. Consider $h_{5}$. Since
$h_{3}\notin\pi(h_{5})$, $h_{4}\notin\pi(h_{5})$, and $h_{6}\notin\pi(h_{5})$
by the design of $H$ it must be that $u_{h_{5}}(\pi)\leq 6$. It follows that
$h_{5}$ has j-envy for $h_{9}$, since $u_{h_{5}}(\pi)\leq
6<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$, $v_{h_{4}}(h_{9})=3<4=v_{h_{4}}(h_{5})$,
and $v_{h_{6}}(h_{9})=1<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,10\\}$. Consider $h_{5}$. Since
$h_{3}\notin\pi(h_{5})$, $h_{4}\notin\pi(h_{5})$, $h_{6}\notin\pi(h_{5})$, and
$h_{10}\notin\pi(h_{5})$ by the design of $H$ it must be that
$u_{h_{5}}(\pi)\leq 4$. It follows that $h_{5}$ has j-envy for $h_{10}$, since
$u_{h_{5}}(\pi)\leq 4<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{10})=1<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{10})=1<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{i_{2},i_{3}\\}=\\{6,11\\}$. Consider $h_{5}$. Since
$h_{3}\notin\pi(h_{5})$, $h_{4}\notin\pi(h_{5})$, and $h_{6}\notin\pi(h_{5})$
by the design of $H$ it must be that $u_{h_{5}}(\pi)\leq 6$. It follows that
$h_{5}$ has j-envy for $h_{11}$, since $u_{h_{5}}(\pi)\leq
6<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$, $v_{h_{4}}(h_{11})=1<4=v_{h_{4}}(h_{5})$,
and $v_{h_{6}}(h_{11})=3<5=v_{h_{6}}(h_{5})$.∎

######  Lemma 45.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$,
$\sigma(H,\pi)=4$, and $u_{h_{1}}(\pi)=4$ then $H$ has an open configuration
in $\pi$.

###### Proof.

Suppose to the contrary that $\sigma(H,\pi)=4$, $u_{h_{1}}(\pi)=4$, and $H$
has an open configuration in $\pi$. Since $\sigma(H,\pi)=4$ it must be that
three triples in $\pi$ each contain exactly three agents in $H$ and one triple
in $\pi$ contains exactly two agents in $H$. Suppose $t_{1},t_{2},t_{3}\in\pi$
each contain exactly three agents in $H$ and $t_{4}\in\pi$ contains exactly
two agents in $H$. Since $u_{h_{1}}(\pi)=4$, by the design of $H$ it follows
that $\pi(h_{1})$ contains two agents in $H\setminus\\{h_{1}\\}$ and therefore
$h_{1}\notin t_{4}$. It follows that
$t_{4}=\\{h_{i_{1}},h_{i_{2}},\alpha_{j}\\}$ where $2\leq i_{1},i_{2}\leq 11$
and $\alpha_{j}\in(N\setminus H)$. We use a case analysis to prove a
contradiction occurs for each possible assignment of
$\\{h_{i_{1}},h_{i_{2}}\\}$ where $2\leq i_{1},i_{2}\leq 11$.

As before, in the proof of Lemma 44, the symmetries of $H$ allow us to shorten
the case analysis. Recall that the structure of the valuations between agents
$H\setminus\\{h_{1}\\}$ has five symmetries. It follows that for any possible
assignment of $\\{{i_{1}},{i_{2}}\\}$ there exist in total five symmetric
assignments, where the case analysis for one assignment is symmetric to the
case analysis for the other four assignments. Since there are
$\binom{10}{2}=45$ possible assignments of $\\{{i_{1}},{i_{2}}\\}$ where
$2\leq i_{1},i_{2}\leq 11$ and five symmetries we need only consider the nine
assignments $\\{2,3\\}$, $\\{2,4\\}$, $\\{2,5\\}$, $\\{2,6\\}$, $\\{2,7\\}$,
$\\{3,4\\}$, $\\{3,5\\}$, $\\{3,6\\}$, $\\{3,7\\}$, of which no two are
symmetric.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{2,3\\}$. Since $h_{2}\notin\pi(h_{4})$ and
$h_{3}\notin\pi(h_{4})$ it must be that $u_{h_{4}}(\pi)\leq 10$. It follows
that $h_{4}$ has j-envy for $\alpha_{j}$ since $u_{h_{4}}(\pi)\leq
10<12=u_{h_{4}}(\\{h_{2},h_{3}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{3}}(\alpha_{j})=0<5=v_{h_{3}}(h_{4})$. This contradicts the supposition
that $\pi$ is j-envy-free. The following proofs concerning other possible
assignments of $\\{{i_{1}},{i_{2}}\\}$ are similar in technique although in
some cases we must make further deductions about the utilities of agents in
$H$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{2,4\\}$. Since $h_{2}\notin\pi(h_{3})$ and
$h_{4}\notin\pi(h_{3})$ it follows that $u_{h_{3}}(\pi)\leq 6$. It then
follows that $h_{3}$ has j-envy for $\alpha_{j}$ since $u_{h_{3}}(\pi)\leq
6<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(\alpha_{j})=0<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(\alpha_{j})=0<5=v_{h_{4}}(h_{3})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{2,5\\}$. If $u_{h_{4}}(\pi)\leq 9$ then
$h_{4}$ has j-envy for $\alpha_{j}$, since $u_{h_{4}}(\pi)\leq
9<10=u_{h_{4}}(\\{h_{2},h_{5}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{5}}(\alpha_{j})=0<4=v_{h_{5}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 10$. The only possibility is that
$\pi(h_{4})=\\{h_{3},h_{4},h_{6}\\}$. Now $h_{3}$ has j-envy for $\alpha_{j}$
since $u_{h_{3}}(\pi)=6<7=u_{h_{3}}(\\{h_{2},h_{5}\\})$,
$v_{h_{2}}(\alpha_{j})=0<4=v_{h_{2}}(h_{3})$, and
$v_{h_{5}}(\alpha_{j})=0<3=v_{h_{5}}(h_{3})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{2,6\\}$. Since $h_{2}\notin\pi(h_{4})$ and
$h_{6}\notin\pi(h_{4})$ it follows that $u_{h_{4}}(\pi)\leq 9$. Now $h_{4}$
has j-envy for $\alpha_{j}$ since $u_{h_{4}}(\pi)\leq
9<12=u_{h_{4}}(\\{h_{2},h_{6}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{6}}(\alpha_{j})=0<6=v_{h_{6}}(h_{4})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{2,7\\}$. If $u_{h_{4}}(\pi)\leq 6$ then
$h_{4}$ has j-envy for $\alpha_{j}$, since $u_{h_{4}}(\pi)\leq
6<7=u_{h_{4}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 7$. By the design of $H$, it follows that $\pi(h_{4})$
contains three agents in $H$. Since $t_{4}=\\{h_{2},h_{7},\alpha_{j}\\}$ it
follows that $\pi(h_{4})=\\{h_{4},h_{i_{3}},h_{i_{4}}\\}$ where
$\\{i_{3},i_{4}\\}\subset\\{1,3,5,6,8,9,10,11\\}$. Recall that
$v_{h_{4}}(h_{1})=2$, $v_{h_{4}}(h_{3})=5$, $v_{h_{4}}(h_{5})=4$,
$v_{h_{4}}(h_{6})=6$, $v_{h_{4}}(h_{8})=1$, $v_{h_{4}}(h_{9})=3$,
$v_{h_{4}}(h_{10})=1$, and $v_{h_{4}}(h_{11})=1$. Since we established
$u_{h_{4}}(\pi)\geq 7$ it follows that there are $11$ possibilities:
$\\{{i_{3}},{i_{4}}\\}=\\{1,3\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{1,6\\}$,
$\\{{i_{3}},{i_{4}}\\}=\\{3,5\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{3,6\\}$,
$\\{{i_{3}},{i_{4}}\\}=\\{3,9\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{5,6\\}$,
$\\{{i_{3}},{i_{4}}\\}=\\{5,9\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{6,8\\}$,
$\\{{i_{3}},{i_{4}}\\}=\\{6,9\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{6,10\\}$, and
$\\{{i_{3}},{i_{4}}\\}=\\{6,11\\}$, which we shall now consider.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{1,3\\}$. It follows that $h_{2}$ has j-envy
for $h_{1}$ since $u_{h_{2}}(\pi)=3<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(h_{1})=2<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(h_{1})=2<6=v_{h_{4}}(h_{2})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{1,6\\}$. Consider $h_{5}$. It must be that
$u_{h_{5}}(\pi)\leq 6$. Now $h_{5}$ has j-envy for $h_{1}$ since
$u_{h_{5}}(\pi)\leq 6<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{1})=2<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{1})=2<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{3,5\\}$. It follows that $h_{2}$ has j-envy
for $h_{5}$ since $u_{h_{2}}(\pi)=3<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(h_{5})=3<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(h_{5})=4<6=v_{h_{4}}(h_{2})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{3,6\\}$. In this case, consider
$\pi(h_{1})$. Since $h_{1}\notin t_{4}$ it follows that $\pi(h_{1})$ contains
three agents in $H$. Suppose $\pi(h_{1})=\\{h_{1},h_{i_{5}},h_{i_{6}}\\}$
where $2\leq{i_{5}},{i_{6}}\leq 11$. Since we have established
$\pi(h_{2})=\\{h_{2},h_{7},\alpha_{j}\\}$ and
$\pi(h_{4})=\\{h_{3},h_{4},h_{6}\\}$ it follows that
$\\{h_{i_{5}},h_{i_{6}}\\}\subset\\{5,8,9,10,11\\}$. Thus there are
$\binom{5}{2}=10$ possible assignments of $\\{h_{i_{5}},h_{i_{6}}\\}$, which
we shall now consider.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,8\\}$ then $h_{7}$ has j-envy for $h_{1}$
since $u_{h_{7}}(\pi)=3<8=u_{h_{7}}(\\{h_{5},h_{8}\\})$,
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{7})$, and
$v_{h_{8}}(h_{1})=2<5=v_{h_{8}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,9\\}$ then $h_{7}$ has j-envy for $h_{1}$
since $u_{h_{7}}(\pi)=3<6=u_{h_{7}}(\\{h_{5},h_{9}\\})$,
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{7})$, and
$v_{h_{9}}(h_{1})=2<3=v_{h_{9}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,10\\}$ then $u_{h_{10}}(\pi)=5$. It follows
that $h_{10}$ has j-envy for $\alpha_{j}$ since
$u_{h_{10}}(\pi)=5<7=u_{h_{10}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{10})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{10})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,11\\}$ then $u_{h_{11}}(\pi)=3$. It follows
that $h_{11}$ has j-envy for $\alpha_{j}$ since
$u_{h_{11}}(\pi)=3<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,9\\}$ then $h_{7}$ has j-envy for $h_{1}$
since $u_{h_{7}}(\pi)=3<8=u_{h_{7}}(\\{h_{8},h_{9}\\})$,
$v_{h_{8}}(h_{1})=2<5=v_{h_{8}}(h_{7})$, and
$v_{h_{9}}(h_{1})=2<3=v_{h_{9}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,10\\}$ then it remains that
$\pi(h_{9})=\\{h_{5},h_{9},h_{11}\\}$ and thus
$u_{h_{9}}(\pi)=u_{\\{h_{5},h_{11}\\}}=4$. It follows that $h_{9}$ has j-envy
for $h_{1}$ since $u_{h_{9}}(\pi)=4<9=u_{h_{9}}(\\{h_{8},h_{10}\\})$,
$v_{h_{8}}(h_{1})=2<4=v_{h_{8}}(h_{9})$, and
$v_{h_{10}}(h_{1})=2<5=v_{h_{10}}(h_{9})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,11\\}$ then $u_{h_{11}}(\pi)=3$. It follows
that $h_{11}$ has j-envy for $\alpha_{j}$ since
$u_{h_{11}}(\pi)=3<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{9,10\\}$ then it remains that
$\pi(h_{9})=\\{h_{5},h_{8},h_{11}\\}$ and thus
$u_{h_{11}}(\pi)=u_{\\{h_{5},h_{8}\\}}=2$. It follows that $h_{11}$ has j-envy
for $\alpha_{j}$ since $u_{h_{11}}(\pi)=2<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{9,11\\}$ then $u_{h_{11}}(\pi)=5$. It follows
that $h_{11}$ has j-envy for $\alpha_{j}$ since
$u_{h_{11}}(\pi)=5<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{10,11\\}$ then $h_{2}$ has j-envy for $h_{1}$
since $u_{h_{2}}(\pi)=3<11=u_{h_{2}}(\\{h_{10},h_{11}\\})$,
$v_{h_{10}}(h_{1})=2<6=v_{h_{10}}(h_{2})$, and
$v_{h_{11}}(h_{1})=2<5=v_{h_{11}}(h_{2})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{3,9\\}$. It follows that $h_{2}$ has j-envy
for $h_{9}$ since $u_{h_{2}}(\pi)=3<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(h_{9})=1<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(h_{9})=3<6=v_{h_{4}}(h_{2})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{5,6\\}$. Consider $h_{3}$. If
$u_{h_{3}}(\pi)\leq 4$ then $h_{3}$ has j-envy for $\alpha_{j}$, since
$u_{h_{3}}(\pi)\leq 4<5=u_{h_{3}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<4=v_{h_{2}}(h_{3})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{3})$. It follows that
$u_{h_{3}}(\pi)\geq 5$. We have established that $h_{4}\notin\pi(h_{3})$,
$h_{5}\notin\pi(h_{3})$ and $h_{2}\notin\pi(h_{3})$ so, by the design of $H$,
there are three possibilities: either $\pi(h_{3})=\\{h_{1},h_{3},h_{8}\\}$,
$\pi(h_{3})=\\{h_{1},h_{3},h_{11}\\}$, or
$\pi(h_{3})=\\{h_{3},h_{8},h_{11}\\}$.

      * *

If $\pi(h_{3})=\\{h_{1},h_{3},h_{8}\\}$ then $u_{h_{8}}(\pi)=5$. It follows
that $h_{8}$ has j-envy for $\alpha_{j}$, since
$u_{h_{8}}(\pi)=5<6=u_{h_{8}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<1=v_{h_{2}}(h_{8})$, and
$v_{h_{7}}(\alpha_{j})=0<5=v_{h_{7}}(h_{8})$.

      * *

If $\pi(h_{3})=\\{h_{1},h_{3},h_{11}\\}$ then $u_{h_{11}}(\pi)=5$. It follows
that $h_{11}$ has j-envy for $\alpha_{j}$, since
$u_{h_{11}}(\pi)=5<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\pi(h_{3})=\\{h_{3},h_{8},h_{11}\\}$ then $u_{h_{8}}(\pi)=4$. It follows
that $h_{8}$ has j-envy for $\alpha_{j}$, since
$u_{h_{8}}(\pi)=4<6=u_{h_{8}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<1=v_{h_{2}}(h_{8})$, and
$v_{h_{7}}(\alpha_{j})=0<5=v_{h_{7}}(h_{8})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{5,9\\}$. Consider $h_{6}$. It must be that
$u_{h_{6}}(\pi)\leq 9$. Now $h_{6}$ has j-envy for $h_{9}$ since
$u_{h_{6}}(\pi)\leq 9<11=u_{h_{6}}(\\{h_{4},h_{5}\\})$,
$v_{h_{4}}(h_{9})=3<6=v_{h_{4}}(h_{6})$, and
$v_{h_{5}}(h_{9})=1<5=v_{h_{5}}(h_{6})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,8\\}$. Consider $h_{10}$. If
$u_{h_{10}}(\pi)\leq 6$ then $h_{10}$ has j-envy for $\alpha_{j}$, since
$u_{h_{10}}(\pi)\leq 6<7=u_{h_{10}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<6=v_{h_{2}}(h_{10})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{10})$. It follows that
$u_{h_{10}}(\pi)\geq 7$. We have established that $h_{2}\notin\pi(h_{10})$ and
$h_{8}\notin\pi(h_{10})$ so, by the design of $H$, there are four
possibilities: either $\pi(h_{10})=\\{h_{1},h_{9},h_{10}\\}$,
$\pi(h_{10})=\\{h_{5},h_{9},h_{10}\\}$,
$\pi(h_{10})=\\{h_{5},h_{10},h_{11}\\}$, or
$\pi(h_{3})=\\{h_{9},h_{10},h_{11}\\}$.

      * *

If $\pi(h_{10})=\\{h_{1},h_{9},h_{10}\\}$ then $h_{8}$ has j-envy for $h_{1}$,
since $u_{h_{8}}(\pi)=7<10=u_{h_{8}}(\\{h_{9},h_{10}\\})$,
$v_{h_{9}}(h_{1})=2<4=v_{h_{9}}(h_{8})$, and
$v_{h_{10}}(h_{1})=2<6=v_{h_{10}}(h_{8})$.

      * *

If $\pi(h_{10})=\\{h_{5},h_{9},h_{10}\\}$ then $h_{8}$ has j-envy for $h_{5}$,
since $u_{h_{8}}(\pi)=7<10=u_{h_{8}}(\\{h_{9},h_{10}\\})$,
$v_{h_{9}}(h_{5})=1<4=v_{h_{9}}(h_{8})$, and
$v_{h_{10}}(h_{5})=3<6=v_{h_{10}}(h_{8})$.

      * *

If $\pi(h_{10})=\\{h_{5},h_{10},h_{11}\\}$ then $u_{h_{11}}(\pi)=5$. It
follows that $h_{11}$ has j-envy for $\alpha_{j}$, since
$u_{h_{11}}(\pi)=5<6=u_{h_{11}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j})=0<5=v_{h_{2}}(h_{11})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{11})$.

      * *

If $\pi(h_{3})=\\{h_{9},h_{10},h_{11}\\}$ then $h_{8}$ has j-envy for
$h_{11}$, since $u_{h_{8}}(\pi)=7<10=u_{h_{8}}(\\{h_{9},h_{10}\\})$,
$v_{h_{9}}(h_{11})=3<4=v_{h_{9}}(h_{8})$, and
$v_{h_{10}}(h_{11})=4<6=v_{h_{10}}(h_{8})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,9\\}$. It must be that $u_{h_{5}}(\pi)\leq
6$. Now $h_{5}$ has j-envy for $h_{9}$ since $u_{h_{5}}(\pi)\leq
6<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$, $v_{h_{4}}(h_{9})=3<4=v_{h_{4}}(h_{5})$,
and $v_{h_{6}}(h_{9})=1<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,10\\}$. It must be that
$u_{h_{5}}(\pi)\leq 5$. Now $h_{5}$ has j-envy for $h_{10}$ since
$u_{h_{5}}(\pi)\leq 5<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{10})=1<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{10})=1<5=v_{h_{6}}(h_{5})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,11\\}$. It must be that
$u_{h_{5}}(\pi)\leq 6$. Now $h_{5}$ has j-envy for $h_{11}$ since
$u_{h_{5}}(\pi)\leq 6<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{11})=1<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{11})=3<5=v_{h_{6}}(h_{5})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{3,4\\}$. If $u_{h_{2}}(\pi)\leq 9$ then
$h_{2}$ has j-envy for $\alpha_{j}$, since $u_{h_{2}}(\pi)\leq
9<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(\alpha_{j})=0<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(\alpha_{j})=0<6=v_{h_{4}}(h_{2})$. It follows that
$u_{h_{2}}(\pi)\geq 10$. The only possibility is that
$\pi(h_{2})=\\{h_{2},h_{10},h_{11}\\}$. Now consider $h_{5}$. If
$u_{h_{5}}(\pi)\leq 6$ then $h_{5}$ has j-envy for $\alpha_{j}$, since
$u_{h_{5}}(\pi)\leq 6<7=u_{h_{5}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{5})$, and
$v_{h_{4}}(\alpha_{j})=0<4=v_{h_{4}}(h_{5})$. It follows that
$u_{h_{5}}(\pi)\geq 7$. Since we have established
$\pi(h_{2})=\\{h_{2},h_{10},h_{11}\\}$ and
$t_{4}=\\{h_{3},h_{4},\alpha_{j}\\}$, there are just two possibilities: either
$\pi(h_{5})=\\{h_{1},h_{5},h_{6}\\}$ or $\pi(h_{5})=\\{h_{5},h_{6},h_{7}\\}$.

    * –

If $\pi(h_{5})=\\{h_{1},h_{5},h_{6}\\}$ then $h_{4}$ has j-envy for $h_{1}$
since $u_{h_{4}}(\pi)=5<10=u_{h_{4}}(\\{h_{5},h_{6}\\})$,
$v_{h_{5}}(h_{1})=2<4=v_{h_{5}}(h_{4})$, and
$v_{h_{6}}(h_{1})=2<6=v_{h_{6}}(h_{4})$.

    * –

If $\pi(h_{5})=\\{h_{5},h_{6},h_{7}\\}$ then $h_{4}$ has j-envy for $h_{7}$
since $u_{h_{4}}(\pi)=5<10=u_{h_{4}}(\\{h_{5},h_{6}\\})$,
$v_{h_{5}}(h_{7})=3<4=v_{h_{5}}(h_{4})$, and
$v_{h_{6}}(h_{7})=4<6=v_{h_{6}}(h_{4})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{3,5\\}$. If $u_{h_{4}}(\pi)\leq 8$ then
$h_{4}$ has j-envy for $\alpha_{j}$, since $u_{h_{4}}(\pi)\leq
8<9=u_{h_{4}}(\\{h_{3},h_{5}\\})$,
$v_{h_{3}}(\alpha_{j})=0<5=v_{h_{3}}(h_{4})$, and
$v_{h_{5}}(\alpha_{j})=0<4=v_{h_{5}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 9$. There are three possibilities: either
$\pi(h_{4})=\\{h_{2},h_{4},h_{6}\\}$, $\pi(h_{4})=\\{h_{2},h_{4},h_{9}\\}$, or
$\pi(h_{4})=\\{h_{4},h_{6},h_{9}\\}$.

    * –

Suppose $\pi(h_{4})=\\{h_{2},h_{4},h_{6}\\}$. In this case, consider
$\pi(h_{1})$. Since $h_{1}\notin t_{4}$ it follows that $\pi(h_{1})$ contains
three agents in $H$. Suppose $\pi(h_{1})=\\{h_{1},h_{i_{5}},h_{i_{6}}\\}$
where $1\leq{i_{5}},{i_{6}}\leq 11$. Since we have established
$\pi(h_{3})=\\{h_{3},h_{5},\alpha_{j}\\}$ and
$\pi(h_{2})=\\{h_{2},h_{4},h_{6}\\}$ it follows that
$\\{h_{i_{5}},h_{i_{6}}\\}\subset\\{7,8,9,10,11\\}$. Thus there are
$\binom{5}{2}=10$ possible assignments of $\\{h_{i_{5}},h_{i_{6}}\\}$, which
we shall now consider.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{7,8\\}$ then $h_{6}$ has j-envy for $h_{1}$,
since $u_{h_{6}}(\pi)=7<10=u_{h_{6}}(\\{h_{7},h_{8}\\})$,
$v_{h_{7}}(h_{1})=2<4=v_{h_{7}}(h_{6})$, and
$v_{h_{8}}(h_{1})=2<6=v_{h_{8}}(h_{6})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{7,9\\}$ then it remains that
$\pi(h_{8})=\\{h_{8},h_{10},h_{11}\\}$. It follows that $h_{8}$ has j-envy for
$h_{1}$, since $u_{h_{8}}(\pi)=7<9=u_{h_{8}}(\\{h_{7},h_{9}\\})$,
$v_{h_{7}}(h_{1})=2<5=v_{h_{7}}(h_{8})$, and
$v_{h_{9}}(h_{1})=2<4=v_{h_{9}}(h_{8})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{7,10\\}$ then $h_{7}$ has j-envy for
$\alpha_{j}$, since $u_{h_{7}}(\pi)=3<4=u_{h_{7}}(\\{h_{3},h_{5}\\})$,
$v_{h_{3}}(\alpha_{j})=0<1=v_{h_{3}}(h_{7})$, and
$v_{h_{5}}(\alpha_{j})=0<3=v_{h_{5}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{7,11\\}$ then $h_{7}$ has j-envy for
$\alpha_{j}$, since $u_{h_{7}}(\pi)=3<4=u_{h_{7}}(\\{h_{3},h_{5}\\})$,
$v_{h_{3}}(\alpha_{j})=0<1=v_{h_{3}}(h_{7})$, and
$v_{h_{5}}(\alpha_{j})=0<3=v_{h_{5}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,9\\}$ then it remains that
$\pi(h_{7})=\\{h_{7},h_{10},h_{11}\\}$. It follows that $h_{7}$ has j-envy for
$h_{1}$, since $u_{h_{7}}(\pi)=2<8=u_{h_{7}}(\\{h_{8},h_{9}\\})$,
$v_{h_{8}}(h_{1})=2<5=v_{h_{8}}(h_{7})$, and
$v_{h_{9}}(h_{1})=2<3=v_{h_{9}}(h_{7})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,10\\}$ then it remains that
$\pi(h_{9})=\\{h_{7},h_{9},h_{11}\\}$. It follows that $h_{9}$ has j-envy for
$h_{1}$, since $u_{h_{9}}(\pi)=6<9=u_{h_{9}}(\\{h_{8},h_{10}\\})$,
$v_{h_{8}}(h_{1})=2<4=v_{h_{8}}(h_{9})$, and
$v_{h_{10}}(h_{1})=2<5=v_{h_{10}}(h_{9})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{8,11\\}$ then $h_{11}$ has j-envy for
$\alpha_{j}$, since $u_{h_{11}}(\pi)=3<4=u_{h_{11}}(\\{h_{3},h_{5}\\})$,
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{11})$, and
$v_{h_{5}}(\alpha_{j})=0<1=v_{h_{5}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{9,10\\}$ then it remains that
$\pi(h_{11})=\\{h_{7},h_{8},h_{11}\\}$. It follows that $h_{11}$ has j-envy
for $h_{1}$, since $u_{h_{11}}(\pi)=2<7=u_{h_{11}}(\\{h_{9},h_{10}\\})$,
$v_{h_{9}}(h_{1})=2<3=v_{h_{9}}(h_{11})$, and
$v_{h_{10}}(h_{1})=2<4=v_{h_{10}}(h_{11})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{9,11\\}$ then it remains that
$\pi(h_{10})=\\{h_{7},h_{8},h_{10}\\}$. It follows that $h_{10}$ has j-envy
for $h_{1}$, since $u_{h_{10}}(\pi)=7<9=u_{h_{10}}(\\{h_{9},h_{11}\\})$,
$v_{h_{9}}(h_{1})=2<5=v_{h_{9}}(h_{10})$, and
$v_{h_{11}}(h_{1})=2<4=v_{h_{11}}(h_{10})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{10,11\\}$ then $h_{2}$ has j-envy for
$h_{1}$, since $u_{h_{2}}(\pi)=7<11=u_{h_{2}}(\\{h_{10},h_{11}\\})$,
$v_{h_{10}}(h_{1})=2<6=v_{h_{10}}(h_{2})$, and
$v_{h_{11}}(h_{1})=2<5=v_{h_{11}}(h_{2})$.

    * –

Suppose $\pi(h_{4})=\\{h_{2},h_{4},h_{9}\\}$. It follows that $h_{3}$ has
j-envy for $h_{9}$, since $u_{h_{3}}(\pi)=3<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{9})=1<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{9})=3<5=v_{h_{4}}(h_{3})$.

    * –

Suppose $\pi(h_{4})=\\{h_{4},h_{6},h_{9}\\}$. It follows that $h_{5}$ has
j-envy for $h_{9}$, since $u_{h_{5}}(\pi)=3<9=u_{h_{5}}(\\{h_{4},h_{6}\\})$,
$v_{h_{4}}(h_{9})=3<4=v_{h_{4}}(h_{5})$, and
$v_{h_{6}}(h_{9})=1<5=v_{h_{6}}(h_{5})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{3,6\\}$. It must be that $u_{h_{4}}(\pi)\leq
10$. It follows that $h_{4}$ has j-envy for $\alpha_{j}$ since
$u_{h_{4}}(\pi)\leq 10<11=u_{h_{4}}(\\{h_{3},h_{6}\\})$,
$v_{h_{3}}(\alpha_{j})=0<5=v_{h_{3}}(h_{4})$, and
$v_{h_{6}}(\alpha_{j})=0<6=v_{h_{6}}(h_{4})$.

  * •

Suppose $\\{{i_{1}},{i_{2}}\\}=\\{3,7\\}$. If $u_{h_{8}}(\pi)\leq 7$ then
$h_{8}$ has j-envy for $\alpha_{j}$, since $u_{h_{8}}(\pi)\leq
7<8=u_{h_{8}}(\\{h_{3},h_{7}\\})$,
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{8})$, and
$v_{h_{7}}(\alpha_{j})=0<5=v_{h_{7}}(h_{8})$. It follows that
$u_{h_{8}}(\pi)\geq 8$. By the design of $H$, it follows that $\pi(h_{8})$
contains three agents in $H$. Since $t_{4}=\\{h_{3},h_{7},\alpha_{j}\\}$ it
must be that $\pi(h_{8})=\\{h_{8},h_{i_{3}},h_{i_{4}}\\}$ where
$\\{i_{3},i_{4}\\}\subset\\{1,2,4,5,6,9,10,11\\}$. Recall that
$v_{h_{8}}(h_{1})=2$, $v_{h_{8}}(h_{2})=1$, $v_{h_{8}}(h_{4})=1$,
$v_{h_{8}}(h_{5})=1$, $v_{h_{8}}(h_{6})=6$, $v_{h_{8}}(h_{9})=4$,
$v_{h_{8}}(h_{10})=6$, and $v_{h_{8}}(h_{11})=1$. Since we established
$u_{h_{8}}(\pi)\geq 8$ it follows that there are five possibilities:
$\\{{i_{3}},{i_{4}}\\}=\\{1,6\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{1,10\\}$,
$\\{{i_{3}},{i_{4}}\\}=\\{6,9\\}$, $\\{{i_{3}},{i_{4}}\\}=\\{6,10\\}$, and
$\\{{i_{3}},{i_{4}}\\}=\\{9,10\\}$, which we shall now consider.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{1,6\\}$. It follows that $h_{7}$ has j-envy
for $h_{1}$, since $u_{h_{7}}(\pi)=1<9=u_{h_{7}}(\\{h_{6},h_{8}\\})$,
$v_{h_{6}}(h_{1})=2<4=v_{h_{6}}(h_{7})$, and
$v_{h_{8}}(h_{1})=2<5=v_{h_{8}}(h_{7})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{1,10\\}$. Consider $h_{9}$. It follows that
$u_{h_{9}}(\pi)\leq 6$. Now $h_{9}$ has j-envy for $h_{1}$, since
$u_{h_{9}}(\pi)\leq 6<9=u_{h_{9}}(\\{h_{8},h_{10}\\})$,
$v_{h_{8}}(h_{1})=2<4=v_{h_{8}}(h_{9})$, and
$v_{h_{10}}(h_{1})=2<5=v_{h_{10}}(h_{9})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,9\\}$. It follows that $h_{7}$ has j-envy
for $h_{9}$, since $u_{h_{7}}(\pi)=1<9=u_{h_{7}}(\\{h_{6},h_{8}\\})$,
$v_{h_{6}}(h_{9})=1<4=v_{h_{6}}(h_{7})$, and
$v_{h_{8}}(h_{9})=4<5=v_{h_{8}}(h_{7})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{6,10\\}$. In this case, consider
$\pi(h_{1})$. Since $h_{1}\notin t_{4}$ it follows that $\pi(h_{1})$ contains
three agents in $H$. Suppose $\pi(h_{1})=\\{h_{1},h_{i_{5}},h_{i_{6}}\\}$
where $2\leq i_{5},i_{6}\leq 11$. Since we have established
$\pi(h_{3})=\\{h_{3},h_{7},\alpha_{j}\\}$ and
$\pi(h_{6})=\\{h_{6},h_{8},h_{10}\\}$ it follows that
$\\{h_{i_{5}},h_{i_{6}}\\}\subset\\{2,4,5,9,11\\}$. Thus there are
$\binom{5}{2}=10$ possible assignments of $\\{h_{i_{5}},h_{i_{6}}\\}$, which
we shall now consider.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{2,4\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{1})=2<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{1})=2<5=v_{h_{4}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{2,5\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<7=u_{h_{3}}(\\{h_{2},h_{5}\\})$,
$v_{h_{2}}(h_{1})=2<4=v_{h_{2}}(h_{3})$, and
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{2,9\\}$ then it remains that
$\pi(h_{11})=\\{h_{4},h_{5},h_{11}\\}$. Now $h_{3}$ has j-envy for $h_{11}$,
since $u_{h_{3}}(\pi)=1<8=u_{h_{3}}(\\{h_{4},h_{5}\\})$,
$v_{h_{4}}(h_{11})=1<5=v_{h_{4}}(h_{3})$, and
$v_{h_{5}}(h_{11})=1<3=v_{h_{5}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{2,11\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<7=u_{h_{3}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{1})=2<4=v_{h_{2}}(h_{3})$, and
$v_{h_{11}}(h_{1})=2<3=v_{h_{11}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{4,5\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<8=u_{h_{3}}(\\{h_{5},h_{5}\\})$,
$v_{h_{4}}(h_{1})=2<5=v_{h_{4}}(h_{3})$, and
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{4,9\\}$ then $h_{4}$ has j-envy for
$\alpha_{j}$, since $u_{h_{4}}(\pi)=5<6=u_{h_{4}}(\\{h_{3},h_{7}\\})$,
$v_{h_{3}}(\alpha_{j})=0<5=v_{h_{3}}(h_{4})$, and
$v_{h_{7}}(\alpha_{j})=0<1=v_{h_{7}}(h_{4})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{4,11\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<8=u_{h_{3}}(\\{h_{4},h_{11}\\})$,
$v_{h_{4}}(h_{1})=2<5=v_{h_{4}}(h_{3})$, and
$v_{h_{11}}(h_{1})=2<3=v_{h_{11}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,9\\}$ then $h_{5}$ has j-envy for
$\alpha_{j}$, since $u_{h_{5}}(\pi)=3<6=u_{h_{5}}(\\{h_{3},h_{7}\\})$,
$v_{h_{3}}(\alpha_{j})=0<3=v_{h_{3}}(h_{5})$, and
$v_{h_{7}}(\alpha_{j})=0<3=v_{h_{7}}(h_{5})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{5,11\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<6=u_{h_{3}}(\\{h_{5},h_{11}\\})$,
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{3})$, and
$v_{h_{11}}(h_{1})=2<3=v_{h_{11}}(h_{3})$.

      * *

If $\\{h_{i_{5}},h_{i_{6}}\\}=\\{9,11\\}$ then $h_{10}$ has j-envy for
$h_{1}$, since $u_{h_{10}}(\pi)=7<9=u_{h_{10}}(\\{h_{9},h_{11}\\})$,
$v_{h_{9}}(h_{1})=2<5=v_{h_{9}}(h_{10})$, and
$v_{h_{11}}(h_{1})=2<4=v_{h_{11}}(h_{10})$.

    * –

Suppose $\\{{i_{3}},{i_{4}}\\}=\\{9,10\\}$. Consider $h_{2}$. If
$u_{h_{2}}(\pi)\leq 6$ then $h_{2}$ has j-envy for $\alpha_{j}$, since
$u_{h_{2}}(\pi)\leq 6<7=u_{h_{2}}(\\{h_{3},h_{7}\\})$,
$v_{h_{3}}(\alpha_{j})=0<4=v_{h_{3}}(h_{2})$, and
$v_{h_{7}}(\alpha_{j})=0<3=v_{h_{7}}(h_{2})$. It follows that
$u_{h_{2}}(\pi)\geq 7$. We have established that $h_{3}\notin\pi(h_{2})$,
$h_{7}\notin\pi(h_{2})$, and $h_{10}\notin\pi(h_{2})$ so, by the design of
$H$, there are three possibilities: either
$\pi(h_{2})=\\{h_{1},h_{2},h_{4}\\}$, $\pi(h_{2})=\\{h_{1},h_{2},h_{11}\\}$,
or $\pi(h_{2})=\\{h_{2},h_{4},h_{11}\\}$.

      * *

If $\pi(h_{2})=\\{h_{1},h_{2},h_{4}\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(h_{1})=2<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(h_{1})=2<5=v_{h_{4}}(h_{3})$.

      * *

If $\pi(h_{2})=\\{h_{1},h_{2},h_{11}\\}$ then $h_{3}$ has j-envy for $h_{1}$,
since $u_{h_{3}}(\pi)=1<7=u_{h_{3}}(\\{h_{2},h_{11}\\})$,
$v_{h_{2}}(h_{1})=2<4=v_{h_{2}}(h_{3})$, and
$v_{h_{11}}(h_{1})=2<3=v_{h_{11}}(h_{3})$.

      * *

If $\pi(h_{2})=\\{h_{2},h_{4},h_{11}\\}$ then it remains that
$\pi(h_{1})=\\{h_{1},h_{5},h_{6}\\}$. Now $h_{7}$ has j-envy for $h_{1}$,
since $u_{h_{7}}(\pi)=1<7=u_{h_{7}}(\\{h_{5},h_{6}\\})$,
$v_{h_{5}}(h_{1})=2<3=v_{h_{5}}(h_{7})$, and
$v_{h_{6}}(h_{1})=2<4=v_{h_{6}}(h_{7})$.∎

######  Lemma 46.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ and
$\sigma(H,\pi)=4$ then $H$ has an open configuration in $\pi$.

###### Proof.

Suppose $\sigma(H,\pi)=4$. Consider $u_{h_{1}}(\pi)$. By the design of $H$, it
must be that $2\leq u_{h_{1}}(\pi)\leq 4$. If $u_{h_{1}}(\pi)<4$ then Lemma 44
shows that $H$ has an open configuration in $\pi$. If $u_{h_{1}}(\pi)=4$ then
Lemma 45 shows that $H$ has an open configuration in $\pi$. ∎

######  Lemma 47.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ and
$\sigma(H,\pi)=5$ then $H$ has an open configuration in $\pi$.

###### Proof.

Suppose, to the contrary, that $\sigma(H,\pi)=5$ and $H$ has a closed
configuration in $\pi$. Then it must be that four triples in $\pi$ each
contain exactly two agents in $H$ and one triple in $\pi$ contains exactly
three agents in $H$. Suppose $t_{1},t_{2},t_{3},t_{4}\in\pi$ each contain
exactly two agents in $H$ and $t_{5}\in\pi$ contains exactly three agents in
$H$, where $t_{1}=\\{h_{i_{1}},h_{i_{2}},\alpha_{j_{1}}\\}$ where $1\leq
i_{1},i_{2}\leq 11$ and $\alpha_{j_{1}}\in N\setminus H$. We use a case
analysis on $v_{h_{i_{1}}}(h_{i_{2}})$ to prove a contradiction. Note that by
the design of $H$ it must be that $1\leq v_{h_{i_{1}}}(h_{i_{2}})\leq 6$.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=6$. By the symmetry of $H$, assume without
loss of generality that $\\{i_{1},i_{2}\\}=\\{2,4\\}$. It follows that
$u_{h_{3}}(\pi)\leq 6$. Now $h_{3}$ has j-envy for $\alpha_{j_{1}}$ since
$u_{h_{3}}(\pi)\leq 6<9=u_{h_{3}}(\\{h_{2},h_{4}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<4=v_{h_{2}}(h_{3})$, and
$v_{h_{4}}(\alpha_{j_{1}})=0<5=v_{h_{4}}(h_{3})$. This contradicts the
supposition that $\pi$ is j-envy-free. We shall use a similar technique to
prove a contradiction when considering the other cases of
$v_{h_{i_{1}}}(h_{i_{2}})$.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=5$. Assume without loss of generality that
$\\{i_{1},i_{2}\\}=\\{3,4\\}$. If $u_{h_{2}}(\pi)\leq 9$ then $h_{2}$ has
j-envy for $\alpha_{j_{1}}$ since $u_{h_{2}}(\pi)\leq
9<10=u_{h_{2}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(\alpha_{j_{1}})=0<4=v_{h_{3}}(h_{2})$, and
$v_{h_{4}}(\alpha_{j_{1}})=0<6=v_{h_{4}}(h_{2})$. It follows that
$u_{h_{2}}(\pi)\geq 10$. The only possibility is that
$\pi(h_{2})=\\{h_{2},h_{10},h_{11}\\}$. It must be that $\pi(h_{2})=t_{5}$. We
now consider $h_{6}$. Since $h_{6}\notin t_{5}$ it must be that either
$h_{6}\in t_{2}$, $h_{6}\in t_{3}$, or $h_{6}\in t_{4}$. Assume without loss
of generality that $h_{6}\in t_{2}$ and that
$t_{2}=\\{h_{6},h_{i_{3}},\alpha_{j_{2}}\\}$ where $1\leq i_{3}\leq 11$ and
$\alpha_{j_{2}}\in N\setminus H$. If $u_{h_{6}}(\pi)\leq 6$ then $h_{6}$ has
j-envy for $\alpha_{j_{1}}$ since $u_{h_{6}}(\pi)\leq
6<7=u_{h_{6}}(\\{h_{3},h_{4}\\})$,
$v_{h_{3}}(\alpha_{j_{1}})=0<1=v_{h_{3}}(h_{6})$, and
$v_{h_{4}}(\alpha_{j_{1}})=0<6=v_{h_{4}}(h_{6})$. It follows that
$u_{h_{6}}(\pi)\geq 7$. Since $v_{h_{6}}(\alpha_{j_{2}})=0$ it follows that
$v_{h_{6}}(h_{i_{3}})=u_{h_{6}}(\pi)\geq 7$, which is a contradiction.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=4$. Assume without loss of generality that
$\\{i_{1},i_{2}\\}=\\{2,3\\}$. If $u_{h_{4}}(\pi)\leq 10$ then $h_{4}$ has
j-envy for $\alpha_{j_{1}}$ since $u_{h_{4}}(\pi)\leq
10<11=u_{h_{4}}(\\{h_{2},h_{3}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{3}}(\alpha_{j_{1}})=0<5=v_{h_{3}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 11$ which, since $h_{2}\notin\pi(h_{4})$, is impossible.
This contradicts our supposition that $v_{h_{i_{1}}}(h_{i_{2}})=4$.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=3$. We assume without loss of generality
that either $\\{i_{1},i_{2}\\}=\\{3,11\\}$ or $\\{i_{1},i_{2}\\}=\\{2,7\\}$.

    * –

Suppose $\\{i_{1},i_{2}\\}=\\{3,11\\}$. If $u_{h_{2}}(\pi)\leq 8$ then $h_{2}$
has j-envy for $\alpha_{j_{1}}$ since $u_{h_{2}}(\pi)\leq
8<9=u_{h_{2}}(\\{h_{3},h_{11}\\})$,
$v_{h_{3}}(\alpha_{j_{1}})=0<4=v_{h_{3}}(h_{2})$, and
$v_{h_{11}}(\alpha_{j_{1}})=0<5=v_{h_{11}}(h_{2})$. It follows that
$u_{h_{2}}(\pi)\geq 9$. By the design of $H$, it follows that
$\pi(h_{2})=t_{5}$. Now consider $h_{1}$. Since $h_{1}\notin t_{5}$ it must be
that either $h_{1}\in t_{2}$, $h_{1}\in t_{3}$, or $h_{1}\in t_{4}$. Assume
without loss of generality that $h_{1}\in t_{2}$ and that
$t_{2}=\\{h_{1},h_{i_{3}},\alpha_{j_{2}}\\}$ where $1\leq i_{3}\leq 11$ and
$\alpha_{j_{2}}\in N\setminus H$. Since $v_{h_{1}}(\alpha_{j_{2}})=0$ it
follows that $u_{h_{1}}(\pi)=v_{h_{1}}(h_{i_{3}})$. By the design of $H$, it
must be that $v_{h_{1}}(h_{i_{3}})=2$ so $u_{h_{1}}(\pi)=2$. Now $h_{1}$ has
j-envy for $\alpha_{j_{1}}$, since
$u_{h_{1}}(\pi)=2<4=u_{h_{1}}(\\{h_{3},h_{11}\\})$,
$v_{h_{3}}(\alpha_{j_{1}})=0<2=v_{h_{3}}(h_{1})$, and
$v_{h_{11}}(\alpha_{j_{1}})=0<2=v_{h_{11}}(h_{1})$. This is a contradiction.

    * –

Suppose $\\{i_{1},i_{2}\\}=\\{2,7\\}$. Consider $h_{1}$. As before, if
$u_{h_{1}}(\pi)\leq 3$ then $h_{1}$ has j-envy for $\alpha_{j_{1}}$, since
$u_{h_{1}}(\pi)\leq 3<4=u_{h_{1}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<2=v_{h_{2}}(h_{1})$, and
$v_{h_{7}}(\alpha_{j_{1}})=0<2=v_{h_{7}}(h_{1})$. It follows that
$u_{h_{1}}(\pi)\geq 4$. By the design of $H$, it must be that
$\pi(h_{1})=\\{h_{1},h_{i_{3}},h_{i_{4}}\\}$ where $2\leq i_{3},i_{4}\leq 11$.
It follows that $\pi(h_{1})=t_{5}$. Now consider $h_{4}$. If
$u_{h_{4}}(\pi)\leq 6$ then $h_{4}$ has j-envy for $\alpha_{j_{1}}$, since
$u_{h_{4}}(\pi)\leq 6<7=u_{h_{1}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{7}}(\alpha_{j_{1}})=0<1=v_{h_{7}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 7$ so, similarly, $\pi(h_{4})$ must contain three agents
in $H$ and thus $h_{4}\in t_{5}$. Assume without loss of generality that
$h_{4}=h_{i_{3}}$ so $t_{5}=\\{h_{1},h_{4},h_{i_{4}}\\}$. Since
$u_{h_{4}}(\pi)\geq 7$ and $v_{h_{4}}(h_{1})=2$ it must be that
$v_{h_{4}}(h_{i_{4}})\geq 5$ and thus that either $i_{4}=3$ or $i_{4}=6$.
Consider $h_{10}$. If $u_{h_{10}}(\pi)\leq 6$ then $h_{10}$ has j-envy for
$\alpha_{j_{1}}$, since $u_{h_{10}}(\pi)\leq
6<7=u_{h_{10}}(\\{h_{2},h_{7}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<6=v_{h_{2}}(h_{10})$, and
$v_{h_{7}}(\alpha_{j_{1}})=0<1=v_{h_{7}}(h_{10})$. It follows that
$u_{h_{10}}(\pi)\geq 7$. Since $h_{10}\notin t_{5}$ it must be that either
$h_{10}\in t_{2}$, $h_{10}\in t_{3}$, or $h_{10}\in t_{4}$. Assume without
loss of generality that $h_{10}\in t_{2}$ and that
$t_{2}=\\{h_{10},h_{i_{5}},\alpha_{j_{2}}\\}$ where $1\leq i_{5}\leq 11$ and
$\alpha_{j_{2}}\in N\setminus H$. Since $v_{h_{10}}(\alpha_{j_{2}})=0$ it
follows that $v_{h_{10}}(h_{i_{5}})=u_{h_{10}}(\pi)\geq 7$, which is a
contradiction.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=2$. It follows that either $i_{1}=1$ or
$i_{2}=1$. Assume without loss of generality that $i_{1}=1$. Note that $2\leq
i_{2}\leq 11$. Consider $h_{i_{2}}$. Note that since
$v_{h_{i_{2}}}(\alpha_{j_{1}})=0$ it must be that
$u_{h_{i_{2}}}(\pi)=v_{h_{i_{2}}}(h_{1})=2$. By the design of $H$, for each
possible assignment of $i_{2}$, namely $2\leq i_{2}\leq 11$, there exist five
agents $h_{i_{3}},h_{i_{4}},h_{i_{5}},h_{i_{6}},h_{i_{7}}$ such that
$v_{h_{i_{2}}}(h_{i_{k}})>2$ for $3\leq k\leq 7$. A counting argument shows
that at least one of these five agents does not belong to $t_{5}$ and hence
must belong to either $t_{2}$, $t_{3}$, or $t_{4}$. Assume without loss of
generality that $h_{i_{3}}\in t_{2}$ and
$t_{2}=\\{h_{i_{3}},h_{i_{8}},\alpha_{j_{2}}\\}$ where $2\leq i_{8}\leq 11$
and $\alpha_{j_{2}}\in N\setminus H$. Recall that
$v_{h_{i_{2}}}(h_{i_{3}})>2$. By the design of $H$ it follows that
$u_{h_{i_{2}}}(\\{h_{i_{3}},h_{i_{8}}\\})>3$. Now $h_{i_{2}}$ has j-envy for
$\alpha_{j_{2}}$ since
$u_{h_{i_{2}}}(\pi)=2<3<u_{h_{i_{2}}}(\\{h_{i_{3}},h_{i_{8}}\\})$,
$v_{h_{i_{3}}}(\alpha_{j_{2}})=0<1\leq v_{h_{i_{3}}}(h_{i_{2}})$, and
$v_{h_{i_{8}}}(\alpha_{j_{2}})=0<1\leq v_{h_{i_{8}}}(h_{i_{2}})$.

  * •

Suppose $v_{h_{i_{1}}}(h_{i_{2}})=1$. Without loss of generality we assume
that either $\\{i_{1},i_{2}\\}=\\{2,5\\}$ or $\\{i_{1},i_{2}\\}=\\{2,6\\}$.

    * –

Suppose $\\{i_{1},i_{2}\\}=\\{2,5\\}$. If $u_{h_{4}}(\pi)\leq 9$ then $h_{4}$
has j-envy for $\alpha_{j_{1}}$, since $u_{h_{4}}(\pi)\leq
9<10=u_{h_{4}}(\\{h_{2},h_{5}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{5}}(\alpha_{j_{1}})=0<4=v_{h_{5}}(h_{4})$. It follows that
$u_{h_{4}}(\pi)\geq 10$. The only possibility is that
$\pi(h_{4})=\\{h_{3},h_{4},h_{6}\\}$ and hence $\pi(h_{4})=t_{5}$. Consider
$h_{1}$. If $u_{h_{1}}(\pi)\leq 3$ then $h_{1}$ has j-envy for
$\alpha_{j_{1}}$, since $u_{h_{1}}(\pi)\leq 3<4=u_{h_{1}}(\\{h_{2},h_{5}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<2=v_{h_{2}}(h_{1})$, and
$v_{h_{5}}(\alpha_{j_{1}})=0<2=v_{h_{5}}(h_{1})$. It follows that
$u_{h_{1}}(\pi)\geq 4$. By the design of $H$, it follows that $\pi(h_{1})$
must contain three agents in $H$, which is a contradiction since $h_{1}\notin
t_{5}$.

    * –

Suppose $\\{i_{1},i_{2}\\}=\\{2,6\\}$. It follows that $u_{h_{4}}(\pi)\leq 9$
so $h_{4}$ has j-envy for $\alpha_{j_{1}}$ since $u_{h_{4}}(\pi)\leq
9<12=u_{h_{4}}(\\{h_{2},h_{6}\\})$,
$v_{h_{2}}(\alpha_{j_{1}})=0<6=v_{h_{2}}(h_{4})$, and
$v_{h_{6}}(\alpha_{j_{1}})=0<6=v_{h_{6}}(h_{4})$.∎

######  Lemma 48.

If $(N,V)$ contains a j-envy-free partition into triples $\pi$ then $H$ has an
open configuration in $\pi$.

###### Proof.

By definition, $4\leq\sigma(H,\pi)\leq 11$. If $\sigma(H,\pi)\leq 5$ then $H$
has an open configuration in $\pi$, by Lemmas 46 and 47. If
$6\leq\sigma(H,\pi)\leq 11$ then, by a counting argument, at least one triple
in $\pi$ must contain exactly one agent in $H$. In other words, $H$ has an
open configuration in $\pi$. ∎

We have shown, in Lemma 48, that if $(N,V)$ contains a j-envy-free partition
into triples $\pi$ then $H$ has an open configuration in $\pi$. By definition,
some triple $t_{\beta}$ in $\pi$ contains exactly one agent in $H$. Since
$|H|=11$, if $t_{\beta}$ is the only triple in $\pi$ to contain exactly one
agent in $H$ then there must exist some triple in $\pi$ that contains exactly
two agents in $H$. By Lemma 43, this is a contradiction. It follows that at
least two triples in $\pi$ exist that each contain exactly one agent in $H$.
Suppose $t_{\beta},t_{\gamma}\in\pi$ are two such triples and
$t_{\beta}=\\{h_{a_{1}},\alpha_{b_{1}},\alpha_{b_{2}}\\}$ and
$t_{\gamma}=\\{h_{a_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}$.

######  Lemma 49.

If $(N,V)$ contains a j-envy-free partition into triples then
$\\{\alpha_{b_{1}},\allowbreak\alpha_{b_{2}},\alpha_{b_{3}},\allowbreak\alpha_{b_{4}}\\}=L$.

###### Proof.

Suppose for a contradiction that
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\neq L$.

By definition,
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\cap
H=\varnothing$ and
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}\neq L$ it
must be that at least one agent in
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}$ belongs to
$C$. Assume without loss of generality that $\alpha_{b_{1}}\in C$.

We have already shown that $t_{\beta}$ contains exactly one agent in $H$.
Since $v_{\alpha_{b_{1}}}(h_{a_{1}})=0$, by the design of the instance it must
be that $u_{\alpha_{b_{1}}}(\pi)=v_{\alpha_{b_{1}}}(\alpha_{b_{2}})\leq 3$. By
the design of the instance $v_{\alpha_{b_{1}}}(\alpha_{b_{3}})\geq 2$ and
$v_{\alpha_{b_{1}}}(\alpha_{b_{4}})\geq 2$ so
$u_{\alpha_{b_{1}}}(\\{\alpha_{b_{3}},\alpha_{b_{4}}\\})\geq 4$. Now
$\alpha_{b_{1}}$ has j-envy for $h_{a_{2}}$ since $u_{\alpha_{b_{1}}}(\pi)\leq
3<4\leq u_{\alpha_{b_{1}}}(\\{\alpha_{b_{3}},\alpha_{b_{4}}\\})$,
$v_{\alpha_{b_{3}}}(h_{a_{2}})=0<2\leq v_{\alpha_{b_{3}}}(\alpha_{b_{1}})$,
and $v_{\alpha_{b_{4}}}(h_{a_{2}})=0<2\leq
v_{\alpha_{b_{4}}}(\alpha_{b_{1}})$. ∎

######  Lemma 50.

If $(N,V)$ contains a j-envy-free partition into triples then
$\\{\\{\alpha_{b_{1}},\allowbreak\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\allowbreak\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},\allowbreak
l_{2}\\},\\{l_{3},\allowbreak l_{4}\\}\\}$.

###### Proof.

By Lemma 49,
$\\{\alpha_{b_{1}},\alpha_{b_{2}},\alpha_{b_{3}},\alpha_{b_{4}}\\}=L$. There
are now three possibilities: first that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{3}\\},\\{l_{2},l_{4}\\}\\}$,
second that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{4}\\},\\{l_{2},l_{3}\\}\\}$,
and third that
$\\{\\{\alpha_{b_{1}},\allowbreak\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\allowbreak\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},\allowbreak
l_{2}\\},\\{l_{3},\allowbreak l_{4}\\}\\}$.

First suppose
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{3}\\},\\{l_{2},l_{4}\\}\\}$.
Now $l_{1}$ has j-envy for $h_{a_{2}}$ since
$u_{l_{1}}(\\{h_{a_{1}},l_{3}\\})=1<3\leq u_{l_{1}}(\\{l_{2},l_{4}\\})$,
$v_{l_{2}}(h_{a_{2}})=0<2=v_{l_{2}}(l_{1})$, and $v_{l_{4}}(h_{a_{2}})=0<1\leq
v_{l_{4}}(l_{1})$.

Second suppose
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{4}\\},\\{l_{2},l_{3}\\}\\}$.
As before, $l_{1}$ has j-envy for $h_{a_{2}}$ since
$u_{l_{1}}(\\{h_{a_{1}},l_{4}\\})=1<3\leq u_{l_{1}}(\\{l_{2},l_{3}\\})$,
$v_{l_{2}}(h_{a_{2}})=0<2=v_{l_{2}}(l_{1})$, and $v_{l_{3}}(h_{a_{2}})=0<1\leq
v_{l_{3}}(l_{1})$.

It remains that
$\\{\\{\alpha_{b_{1}},\alpha_{b_{2}}\\},\\{\alpha_{b_{3}},\alpha_{b_{4}}\\}\\}=\\{\\{l_{1},l_{2}\\},\\{l_{3},l_{4}\\}\\}$.
∎

By Lemma 50, either $\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{1},l_{2}\\}$ or
$\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{3},l_{4}\\}$. Without loss of
generality assume that
$\\{\alpha_{b_{1}},\alpha_{b_{2}}\\}=\\{l_{1},l_{2}\\}$.

######  Lemma 51.

If $(N,V)$ contains a j-envy-free partition into triples then
$u_{c_{i}}(\pi)=6$ for each $i$ where $1\leq i\leq 3q$.

###### Proof.

Suppose to the contrary that some $1\leq i\leq 3q$ exists where
$u_{c_{i}}(\pi)<6$. Then $c_{i}$ has j-envy for $h_{a_{1}}$ since
$u_{c_{i}}(\pi)\leq 5<6\leq u_{c_{i}}(\\{l_{1},l_{2}\\})$,
$v_{l_{1}}(h_{a_{1}})=0<3=v_{l_{1}}(c_{i})$, and
$v_{l_{2}}(h_{a_{1}})=0<3=v_{l_{2}}(c_{i})$. This contradicts our supposition
that $\pi$ is j-envy-free. ∎

######  Lemma 52.

If $(N,V)$ contains a j-envy-free partition into triples then $G$ contains a
partition into triangles.

###### Proof.

Suppose $(N,V)$ contains a j-envy-free partition into triangles $\pi$. Lemma
51 shows that $u_{c_{i}}(\pi)=6$ for each $i$ where $1\leq i\leq 3q$. By
construction, it follows that $\pi(c_{i})$ contains two agents $c_{j},c_{k}$
such that $v_{c_{i}}(c_{j})=v_{c_{i}}(c_{k})=3$. By construction, $c_{j}$ and
$c_{k}$ therefore correspond to vertices $w_{j},w_{k}\in W$ where
$\\{w_{i},w_{j}\\}\in E$ and $\\{w_{i},w_{k}\\}\in E$. It follows thus that
there are exactly $q$ triples in $\pi$ each containing three agents
$\\{c_{i},c_{j},c_{k}\\}$, where the three corresponding vertices
$w_{i},w_{j},w_{k}$ are pairwise adjacent in $G$. From these triples a
partition into triangles $X$ can be easily constructed. ∎

We have now shown that the ASHG $(N,V)$ contains a j-envy-free partition into
triples if and only if the PIT instance $G$ contains a partition into
triangles. This shows that the reduction is correct.

######  Theorem 7.

Deciding if a given ASHG contains a j-envy-free partition into triples is
$\NP$-complete, even when preferences are symmetric and the maximum possible
valuation is $6$.

###### Proof.

It is straightforward to show that this decision problem belongs to $\NP$,
since for any two agents $\alpha_{i},\alpha_{j}\in N$ we can test if
$\alpha_{i}$ j-envies $\alpha_{j}$ in constant time.

We have presented a polynomial-time reduction from Partition Into Triangles
(PIT), which is $\NP$-complete [26]. Given a graph $G$, the reduction
constructs an ASHG $(N,V)$ with symmetric preferences in which the maximum
valuation is $6$. Lemmas 42 and 52 show that $(N,V)$ contains a j-envy-free
partition into triples if and only if $G$ contains a partition into triangles
and thus that this decision problem is $\NP$-hard. ∎

######  Remark.

The authors designed the reduction in Theorem 7 around a particular instance
that contains no j-envy-free partition into triples (which can be constructed
by removing $l_{2},l_{3},l_{4}$ and $C$ from any instance produced by the
reduction). This particular instance was discovered by a guided computer
search, using an Integer Programming [30] model to test candidate solutions.
One assumption made was the valuations of $h_{1}$, in the spirit of an
“undesired guest” [15]. A similar technique has been applied in another
setting of hedonic games [31]. We believe that this was an effective technique
to identify ASHGs that have no partition into triples satisfying a particular
solution concept, although it remains open if the instance described contains
a minimal number of agents.

##  6 Conclusion

We considered three successively weaker solution concepts: envy-freeness,
weakly justified envy-freeness, and justified envy-freeness, and studied the
existence of partitions into triples that satisfy each concept together with
associated decision and construction problems.

From a practical perspective, the polynomial-time algorithms for envy-freeness
and wj-envy-freeness impose a strict requirement on the structure of the
agents’ preferences. While such restrictions may not necessarily be achievable
in practice, the identification of this frontier between solvability and
$\NP$-completeness is a first step. On the other hand, the polynomial-time
algorithm for justified envy-freeness can be applied more generally to
situations involving “friends” and “neutrals”.

The scope for future work is wide.

One immediate open problem relates to justified envy-freeness and preferences
that are symmetric and ternary (a strengthening of Theorem 7). Another
immediate direction is to what extent our results generalise to other
restrictions on coalition size, for example a model in which coalitions must
have size $k$, for some $k\geq 3$. We conjecture that all of our
$\NP$-hardness reductions can be generalised to this setting. Although the
restriction of maximum degree $2$ is a strong one, it is unclear if our
positive results can be similarly generalised.

Studying weaker solution concepts, such as $r$-approximate envy-freeness,
denoted EF-$r$, may lead to practical and interesting efficient algorithms. Li
et al. [18] pose a similar question in their related model, asking if every
instance with binary and symmetric preferences contains a balanced EF-$2$
partition.

Similarly, it could also be interesting to investigate ordinal preferences,
for example considering complete, $\mathscr{B}$-, $\mathscr{W}$-, or
lexicographic preferences [32, 33, 34]. We conjecture that in a hedonic game
model with $\mathscr{B}$-preferences [32], an envy-free partition may not
exist, and the associated existence problem is solvable in polynomial time.

Another possibility is to identify other restrictions on the agents’
valuations in which an envy-free, wj-envy-free or j-envy-free partition into
triples can be found in polynomial time. The gadgets used in our reductions
are highly regular and it might be that there exist interesting classes of
instances that must contain an envy-free, wj-envy-free, or j-envy-free
partition into triples. Alternatively, we could study these problems from the
perspective of parameterised complexity. For example, in the case of binary
and symmetric preferences, one could consider the tree-width [35] of the
underlying graph.

We believe that it would be very interesting to estimate the probability that
a randomly chosen ASHG contains an envy-free, wj-envy-free, or j-envy-free
partition into triples, or to estimate the same probability in a random ASHG
with binary or ternary preferences. Our complexity results indicate that,
among instances with binary and symmetric preferences and maximum degree $2$,
the set of ASHGs that contain a j-envy-free partition into triples (i.e. all
instances) is larger than the set of ASHGs that contain a wj-envy-free
partition into triples, which is in turn larger than the set of ASHGs that
contain an envy-free partition into triples. We conjecture that, in general,
the probability that a given ASHG contains an envy-free partition into triples
is smaller than the probability that it contains a wj-envy-free partition into
triples, which is in turn smaller than the probability that it contains a
j-envy-free partition into triples. In this direction, it might be possible to
apply probabilistic techniques from graph theory, such as the Erdös-Rényi
model of a random graph. Of course, the probabilistic events in which agents
have envy for other agents are not independent, which complicates the
analysis. Alternatively, an empirical approach might be informative.

## Acknowledgements

We are very grateful to the anonymous reviewers who have previously offered
comments on this work. Their suggestions have helped us to significantly
improve the presentation and style of this paper.

## References

  * [1] S. Banerjee, H. Konishi, T. Sönmez, Core in a simple coalition formation game, Social Choice and Welfare 18 (2001) 135–153.
  * [2] M. Olsen, Nash stability in additively separable hedonic games is -hard, in: Proceedings of CiE ’07: The 3rd Conference on Computability in Europe, Vol. 4497 of LNCS, Springer, 2007, pp. 598–605.
  * [3] H. Aziz, R. Savani, H. Moulin, Hedonic games, in: F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (Eds.), Handbook of Computational Social Choice, Cambridge University Press, 2016, pp. 356–376.
  * [4] J. Drèze, J. Greenberg, Hedonic coalitions: optimality and stability, Econometrica 48 (4) (1980) 987–1003.
  * [5] E. Elkind, M. Wooldridge, Hedonic coalition nets, in: Proceedings of AAMAS ’09: the 8th International Conference on Autonomous Agents and Multiagent Systems, Vol. 1, International Foundation for Autonomous Agents and Multiagent Systems, 2009, pp. 417–424.
  * [6] N. Barrot, M. Yokoo, Stable and envy-free partitions in hedonic games, in: Proceedings of IJCAI ’19: the 28th International Joint Conference on Artificial Intelligence, IJCAI Organization, 2019, pp. 67–73.
  * [7] S. Ueda, Envy based fairness in hedonic games, in: Proceedings of GECCO ’18: the Genetic and Evolutionary Computation Conference, ACM, 2018, pp. 1852–1853.
  * [8] R. Bredereck, K. Heeger, D. Knop, R. Niedermeier, Multidimensional stable roommates with master list, in: Proceedings of WINE ’20: The 16th Conference on Web and Internet Economics, Vol. 12495 of LNCS, Springer, 2020, pp. 59–73.
  * [9] C.-C. Huang, Two’s company, three’s a crowd: Stable family and threesome roommates problems, in: Proceedings of ESA ’07: the 15th European Symposium on Algorithms, Vol. 4698 of LNCS, Springer, 2007, pp. 558–569.
  * [10] K. Iwama, S. Miyazaki, K. Okamoto, Stable roommates problem with triple rooms, in: Proceedings of WAAC ’07: the 10th Korea-Japan Workshop on Algorithms and Computation, 2007, pp. 105–112, archived as Technical Report COMP2007-41 in the Kyoto University Research Information Repository.
  * [11] M. McKay, D. Manlove, The three-dimensional stable roommates problem with additively separable preferences, in: Proceedings of SAGT ’21: The 14th International Symposium on Algorithmic Game Theory, Vol. 12885 of LNCS, Springer, 2021, pp. 266–280.
  * [12] C. Ng, D. Hirschberg, Three-dimensional stable matching problems, SIAM Journal on Discrete Mathematics 4 (1) (1991) 245–252.
  * [13] L. Sless, N. Hazon, S. Kraus, M. Wooldridge, Forming $k$ coalitions and facilitating relationships in social networks, Artificial Intelligence 259 (2018) 217–245.
  * [14] T. Rahwan, T. P. Michalak, M. Wooldridge, N. R. Jennings, Coalition structure generation: A survey, Artificial Intelligence 229 (2015) 139–174.
  * [15] A. Bogomolnaia, M. O. Jackson, The stability of hedonic coalition structures, Games and Economic Behavior 38 (2) (2002) 201–230.
  * [16] H. Aziz, F. Brandt, H. G. Seedig, Computing desirable partitions in additively separable hedonic games, Artificial Intelligence 195 (2013) 316–334.
  * [17] K. Cechlárová, Stable partition problem, in: The Encyclopedia of Algorithms, Springer, 2008, pp. 885–888.
  * [18] L. Li, E. Micha, A. Nikolov, N. Shah, Partitioning friends fairly, unpublished manuscript. (2022).
URL
https://web.archive.org/web/20220912204204/https://www.cs.toronto.edu/~nisarg/papers/fair-
partition.pdf

  * [19] B. Li, Y. Li, Fair resource sharing and dorm assignment, in: Proceedings of AAMAS ’20: the 19th International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2020, p. 708–716.
  * [20] N. Boehmer, E. Elkind, Stable roommate problem with diversity preferences, in: Proceedings of IJCAI ’20: the 29th International Joint Conference on Artificial Intelligence, IJCAI Organization, 2020, pp. 96–102.
  * [21] D. Manlove, Algorithmics of Matching Under Preferences, World Scientific, Singapore, 2013.
  * [22] Á. Cseh, T. Fleiner, P. Harján, Pareto optimal coalitions of fixed size, Journal of Mechanism and Institution Design 4 (1) (2019) 87–108.
  * [23] V. Bilò, G. Monaco, L. Moscardelli, Hedonic games with fixed-size coalitions, in: Proceedings of AAAI ’22: the 36th AAAI Conference on Artificial Intelligence, AAAI Press, 2022, pp. 9287–9295.
  * [24] J. Alcalde, Exchange-proofness or divorce-proofness? Stability in one-sided matching markets, Economic design 1 (1994) 275–287.
  * [25] H. Aziz, F. Brandl, F. Brandt, P. Harrenstein, M. Olsen, D. Peters, Fractional hedonic games, ACM Transactions on Economics and Computation 7 (2) (2019) 1–29.
  * [26] M. Garey, D. Johnson, Computers and Intractability, Freeman, San Francisco, CA, 1979\.
  * [27] T. J. Schaefer, The complexity of satisfiability problems, in: Proceedings of STOC ’78: the 10th Annual ACM Symposium on Theory of Computing, 1978, pp. 216–226.
  * [28] S. Porschen, T. Schmidt, E. Speckenmeyer, A. Wotzlaw, XSAT and NAE-SAT of linear CNF classes, Discrete Applied Mathematics 167 (2014) 1–14.
  * [29] K. Cechlárová, T. Fleiner, D. Manlove, The kidney exchange game, in: Proceedings of SOR ’05: the 8th International Symposium on Operations Research in Slovenia, 2005, pp. 77–83, IM Preprint series A, no. 5/2005, PJ Šafárik University, Faculty of Science, Institute of Mathematics.
  * [30] M. Conforti, G. Cornuéjols, G. Zambelli, Integer Programming, Vol. 271 of Graduate Texts in Mathematics, Springer, 2014.
  * [31] M. Bullinger, Single-agent dynamics in hedonic games, talk presented at Dagstuhl Seminar 21331 “Coalition Formation Games” in Dagstuhl, Germany (2021).
URL
https://web.archive.org/web/20220913192100/https://drops.dagstuhl.de/opus/volltexte/2021/15588/pdf/dagrep˙v011˙i007˙p001˙21331.pdf

  * [32] K. Cechlárová, J. Hajduková, Computational complexity of stable partitions with $\mathscr{B}$-preferences, International Journal of Game Theory 31 (2002) 353–364.
  * [33] K. Cechlárová, J. Hajduková, Stable partitions with $\mathscr{W}$-preferences, Discrete Applied Mathematics 138 (3) (2004) 333–347.
  * [34] J. Hajduková, Coalition formation games: a survey, International Game Theory Review 8 (4) (2006) 613–641.
  * [35] N. Robertson, P. Seymour, Graph minors. III. planar tree-width, Journal of Combinatorial Theory, Series B 36 (1) (1984) 49–64.