${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}$,
the property trivially holds. Additionally since
$\hat{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}}$
is a minimal all the goods in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}$
are relevant to agent $i$. Now, we only need to show that for every agent
$j\rightarrow k\in P$ all the goods in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}$
are relevant to $j$. Assume by contradiction that there exist a good
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}$
that is not relevant to agent $j$. Then, we have:

$\displaystyle
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\setminus\\{g\\})$
$\displaystyle=v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
$g$ is not relevant to $j$
$\displaystyle=v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})w_{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}(j,k)$
Definition 2.3
$\displaystyle=v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})\frac{\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}{\mathfrak{R}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}$
Observation 2.1
$\displaystyle=\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
Definition 2.7
$\displaystyle>\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\mbox{$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})>1$}.$

Therefore, $j$ virtually strongly envies $k$ in allocation $\textstyle\chi$.
This contradicts the fact that $\textstyle\chi$ satisfies Property
${\dagger}\\!\\!$ (ii). $\Box$

######  Corollary 7.6 (of Lemmas 7.2, 7.4 and 7.5).

Let $\textstyle\chi$ be an allocation satisfying Properties ${\dagger}\\!\\!$
(i) and ${\dagger}\\!\\!$ (ii) and ${\dagger}\\!\\!$ (iii), and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the allocation after applying Rule 1. Then, for every agent $j$,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}[j]={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}$.

######  Lemma 7.7.

Let $\textstyle\chi$ be an allocation satisfying Properties ${\dagger}\\!\\!$
(i) and ${\dagger}\\!\\!$ (ii), and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the allocation after applying Rule 1. Then,
$\mathsf{NSW}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})>\mathsf{NSW}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$.

Proof. Since the bundle of agents that are not in $P$ is still the same as
before, it is sufficient to show that the product of valuation of agents in
path $P$ increases.

$\displaystyle\prod_{j\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j})$
$\displaystyle=v_{i}(\hat{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}})\prod_{j\rightarrow
k\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
Bundles are shifted through path $P$
$\displaystyle>\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\prod_{j\rightarrow
k\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
$v_{i}(\hat{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}})>\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle=\frac{v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})}{\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}\prod_{j\rightarrow
k\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
Definition 2.7
$\displaystyle=\frac{v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})}{\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}\prod_{j\rightarrow
k\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})w_{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}(j,k)$
Definition 2.3
$\displaystyle=\frac{\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}{\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})}\prod_{j\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})$
$P$ is rankpath of $i$ $\displaystyle=\prod_{j\in
P}v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}).$

Therefore
$\mathsf{NSW}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})>\mathsf{NSW}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$.
$\Box$

In conclusion, after applying this update rule the resulting allocation is
virtually $\mathsf{EFX}$, virtual values of agents do not decrease and Nash
social welfare of the allocation strictly increases.

###  7.2 Final Step

When Rule 1 not applicable, we perform a final step to achieve a complete
$\frac{\sqrt{2}}{2}$-$\mathsf{EFX}$ allocation. Let $i$ be an agent with rank
equal to one in $\textstyle\chi$, and $S$ be the set of all other agents whose
rank is at most $\sqrt{2}$. In the final step, first we iterate through $S$ in
an arbitrary order and ask each agent to pick all the goods in the pool that
are relevant to her, then we allocate all the remaining goods in the pool to
agent $i$ and return the allocation.

######  Theorem 7.8.

Suppose that the valuations are restricted additive, and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
be the allocation returned by C$\sqrt{2}$XPQ. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
is a $\frac{\sqrt{2}}{2}$-$\mathsf{EFX}$ allocation.

Proof. First we show that for every agents $j\in S$ and $k\in N$, agent $k$
does not $\sqrt{2}$-envy agent $j$. Note that since
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\subseteq{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{k}$
we have
$v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})\leq
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{k})$.
Additionally, since agent $j$ only receives the goods from the pool that are
relevant to her and the valuations are $(\infty,1)$-bounded, at most one good
in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{j}$
is relevant to agent $k$. We denote this good as $g$. If
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}$,
since Rule 1 is not applicable
$v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})\geq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq
v_{k}(g)$ and $k$ does not envy agent $j$; otherwise
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}$
and since
$\mathfrak{R}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\sqrt{2}$
agent $k$ does not $\sqrt{2}$-envy
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}$.
Hence, agent $k$ does not $\sqrt{2}$-envy $j$.

Now, we need to prove that there is no agent $k\in N$ who $\sqrt{2}$-envies
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i}$.
In the case that $k\in S$, since $k$ has picked all the goods from the pool
which are relevant to her, agent $i$ does not receive any good that is
relevant to agent $k$. Furthermore, since
$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$,
agent $k$ does not envy agent $i$. For the case that
$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})>\sqrt{2}$,
since Rule 1 is not applicable we have
$v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0})<\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\frac{\sqrt{2}}{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$.
Additionally, since $\textstyle\chi$ satisfies Property ${\dagger}\\!\\!$ (i)
we have
$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})w_{\scriptscriptstyle{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}}(k,i)\leq\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$,
and since
$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$
and
$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})>\sqrt{2}$
we have
$v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})\leq\frac{\sqrt{2}}{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$.
Therefore:

$\displaystyle
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i})$
$\displaystyle\leq
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0})$
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i}\subseteq{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}$
$\displaystyle\leq
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})+v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0})$
Subadditivity $\displaystyle\leq
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})+\frac{\sqrt{2}}{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
Rule 1 is not applicable
$\displaystyle\leq\frac{\sqrt{2}}{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})+\frac{\sqrt{2}}{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$
$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$
$\displaystyle=\sqrt{2}v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k})$

Hence, there is no agent $k$ that $\sqrt{2}$-envies agent $i$.

It only remains to prove that for every agents $j$ and $k$ such that
$\mathfrak{R}_{k}>\sqrt{2}$, agent $j$ does not strongly-envy agent $k$. Note
that $\textstyle\chi$ satisfies Property ${\dagger}\\!\\!$ (ii), which means
for every good
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}$
we have
$\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\geq
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\setminus\\{g\\})$.
Additionally, since
$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})>\sqrt{2}$,
$k$ does not receive any good in the final step, i.e.,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{k}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}$.
Therefore
$v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{j})\geq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\geq
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\setminus\\{g\\})$
and agent $j$ does not strongly envy agent $k$.

In conclusion, after the final step, there is no agent who $\sqrt{2}$-envies
an agent $j$ such that
$\mathfrak{R}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\sqrt{2}$
and there is no agent who strongly envies an agent $k$ such that
$\mathfrak{R}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})>\sqrt{2}$.

$\Box$

##  8 $\mathsf{EFX}$ for Restricted Additive Valuations with p = 2

Our last algorithm finds a complete $\mathsf{EFX}$ allocation for the case
that the set of valuations is $(2,\infty)$-bounded and restricted additive.
With $p=2$, each good is relevant to a maximum of 2 agents, while any pair of
agents may share multiple relevant goods.

Our algorithm consists of four updating rules and a final step. Unlike our
previous algorithms, agents may become satisfied and be eliminated from the
process. Therefore, here $N$ refers to the set of remaining agents. We also
define rank, rankpath, and virtual value based on the allocation of the
remaining agents. We utilize the following potential function to prove the
termination of our algorithm:

$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=(n-|N|,\mathsf{NSW}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})).$

Therefore, after each update, either the number of satisfied agents increases
or the Nash social welfare of the allocation increases. We designate our
algorithm in this section as PQRAX. Furthermore, our updates are designed in a
way that the following properties are always satisfied during the algorithm:

  1. $\uparrow\\!\\!$ (i)

For every agent $i\in N$, there is some agent $j$ such that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\subseteq
M{[i,j]}$. We call agent $j$, the corresponding agent of agent $i$. Note that
the corresponding agent of $i$ can be $i$ itself.

  2. $\uparrow\\!\\!$ (ii)

For every agent $i,j\in N$, and every
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}$
we have
$v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}\setminus
g)\leq\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}).$

Note that Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii) trivially
hold for the basic feasible allocation.

######  Observation 8.1.

Let $X$ be an allocation that satisfies Property $\uparrow\\!\\!$ (i). Then
for every $i,j\in N$ such that $X_{j}\subseteq M{[i,j]}$, we have
$v_{i}(X_{j})=v(X_{j})$.

######  Observation 8.2.

Let $X$ be an allocation that satisfies Property $\uparrow\\!\\!$ (i). Then
for every $i\in N$, we have
$\mathfrak{v}_{i}(X)=v(X_{\textsf{root}({i},{X})})$.

Proof. Let $i_{1}\rightarrow i_{2}\rightarrow\dots\rightarrow i_{k}\rightarrow
i$ be the rankpath of agent $i$ in $G_{X}$.

$\displaystyle\mathfrak{R}_{i}(X)$ $\displaystyle=w_{\scriptscriptstyle
X}(i_{1},i_{2})\times w_{\scriptscriptstyle X}(i_{2},i_{3})\times\ldots\times
w_{\scriptscriptstyle X}(i_{k},i)$ $\displaystyle\text{Definition
\ref{weighted-envy-def}},$
$\displaystyle=\frac{v_{i_{1}}(X_{i_{2}})}{v_{i_{1}}(X_{i_{1}})}\times\frac{v_{i_{2}}(X_{i_{3}})}{v_{i_{2}}(X_{i_{2}})}\times\ldots\times\frac{v_{i_{k}}(X_{i})}{v_{i_{k}}(X_{i_{k}})}$
$\displaystyle=\frac{v(X_{i_{2}})}{v(X_{i_{1}})}\times\frac{v(X_{i_{3}})}{v(X_{i_{2}})}\times\ldots\times\frac{v(X_{i})}{v(X_{i_{k}})}$
$\displaystyle\text{Observation \ref{rel}},$
$\displaystyle=\frac{v(X_{i})}{v(X_{i_{1}})}.$

Therefore
$\mathfrak{v}_{i}(X)=\frac{v(X_{i})}{\mathfrak{R}_{i}(X_{i})}=v(X_{i})\frac{v(X_{i_{1}})}{v(X_{i})}=v(X_{i_{1}})=v(X_{\textsf{root}({i},{X})})$.
$\Box$

### Update Rule 1

The first updating rule is applicable when an agent $i\in N$ with
$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$
and a good
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}$
exists such that $g$ has the same type as the goods in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$.
Formally, assuming
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\subseteq
M{[i,j]}$ for some $j$, then $g$ also belongs to $M{[i,j]}$. If these
conditions are met, we replace
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$
with a minimal subset of
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup\\{g\\}$
that has a value greater than
$v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$.

######  Observation 8.3.

Let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the result of applying Rule 1 on $\textstyle\chi$. Then all edges of
$G_{0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}}$
are same as the edges of
$G_{0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}}$.

######  Lemma 8.1.

Let $\textstyle\chi$ be an allocation satisfying Properties $\uparrow\\!\\!$
(i) and$\uparrow\\!\\!$ (ii), and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the result of applying Rule 1 on $\textstyle\chi$. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).
Furthermore, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
and for every remaining agent $k$ we have
$\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

Proof. Given that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}\subseteq
M{[i,j]}$ and the other bundles remain unchanged,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Property $\uparrow\\!\\!$ (i). We prove that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Property $\uparrow\\!\\!$ (ii). This implies that for every
remaining agent $k$ and
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{k}$,
we have
$v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{k}\setminus\\{g\\})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.
There are two cases $k=i$ and $k\neq i$. Let $k\neq i$ and a good
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{k}$
and
$r=\textsf{root}({k},{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}})$.
We have:

$\displaystyle
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{k}\setminus\\{g\\})$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\setminus\\{g\\})$
$\displaystyle\text{($k\neq i$)},$
$\displaystyle\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$
satisfies Property \ref{prop43}},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{r})$
$\displaystyle\text{Observation \ref{graph-unchanged}},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r})$
$\displaystyle=\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
$\displaystyle\text{Observation \ref{obs41}}.$

Now let $k=i$ and a good
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}$
and
$r=\textsf{root}({i},{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}})$.
We have:

$\displaystyle
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}\setminus\\{g\\})$
$\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$
$\displaystyle\text{(${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}$
is minimal)},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{r})$
$\displaystyle\text{($\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$)},$
$\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r})$
$\displaystyle=\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
$\displaystyle\text{Observation \ref{obs41}}.$

Therefore,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies both Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).

Since
$v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})<v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i})$,
and all other bundles remain unchanged, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

In order to show that for every agent $k$ we have
$\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$,
let
$r=\textsf{root}({k},{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}})$.
We have:

$\displaystyle\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{r})$
$\displaystyle\text{Observation \ref{graph-unchanged}},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r})$
$\displaystyle=\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
$\displaystyle\text{Observation \ref{obs41}}.$

$\Box$

### Update Rule 2

This rule is applicable if there exists an agent $i\in N$ such that for some
$j$,
$\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i,j]}).$
If so, we update the allocation as follows: let $j$ be the agent with the
minimum virtual value such that
$\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i,j]})$,
and let $P=i_{1}\rightarrow i_{2}\rightarrow\ldots\rightarrow i_{k}\rightarrow
i$ be the rankpath of agent $i$. We allocate a minimal subset of
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i,j]}$
with value more than
$\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
to agent $i$, shift the bundles through $P$, and return
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i_{1}}$
back to the pool
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}$.

######  Lemma 8.2.

Let $\textstyle\chi$ an allocation satisfying Properties $\uparrow\\!\\!$ (i)
and$\uparrow\\!\\!$ (ii), and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the result of applying Rule 2 on $\textstyle\chi$. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).
Furthermore, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
and for every remaining agent $k$ we have
$\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

Proof. During the update, only the bundle of agent $i$ is modified. 333While
other bundles may be transferred among agents, none is modified. Therefore,
Property $\uparrow\\!\\!$ (i) remains valid for agents other than $i$. For
agent $i$ we also know that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}\subseteq
M{[i,j]}$. Therefore, Property $\uparrow\\!\\!$ (i) holds for
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$.

To show that Property $\uparrow\\!\\!$ (ii) holds after the update, we note
that this update rule is indeed exactly the same as Rule 1 in Section 7.
Therefore, by Lemma 7.3 we conclude that virtual values do not decrease after
the update. Furthermore, by Lemma 7.4,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Property $\uparrow\\!\\!$ (ii), and by Lemma 7.7 we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

$\Box$

### Update Rule 3

The third updating rule is applicable when there is an agent $i\in N$ such
that for every agent $j\in N$,
$v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})=0$.
If so, we ask agent $i$ to pick either
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$
or
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$
that is more valuable to him and return the other bundle back to the pool.
Also, we mark agent $i$ as satisfied and remove her from the process.

######  Lemma 8.3.

Let $\textstyle\chi$ an allocation satisfying Properties $\uparrow\\!\\!$ (i)
and$\uparrow\\!\\!$ (ii), and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the result of applying Rule 3 on $\textstyle\chi$. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).
Furthermore, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
and for every remaining agent $k$ we have
$\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

Proof. According to Rule 3, for every remaining agent $j$, we have
$v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j})=0$,
meaning agent $i$ isn’t in agent $j$’s rankpath. Thus,
$\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.
Also, the update keeps all the remaining agents’ bundles unchanged. Thus,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii). Finally,
since $|N|$ decreases, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

$\Box$

######  Lemma 8.4.

Let $i$ be an agent satisfied by Rule 3. Then, $i$ will never strongly envy
any remaining agent, and no remaining agent will ever strongly envy agent $i$.

Proof. After the update, we have
$v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{0})\leq
v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i})$,
and for every remaining agent $j$,
$v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j})=0$.
Therefore,
$v_{i}(\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})\leq
v_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i})$
which means that agent $i$ will not envy any remaining agent in subsequent
steps. Furthermore, considering Property $\uparrow\\!\\!$ (i) for
$\textstyle\chi$, there exists an agent $j$ such that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\subseteq
M{[i,j]}$. The only agent who might strongly envy $i$ is agent $j$. Post-
update,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}$
can either be
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$
or
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$.

If
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$,
let
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}$,
and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
denote the final allocation. We have:

$\displaystyle
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}\setminus
g)$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\setminus
g)$ $\displaystyle\text{since
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$},$
$\displaystyle\leq\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{by Property \ref{prop43} of
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{due to $j\rightarrow i$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*})$
$\displaystyle\text{virtual values do not decrease},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{j}).$

Thus, agent $j$ does not strongly envy $i$ in the final allocation.

Now, if
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$,
for any remaining agent $j\in N^{\prime}$ in the final allocation
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$,
we have:

$\displaystyle
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i})$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i,j]})$
$\displaystyle\text{since
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{since Rule 2 does not apply to
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*})$
$\displaystyle\text{virtual values do not decrease},$ $\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{j}).$

Therefore, agent $j$ does not strongly envy $i$ in the final allocation.
$\Box$

### Update Rule 4

Before describing this rule, we prove that when the first three rules are not
applicable, then
$G_{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}},0}$
exhibits a special structure.

######  Lemma 8.5.

Let $\textstyle\chi$ be an allocation satisfying Properties $\uparrow\\!\\!$
(i) and $\uparrow\\!\\!$ (ii). If the first three rules are not applicable,
then
$G_{0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}}$
consists of one or several disjoint cycles.

Proof. Since $\textstyle\chi$ satisfies Property $\uparrow\\!\\!$ (i), the in-
degree of each vertex in
$G_{0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}}$
is equal to $1$. Additionally since Rule 3 is not applicable to
$\textstyle\chi$, the out-degree of each vertex is at least $1$. Therefore
$G_{0,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}}$
consists of one or more cycles. $\Box$

In the fourth updating rule, we select and satisfy one agent with rank 1. Let
$i$ be an agent with
$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$
and suppose $i\rightarrow j_{1}\rightarrow j_{2}\ldots\rightarrow
j_{k}\rightarrow i$ be the cycle in
$G_{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}},0}$
containing $i$. We ask agent $i$ to pick either
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$
or
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$,
whichever that is more valuable to her. We then mark agent $i$ as satisfied
and remove her from the process. Finally, if agent $i$ picked
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$,
we shift the bundles through the cycle, i.e., for every $2\leq\ell<k$, we give
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{\ell+1}$
to agent $j_{\ell}$ and give
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$
to agent $j_{k}$.

######  Lemma 8.6.

Let $\textstyle\chi$ be an allocation satisfying Properties $\uparrow\\!\\!$
(i) and $\uparrow\\!\\!$ (ii) and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
be the result of applying Rule 4 on $\textstyle\chi$. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).
Furthermore, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
and for every remaining agent $k$ we have
$\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.

Proof. First we show that the virtual value of each remaining agent does not
decrease after the update. By Observation 8.2, the virtual value of each agent
in a cycle, is equal to the minimum value of bundles in that cycle. Therefore
we have
$\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=\mathfrak{v}_{j_{1}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=\mathfrak{v}_{j_{2}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=\ldots=\mathfrak{v}_{j_{k}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$.
Now let
$r^{\prime}=\textsf{root}({k},{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}})$
and let $l$ be the agent such that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r^{\prime}}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{l}$.
For every remaining agent $j$ we have:

$\displaystyle\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle=\mathfrak{v}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
,
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$
$\displaystyle\text{$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$},$
$\displaystyle\leq
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{l})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}$
is the bundle with minimum value in the cycle},$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r^{\prime}})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{r^{\prime}}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{l}$},$
$\displaystyle=\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$
$\displaystyle\text{$\textsf{root}({k},{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}})=r^{\prime}$}.$

Hence, the virtual values of the remaining agents do not decrease.

Since the set of bundles in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
remains unchanged,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Property $\uparrow\\!\\!$ (i). To Prove that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies Property $\uparrow\\!\\!$ (ii), let $j$ be the remaining agent and
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}j={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}$.
We have:

$\displaystyle
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{j}\setminus\\{g\\})$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}\setminus\\{g\\})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}j={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}$},$
$\displaystyle\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$
satisfies Property \ref{prop43}},$
$\displaystyle=\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{all virtual values are
$v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}).$

Therefore
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}$
satisfies both Properties $\uparrow\\!\\!$ (i) and $\uparrow\\!\\!$ (ii).

Since $|N^{\prime}|=|N|-1$, we have
$\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})<\phi({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime})$.
$\Box$

######  Lemma 8.7.

Let $i$ be an agent satisfied by Rule 4. Then, $i$ will never strongly envy
any remaining agent, and no remaining agent will ever strongly envy agent $i$.

Proof. Since only
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0},{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i},{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$
may be relevant to agent $i$, and this agent picks the more valuable bundle
between
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$,
it doesn’t matter what happens in the future, and $i$ will not envy any bundle
in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$.

Suppose that $j$ is the corresponding agent of agent $i$. There are two cases
for
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i}$.
The first case is
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\cup{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i]}$.
In this case for agent $k\neq j$ we have:

$\displaystyle
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i})$
$\displaystyle={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}{[i,k]}$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\subseteq
M{[i,j]}$},$
$\displaystyle\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{Rule 2 is not applicable on
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$},$
$\displaystyle\leq\mathfrak{v}_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*})$
$\displaystyle\text{virtual values does not decrease},$ $\displaystyle\leq
v_{k}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{k}^{*}).$

and for agent $j$ we have:

$\displaystyle
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i})$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}{[i,j]})$
$\displaystyle\text{Rule 1 is not applicable on
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$},$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{i}\subseteq
M{[i,j]}$},$
$\displaystyle=\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{$\mathfrak{R}_{i}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})=1$},$
$\displaystyle\leq\mathfrak{v}_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*})$
$\displaystyle\text{virtual values does not decrease},$ $\displaystyle\leq
v_{j}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j}^{*}).$

The second case is
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{\prime}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$.
In this case only $j_{1}$ may envy $i$. Let
$g\in{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$.
We have:

$\displaystyle
v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i}\setminus\\{g\\})$
$\displaystyle=v({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}\setminus\\{g\\})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}_{i}={\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}$},$
$\displaystyle\leq\mathfrak{v}_{j_{1}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}})$
$\displaystyle\text{${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}$
satisfies Property \ref{prop43}},$
$\displaystyle\leq\mathfrak{v}_{j_{1}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*})$
$\displaystyle\text{virtual values does not decrease},$ $\displaystyle\leq
v_{j_{1}}({\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{j_{1}}^{*}).$

Therefore no agent in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
will strongly envy $i$. $\Box$

### Final Step

Finally, if only one agent is left behind, i.e., $|N|=1$, we allocate the
whole set of items in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{0}$
to the remaining agent and return the allocation.

######  Theorem 8.8.

Suppose that the valuations are restricted additive and $(2,\infty)$-bounded,
and let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
be the allocation returned by PQRAX. Then,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}^{*}$
is a $\mathsf{EFX}$ allocation.

Proof. In this algorithm, we satisfy all agents one by one. By Lemmas 8.4 and
8.7, the returned allocation by PQRAX is $\mathsf{EFX}$. $\Box$

## References

  * [1] H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta.  Efx allocations: Simplifications and improvements.  arXiv preprint arXiv:2205.07638, 2022.
  * [2] H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta.  Efx: a simpler approach and an (almost) optimal guarantee via rainbow cycle number.  In Proceedings of the 24th ACM Conference on Economics and Computation, pages 61–61, 2023.
  * [3] H. Akrami, R. Rezvan, and M. Seddighin.  An ef2x allocation protocol for restricted additive valuations.  arXiv preprint arXiv:2202.13676, 2022.
  * [4] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris.  Fair division of indivisible goods: A survey.  arXiv preprint arXiv:2202.07551, 2022.
  * [5] G. Amanatidis, E. Markakis, and A. Ntokos.  Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination.  Theoretical Computer Science, 841:94–109, 2020.
  * [6] C. Annamalai, C. Kalaitzis, and O. Svensson.  Combinatorial algorithm for restricted max-min fair allocation.  ACM Transactions on Algorithms (TALG), 13(3):1–28, 2017.
  * [7] A. Asadpour, U. Feige, and A. Saberi.  Santa claus meets hypergraph matchings.  ACM Transactions on Algorithms (TALG), 8(3):1–9, 2012.
  * [8] H. Aziz, B. Li, H. Moulin, and X. Wu.  Algorithmic fair allocation of indivisible items: A survey and new questions.  ACM SIGecom Exchanges, 20(1):24–40, 2022.
  * [9] H. Aziz and S. Mackenzie.  A discrete and bounded envy-free cake cutting protocol for any number of agents.  In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 416–427. IEEE, 2016.
  * [10] É. Bamas and L. Rohwedder.  Better trees for santa claus.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1862–1875, 2023.
  * [11] S. Barman, D. Kar, and S. Pathak.  Parameterized guarantees for almost envy-free allocations.  arXiv preprint arXiv:2312.13791, 2023.
  * [12] S. Barman, S. K. Krishnamurthy, and R. Vaish.  Finding fair and efficient allocations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557–574, 2018.
  * [13] B. A. Berendsohn, S. Boyadzhiyska, and L. Kozma.  Fixed-point cycles and efx allocations.  arXiv preprint arXiv:2201.08753, 2022.
  * [14] B. Berger, A. Cohen, M. Feldman, and A. Fiat.  Almost full efx exists for four agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4826–4833, 2022.
  * [15] I. Bezáková and V. Dani.  Allocating indivisible goods.  ACM SIGecom Exchanges, 5(3):11–18, 2005.
  * [16] S. J. Brams and A. D. Taylor.  An envy-free cake division protocol.  American Mathematical Monthly, pages 9–18, 1995.
  * [17] S. J. Brams and A. D. Taylor.  Fair Division: From cake-cutting to dispute resolution.  Cambridge University Press, 1996.
  * [18] E. Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [19] I. Caragiannis, J. Garg, N. Rathi, E. Sharma, and G. Varricchio.  Existence and computation of epistemic efx allocations.  arXiv e-prints, pages arXiv–2206, 2022.
  * [20] I. Caragiannis, N. Gravin, and X. Huang.  Envy-freeness up to any item with high nash welfare: The virtue of donating items.  In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 527–545, 2019.
  * [21] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 305–322. ACM, 2016.
  * [22] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019.
  * [23] B. R. Chaudhury, J. Garg, and K. Mehlhorn.  Efx exists for three agents.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 1–19, 2020.
  * [24] B. R. Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra.  Improving efx guarantees through rainbow cycle number.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 310–311, 2021.
  * [25] B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa.  A little charity guarantees almost envy-freeness.  SIAM Journal on Computing, 50(4):1336–1358, 2021.
  * [26] X. Chen, X. Deng, and S.-H. Teng.  Settling the complexity of computing two-player nash equilibria.  Journal of the ACM (JACM), 56(3):1–57, 2009.
  * [27] G. Christodoulou, A. Fiat, E. Koutsoupias, and A. Sgouritsa.  Fair allocation in graphs.  In Proceedings of the 24th ACM Conference on Economics and Computation, pages 473–488, 2023.
  * [28] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou.  The complexity of computing a nash equilibrium.  Communications of the ACM, 52(2):89–97, 2009.
  * [29] S. Davies, T. Rothvoss, and Y. Zhang.  A tale of santa claus, hypergraphs and matroids.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2748–2757. SIAM, 2020.
  * [30] L. E. Dubins and E. H. Spanier.  How to cut a cake fairly.  American mathematical monthly, pages 1–17, 1961.
  * [31] S. Even and A. Paz.  A note on cake cutting.  Discrete Applied Mathematics, 7(3):285–296, 1984.
  * [32] A. Farhadi, M. Hajiaghayi, M. Ghodsi, S. Lahaie, D. Pennock, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods to asymmetric agents.  In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 1535–1537. International Foundation for Autonomous Agents and Multiagent Systems, 2017.
  * [33] A. Farhadi, M. Hajiaghayi, M. Latifian, M. Seddighin, and H. Yami.  Almost envy-freeness, envy-rank, and nash social welfare matchings.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5355–5362, 2021.
  * [34] M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 539–556. ACM, 2018.
  * [35] L. Gourvès, J. Monnot, and L. Tlilane.  Near fairness in matroids.  In ECAI, volume 14, pages 393–398, 2014.
  * [36] P. Hall.  On representatives of subsets.  Classic Papers in Combinatorics, pages 58–62, 1987.
  * [37] S. C. Jahan, M. Seddighin, S.-M. Seyed-Javadi, and M. Sharifi.  Rainbow cycle number and efx allocations:(almost) closing the gap.  arXiv preprint arXiv:2212.09482, 2022.
  * [38] S. Khot and A. K. Ponnuswami.  Approximation algorithms for the max-min allocation problem.  In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 204–217. Springer, 2007.
  * [39] D. Kurokawa, A. D. Procaccia, and J. Wang.  Fair enough: Guaranteeing approximate maximin shares.  Journal of the ACM (JACM), 65(2):8, 2018.
  * [40] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings of the 5th ACM conference on Electronic commerce, pages 125–131. ACM, 2004.
  * [41] B. Plaut and T. Roughgarde.  Almost envy-freeness with general valuations.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2584–2603. SIAM, 2018.
  * [42] A. D. Procaccia.  Cake cutting: Not just child’s play.  Communications of the ACM, 56(7):78–87, 2013.
  * [43] A. D. Procaccia.  Technical perspective: An answer to fair division’s most enigmatic question.  Communications of the ACM, 63(4):118–118, 2020.
  * [44] H. Steinhaus.  The problem of fair division.  Econometrica, 16(1), 1948.
  * [45] W. Stromquist.  How to cut a cake fairly.  The American Mathematical Monthly, 87(8):640–644, 1980.

##  Appendix A Missing Proofs

Lemma A.1 helps us prove some of our claims in Section 6. A Lemma similar to
Lemma A.1 has been previously proved by Akrami et al. .[3]. For completeness,
here we restate and prove this lemma.

######  Lemma A.1.

Let $X$ and $X^{\prime}$ be two allocations. Define:

$\displaystyle A=\\{i|X_{i}\neq X^{\prime}_{i}\\}$ $\displaystyle x=\min_{i\in
A}(v(X_{i}))$ $\displaystyle x^{\prime}=\min_{i\in A}(v(X^{\prime}_{i})).$

Assume the following conditions hold:

  * •

$x<x^{\prime}$,

  * •

There is only one source agent in $A$ in $G{\beta,X}$,

  * •

If $i$ is the source agent in $A$, then $v(X_{i})=x$.

Then, $\phi(X)<\phi(X^{\prime})$.

Proof. Denote the sources of $G_{\beta,X}$ by $s_{1},s_{2},\ldots,s_{k}$ and
the sources of $G_{\beta,X^{\prime}}$ by
$s^{\prime}_{1},s^{\prime}_{2},\ldots,s^{\prime}_{k^{\prime}}$. Then:

$\displaystyle\phi(X)=\big{[}v(X_{s_{1}}),v(X_{s_{2}}),\ldots,v(X_{s_{k}}),\infty\big{]},$
$\displaystyle\phi(X^{\prime})=\big{[}v(X^{\prime}_{s^{\prime}_{1}}),v(X^{\prime}_{s^{\prime}_{2}}),\ldots,v(X^{\prime}_{s^{\prime}_{k^{\prime}}}),\infty\big{]}.$

Since agent $i$ is a source in $G_{\beta,X}$, we can assume without loss of
generality that there exist an index $l$ such that $s_{l}=i$, and
$v(X_{s_{l}})\neq v(X{s_{l+1}})$. (we can reorder same values in $\phi$ to
satisfy this condition). We show that for every $l^{\prime}<l$ we have
$\phi(X)_{l^{\prime}}=\phi(X^{\prime})_{l^{\prime}}$ and for $l$ we have
$\phi(X)_{l}<\phi(X^{\prime})_{l}$.

  * •

For every $l^{\prime}<l$, we claim that $s_{l^{\prime}}$ remains a source in
$G_{\beta,X^{\prime}}$. To prove this, we show that for every agent $j$ we
have $v_{j}(X^{\prime}_{s_{l^{\prime}}})<\beta v_{j}(X^{\prime}_{j})$. If
$j\notin A$, our claimi is trivial since $s_{l^{\prime}}$ is a source in
$G_{\beta,X}$. If $j\in A$, we have:

$\displaystyle v_{j}(X^{\prime}_{s_{l^{\prime}}})$ $\displaystyle\leq
v(X^{\prime}_{s_{l^{\prime}}})$ $\displaystyle=v(X_{s_{l^{\prime}}})$
$s_{l^{\prime}}\notin A$ $\displaystyle\leq x$
$\displaystyle\text{$l^{\prime}<l$},$ $\displaystyle<x^{\prime}$
$\displaystyle\leq v(X^{\prime}_{j})$ $\displaystyle\text{$j\in A$},$
$\displaystyle=v_{j}(X^{\prime}_{j})$ $\displaystyle\leq\beta
v_{j}(X^{\prime}_{j}).$

Therefore $j$ does not $\beta$-envy $s_{l^{\prime}}$ in $X^{\prime}$ and
$\phi(X)_{l^{\prime}}=\phi(X^{\prime})_{l^{\prime}}$.

  * •

To prove $\phi(X)_{l}<\phi(X^{\prime})_{l}$, we need to show that for any
source agent $j$ in $G_{\beta,X^{\prime}}$ such that
$j\notin\\{s_{1},s_{2},\dots,s_{l-1}\\}$ we have
$v(X^{\prime}_{j})>x=\phi(X)_{l}$. We have three cases. The first case is
$j\in A$. In this case we have:

$\displaystyle\phi(X)_{l}$ $\displaystyle=x$ $\displaystyle<x^{\prime}$
$\displaystyle\leq v(X^{\prime}_{j})$ $\displaystyle\text{$j\in A$}.$

In the second case we have $j\notin A$ and $j$ is also a source in
$G_{\beta,X}$. In this case we have:

$\displaystyle\phi(X)_{l}$ $\displaystyle=x$ $\displaystyle<v(X_{j})$
$\displaystyle\text{$j\notin{s_{1},s_{2},\dots,s_{l-1}}$},$
$\displaystyle=v(X^{\prime}_{j})$ $\displaystyle\text{$j\notin A$}.$

In the last case we have $j\notin A$ and $j$ is not a source in $G_{\beta,X}$.
We know there exists another agent $j^{\prime}\in A$ such that $j^{\prime}$
$\beta$-envies agent $j$ in $G_{\beta,X}$. Therefore we have:

$\displaystyle\phi(X)_{l}$ $\displaystyle=x$ $\displaystyle<\sqrt{2}x$
$\displaystyle\leq\sqrt{2}v(X_{j^{\prime}})$
$\displaystyle\text{$j^{\prime}\in A$},$ $\displaystyle<v(X_{j})$
$\displaystyle\text{$j^{\prime}$ envies $j$ in $X$},$
$\displaystyle=v(X^{\prime}_{j})$ $\displaystyle\text{$j\notin A$}.$

Hence, $\phi(X^{\prime})_{l}$ is replaced with an agent with a larger value,
or $\phi(X^{\prime})_{l}=\infty$.

$\Box$.


0}(\sigma_{N}(\bar{\beta})R_{N})^{k+\ell}\,\mathrm{P}(\tau_{k}^{\scriptscriptstyle(N)}=n)\,\mathrm{P}(\tau_{\ell}^{\scriptscriptstyle(N)}=n)\leq\frac{(C^{\prime})^{2}}{n^{2}(\log
N)^{2}}\Big{(}\sum_{k\geq 0}k\cdot(\bar{\beta}^{\prime})^{k}\Big{)}^{2}\,.$

for some $\bar{\beta}^{\prime}\in(\bar{\beta},1)$. Since
$\bar{\beta}^{\prime}<1$ we have that $\sum_{k\geq
0}k\cdot(\bar{\beta}^{\prime})^{k}<\infty$, therefore we deduce that there
exists a constant $C=C(\bar{\beta}^{\prime})$ such that
$\big{(}U^{\bar{\beta}}_{N}\big{)}^{2}(n)\leq\frac{C}{n^{2}\,(\log N)^{2}}$.
Since $\sum_{n\geq 1}\frac{1}{n^{2}}<\infty$, there exists a constant
$C=C(\bar{\beta}^{\prime})\in(0,\infty)$ such that

$\sum_{n\geq 0}\big{(}U^{\bar{\beta}}_{N}\big{)}^{2}(n)\leq\frac{C}{(\log
N)^{2}}\xrightarrow{N\to\infty}0\,,$

The two bounds above, in combination with (3.55) and (3.56), allow us to
write:

$\begin{split}\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}&\geq(1-e^{-cR^{2}})^{2Kh}\,(1-e^{-\kappa\,R})^{K}\,(1-e^{-\kappa\,R^{2}\,C^{2}_{K,M}})^{K}\\\
&\qquad\qquad\times\Bigg{(}\prod_{1\leq i<j\leq
h}\mathrm{E}\Big{[}e^{\frac{\pi\beta_{i,j}}{\log
N}\,\mathsf{L}^{(i,j)}_{N}}\Big{]}-K\cdot\widetilde{C}_{K}\cdot\varepsilon_{N,M}-o_{N}(1)-o_{K}(1)\Bigg{)}\,,\end{split}$

which together with upper bound (3.52) entail that

$\lim_{K\to\infty}\lim_{M\to\infty}\lim_{R\to\infty}\lim_{N\to\infty}\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}=\prod_{1\leq
i<j\leq h}\frac{1}{1-\beta_{i,j}}\,.$

∎

We are now ready to put all pieces together and prove the main result of the
paper, Theorem 1.1.

  * Proof of Theorem 1.1.

Let $\varepsilon>0$. There exists large $K=K_{\varepsilon}\in\mathbb{N}$ such
that uniformly in $N\in\mathbb{N}$

$\Big{|}M^{\boldsymbol{\beta}}_{N,h}-\sum_{r=0}^{K}H_{r,N}\Big{|}\leq\varepsilon\,,$
(3.57)

by Proposition 3.2. We have

$\begin{split}\Big{|}\sum_{r=0}^{K}H_{r,N}-\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}\Big{|}\leq\bigg{(}\sum_{r=0}^{K}(H^{\mathsf{(superdiff)}}_{r,N,R}+H^{\mathsf{(multi)}}_{r,N})\bigg{)}+&\Big{|}\sum_{r=0}^{K}(H^{\mathsf{(diff)}}_{r,N,R}-H^{\mathsf{(main)}}_{r,N,R,M})\Big{|}\\\
&+\Big{|}\sum_{r=0}^{K}(H^{\mathsf{(main)}}_{r,N,R,M}-H^{\mathsf{(rew)}}_{r,N,R,M})\Big{|}\,.\end{split}$

By Propositions 3.1, 3.3 we have that

$\lim_{R\to\infty}\lim_{N\to\infty}\bigg{(}\sum_{r=0}^{K}(H^{\mathsf{(superdiff)}}_{r,N,R}+H^{\mathsf{(multi)}}_{r,N})\bigg{)}\leq\lim_{R\to\infty}\sup_{N\in\mathbb{N}}\sum_{r=0}^{K}H^{\mathsf{(superdiff)}}_{r,N,R}+\lim_{N\to\infty}\sum_{r=0}^{K}H^{\mathsf{(multi)}}_{r,N}=0\,.$

Moreover, by Proposition 3.5 we have that

$\lim_{R\to\infty}\lim_{M\to\infty}\lim_{N\to\infty}\Big{|}\sum_{r=0}^{K}H^{\mathsf{(diff)}}_{r,N,R}-\sum_{r=0}^{K}H^{\mathsf{(main)}}_{r,N,R,M}\Big{|}=0\,.$

Last, by Proposition 3.7 we have that

$\lim_{R\to\infty}\lim_{M\to\infty}\lim_{N\to\infty}\Big{|}\sum_{r=0}^{K}H^{\mathsf{(main)}}_{r,N,R,M}-\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}\Big{|}=0\,,$

therefore

$\lim_{R\to\infty}\lim_{M\to\infty}\lim_{N\to\infty}\Big{|}\sum_{r=0}^{K}H_{r,N}-\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}\Big{|}=0\,.$
(3.58)

By Proposition 3.11 we have that

$\lim_{K\to\infty}\lim_{R\to\infty}\lim_{M\to\infty}\lim_{N\to\infty}\sum_{r=0}^{K}H^{\mathsf{(rew)}}_{r,N,R,M}=\prod_{1\leq
i<j\leq h}\frac{1}{1-\beta_{i,j}}\,,$ (3.59)

Therefore, by (3.57), (3.58) and (3.59) we obtain that

$\lim_{N\to\infty}M^{\boldsymbol{\beta}}_{N,h}=\prod_{1\leq i<j\leq
h}\frac{1}{1-\beta_{i,j}}\,.$

∎

Acknowledgements. We thank Francesco Caravenna and Rongfeng Sun for useful
comments on the draft. D. L. acknowledges financial support from EPRSC through
grant EP/HO23364/1 as part of the MASDOC DTC at the University of Warwick. NZ
was supported by EPSRC through grant EP/R024456/1.

## References

  * [CSZ17] F. Caravenna, R. Sun, N. Zygouras. Universality in marginally relevant disordered systems. Ann. Appl. Prob. 27, 3050–3112 (2017).
  * [CSZ18] F. Caravenna, R. Sun, N. Zygouras, The two-dimensional KPZ equation in the entire subcritical regime, Ann. Prob. 48(3), 1086-1127 (2020)
  * [CSZ19a] F. Caravenna, R. Sun, N. Zygouras. The Dickman subordinator, renewal theorems and disordered systems. Electronic J. Prob., 24, (2019).
  * [CSZ21] F. Caravenna, R. Sun, N. Zygouras. The critical $2d$ stochastic heat flow, arXiv:2109.03766, (2021).
  * [C17] F. Comets, Directed Polymers in Random Environments, Lecture Notes in Mathematics, 2175. Springer, Cham, (2017)
  * [CZ21] C. Cosco, O. Zeitouni, Moments of partition functions of $2d$ gaussian polymers in the weak disorder regime - I, arXiv:2112.03767, (2021).
  * [DFT94] G. F. Dell’Antonio, R. Figari, A. Teta. Hamiltonians for systems of N particles interacting through point interactions. Ann. de l’IHP Physique théorique, Vol. 60, No. 3, pp. 253-290, (1994).
  * [DR04] J. Dimock and S. Rajeev. Multi-particle Schrödinger operators with point interactions in the plane. J Phys A: Math Gen, 37(39):9157, (2004).
  * [ET60] P. Erdös, S.J. Taylor. Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar. 11, 137–162, (1960).
  * [GS09] J. Gärtner, R. Sun, A quenched limit theorem for the local time of random walks on $Z^{2}$, Stoch. Processes and their Appl., 119(4), 1198-1215, (2009),
  * [GQT21] Y. Gu. J. Quastel, L.C. Tsai, Moments of the 2D SHE at criticality. Prob. and Math. Physics, 2(1), 179-219, (2021).
  * [Kn93] F. B. Knight. Some remarks on mutual windings. Séminaire de probabilités de Strasbourg, Springer, 27, p. 36-43, (1993).
  * [Kn94] F. B. Knight. Erratum to: “Some remarks on mutual windings”, Séminaire de probabilités de Strasbourg, Springer, 28, p. 334, (1994).
  * [LL10] G.F. Lawler, V. Limic. Random walk: a modern introduction. Cambridge Studies in Advanced Mathematics, 123, Cambridge University Press, (2010).
  * [LZ21] D. Lygkonis, N. Zygouras. Moments of the 2d directed polymer and a generalisation of the Erdös-Taylor theorem, arXiv:2109.06115, (2021).
  * [PY86] J. Pitman, M. Yor. Asymptotic laws of planar Brownian motion. Ann. Probab. 14(3): 733-779, (1986).
  * [Y91] M. Yor. Étude asymptotique des nombres de tours de plusieurs mouvement browniens complexes corrélés. Random walks, Brownian motion, and interacting particle systems, 441- 455, Prog. Probab. 28, Birkhauser, (1991).