$B^{(r)}=0$. Our choice $\Im(k_{j})>0$ and $\Im(k^{\prime}_{j})=-\Im(k_{j})<0$
for evanescent channels ensures that $r^{(r)}_{pe}(L)$, $r^{(r)}_{ep}(L)$, and
$r^{(r)}_{ee}(L)$ decay exponentially with $L$. This is also the case for
$t^{(r)}_{pe}(L)$ whereas $t^{(r)}_{pp}(L)$ oscillates with $L$.
The general composition law reads

$t=t^{(r)}(L)(\mathds{1}-r^{\prime(l)}r^{(r)}(L))^{-1}t^{(l)}$ (72)

In the limit where $L\Im(k_{j})\gg 1$ for all $p+1\leq j\leq N$, we get for
large $L$

$t\approx
t^{(r)}(L)\Pi_{p}(\mathds{1}-r^{\prime(l)}_{pp}r^{(r)}_{pp}(L))^{-1}\Pi_{p}t^{(l)}$
(73)

where we have introduced the rank $p$ projector $\Pi_{p}$ on the subset of
propagating channels inside the intermediate region. From the above equation
we can directly see that if $p=0$, i.e all channels are evanescent, in the
large $L$ limit, there is no transmission. Moreover, if there is only one
propagating channel, $p=1$, and $|r^{(l)}_{pp}|$ and $|r^{(r)}_{pp}|$ are
close to 1, sharp resonances with maximal transmission are possible. However,
when $p\geq 2$, interference between the various propagating channels in the
intermediate region decreases the maximal transmission at resonances.
To illustrate this point further, we note that the unitary relations 69, 70
imply that the scattering sub-matrix $S_{pp}$ associated to an interface and
defined by:

$S_{pp}=\begin{pmatrix}r_{pp}&t^{\prime}_{pp}\\\
t_{pp}&r^{\prime}_{pp}\end{pmatrix}$ (74)

is unitary.

From Eq. 73, we see that resonances may occur when $t^{(l)}_{pp}$ and
$t^{(r)}_{pp}$ are small. When $t$ is small, we can write a unitary scattering
matrix as

$S\cong\begin{pmatrix}r_{0}(\mathds{1}-\frac{1}{2}t^{\dagger}t)&-r_{0}t^{\dagger}r^{\prime}_{0}\\\
t&(\mathds{1}-\frac{1}{2}tt^{\dagger})r^{\prime}_{0}\end{pmatrix}$ (75)

where $r_{0}$ and $r^{\prime}_{0}$ are unitary matrices and all entries of $t$
are small of order $\epsilon$. Then $S^{\dagger}S=\mathds{1}+O(\epsilon^{3})$.
Using this parameterization for $S^{(l)}_{pp}$ and $S^{(r)}_{pp}$ and dropping
the $pp$ subscript for notational convenience, Eq. 73 becomes:

$t\cong
t^{(r)}e^{ikL}(\mathds{1}-(\mathds{1}-t^{(l)}t^{\dagger(l)}/2)r^{\prime(l)}_{0}e^{-ik^{\prime}L}r^{(r)}_{0}\\\
\times(\mathds{1}-\frac{1}{2}t^{\dagger(r)}t^{(r)})e^{ikL})^{-1}t^{(L)}$ (76)

So, the condition for resonance now selects the energies at which the unitary
matrix $r^{\prime(l)}_{0}e^{-ik^{\prime}(E)L}r_{0}^{(r)}e^{ik(E)L}$ has an
eigenvalue equal to 1. When the number of propagating channels is at least
two, we expect that the behavior of the transmission near these resonances is
going to be significantly more complex than for a single propagating channel.

##  Appendix F Tight-Binding model and forms of the matrix elements

In the main text we saw that the Schrödinger equation could be expressed as a
tight binding equation relating the wavefunctions of a slice to those to its
left and right. On discretizing the energy functional and then taking the
derivative we get a tight-binding problem with nearest and next nearest
neighbour hoppings. In this section we give illustrative examples of how the
matrix elements for the matrices relating the different slices look. The
nearest and next nearest neighbour from the right contributions will enter as
matrix elements in the $A_{R}$ matrix, similar contributions from the left
will enter in the $A_{L}$ matrix and onsite contributions and nearest
neighbour contributions from above and below will enter in the $D$ matrix. Let
us look at some of the forms of these matrix elements.
First consider the exchange term. One can discretize this term by simply
writing the contribution from the $i^{\rm{th}}$ site as

$E_{Ji}=J(\bm{n}_{i}-\bm{n}_{i+1})^{2}$ (77)

exapnding the above equation we get constants plus an
$\bm{n}_{i}\cdot\bm{n}_{i+1}$ term. One can expand this term by expressing the
$\bm{n}_{i}$ in terms of $\chi_{1}$ and $\chi_{2}$ by using Eqs. (43), (44) in
appendix A. On doing so, and keeping upto $\rm{O}(\chi_{1/2}^{2})$ terms one
finds that

$\displaystyle\frac{\partial E_{ji}}{\partial\chi_{1i}}$
$\displaystyle=\bm{n}_{0i}\cdot\bm{n}_{0j}\chi_{1i}-\bm{e}_{1i}\cdot(\chi_{1j}\bm{e}_{1j}+\chi_{2j}\bm{e}_{2j})$
(78) $\displaystyle\frac{\partial E_{ji}}{\partial\chi_{2i}}$
$\displaystyle=\bm{n}_{0i}\cdot\bm{n}_{0j}\chi_{2i}-\bm{e}_{2i}\cdot(\chi_{1j}\bm{e}_{1j}+\chi_{2j}\bm{e}_{2j})$
(79)

from the above two equations one can directly read out the nearest neighbour
and on-site contributions from the coefficients of $\chi_{1/2j}$ and
$\chi_{1/2i}$ respectively. The exchange term does not induce next-nearest
neighbor hopping. Now, after discretizing the topological charge terms as in
the main text, we obtained a tight-binding model with hopping terms up to
second nearest neighbours. Let us consider one term from the first line in Eq.
20 of the main text. The derivative of this term can be expressed as

$\displaystyle\begin{split}\frac{\partial\delta\Omega_{01}^{2}}{\partial\chi_{10}}&=2\delta\Omega_{01}\frac{\partial\delta\Omega_{01}}{\partial\chi_{10}}\\\
&=2\delta\Omega_{01}(-f_{\alpha_{01}}\bm{z}_{01}\cdot\bm{e}_{10})\end{split}$
(80)

where $f_{\alpha_{01}}=\sin(\alpha_{01})/(1+\cos(\alpha_{01}))$, and
$\bm{n}_{0}\times\bm{n}_{1}=\sin(\alpha_{01})\bm{z}_{01}$. One can then expand
$\delta\Omega_{01}$ using Eq. 18 in the main text, and then read off the
coefficients same as above. A similar procedure can be used for all the other
terms in Eq. 20.

##  Appendix G Scaling functions for discretization

Th real space discretization procedure outlined in the main text requires each
coupling constant to be scaled by a factor, so that the results are
independent of $N$ is the large $N$ limit.
From the standard finite-difference type discretization scheme for the
exchange terms, we know that the denominator will be $(a/N)^{2}$ because of
the double derivative, where $a/N$ is the grid-size. Therefore, to get the
correct continuum limit $J$ should be multiplied by $(N/a)^{2}$. Similarly
from the expression of the topological charge density, we can see that the
denominator will be $(a/N)^{4}$, hence $g$ should be multiplied by
$(N/a)^{4}$.
While the argument above for the exchange term is pretty well known, the
argument for the scaling of the $g$ term might be a bit too simplistic. In
which case one can also come up with a more sophisticated argument with the
same result. Let us denote the topological charge of the $\bm{n}_{0}$ field
generated by the theta functions in section III, over a plaquette, to be
$Q_{\square}$. If we change $\bm{n}_{0}$ to $\bm{n}_{0}+\bm{n}_{1}$, where
$\bm{n}_{1}$ is some small deviation such that $\bm{n}_{0}\cdot\bm{n}_{1}=0$
everywhere, $Q_{\square}$ is changed into $Q_{\square}+\triangle Q_{\square}$,
where

$\triangle
Q_{\square}=\frac{1}{4\pi}\oint\bm{n}_{0}\cdot\bigg{(}\bm{n}_{1}\times\frac{\partial\bm{n}_{0}}{\partial
u}\bigg{)}du$ (81)

Here, the integral is taken along the boundary of the above square plaquette
and $u$ is an arbitrary parameter on this boundary. It is convenient to write
$\bm{n}_{1}=\bm{v}(\bm{r})\times\bm{n}_{0}(\bm{r})$, where $\bm{v}(\bm{r})$ is
an infinitesimal rotation vector. Using the fact that
$\bm{n}_{0}\cdot\partial\bm{n}_{0}/\partial u=0$, we get

$\triangle
Q_{\square}=\frac{1}{4\pi}\oint\bm{v}\cdot\frac{\partial\bm{n}_{0}}{\partial
u}du$ (82)

Using Green's equation one can express the above as an integral over the whole
plaquette as:

$\triangle
Q_{\square}=\frac{1}{4\pi}\int\int_{\square}dxdy\bigg{(}\frac{\partial\bm{v}}{\partial
x}\cdot\frac{\partial\bm{v}}{\partial y}-\frac{\partial\bm{v}}{\partial
y}\cdot\frac{\partial\bm{n}_{0}}{\partial x}\bigg{)}$ (83)

As in the next section we check that if $v$ is constant in space (global
rotation in spin space), $\triangle Q_{0}=0$. Also, we see that $\triangle
Q_{\square}$ is expected to be proportional to the plaquette area $(a/N)^{2}$,
when $N$ is large and $\bm{n}_{0}$ and $\bm{v}$ are smooth fields. Therefore,
we may write

$\triangle Q_{\square}=\delta\rho(a/N)^{2},$ (84)

with $\delta\rho$ being the variation of the local topological charge density.
Therefore the 1st term in Eq. 46 should scale as (in the large $N$ limit,
which is the relevant limit for numerics)

$\displaystyle\begin{split}g\int(\delta\rho)^{2}dxdy&\approx
g\sum_{\rm{plaq}}[\triangle
Q_{\square}(\frac{N}{a}^{2})]^{2}(\frac{a}{N})^{2}\\\ &\approx
g^{\prime}\sum_{\rm{plaq}}(\triangle
Q_{\square})^{2}(\frac{a}{N})^{2}\end{split}$ (85)

Hence, we see that the scaled version should be $g^{\prime}=g(N/a)^{4}$

##  Appendix H Test for topological charge discretization scheme

To test whether our geodesic scheme for discretizing the topological charge
density is correct, we perform the following non-trivial check. As in the last
section we take an infinitesimal rotation vector $\bm{v}$, constant in space,
and rotate the ground state spin vector $\bm{n}_{0}({\bm{r}})$. On doing so,
we can define new variables $\chi^{\prime}_{1}$ and $\chi^{\prime}_{2}$ which
are related to the old variables by

$\displaystyle\begin{split}\chi^{\prime}_{1}(\bm{r})&=\bm{v}\cdot\bm{e}_{2}(\bm{r})\\\
\chi^{\prime}_{2}(\bm{r})&=-\bm{v}\cdot\bm{e}_{1}(\bm{r})\end{split}$ (86)

Using the above expressions we form a column vector of the
$\chi^{\prime}(\bm{r})=\chi^{\prime}_{1}(\bm{r})+i\chi^{\prime}_{2}(\bm{r})$
and
$\bar{\chi}^{\prime}(\bm{r})=\chi^{\prime}_{1}(\bm{r})(\bm{r})-i\chi^{\prime}_{2}(\bm{r})$
from all the sites. We then right multiply the Hamiltonian constructed from
only the topological charge density term ($J=0$) and multiply it with this
vector. If the discretization scheme is correct, then this product should be
zero, since an infinitesimal global rotation should not induce any variation
of the topological charge density. We have checked this in our calculations
and indeed it does return a column of values which are for all intents and
purposes zero ($O(1e-16)$).

##  Appendix I Boundary conditions for spectra and relation between $\chi$ and
$\bar{\chi}$

To obtain the spectra of the skyrmion crystal, we considered periodic boundary
conditions along both $x$ and $y$\- axes of an $a\times a$ unit cell. For the
tight-binding model after taking the derivative of the discretized energy
functional, this implies that the for the right(left)-most site, the
right(left) nearest neighbor contribution will pick up a
$e^{iq_{x}a}(e^{-iq_{x}a})$ phase-factor and similarly for the
top(bottom)-most site, the top(bottom) nearest neighbor contribution will pick
up a $e^{iq_{y}a}(e^{-iq_{y}a})$ phase factor. The phase factors encode how
the momentum dependence enters the Hamiltonian matrix. The Hamiltonian is
constructed in the site basis, so if there are $N$ rows and columns each in
the unit cell, the Hamiltonian has a size $2N^{2}\times 2N^{2}$, where the
factor of $2$ comes because of the presence of both $\chi$ and $\bar{\chi}$.
Each diagonal $2N\times 2N$ block of the Hamiltonian comprises the on-site,
right and left nearest neighbor contributions that come from that particular
row. The off-diagonal blocks comprise the up and down nearest neighbor terms
as well as the second nearest neighbor contributions.
An important point to note while doing these calculations for the spectra and
the scattering problem is that $\chi$ and $\bar{\chi}$ aren't always complex
conjugates of one another. To see this remember that from appendix A,
$\chi=\chi_{1}+i\chi_{2}$ and $\bar{\chi}=\chi_{1}-i\chi_{2}$, however, both
$\chi_{1}$ and $\chi_{2}$ pickup complex phase factors $e^{\pm iq_{x/y}a}$ due
to the boundary conditions as described above. For $q_{x},q_{y}=0$, the
relation $\chi=\bar{\chi}^{*}$ holds since $\chi_{1}$ and $\chi_{2}$ are real.
However, generally, this is not the case, since
$\chi_{1},\chi_{2}\in\mathbb{C}$, and so $\chi\neq\bar{\chi}^{*}$.

##  Appendix J Lie-algebra structure in non-linear sigma model

In this appendix we give details on some of the calculations to show the Lie-
algebra structure of the vector fields mentioned in section X of the main
text. We showed that $\bm{x}\rightarrow X_{\bm{\epsilon}(\bm{x})}$ is a vector
field associated to the infinitesimal left rotation
$\exp(-i\bm{\epsilon}\cdot\bm{\sigma}/2)$. We know that vector fields form a
Lie-algebra under the Lie-bracket. The Lie-bracket is defined as

$L_{[\bm{X},\bm{Y}]}(f)=(L_{\bm{X}}L_{\bm{Y}}-L_{\bm{Y}}L_{\bm{X}})f$ (87)

for any arbitrary function $f$, where
$L_{\bm{X}}f\equiv\sum_{i}X^{i}\partial_{i}f$ denotes the Lie derivative of f
along vector field $\bm{X}$. We can write the Lie derivative as

$\displaystyle\begin{split}&(L_{\bm{X}}L_{\bm{Y}}-L_{\bm{Y}}L_{\bm{X}})f=X^{i}\partial_{i}(Y^{j}\partial_{j}f)-Y^{j}\partial_{j}(X^{i}\partial_{i}f)\\\
&=(X^{i}\partial_{i}Y^{j}-Y^{i}\partial_{i}X^{j})\partial_{j}f\equiv[\bm{X},\bm{Y}]^{j}\partial_{j}f\end{split}$
(88)

therefore we get
$[\bm{X},\bm{Y}]=\bm{X}\cdot\bm{\nabla}\bm{Y}-\bm{Y}\cdot\bm{\nabla}\bm{X}\equiv
Y^{\prime}(X)-X^{\prime}(Y)$ where $\bm{X}^{\prime}$ denotes the Jacobian
matrix $(X^{\prime})^{j}_{i}\equiv\partial_{i}X^{j}$. Now, let us compute
$[\bm{X}_{\bm{\epsilon}},\bm{X}_{\bm{\eta}}]$. Using Eq. 31 from the main text
we can write

$\displaystyle\begin{split}\bm{X}^{\prime}_{\bm{\eta}}(\bm{X}_{\bm{\epsilon}})&=-\dfrac{\bm{x}}{\sqrt{1-\bm{x}^{2}}}\cdot(\sqrt{1-\bm{x}^{2}}\frac{\bm{\epsilon}}{2}-\frac{\bm{\epsilon}}{2}\times\bm{x})\frac{\bm{\eta}}{2}\\\
&-\dfrac{\bm{\eta}}{2}\times(\sqrt{1-\bm{x}^{2}}\frac{\bm{\epsilon}}{2}-\frac{\bm{\epsilon}}{2}\times\bm{x})\\\
&=-\frac{1}{4}\bigg{(}(\bm{x}\cdot\bm{\epsilon})\bm{\eta}+\sqrt{1-\bm{x}^{2}}\,\bm{\eta}\times\bm{\epsilon}-\bm{\eta}\times(\bm{\epsilon}\times\bm{x})\bigg{)}\end{split}$
(89)

Similarly one can also write

$\bm{X}^{\prime}_{\bm{\epsilon}}(\bm{X}_{\bm{\eta}})=-\frac{1}{4}\bigg{(}(\bm{x}\cdot\bm{\eta})\bm{\epsilon}+\sqrt{1-\bm{x}^{2}}\,\bm{\epsilon}\times\bm{\eta}-\bm{\epsilon}\times(\bm{\eta}\times\bm{x})\bigg{)}$
(90)

Using the above two equations one gets

$\displaystyle\begin{split}[\bm{X}_{\bm{\epsilon}},\bm{X}_{\bm{\eta}}]&=\frac{1}{4}\bigg{(}\big{(}(\bm{x}\cdot\bm{\eta})\bm{\epsilon}-(\bm{x}\cdot\bm{\epsilon})\bm{\eta}\big{)}+2\sqrt{1-\bm{x}^{2}}\bm{\epsilon}\times\bm{\eta}\\\
&-\big{(}\bm{\epsilon}\times(\bm{\eta}\times\bm{x})-\bm{\eta}\times(\bm{\epsilon}\times\bm{x})\big{)}\bigg{)}\\\
&=\sqrt{1-\bm{x}^{2}}\,\dfrac{\bm{\epsilon}\times\bm{\eta}}{2}-\frac{1}{2}(\bm{\epsilon}\times\bm{\eta})\times\bm{x}\\\
&=\bm{X}_{\bm{\eta}\times\bm{\epsilon}}\end{split}$ (91)

and hence, we recover the Lie-algebra structure of $\rm{SO}(3)$. Similarly for
the right action we get,

$[\bm{Y}_{\bm{\epsilon}},\bm{Y}_{\bm{\eta}}]=-\bm{Y}_{\bm{\epsilon}\times\bm{\eta}}=\bm{Y}_{\bm{\eta}\times\bm{\epsilon}}$
(92)

Let us examine the correspondence between Poisson brackets $\\{g,h\\}$ and Lie
brackets $[X_{g},X_{h}]$ of their associated Hamiltonian vector fields $X_{g}$
and $X_{h}$. Hamilton's equations, relating $X_{g}$ to $g$, are equivalent to
requiring $L_{X_{g}}f=\\{f,g\\}$ for any function $f$ over phase-space. Then
we have that

$\displaystyle\begin{split}L_{X_{g}}L_{X_{h}}(f)&=\\{\\{f,h\\},g\\}\\\
L_{X_{h}}L_{X_{g}}(f)&=\\{\\{f,g\\},h\\}\end{split}$ (93)

hence one can express the Lie-bracket as

$\displaystyle\begin{split}L_{[X_{g},X_{h}]}(f)&=\\{\\{f,h\\},g\\}+\\{\\{g,f\\},h\\}=-\\{\\{h,g\\},f\\}\\\
&==\\{f,\\{h,g\\}\\}=L_{X_{\\{h,g\\}}}(f)\\\
[X_{g},X_{h}]&=X_{\\{h,g\\}}\end{split}$ (94)

where in the 2nd equality of the first line in the above equation we have used
the Jacobi identity.

## References

  * Anderson (2018) P. W. Anderson,  _Basic notions of condensed matter physics_ (CRC Press, 2018).
  * Moessner and Moore (2021) R. Moessner and J. E. Moore,  _Topological phases of matter_ (Cambridge University Press, 2021).
  * Sondhi  _et al._ (1993) S. L. Sondhi, A. Karlhede, S. A. Kivelson, and E. H. Rezayi, Phys. Rev. B 47, 16419 (1993).
  * Brey  _et al._ (1995) L. Brey, H. A. Fertig, R. Côté, and A. H. MacDonald, Phys. Rev. Lett. 75, 2562 (1995).
  * Rajaraman (1982) R. Rajaraman, Solitons and instantons (1982).
  * Mühlbauer  _et al._ (2009) S. Mühlbauer, B. Binz, F. Jonietz, C. Pfleiderer, A. Rosch, A. Neubauer, R. Georgii, and P. Böni, Science 323, 915 (2009).
  * Yu  _et al._ (2010) X. Yu, Y. Onose, N. Kanazawa, J. H. Park, J. Han, Y. Matsui, N. Nagaosa, and Y. Tokura, Nature 465, 901 (2010).
  * Gervais  _et al._ (2005) G. Gervais, H. Stormer, D. Tsui, P. Kuhns, W. Moulton, A. Reyes, L. Pfeiffer, K. Baldwin, and K. West, Physical review letters 94, 196803 (2005).
  * Desrat  _et al._ (2002) W. Desrat, D. Maude, M. Potemski, J. Portal, Z. Wasilewski, and G. Hill, Physical review letters 88, 256807 (2002).
  * Bayot  _et al._ (1996) V. Bayot, E. Grivei, S. Melinte, M. B. Santos, and M. Shayegan, Phys. Rev. Lett. 76, 4584 (1996).
  * Gallais  _et al._ (2008) Y. Gallais, J. Yan, A. Pinczuk, L. N. Pfeiffer, and K. W. West, Phys. Rev. Lett. 100, 086806 (2008).
  * Zhu  _et al._ (2010) H. Zhu, G. Sambandamurthy, Y. P. Chen, P. Jiang, L. W. Engel, D. C. Tsui, L. N. Pfeiffer, and K. W. West, Phys. Rev. Lett. 104, 226801 (2010).
  * Wei  _et al._ (2018) D. S. Wei, T. Van Der Sar, S. H. Lee, K. Watanabe, T. Taniguchi, B. I. Halperin, and A. Yacoby, Science 362, 229 (2018).
  * Zhou  _et al._ (2021) T. X. Zhou, J. J. Carmiggelt, L. M. Gächter, I. Esterlis, D. Sels, R. J. Stöhr, C. Du, D. Fernandez, J. F. Rodriguez-Nieva, F. Büttner, _et al._ , Proceedings of the National Academy of Sciences 118, e2019473118 (2021).
  * Zhou  _et al._ (2022) H. Zhou, C. Huang, N. Wei, T. Taniguchi, K. Watanabe, M. P. Zaletel, Z. Papić, A. H. MacDonald, and A. F. Young, Physical Review X 12, 021060 (2022).
  * Pierce  _et al._ (2022) A. T. Pierce, Y. Xie, S. H. Lee, P. R. Forrester, D. S. Wei, K. Watanabe, T. Taniguchi, B. I. Halperin, and A. Yacoby, Nature Physics 18, 37 (2022).
  * Assouline  _et al._ (2021) A. Assouline, M. Jo, P. Brasseur, K. Watanabe, T. Taniguchi, T. Jolicoeur, D. Glattli, N. Kumada, P. Roche, F. Parmentier, _et al._ , Nature Physics 17, 1369 (2021).
  * Zhang  _et al._ (2005) Y. Zhang, Y.-W. Tan, H. L. Stormer, and P. Kim, nature 438, 201 (2005).
  * Novoselov  _et al._ (2007) K. S. Novoselov, Z. Jiang, Y. Zhang, S. Morozov, H. L. Stormer, U. Zeitler, J. Maan, G. Boebinger, P. Kim, and A. K. Geim, science 315, 1379 (2007).
  * Girvin (2002) S. M. Girvin,  _Aspects topologiques de la physique en basse dimension. Topological aspects of low dimensional systems: Session LXIX. 7–31 July 1998_ , , 53 (2002).
  * Hasan and Kane (2010) M. Z. Hasan and C. L. Kane, Rev. Mod. Phys. 82, 3045 (2010).
  * Zhou  _et al._ (2020) H. Zhou, H. Polshyn, T. Taniguchi, K. Watanabe, and A. Young, Nature Physics 16, 154 (2020).
  * Debarre (2005) O. Debarre,  _Complex tori and abelian varieties_ , 6 (American Mathematical Soc., 2005).
  * Douçot  _et al._ (2008) B. Douçot, M. O. Goerbig, P. Lederer, and R. Moessner, Phys. Rev. B 78, 195327 (2008).
  * Pendry (1994) J. Pendry, Journal of Modern Optics 41, 209 (1994).
  * Iwasaki  _et al._ (2014) J. Iwasaki, A. J. Beekman, and N. Nagaosa, Phys. Rev. B 89, 064412 (2014).
  * Schütte and Garst (2014) C. Schütte and M. Garst, Phys. Rev. B 90, 094423 (2014).
  * Atteia  _et al._ (2022) J. Atteia, F. Parmentier, P. Roulleau, and M. O. Goerbig, arXiv:2204.12795 (2022).
  * Wei  _et al._ (2021) N. Wei, C. Huang, and A. H. MacDonald, Phys. Rev. Lett. 126, 117203 (2021).
  * Moon  _et al._ (1995) K. Moon, H. Mori, K. Yang, S. M. Girvin, A. H. MacDonald, L. Zheng, D. Yoshioka, and S.-C. Zhang, Phys. Rev. B 51, 5138 (1995).
  * Kovrizhin  _et al._ (2013a) D. L. Kovrizhin, B. Douçot, and R. Moessner, Phys. Rev. Lett. 110, 186802 (2013a).
  * Haldane and Rezayi (1985) F. D. M. Haldane and E. H. Rezayi, Phys. Rev. B 31, 2529 (1985).
  * Pichard and Sarma (1981) J.-L. Pichard and G. Sarma, Journal of Physics C: Solid State Physics 14, L617 (1981).
  * MacKinnon and Kramer (1981) A. MacKinnon and B. Kramer, Phys. Rev. Lett. 47, 1546 (1981).
  * Fisher and Lee (1981) D. S. Fisher and P. A. Lee, Phys. Rev. B 23, 6851 (1981).
  * Douçot  _et al._ (2018) B. Douçot, D. L. Kovrizhin, and R. Moessner, Annals of Physics 399, 239 (2018).
  * Kharitonov (2012) M. Kharitonov, Phys. Rev. B 85, 155439 (2012).
  * Côté  _et al._ (2007a) R. Côté, D. B. Boisvert, J. Bourassa, M. Boissonneault, and H. A. Fertig, Phys. Rev. B 76, 125320 (2007a).
  * Kovrizhin  _et al._ (2013b) D. L. Kovrizhin, B. Douçot, and R. Moessner, Phys. Rev. Lett. 110, 186802 (2013b).
  * Côté  _et al._ (2007b) R. Côté, D. B. Boisvert, J. Bourassa, M. Boissonneault, and H. A. Fertig, Phys. Rev. B 76, 125320 (2007b).
  * Kim  _et al._ (2020) M. Kim, S. Xu, A. Berdyugin, A. Principi, S. Slizovskiy, N. Xin, P. Kumaravadivel, W. Kuang, M. Hamer, R. Krishna Kumar, _et al._ , Nature communications 11, 2339 (2020).
  * Fertig  _et al._ (1997) H. A. Fertig, L. Brey, R. Côté, A. H. MacDonald, A. Karlhede, and S. L. Sondhi, Phys. Rev. B 55, 10671 (1997).
  * Cao  _et al._ (2018a) Y. Cao, V. Fatemi, A. Demir, S. Fang, S. L. Tomarken, J. Y. Luo, J. D. Sanchez-Yamagishi, K. Watanabe, T. Taniguchi, E. Kaxiras, _et al._ , Nature 556, 80 (2018a).
  * Cao  _et al._ (2018b) Y. Cao, V. Fatemi, S. Fang, K. Watanabe, T. Taniguchi, E. Kaxiras, and P. Jarillo-Herrero, Nature 556, 43 (2018b).
  * Khalaf  _et al._ (2021) E. Khalaf, S. Chatterjee, N. Bultinck, M. P. Zaletel, and A. Vishwanath, Science advances 7, eabf5299 (2021).
  * Khalaf and Vishwanath (2022) E. Khalaf and A. Vishwanath, Nature Communications 13, 6245 (2022).
  * Kwan  _et al._ (2022) Y. H. Kwan, G. Wagner, N. Bultinck, S. H. Simon, and S. Parameswaran, Physical Review X 12, 031020 (2022).
  * Chatterjee  _et al._ (2020) S. Chatterjee, N. Bultinck, and M. P. Zaletel, Physical Review B 101, 165141 (2020).
  * Grover  _et al._ (2022) S. Grover, M. Bocarsly, A. Uri, P. Stepanov, G. Di Battista, I. Roy, J. Xiao, A. Y. Meltzer, Y. Myasoedov, K. Pareek, _et al._ , Nature physics 18, 885 (2022).
  * Xu  _et al._ (2021) Y. Xu, A. Ray, Y.-T. Shao, S. Jiang, D. Weber, J. E. Goldberger, K. Watanabe, T. Taniguchi, D. A. Muller, K. F. Mak, _et al._ , arXiv:2103.09850 (2021).
  * Akram  _et al._ (2021) M. Akram, H. LaBollita, D. Dey, J. Kapeghian, O. Erten, and A. S. Botana, Nano Letters 21, 6633 (2021).
  * Brey  _et al._ (1996) L. Brey, H. A. Fertig, R. Côté, and A. H. MacDonald, Phys. Rev. B 54, 16888 (1996).
  * Kamilla  _et al._ (1996) R. Kamilla, X. Wu, and J. Jain, Solid state communications 99, 289 (1996).
  * Balram  _et al._ (2015) A. C. Balram, U. Wurstbauer, A. Wójs, A. Pinczuk, and J. Jain, Nature communications 6, 8981 (2015).
  * Doretto  _et al._ (2005) R. L. Doretto, M. O. Goerbig, P. Lederer, A. O. Caldeira, and C. M. Smith, Physical Review B 72, 035341 (2005).
  * Wójs and Quinn (2002) A. Wójs and J. J. Quinn, Physical Review B 66, 045323 (2002).
  * Lian and Goerbig (2017) Y. Lian and M. O. Goerbig, Phys. Rev. B 95, 245428 (2017).
  * Weber  _et al._ (2022) T. Weber, D. M. Fobes, J. Waizner, P. Steffens, G. Tucker, M. Bohm, L. Beddrich, C. Franz, H. Gabold, R. Bewley, _et al._ , Science 375 (2022).
  * Yan  _et al._ (2011) P. Yan, X. S. Wang, and X. R. Wang, Phys. Rev. Lett. 107, 177207 (2011).
  * Kim  _et al._ (2014) S. K. Kim, Y. Tserkovnyak, and O. Tchernyshyov, Phys. Rev. B 90, 104406 (2014).
  * Šmejkal  _et al._ (2018) L. Šmejkal, Y. Mokrousov, B. Yan, and A. H. MacDonald, Nature physics 14, 242 (2018).
  * Lee  _et al._ (2022) S. Lee, K. Nakata, O. Tchernyshyov, and S. K. Kim, arXiv:2211.00030 (2022).


# Fairly Allocating Goods in Parallel

Rohan Garg  Department of Computer Science, Purdue University. Email:
<EMAIL_ADDRESS>Alexandros Psomas  Department of Computer
Science, Purdue University. Email<EMAIL_ADDRESS>
###### Abstract

We initiate the study of parallel algorithms for fairly allocating indivisible
goods among agents with additive preferences. We give fast parallel algorithms
for various fundamental problems, such as finding a Pareto Optimal and EF1
allocation under restricted additive valuations, finding an EF1 allocation for
up to three agents, and finding an envy-free allocation with subsidies. On the
flip side, we show that fast parallel algorithms are unlikely to exist
(formally, CC-hard) for the problem of computing Round-Robin EF1 allocations.

##  1 Introduction

The last two decades have witnessed a remarkable improvement in our
computational power, largely due to the widespread adoption of parallel
computing. Parallel computing has become the dominant paradigm in computer
architecture, mainly in the form of multi-core processors. At the same time,
in the overwhelming majority of the AI literature, “efficient algorithm” is a
synonym for “efficient sequential algorithm.” In this paper, we initiate the
study of parallel algorithms for a fundamental problem in fair division:
allocating a set of $m$ indivisible items to $n$ agents with additive
preferences.

Some classical algorithms for this problem proceed in rounds, e.g. the Round
Robin procedure or the Envy-Cycle Elimination procedure [17] that achieve
envy-freeness up to one item (henceforth, EF1), while others are
computationally intractable (NP-hard), e.g. the maximum Nash welfare (MNW)
solution that achieves Pareto efficiency (henceforth, PO) and EF1. Our goal in
this paper is to design, for various, fundamental fair division tasks,
algorithms that run in polylogarithmic time and use a polynomial number of
processors, or to prove that no such algorithm is likely to exist.

###  1.1 Our contribution

As a warm-up for the reader unfamiliar with the capabilities of parallel
algorithms, in Section 3 we consider the basic problem of whether, given an
allocation, various fairness properties can be quickly verified in parallel.
We show that envy-freeness (EF), envy-freeness up-to-one item (EF1), and envy-
freeness up-to-any item (EFX) can all be checked efficiently in parallel, i.e.
we give NC algorithms for verifying these properties. In Section 4, we show
how to use algorithms with logarithmic query complexity [20] to get fast
parallel algorithms for computing EF1 allocations for two and three agents, as
well as how to compute EF1 and fractionally PO allocations for two agents, by
mimicking the adjusted winner process.

In Sections 5 and 6, we study the complexity of allocating items to restricted
additive agents, that is when the value of agent $i$ for item $j$ is either
$0$ or $v_{j}$ (i.e. each item has an inherent value $v_{j}$ and agent $i$
either sees this value or not), and the value of agent $i$ for a subset of
items $S$ is simply $\sum_{j\in S}v_{i,j}$. We first explore the complexity of
finding an EF1 allocation. Arguably, the simplest EF1 algorithm in this
setting is the Round-Robin procedure (agents choose items one at a time,
following a fixed order). In Section 5, we show that, for a given order
$\sigma$ over the agents, one cannot “shortcut” the execution of Round-Robin:
the problem is CC-hard. Surprisingly, this holds even for the case when each
agent positively values at most $3$ items and each item is positively valued
by at most $3$ agents.

Despite this strong negative result, we can efficiently, in parallel, compute
an EF1 and PO allocation when there are a constant number of inherent values,
even when agents positively value more items, and items are positively valued
by more agents. Furthermore, quite similarly to Round-Robin, the allocations
output by our algorithm are “balanced,” in the sense that agents receive the
same number of items (up to divisibility issues). The complexity of our
algorithm is parameterized by $t$, the number of inherent values: it runs in
time $O(\log^{2}(mn))$ and requires $O(m^{5.5+t}n^{5.5})$ processors. Our
algorithm is via a reduction to the problem of _maximum weight perfect
matching_ in a bipartite graph. A beautiful result of [19] shows that a
_minimum_ weight perfect matching (which can be used to find a maximum weight
perfect matching) can be found efficiently in parallel when the weight of the
heaviest edge is polynomially bounded. Our reduction creates multiple copies
of each agent such that the unique item matched to the $j$-th copy corresponds
to the item allocated in the $j$-th round of _some_ Round-Robin procedure (and
hence the overall allocation is EF1). The edge weights are increasing (for
different copies of the same agent), in a way that every maximum weight
matching must give a high-value item to a copy of agent $i$ before giving two
high-value items to copies of a different agent. The restriction on the
valuations allows us to control the rate at which the weights increase, and
specifically bound the maximum weight by a polynomial, so that the algorithm
of [19] can be used. We note that when weights are not bounded by a
polynomial, the maximum weight matching problem cannot be solved efficiently
in parallel (formally, the problem is CC-hard), so removing the condition on
the valuation functions would require a fundamentally different approach.

Finally, in Section 7, we study the problem of fair allocation with subsidies
[12, 4], where the goal is to find an integral allocation of the items as well
as payments to the agents, such that the overall solution is envy-free. We
give an NC algorithm for this problem, and, in fact, prove that one can
compute similar solutions in parallel even in the presence of additional
constraints on the payments, e.g. “A should not be paid more than B”, or “A
should be paid no more than 10 dollars.” We formulate the problem of finding a
constraint-satisfying and envy-eliminating vector as a purely graph-theoretic
problem on a graph we call the payment rejection graph. The constraints are
included by adding edges to this graph. In the most general sense, we can add
edges to our graph that correspond to a constraint of the form “if agent $i$
gets paid more than $x$ dollars, then agent $j$ must get paid more than $y$
dollars”. Any meaningful overall constraint that can be formulated as a set of
such smaller constraints can be added to the problem instance. We highlight
that it is not straightforward to implement such constraints in the existing
algorithms for the fair division with subsidies problem, especially if one
insists on a parallel solution. Our main insight here is that by carefully
constructing a large graph to represent the set of all payment vectors, the
problem of simultaneously eliminating envy and satisfying constraints can be
solved by computing directed reachability in parallel.

###  1.2 Related work

Understanding the parallel complexity of various problems has been a central
theme in theoretical computer science, with some major recent breakthroughs,
e.g. [3]. However, the parallel complexity of problems in fair division
remains relatively unstudied. The closest works to ours are that of [21] and
[8]. [21] study the housing allocation and housing market problems, and give
parallel and distributed algorithms. The housing allocation problem asks for a
matching between $n$ agents and $n$ houses when agents have strict orderings
over the houses. The housing market problem asks for a matching between $n$
agents and $n$ houses when the agents arrive at a market each owning a single
house. On the flip side, [21] show that finding the core of a housing market
is CC-hard by showing that the Top-Trading Cycle Algorithm also solves a CC-
complete problem: Lexicographically First Maximal Matching. In [8], the
authors study the parallel complexity of allocating $m$ divisible homogeneous
resources to a set of $n$ agents with nondecreasing utility functions over the
amount of each resource received. They show, that for $n$ processors, the
parallel time complexity of finding an allocation that has welfare no more
than $\epsilon$ less than a welfare-maximizing allocation is lower bounded by
$\Omega(m\log\frac{1}{n\epsilon})$. They also give an efficient parallel
algorithm that computes an approximately accurate solution for $m=2$
resources.

##  2 Preliminaries

We consider the problem of allocating a set $\mathcal{M}$ of indivisible
goods, labeled by $\\{1,\dots,m\\}$, to a set of agents $\mathcal{N}$, labeled
by $\\{1,\dots,n\\}$. A fractional allocation $X\in[0,1]^{n\cdot m}$ defines
for each agent $i\in\mathcal{N}$ and $j\in\mathcal{M}$ the fraction of item
$j$ that agent $i$ receives. A allocation $X$ is integral if
$X_{i,j}\in\\{0,1\\}$ for all $i\in\mathcal{N}$ and $j\in\mathcal{M}$. An
allocation $X=(X_{1},\dots,X_{n})$ is complete if
$\cup_{i\in\mathcal{N}}X_{i}=\mathcal{M}$ and partial otherwise. Unless stated
otherwise, we use allocation to refer to a complete allocation. We use the
term bundle to refer to a subset of items, and use [$k$] to denote the set
$\\{1,\dots,k\\}$.

Each agent $i\in\mathcal{N}$ has a private valuation function
$v_{i}:2^{\mathcal{M}}\rightarrow\mathbb{R}_{+}$ which describes the utility
agent $i$ receives for each bundle. A valuation function $v_{i}$ is _additive_
if $v_{i}(X_{i})=\sum_{j\in X_{i}}X_{i,j}\cdot v_{i}(\\{j\\})$. A valuation
function $v_{i}$ is _restricted additive_ when $v_{i}$ is additive, and for
each item $g\in\mathcal{M}$, $v_{i}(g)\in\\{0,v(g)\\}$. To ease notation, we
write $v_{i,j}=v_{i}(\\{j\\})$ for the value of agent $i$ for item $j$.

An allocation $X$ is _envy-free_ (EF) if $v_{i}(X_{i})\geq v_{i}(X_{j})$ for
all agents $i,j\in\mathcal{N}$. Since integral EF allocations don’t always
exist (e.g. consider the case of a single item and two agents that have
positive value for it), the community has turned to notions of approximate
fairness. An integral allocation $X$ is _envy-free up to one good_ (EF1) if
for all agents $i,j\in\mathcal{N}$ there exists a good $g\in X_{j}$ such that
$v_{i}(X_{i})\geq v_{i}(X_{j}\backslash g)$ [17]. An integral allocation $X$
is _envy-free up to any good_ (EFX) if for all agents $i,j\in\mathcal{N}$, for
all goods $g\in X_{j}$, $v_{i}(X_{i})\geq v_{i}(X_{j}\backslash g)$ [7]. The
envy-graph for an allocation $X$ is the complete weighted directed graph
$G_{X}=(\mathcal{N},E)$, where there is a vertex for each agent
$i\in\mathcal{N}$, and there is an edge $e\in E$ from vertex $i$ to vertex $j$
with the weight $v_{i}(X_{j})-v_{i}(X_{i})$ [17].

An allocation $X$ Pareto dominates another allocation $Y$ if $v_{i}(X_{i})\geq
v_{i}(Y_{i})$, for all $i\in\mathcal{N}$, and there exists some agent $j$ such
that $v_{j}(X_{j})>v_{j}(Y_{j})$. An integral allocation is called Pareto-
Optimal (PO) or Pareto-Efficient (PE) if no other integral allocation Pareto
dominates it. An allocation is called Fractionally Pareto-Optimal (fPO) if no
other (integral or fractional) allocation Pareto dominates it.

#### Fair division with subsidies.

In the problem of fair division with subsidies, we eliminate the envy of an
allocation by using payments. An allocation with payments
$X_{\vec{q}}=(X,\vec{q})$ is a tuple of an integral allocation $X$ and a
payment vector $\vec{q}=(q_{1},\dots,q_{n})$, where $q_{i}$ is the payment to
agent $i$. Under such an allocation with payments $X_{\vec{q}}$, agent $i$’s
utility is $v_{i}(X_{i})+q_{i}$. We can extend the definition of envy-freeness
to this setting: an allocation with payments $(X,\vec{q})$ is _envy-free_ if
$v_{i}(X_{i})+q_{i}\geq v_{i}(X_{j})+q_{j}$ for all agents
$i,j\in\mathcal{N}$. An allocation $X$ is _envy-freeable_ if there exists a
payment vector $\vec{q}$ such that $(X,\vec{q})$ is envy-free. For a given
envy-freeable allocation $X$, a payment vector $\vec{q}$ is envy-eliminating
if the allocation with payments $X_{\vec{q}}$ is envy-free. [12] prove that,
given an envy-freeable allocation $X$, one can find an envy-eliminating
payment vector for $X$ by computing all-pairs-shortest paths on the envy graph
of $X$ with the edge weights negated.

#### Parallel computation.

For sequential algorithms, our model of computation is typically a single
processor that has access to some memory. For parallel algorithms, in this
paper we adopt the CREW (Concurrent Read Exclusive Write) PRAM (Parallel RAM)
model of computation [15]. The CREW PRAM model allows simultaneous access to
any one memory location for read instructions only.111It is well known that
the strongest PRAM model, the CRCW PRAM model, with $p$ processors can be
simulated by the weakest PRAM model, the EREW PRAM model, with $p$ processors
with at most a $O(\log p)$ factor slowdown [13]. We assume a shared memory
model where each processor has some local memory to execute its program and
all processors can access global shared memory. Additionally, all computation
is synchronous, i.e., all processors are coordinated by some common clock.

To describe parallel algorithms, we use $p_{k}$ to denote the $k$-th
processor. Often we will index processors by items or agents or pairs, e.g.
$p_{j}$ for the processor assigned to item $j$, or $p_{(i,j)}$ for the
processor assigned to the agent $i$, item $j$ pair. We give the basic notions
of efficiency and hardness in the parallel world as well as some useful
parallel primitives. A reader familiar with parallel algorithms can safely
skip the remainder of this section.

For sequential algorithms, we seek polynomial time algorithms, a.k.a
algorithms in P. The analog of this for parallel algorithms is NC or Nick’s
Class. The randomized counterpart of P is RP; similarly, here we have RNC.

######  Definition 1 (NCk [13]).

The class NCk includes all problems of input size $N$ that can be solved in
time $O(\log^{k}n)$ using a polynomial in $N$ number of processors.

######  Definition 2 (RNCk [13]).

The class RNCk includes all problems of input size $N$ that can be solved in
time $O(\log^{k}n)$ using a polynomial in $N$ number of processors, where each
processor can generate an (independently drawn) uniformly random integer in
the range $[1,\dots,M]$ for some integer $M\geq 1$.

The class NC (resp. RNC) includes all problems of input size $N$ that are in
NCk (resp. RNCk) for some constant (with respect to $N$) $k$. We seek NC and
RNC algorithms. That is, when we say that some problem can be solved
efficiently in parallel, this means there is an NC or RNC algorithm for it.

On the flip side, when we say that a problem cannot be solved efficiently in
parallel, we mean that the problem is CC-hard222Another notion of parallel
hardness, P-Completeness, is often used to identify problems in P that seem to
be inherently sequential and thus are likely to not admit any efficient
parallel algorithm. The classes NC and CC are incomparable as are RNC and CC
[10]. Currently, no fast parallel algorithms are known for problems in CC.. To
define the complexity class CC, we need to define the Circuit Comparator Value
Problem (CCVP) and comparator gates. A comparator gate is a gate that has two
inputs and two outputs. The first output wire outputs the minimum of the
inputs, and the second output wire outputs the maximum of the inputs. CCVP is
defined as follows: given a circuit of comparator gates, the inputs to the
circuit, and one output wire of the circuit, calculate the value of this wire.

######  Definition 3 (CC [18]).

CC is the class of all problems that are log-space many-one reducible to CCVP.

The class CC is not known to be in NC nor P-Complete, and, if some problem is
CC-hard, this fact can be taken as evidence that the problem does not admit an
efficient parallel solution. The class CC has natural complete problems, such
as the Stable Marriage Problem and the Lexicographically First Maximal
Matching problem [10].

###  2.1 Useful parallel primitives

When describing efficient sequential algorithms we utilize various primitives,
e.g. summation, multiplication, sorting, max-weight matching, etc, that take
polynomial time, and we can assume the reader knows, without proof. In the
case of parallel algorithms, we find it instructive to state some of these
useful primitives in this subsection.

Sum. We can efficiently take the sum of $n$ numbers in parallel. To see this,
notice that we can use $n$ processors to create a binary tree where the leaves
of the tree are the $n$ numbers. In each time step, we use a processor to sum
two values and then pass that value up the tree. In $O(\log n)$ steps, we will
have the sum of all numbers.

Sorting. We can efficiently sort $n$ numbers in parallel. For a more detailed
discussion on parallel sorting algorithms, we refer the reader to [13]. In our
parallel algorithms, we use the bitonic sorting network. The bitonic sorting
network requires $O(\log^{2}n)$ time and uses $O(n)$ processors. It is
theoretically possible to sort in parallel using only $O(\log n)$ time using
$O(n)$ processors via the AKS sorting network, but the constant hidden by the
big-O notation is too large for use in practice [2].

Reduction Operators. A reduction operator allows us to quickly aggregate the
entries of an array into one value in parallel. We will often find the maximum
(or minimum) of a list of $n$ values. We can execute this in $O(\log n)$ time
by using $O(n)$ processors. Similar to computing sums, we create a binary tree
where the leaves of the tree are the $n$ numbers. In each time step, we use a
separate processor to compute the maximum (or minimum) of two values and then
pass that value up the tree. In $O(\log n)$ steps, we will have the maximum
(or minimum) of all numbers. Similarly, for binary entries, we can compute the
AND or OR over all entries.

Graph Algorithms. Many problems on graphs can be solved efficiently in
parallel. For example, we can compute all-pairs shortest paths and find the
minimum spanning tree efficiently (and deterministically) in parallel [13]. We
can find minimum weight perfect matchings [19] and find the global minimum cut
of an undirected graph efficiently in parallel by utilizing randomization
[14]. For brevity, this is all we list here and refer the reader to [13] for
more parallel graph algorithms.

##  3 Verification of fairness

As a warm-up, we begin by showing that, given an allocation, we can
efficiently, in parallel, verify its fairness properties.

######  Theorem 1.

Given an allocation $X$ and the valuation functions of $n$ additive (or
restricted additive) agents, the problem of deciding whether $X$ satisfies EF
is in NC.

###### Proof.

We wish to test whether or not each agent prefers their own bundle to any
other agent’s bundle. For each ordered pair of agents $(i,j)$, we assign
$|X_{i}|+|X_{j}|\leq m$ processors. First, we compute the value of
$v_{i}(X_{i})$ and $v_{i}(X_{j})$ using parallel sum procedures; each sum
takes $O(\log m)$ time. Next, we test whether $v_{i}(X_{i})\geq v_{i}(X_{j})$.
For each ordered pair of agents $(i,j)$, we assign one bit in memory,
initially set to 0. If $v_{i}(X_{i})\geq v_{i}(X_{j})$, processor $p_{(i,j)}$
will flip the bit indexed by the agent pair $(i,j)$ to $1$. Setting this bit
for all ordered pairs is done simultaneously. Finally, using $n^{2}$
processors, we take the minimum across these bits to find if there is any pair
of agents that does not respect envy-freeness; this step takes $O(\log n^{2})$
time; if the minimum is 1, then the allocation is envy-free. We overall used
at most $O(n^{2}m)$ processors, and the total time was $O(\log m+\log n)$. ∎

To test if an allocation is EF1, we use similar ideas to that of testing EF.
For every ordered pair of agents, we allocate $O(m)$ processors to test
whether or not the removal of each item from $j$’s bundle eliminates $i$’s
envy. For each item, we set a separate bit to 1 to signify whether or not that
item’s removal eliminates envy. We take the maximum across all bits to see if
there is any one item that satisfies EF1. Then we ensure that the minimum for
all ordered pairs of agents is 1.

To test if an allocation is EFX, we run the same procedure as that of testing
EF1 except instead of computing maximums of the inequality bits, we compute
minimums. It is straightforward to see that this difference results in a
correct EFX verification procedure. We include the full proofs for
completeness.

######  Theorem 2.

Given an allocation $X$ and the valuation functions of $n$ additive (or
restricted additive) agents, the problem of deciding whether $X$ satisfies EF1
is in NC.

###### Proof.

For each (ordered) pair of agents $(i,j)$ we will allocate $|X_{j}|\leq m$
processors. Each processor is in charge of testing whether or not the removal
of a specific item in $j$’s bundle will reduce $i$’s value for $j$’s bundle so
that $i$ no longer envies $j$. Let $X_{j,k}$ denote the $k$-th item in $j$’s
bundle in allocation $X$, and let $p_{(i,j,k)}$ be the processor assigned to
the (ordered) pair $(i,j)$ and item $X_{j,k}$. $p_{(i,j,k)}$ tests the
following inequality: $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus\\{X_{j,k}\\})$.
The values for $v_{i}(X_{i})$ and $v_{i}(X_{j})$ can be computed in parallel
via parallel sum.

For each ordered pair of agents $(i,j)$, we will also allocate $m$ bits in
shared memory. These bits will initially be set to 0. If any processor
$p_{(i,j,k)}$ assigned to the ordered pair $(i,j)$ finds that the $k$-th item
makes the inequality hold, the corresponding bit is set to 1. After all
processors test their assigned inequality, we compute the maximum (the OR
operation) of these $m$ bits for each agent. This can be done in $O(\log m)$
time using $m$ additional processors, via a tournament.333Think of building a
binary-tree bottom-up, with the leaves corresponding to the original $m$ bits.
In the first time step, processor $i$ takes the maximum of the leaves in
positions $2i$ and $2i+1$ and stores it in the corresponding parent node. In
the second time step, processor $i$ takes the maximum of the nodes in
positions $i$ and $i+1$ from the parent nodes in the previous step, and so on.
If the maximum of these $m$ bits is $1$, then there is one item that can be
removed from $j$’s bundle such that $i$ no longer envies $j$. We can compute
this “EF1-bit” for all $n^{2}$ ordered pairs of agents in parallel. Finally,
we take the minimum (AND operator) of these $n^{2}$ bits in a similar way; if
this minimum bit is $0$, then there exists a pair of agents that do not
satisfy the EF1 relation, and otherwise, EF1 is satisfied for all pairs.

The time complexity of this process is $O(1)$ time to populate the bits and
then $O(\log n+\log m)$ time to compute the maximums, minimums, and sums. We
use $O(n^{2}m)$ processors. ∎

######  Theorem 3.

Given an allocation $X$ and the valuation functions of $n$ additive (or
restricted additive) agents, the problem of deciding whether $X$ satisfies EFX
is in NC.

###### Proof.

For each (ordered) pair of agents $(i,j)$ we will allocate $|X_{j}|\leq m$
processors. Each processor is in charge of testing whether or not the removal
of a specific item in $j$’s bundle will reduce $i$’s value for $j$’s bundle so
that $i$ no longer envies $j$. Let $X_{j,k}$ denote the $k$-th item in $j$’s
bundle in allocation $X$, and let $p_{(i,j,k)}$ be the processor assigned to
the (ordered) pair $(i,j)$ and item $X_{j,k}$. $p_{(i,j,k)}$ tests the
following inequality: $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus\\{X_{j,k}\\})$.
The values for $v_{i}(X_{i})$ and $v_{i}(X_{j})$ can be computed in parallel
via parallel sum.

For each ordered pair of agents $(i,j)$, we will also allocate $m$ bits in
shared memory. These bits will initially be set to 0. If any processor
$p_{(i,j,k)}$ assigned to the ordered pair $(i,j)$ finds that the $k$-th item
makes the inequality hold, the corresponding bit is set to 1. After all
processors test their assigned inequality, we compute the minimum (the AND
operation) of these $m$ bits for each agent. This can be done in $O(\log m)$
time using $m$ additional processors, via a tournament. If the minimum of
these $m$ bits is $1$, then any item can be removed from $j$’s bundle to
ensure that $i$ no longer envies $j$. We can compute this “EFX-bit” for all
$n^{2}$ ordered pairs of agents in parallel. Finally, we take the minimum (AND
operator) of these $n^{2}$ bits in a similar way; if this minimum bit is $0$,
then there exists a pair of agents that do not satisfy the EFX relation, and
otherwise, EFX is satisfied for all pairs.

The time complexity of this process is $O(1)$ time to populate the bits and
then $O(\log m+\log n)$ time to compute the minimums, and sums. We use
$O(n^{2}m)$ processors.∎

##  4 EF1 allocations for two and three additive agents

In this section, we discuss how to efficiently, in parallel, compute EF1
allocations for two and three additive agents.

Our algorithms work via a reduction. Specifically, Oh et al. [20] prove that
EF1 allocations can be found using a logarithmic number of value queries444A
value query on input $i$, $S\subseteq\mathcal{M}$ returns the value $v_{i}(S)$
of agent $i$ for the subset $S$ of items. for two agents with monotonic
utilities and three agents with additive utilities. For sequential algorithms
and additive agents, implementing a query takes $O(m)$ time, since one needs
to sum the values of the items in a subset. However, using $O(m)$ processors,
one can implement a value query in $O(\log m)$ time. Therefore, the results of
[20] can be directly translated to our setting.

######  Theorem 4.

For the case of additive agents, if there exists a query algorithm that uses
$k$ queries to compute an allocation $X$, then there exists a parallel
algorithm that uses $O(m)$ processors and computes $X$ in time $O(k\log m)$.

###### Proof.

Consider any sequential fair division algorithm $\mathcal{A}$ for additive
agents that only has query access to agents’ valuations, and specifically, it
can ask a query, $query(S,i)$, to learn the value of subset $S$ for agent $i$.
Suppose $\mathcal{A}$ requires $k$ query calls. We give a parallel algorithm
that efficiently implements $query(S,i)$. In order to implement $query(S,i)$,
we run a parallel-sum procedure using $O(m)$ processors on the elements
specified by $S$, using the valuation function of agent $i$. In $O(\log m)$
time, we then have the sum of all item values in $S$ for agent $i$. Since
$\mathcal{A}$ uses $k$ queries, and for each query we compute a sum, we get an
overall runtime of $O(k\log m)$ using $O(m)$ processors. ∎

As corollaries, we can derive NC algorithms that produce EF1 allocations for
two or three agents with additive utilities via the algorithms of Oh et al.
[20], since these algorithms have polylogarithmically many value queries.

######  Corollary 1.

The problem of finding an EF1 allocation for two and three additive agents is
in NC.

Next, we notice that the two-agent algorithm of Oh et al. [20] mimics the
classic cut-and-choose algorithm from continuous cake-cutting. The authors
show that for any ordering of indivisible items on a line, there exists a way
for the first agent to cut (split the items into two pieces) such that when
the second agent selects her favorite piece, the overall allocation is EF1.
The main difficulty is, of course, finding this cut using only a logarithmic
number of queries. Here, we observe that since such a cut can be found for an
arbitrary ordering of the items, by ordering the items in increasing
$v_{1,j}/v_{2,j}$ (mimicking the adjusted-winner process [6]) we can also
guarantee fractional Pareto efficiency (fPO). Since the basic operations
(sorting, adding, etc) in the adjusted winner process can be done in parallel,
we overall get a fractionally PO and EF1 NC algorithm.

######  Theorem 5.

The problem of finding an fPO and EF1 allocation for two additive agents is in
NC.

###### Proof.

Consider sorting the items in non-increasing order of the ratio
$v_{1,j}/v_{2,j}$ on a line. In [1], it is shown that every fPO allocation is
a split of the items such that agent 1 gets all the items to the left of the
split and agent 2 gets all the items to the right of the split and the
allocation is discrete. This leaves us with $m+1$ allocations where each
allocation is a partition of the goods into left and right halves. In [5] it
is shown that an EF1 + fPO allocation must exist. Thus, it must be one of
these $m+1$ splits. Now, we can run a binary search over the splits to find
one that is EF1. Checking if an allocation is EF1 can be done in parallel by
Theorem 2. After each check, we reduce the set of allocations to the correct
half by checking which agent’s envy violates EF1.

We can sort the items by their ratios using bitonic sorting. Checking each
individual split takes $O(\log m)$ time and requires $O(m)$ processors. Since
there are $m+1$ allocations, running binary search over them takes $O(\log m)$
time where at each step we check if the allocation is EF1. This gives us a
final time complexity of $O(\log^{2}m)$, where we require $O(m)$ processors. ∎

Finally, we show that for $n$ identical and additive agents, there exists a
simple NC algorithm for finding an EF1 allocation. Notice that for identical
agents, it is easy to predict what item will be allocated in the $k$-th round
of the Round-Robin procedure: since all agents have the same ranking over the
items, the $k$-th item allocated is precisely the $k$-th favorite item.

######  Theorem 6.

The problem of finding an EF1 allocation for $n$ identical, additive agents is
in NC.

###### Proof.

Begin by sorting the items in decreasing value (breaking ties arbitrarily) and
let the item with the $k$-th highest value be labeled $m_{k}$. Let $\sigma$ be
some order over the agents and let $\sigma_{i}$, for $i\in[n]$, represent the
agent in the $i$’th index of $\sigma$. Consider allocating any item $m_{k}$.
If $k$ is not divisible by $n$, we allocate item $m_{k}$ to agent
$\sigma_{k~{}mod~{}n}$. If $k$ is divisible by $n$, we allocate item $m_{k}$
to agent $\sigma_{n}$. This returns the same allocation as that of running
Round-Robin using the order $\sigma$ and as such is an EF1 allocation. Sorting
the items takes $O(\log^{2}m)$ time and requires $O(m)$ processors. Then,
allocating each item simultaneously takes $O(1)$ time and a total of $O(m)$
processors. In total, the time complexity is $O(\log^{2}m)$ time and we
require $O(m)$ processors. ∎

##  5 Traditional EF1 algorithms are inherently sequential

In this section, we give limits to what parallel algorithms can achieve in our
setting. Specifically, we show that “Round-Robin looking” allocations cannot
be found efficiently in parallel. We consider the following problem, which we
call Fixed-Order Round-Robin: Given a set $\mathcal{M}$ of $m$ items, a set
$\mathcal{N}$ of $n$ agents, a strict ordering
$\sigma=\\{\sigma_{1}\succ\dots\succ\sigma_{n}\\}$ over the agents, and a
designated agent, item pair $(i^{*},j^{*})$, decide if agent $i^{*}$ is
allocated item $j^{*}$ by Round-Robin with $\sigma$ as the order over the
agents. We give a log-space reduction from Lexicographically-First Maximal
Matching to Fixed-Order Round-Robin.

######  Theorem 7.

Fixed-Order Round-Robin is CC-Hard, even for the case of $n$ restricted
additive agents, i.e. $v_{i,j}\in\\{0,v(j)\\}$, where every agent positively
values at most $3$ items and every item is positively valued by at most $3$
agents.

###### Proof.

We reduce the 3-Lexicographically-First Maximal Matching (3-LFMM) problem to
Fixed-Order Round-Robin. In the LFMM problem, we are given a bipartite graph
$G=(X,Y,E)$ where $X=\\{x_{i}\\}^{n}_{i=1}$, $Y=\\{y_{i}\\}^{m}_{i=1}$, and
$E\subseteq X\times Y$. The lexicographically first maximal matching of $G$,
$M_{lex}$, is produced by successively matching vertices in $X$, in the order
$x_{1},\dots,x_{n}$, each one with the available vertex in $Y$ that has the
smallest index. The LFMM problem is to decide if a designated edge belongs to
the lexicographically first maximal matching of a bipartite graph $G$. In the
3-LFMM problem, each vertex in $G$ has degree at most $3$. [16] prove that
3-LFMM is CC-complete.

Let $G=(X,Y,E)$ with a designated edge $e^{*}$ be an instance of the 3-LFMM
problem. Without loss of generality, let $|X|\geq|Y|$. We construct an
instance of Fixed-Order Round-Robin as follows. For each vertex $x_{i}\in X$
we create an agent, and for each vertex $y_{j}\in Y$ we create an item. For
each $e=(x_{i},y_{j})\in E$, we set $v_{i,j}=m-j+1$. For
$e=(x_{i},y_{j})\notin E$, $v_{i,j}=0$. By construction, since each vertex in
$G$ has degree at most $3$, each agent values positively at most $3$ items,
and each item is valued positively by at most $3$ agents. Let the ordering of
the vertices in $X$ correspond to $\sigma$, i.e. $\sigma_{i}=i$. Notice that
this construction takes logarithmic space. Therefore, to conclude the proof of
Theorem 7, it suffices to show that $e^{*}=(x_{i^{*}},y_{j^{*}})\in M_{lex}$
if and only if agent $i^{*}$ gets item $j^{*}$ in the execution of Round-Robin
that corresponds to $\sigma$. We prove a stronger statement, using induction.

Our inductive hypothesis is that, for a given number $k$, for any $j\in[m]$,
$(x_{k},y_{j})\in M_{lex}$ if and only if agent $k$ gets item $j$ in the
$k$-th round of the execution of Round-Robin that corresponds to $\sigma$. For
$k=1$, we have that $(x_{1},y_{j})\in M_{lex}$ if and only if
$j=argmin_{\ell\in[m]}\\{(x_{1},y_{\ell})\in E\\}$, which, by construction,
happens if and only if $v_{1,j}>v_{1,\ell}$ for all $\ell\in[m]$, i.e., if and
only if agent $1$ picks item $j$ in the execution of Round Robin, noting that
agent $1$ is first in $\sigma$ and that agents don’t pick items they have zero
value for. Assume the hypothesis is true for numbers less than or equal to
$k$, and that $(x_{k+1},y_{j})\in M_{lex}$. By the inductive hypothesis, all
edges $(x_{i},y_{\ell})\in M_{lex}$ for $i\leq k$ correspond to items
allocated in the first $k$ rounds in the execution of Round-Robin.
$(x_{k+1},y_{j})\in M_{lex}$ if and only if $j$ is the smallest index among
all unmatched neighbors of $x_{k+1}$ at the $(k+1)$-st step of building the
lexicographically first maximal matching. Since smaller indices (of edges)
correspond to strictly higher valuations, we have that, by construction,
$(x_{k+1},y_{j})\in M_{lex}$ if and only if $v_{k+1,j}>v_{k+1,\ell}$ for all
items $\ell\in[m]$ that have not been allocated in the first $k$ rounds in the
execution of Round-Robin. This holds if and only if $j$ is the item selected
by agent $k+1$ in the $(k+1)$-st round of Round-Robin (noting once again that,
in Round-Robin, agents don’t pick items with zero value for them). ∎

##  6 EF1 + PO for restricted additive with a bounded number of values

In this section, we present a new randomized parallel algorithm that gives an
EF1 and PO allocation for assigning $m$ indivisible items to $n$ agents with
restricted additive valuations. Recall that a valuation function $v_{i}$ is
_restricted additive_ if $v_{i}$ is additive, and for each item
$g\in\mathcal{M}$, $v_{i}(g)\in\\{0,v(g)\\}$. The complexity of the algorithm
is parameterized by $t$, the number of “inherent” item values, i.e. the number
of different values $v(g)$ can take. Formally, our parallel algorithm has
polylog(m, n) time complexity and requires poly$(m,n)\cdot O(m^{t})$
processors.

Here, we describe how our algorithm works. We construct a weighted bipartite
graph $G$ where on one side of the graph, we have vertices corresponding to
items, and on the other side, we have vertices corresponding to copies of
agents. We ensure that the two sides have the same number of vertices by
adding $mn-m$ dummy items that all agents have zero value for. We first
describe the vertices representing the set of items. Let this side be $A$. To
populate $A$, we create a vertex $a_{j}$ for each $j\in\mathcal{M}$. We will
think of $A$ as partitioned in buckets $\mathcal{M}_{1}\dots\mathcal{M}_{t}$,
where $t$ is the number of different item values. $M_{i}$ is the set of items
with the $i$’th highest value. Finally, we add vertices that correspond to
dummy items. Let the set of dummy vertices be $\mathcal{M}_{d}$. On the other
side of the bipartition, we have vertices corresponding to copies of agents.
Let this side be $B$. We create $m$ buckets of $n$ vertices where each of
these $n$ vertices represents an agent. Formally, we create a set of vertices
$\\{b_{(1,j)},b_{(2,j)},\dots,b_{(n,j)}\\}$ for $j\in[m]$. The $c$-th bucket
will be called $\mathcal{N}_{c}$. For each $j\in\mathcal{M}_{f}$ and
$i\in\mathcal{N}$, if $v_{i,j}>0$, we add, for all $c\in[m]$, the edge
$(a_{j},b_{(i,c)})$ with weight $-m^{(t-f)}\cdot c$. For each dummy item
$j\in\mathcal{M}_{d}$ and $i\in[n]$, we add, for all $c\in[m]$, the edge
$(a_{j},b_{(i,c)})$ with weight 0. We refer to this weight function as
$w(\cdot)$. We give an example of the weighted bipartite graph in Figure 1
where there are three agents, and three items in buckets $\mathcal{M}_{1}$ and
$\mathcal{M}_{f}$ along with some dummy vertices in $\mathcal{M}_{d}$.

Figure 1: $G$ for an instance with three agents.

Once the graph $G=(X\cup Y,E,w)$ is constructed, we compute a maximum-weight
perfect matching $M^{*}$ and return the allocation corresponding to $M^{*}$.
We assume that every (non-dummy) item is valued by someone. This is without
loss of generality since, if an item is not valued by anyone, this can be
checked efficiently in parallel, and the item can be discarded. The formal
description of the algorithm is given in Algorithm 1. We prove that this
algorithm always outputs an EF1 and PO allocation.

Algorithm 1 Parallel Algorithm for Division of Goods with Restricted Additive
Values

1:$n$ agents, $m$ items, $v_{i}(g)\in[0,v(g)]~{}\forall
i\in\mathcal{N},g\in\mathcal{M}$

2:EF1 + PO Allocation $X$

3:Sort the items into buckets by value
$\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{t}$

4:Add a set of $mn-m$ dummy items $\mathcal{M}_{d}$ to $\mathcal{M}$

5:Create an empty, weighted, undirected graph $G$

6:for all $j\in\mathcal{M}$ in parallel do

7: Add a vertex $a_{j}$

8:for all $j\in\mathcal{M}$, $i\in\mathcal{N}$ in parallel do

9: Add a vertex $b_{(i,j)}$

10:for all $j\in\mathcal{M}$, $b_{(i,c)}$ for $i\in\mathcal{N}$ and $c\in[m]$
in parallel do

11: if $(v_{i,j}>0)$ then

12: Add the edge $(a_{j},b_{(i,c)})$ to $G$ with weight $-m^{(t-f)}\cdot c$ if
item $j\in\mathcal{M}_{f}$

13: if $(a_{j}\in\mathcal{M}_{d})$ then

14: Add the edge $(a_{j},b_{(i,c)})$ to $G$ with weight $0$

15:Compute the Max-Weight Perfect Matching $M^{*}$ in $G$

16:for all $j\in\mathcal{M}$, $b_{(i,c)}$ for $i\in\mathcal{N}$ and $c\in[m]$
in parallel do

17: if $((a_{j},b_{(i,c)})\in M^{*})$ then

18: $X_{i}=X_{i}\cup j$

19:return: $X$

The following lemma shows that this algorithm satisfies Pareto Optimality.

######  Lemma 1.

Algorithm 1 outputs a Pareto Optimal allocation.

###### Proof.

We show that the resulting maximum-weight matching saturates the left side of
the bipartition. As a result, all items are allocated to agents that value
those items since an edge in the graph is only present between an item-agent
pair when the agent values that item.

We show this by using Hall’s Marriage Theorem. Hall’s Theorem characterizes
necessary and sufficient conditions for a bipartite graph to have a perfect
matching. Recall Hall’s Theorem:

######  Theorem 8 (Hall’s Theorem [11]).

A bipartite graph $G=(L\cup R,E)$ contains an $L$-saturating perfect matching
if and only if for every subset $W$ of $L$, its neighborhood, $N_{G}(W)$,
satisfies

$|N_{G}(W)|\geq|W|$

.

This holds for the graph $G$ used in Algorithm 1. Consider any subset $W$ of
$A$. Since $W$ is comprised of vertices corresponding to non-dummy items and
vertices corresponding to dummy items, it suffices to show that a vertex of
either type has a large enough neighborhood in $B$. Every item
$j\in\mathcal{M}$ is associated with a vertex $a_{j}\in A$. A vertex $a_{j}$
corresponding to the non-dummy item $j$ has at least $m$ edges coming out of
it: an edge to the same agent $i$ in each of the $m$ blocks. Any vertex
corresponding to a dummy item is connected to all vertices in $B$. Thus, any
subset $W$ of $A$ will result in a neighborhood of size at least $|W|$ in $B$.
So, $G$ will always contain at least one perfect matching that saturates $A$.
Since our allocation corresponds to this matching, each item is given to an
agent that values it. In the restricted additive setting, this corresponds to
a Pareto Optimal allocation. ∎

The next lemma is crucial for showing the EF1 guarantee of Algorithm 1.

######  Lemma 2.

For any two agents $i$ and $j$, and $c\in[m-1]$, $i$ weakly prefers the item
matched to her in bucket $\mathcal{N}_{c}$ to the item that is matched to $j$
in bucket $\mathcal{N}_{c+1}$.

###### Proof.

Let vertex $j$ be matched to $M^{*}(j)$ in $M^{*}$. We want to show that

$v_{i}(M^{*}(b_{(i,c)}))\geq v_{i}(M^{*}(b_{(j,(c+1))})).$

Assume that this is not true. Then, the following holds for matching $M^{*}$.
Agent $i$ is matched to item $\ell$ from $\mathcal{M}_{f+h}$ for some
$h\in[t-f]$ in bucket $\mathcal{N}_{c}$ and agent $j$ is matched to item
$\ell^{\prime}$ from $\mathcal{M}_{f}$ in bucket $\mathcal{N}_{c+1}$. However,
we know that agent $i$ values item $\ell^{\prime}$. So the edge
$(a_{\ell^{\prime}},b_{(i,c)})$ exists in $G$. We show that we can augment
$M^{*}$ and increase its weight, thus proving that it was not the maximum
weight matching in the first place; a contradiction. Towards this, consider
matching item $\ell^{\prime}$ to agent $i$ in bucket $\mathcal{N}_{c}$ and
matching item $\ell$ to agent $i$ in any bucket $\mathcal{N}_{p}$ for $p>c$
where $b_{(i,p)}$ is unmatched. We show that the new matching has a higher
total weight.

Notice that besides this item switch, all other edges remain the same. So, we
need to show:

$\displaystyle
w(a_{\ell^{\prime}},b_{(i,c)})+w(a_{\ell},b_{(i,p)})>w(a_{\ell^{\prime}},b_{(j,(c+1))})+w(a_{\ell},b_{(i,c)})$

Expanding using the weight function, we have:

$\displaystyle
w(a_{\ell^{\prime}},b_{(i,c)})+w(a_{\ell},b_{(i,p)})=-cm^{(t-f)}-pm^{t-(f+h)}$
$\displaystyle
w(a_{\ell^{\prime}},b_{(j,(c+1))})+w(a_{\ell},b_{(i,c)})=-(c+1)m^{(t-f)}-cm^{t-(f+h)}.$

Subtracting the weight of the old edges from the modified matching edges, we
have:

$\displaystyle-
cm^{(t-f)}-pm^{t-(f+h)}-(-(c+1)m^{(t-f)}-cm^{t-(f+h)})=m^{(t-f)}+(c-p)m^{t-(f+h)}.$

We have that $c\geq 1$ and $p\leq m$, so the smallest value that $(c-p)$ can
take is $(1-m)$. We have:

$\displaystyle m^{(t-f)}+(c-p)m^{(f+h)}$ $\displaystyle\geq
m^{(t-f)}+(1-m)m^{t-(f+h)}$ $\displaystyle>m^{(t-f)}+(-m)m^{t-(f+h)}$
$\displaystyle=m^{(t-f)}-m^{(t-f-h+1)}.$

The largest value that the second term can take is when $h=1$. This gives us,

$\displaystyle m^{(t-f)}-m^{(t-f-h+1)}\geq m^{(t-f)}-m^{(t-f)}=0.$

Thus, we can strictly increase the weight of the matching; a contradiction. ∎

The repeated application of Lemma 2 gives us Lemma 3.

######  Lemma 3.

Algorithm 1 outputs an EF1 allocation.

###### Proof.

Notice that every vertex in $B$ is matched to some item in $A$ (the matched
item may be a dummy item of value 0). By Lemma 2, for any two agents $i$ and
$j$, we have that $v_{i}(M^{*}(b_{(i,c)}))\geq v_{i}(M^{*}(b_{(j,(c+1))}))$.
So, in particular, we have that agent $i$ weakly prefers the item they
received in bucket $\mathcal{N}_{1}$ to the item agent $j$ receives in bucket
$\mathcal{N}_{2}$. Agent $i$ also weakly prefers the item they received in
bucket $\mathcal{N}_{2}$ to the item agent $j$ receives in bucket
$\mathcal{N}_{3}$ and so on. As a result, we know that agent $i$ has at least
the same value for the set of items she receives in buckets $\mathcal{N}_{1}$
through bucket $\mathcal{N}_{m}$ as that of the set of items agent $j$
receives in buckets $\mathcal{N}_{2}$ through bucket $\mathcal{N}_{m}$. Thus,
by removing the item agent $j$ receives in $\mathcal{N}_{1}$, agent $i$ will
certainly have no envy for agent $j$. ∎

Finally, we show that Algorithm 1 runs in randomized polylogarithmic time
using $f(m,n)\cdot O(m^{t})$ processors where $f$ is a polynomial (in $m$ and
$n$) function.

######  Lemma 4.

Algorithm 1 takes $O(\log^{2}(mn))$ time using $O(m^{5.5+t}n^{5.5})$
processors.

###### Proof.

We will show that each step of Algorithm 1 runs in polylogarithmic time using
at most $f(m,n)\cdot O(m^{t})$ processors. In Algorithm 1, sorting the items
takes $O(\log^{2}m)$ time and $O(m)$ processors. Adding the dummy items takes
$O(1)$ time using $O(mn)$ processors. The first for loop runs in $O(1)$ time
using $O(mn)$ processors. The second for loop runs in $O(1)$ time using
$O(mn)$ processors. The third for loop runs in $O(1)$ time using $O(m^{2}n)$
processors. Computing the maximum weight perfect matching is the only step in
our algorithm that requires $f(m,n)\cdot O(m^{t})$ processors when we have $t$
different inherent item values. From [19], there is a randomized parallel
algorithm that computes the _minimum weight perfect matching_ of a graph.
Notice that one can compute the maximum weight perfect matching of the graph
by first negating the edge weights and then running a minimum weight perfect
matching algorithm. The algorithm of [19] takes $O(\log^{2}(mn))$ time using
$O(m^{5.5}n^{5.5}W)$ processors where we have $n$ agents and $m$ items and $W$
is the weight of the heaviest edge in unary. When we have $t$ different item
values, we have $W\leq m^{t}$. Finally, extracting the allocation from the
maximum weight perfect matching takes $O(1)$ time using $O(m^{2}n)$
processors. The step with the largest time complexity is computing the maximum
weight perfect matching. Thus, the total time complexity of Algorithm 1 is
$O(\log^{2}(mn))$ and requires a total of $O(m^{5.5+t}n^{5.5})$ processors. ∎

Combined, Lemmas 1, 3, and 4 give us the following theorem.

######  Theorem 9.

Algorithm 1 is a parallel algorithm that returns an EF1 and Pareto Optimal
allocation of $m$ indivisible items to $n$ agents with restricted-additive
valuations, from a set of $t$ different inherent item-values, in time
$O(\log^{2}(mn))$ using $O(m^{5.5+t}n^{5.5})$ processors.

Notice that binary valuations are a special case of restricted additive
valuations (with one inherent item value). Thus, we get an RNC algorithm for
binary valuations.

######  Corollary 2.

The problem of finding an EF1 and Pareto Optimal allocation for $n$ additive
agents with binary valuations is in RNC.

We note here that for a given instance of restricted additive fair division,
we can reduce the number of inherent item values at the expense of some loss
in the EF1 and PO guarantees. Concretely, if we round the valuations $v_{i,j}$
to $v^{\prime}_{i,j}$ such that $v^{\prime}_{i,j}\in[\alpha\cdot
v_{i,j},v_{i,j}]$, for an $\alpha\in[0,1)$, then an EF1 and PO allocation in
$v^{\prime}$ is an $\alpha$-EF1 and $\alpha$-PO allocation with respect to
$v$. Assuming the item values are in the range $[1,V]$, one can use such a
rounding to create $\lceil\log_{\frac{1}{\alpha}}(V+1)\rceil$ intervals.

######  Theorem 10.

Let there be $n$ restricted additive agents and $m$ indivisible items such
that $v(g)\in[1,V]$ for all $g\in\mathcal{M}$. Then, there exists a parallel
algorithm that computes an $\alpha$-EF1 and $\alpha$-PO allocation in time
$O(\log^{2}(mn))$ using
$O(m^{5.5+\lceil\log_{\frac{1}{\alpha}}(V+1)\rceil}n^{5.5})$ processors.

###### Proof.

We begin by rounding the valuations $v$ to new valuation functions
$v^{\prime}$ where $v^{\prime}_{i,j}\in[\alpha\cdot v_{i,j},v_{i,j})$ for some
$\alpha\in[0,1)$. Specifically, all values in the interval $[1,1/\alpha)$ will
be rounded down to $1$, values in the interval $[1/\alpha,(1/\alpha)^{2})$
will be rounded down to $1/\alpha$, and so on. This creates
$\lceil\log_{\frac{1}{\alpha}}(V+1)\rceil$ intervals, and therefore
$t=\lceil\log_{\frac{1}{\alpha}}(V+1)\rceil$ different inherent item-values in
$v^{\prime}$. Using Algorithm 1, we can compute an EF1 and PO allocation $X$
with respect to $v^{\prime}$. We claim that $X$ is an $\alpha$-EF1 and
$\alpha$-PO allocation with respect to $v$.

First, we show the $\alpha$-EF1 guarantee. Since $X$ is EF1 with respect to
$v^{\prime}$, for every pair of agents $i,j$, there exists some good $g$ in
agent $j$’s bundle such that (1) $v^{\prime}_{i}(X_{i})\geq
v^{\prime}_{i}(X_{j}\setminus\\{g\\})$. Since $\alpha\in[0,1)$, we have that
(2) $v_{i}(X_{i})\geq v^{\prime}_{i}(X_{i})$. By the construction of
$v^{\prime}$, we also have (3)
$v^{\prime}_{i}(X_{j}\setminus\\{g\\})\geq\alpha\cdot
v_{i}(X_{j}\setminus\\{g\\})$. Stitching (1), (2), and (3) together, we the
$\alpha$-EF1 guarantee:

$\displaystyle v_{i}(X_{i})\geq v^{\prime}_{i}(X_{i})\geq
v^{\prime}_{i}(X_{j}\setminus\\{g\\})\geq\alpha\cdot
v_{i}(X_{j}\setminus\\{g\\}).$

Next, we show the $\alpha$-PO guarantee. Consider some other allocation
$X^{\prime}$. Since $X$ is PO with respect to $v^{\prime}$, we know, for any
other allocation $X^{\prime}$, $X^{\prime}$ does not Pareto dominate $X$. That
is, there exists at least one agent $i$ such that
$v^{\prime}_{i}(X^{\prime}_{i})\leq v^{\prime}_{i}(X_{i})$. By construction of
$v^{\prime}$, we have that, for every subset of items $S$, $\alpha\cdot
v_{i}(S)\leq v^{\prime}_{i}(S)\leq\ v_{i}(S)$. Therefore, we have:

$\displaystyle\alpha\cdot v_{i}(X^{\prime}_{i})\leq
v^{\prime}_{i}(X^{\prime}_{i})\leq v^{\prime}_{i}(X_{i})\leq v_{i}(X_{i}).$

That is, agent $i$’s utility cannot be improved by a factor more than
$1/\alpha$; $X$ is $\alpha$-PO. ∎

##  7 Fair allocations with subsidies in parallel

In this section, we study fair division with subsidies. First, in Section 7.1,
we show how to adjust the algorithm of [12] and compute an envy-freeable
allocation and corresponding envy-eliminating payment vector in parallel.
Second, in Section 7.2, we give an efficient parallel algorithm that computes
a payment vector that not only eliminates envy but additionally satisfies
other user-specified constraints (defined later in this section).

###  7.1 Envy-Freeable allocations and payments in NC

We prove that the algorithm of [12], for finding an envy-freeable allocation
and envy-eliminating payment vectors can be parallelized.

First, note that the welfare-maximizing allocation, which gives each item to
the agent with the highest value for it, can be shown to be envy-freeable.
Now, given an envy-freeable allocation $X$, the algorithm of [12] for finding
envy-eliminating payments at a high-level, constructs the envy-graph $G_{X}$,
negates all the edge weights in $G_{X}$, and computes all-pairs-shortest-paths
on the modified $G_{X}$. Then, for each agent, $i$, the algorithm singles out
the path with the lowest overall weight (out of $n$ shortest paths) that
starts at $i$’s vertex in $G_{X}$. One can show that paying agent $i$ the sum
of the edge weights along this path results in an envy-eliminating payment. We
show that all these steps can be parallelized efficiently, noting that one can
apply known techniques to solve the all-pairs-shortest-paths problem in
parallel. The full proof is included for completeness.

######  Theorem 11.

The problem of finding an envy-freeable allocation $X$ and an envy-eliminating
payment vector for $X$ for $n$ additive agents is in NC.

###### Proof.

Consider computing a welfare-maximizing allocation. A welfare-maximizing
allocation is one in which the sum of utilities is maximized. This can be
achieved by allocating each item to whichever agent values it the most. The
characterization that welfare-maximizing allocations are envy-freeable is
given in [12]. Finding a welfare-maximizing allocation can be done efficiently
in parallel because, for each item, we can use the parallel reduction operator
to find the agent with maximum value in $O(\log n)$ time. This gives us a time
complexity of $O(\log n)$ using $O(mn)$ processors.

The algorithm of [12] for finding envy-eliminating payments proceeds as
follows. Construct the envy-graph $G_{X}$ for an envy-freeable allocation $X$.
Negate all the edge weights in $G_{X}$ and run an all-pairs-shortest-paths
algorithm on $G_{X}$. Let $\ell(i,j)$ be the length of the shortest path from
$i$ to $j$ in $G_{X}$ with all the weights negated. For each agent $i$, find
the vertex $j^{*}$ such that $\ell(i,j^{*})$ is the least out of all
$\ell(i,j)$ values. Set $\vec{q}_{i}=\ell(i,j^{*})$. To see that this can be
parallelized, consider each step in turn. Using $O(n^{2})$ processors, we can
create the envy graph and add weights (negating them first) to all the edges
appropriately in $O(1)$ time. Computing all-pairs shortest paths on this graph
can be done in time $O(\log^{2}n)$ using $O(n^{3})$ processors [13]. Finding
the shortest path that starts at agent $i$ in $G_{X}$ can be done using a
parallel reduction operator. Using $O(n^{2})$ processors total, we can find
the shortest path for each agent in $O(\log n)$ time. Thus, given an envy-
freeable allocation $X$, the problem of finding an envy-eliminating payment
vector for $X$ lies in NC.

Combining these two steps, we can find an envy-freeable allocation $X$ and an
envy-eliminating payment vector for $X$ for $n$ additive agents efficiently in
parallel. ∎

###  7.2 Computing constrained envy-eliminating payment vectors in NC

In this section, we give a different algorithm for finding an envy-eliminating
payment vector, $\vec{q}$. A key feature of our algorithm is that it allows
for additional constraints on the final solution.

Formally, we are given an allocation $X$ of $m$ items to $n$ additive agents
each with a valuation function $v_{i}$ that takes integer values, and a set
$C$ of constraints of the form “if agent $i$ is paid more than $x$ dollars,
then agent $j$ must be paid more than $y$ dollars.” We are interested in
computing a payment vector $\vec{q}$ that is envy-eliminating and satisfies
all such constraints in $C$, or deciding that no such vector exists. We call
this problem Constrained Payments. We assume that no agent is paid more than
$m\Delta$ dollars, where $\Delta=\max_{i,j}v_{i,j}$. This is because, for any
meaningful solution, we need not pay any one agent more than $m\Delta$ dollars
as this is the maximum value any agent can have for the entire set of items.

We note that many non-trivial constraints on the payment vector can be
formulated as a set of these smaller individual constraints. For example, the
constraint “agent 1 should not be paid more than agent 2” can be imposed by
adding the constraint “if agent 1 is paid more than $x$ dollars, then agent 2
is paid more than $x$ dollars” for all $x\in[m\Delta]$. Or, the constraint
“agent 1 should not be paid more than 10 dollars” can be imposed by adding the
constraint “if agent $1$ is paid more than 10 dollars, then agent 2 is paid
more than $m\Delta$ dollars”. When $C$ is empty, we get back the original
problem of finding an unconstrained envy-eliminating payment vector. Our main
result for the fair division with subsidies problem is Theorem 12 whose proof
is given later in this section.

######  Theorem 12.

If $v_{i,j}$ is integral for all $i\in[n]$ and $j\in[m]$, Constrained Payments
can be solved in $O(\log^{2}(mn\Delta))$ time using $O(n^{3}m^{3}\Delta^{3})$
processors, where $\Delta=\max_{i,j}v_{i,j}$.

Before we give the proof, we give an informal explanation of the key ideas and
the main algorithm. The full algorithm is given later in this section as
Algorithm 2 along with the proof of Theorem 12.

Note that $C$ is upper-bounded by $O(n^{2}m^{2}\Delta^{2})$, and hence the
size of $C$ does not appear in the bounds of Theorem 12. The main challenge
with incorporating constraints into the final payment vector is that the
previous approach of running all-pairs-shortest-paths on the envy graph does
not allow us to isolate specific dollar amounts for which we want to impose a
constraint on. To resolve this, we construct a larger, modified graph where
each vertex corresponds to an agent _coupled_ with a specific payment amount.
We call this graph the payment rejection graph. Our goal is to select a single
vertex for each agent from the payment rejection graph, which will define the
final payment vector. An edge in the payment rejection graph will exactly
represent the causal relationship defined by a constraint.

Formally, the payment rejection graph is a directed graph $G_{p}=(V,E)$ with a
total of $nm\Delta$ vertices. We arrange the $nm\Delta$ vertices on an
$n\times m\Delta$ two-dimensional grid. Vertex $(i,j)$ corresponds to agent
$i$ being paid $\vec{q}_{i}=j$ dollars. We use the term rejecting a vertex
$(i,j)$ to denote that $\vec{q}_{i}=j$ will not be in the final payment
vector. We use the term payment row for an agent $i$ when referring to the set
of vertices $\\{(i,j)~{}|~{}j\in[m\Delta]\\}$. An edge from node $(i,j)$ to
$(k,\ell)$, denoted by $(i,j)\rightarrow(k,\ell)$, signifies that if we have
rejected all vertices $(i,j^{\prime})$ for $j^{\prime}\leq j$, then we also
reject all vertices $(k,\ell^{\prime})$ for $\ell^{\prime}\leq\ell$. The idea
of modeling rejections as edges in a directed graph was first used to find
consistent global states in distributed systems [9]. We adapt this approach to
find envy-eliminating payments.

We maintain a “current” payment vector and initialize it to the all-zero
payment vector (i.e we select the vertex $(i,0)$ for each agent $i$). Then, we
iteratively increase the agents’ payments by one dollar until no envy is
present. Although this process seems sequential, we show that we can quickly,
in parallel, determine which payment components are not part of _any_ envy-
eliminating payment vector. To see this, consider two agents $i$ and $j$ and a
current payment vector $\vec{q}$. We can compute the envy $i$ has for $j$ (or,
similarly, $j$ has for $i$) subject to these two payments by comparing $i$’s
value for $i$’s bundle and payment ($v_{i}(X_{i})+\vec{q}_{i}$) to that of
$j$’s ($v_{i}(X_{j})+\vec{q}_{j}$). If it is the case that $i$ envies $j$
subject to the payments $\vec{q}_{i}$ and $\vec{q}_{j}$, we must increase
$i$’s payment by one dollar. So, we will increment $\vec{q}_{i}$ to
$\vec{q}_{i}+1$. Now, if there is any other agent $k$ that envies $i$ subject
to the new payment, we know we will have to increase $k$’s payment by one
dollar as well. As a result, we can make the following inference: if we pay
agent $i$ more than $\vec{q}_{i}$ dollars, we have to pay agent $k$ more than
$\vec{q}_{k}$ dollars. So, we can place an edge
$(i,\vec{q}_{i})\rightarrow(k,\vec{q}_{k})$. Notice that the meaning of these
edges holds transitively (i.e if $(i,\vec{q}_{i})\rightarrow(j,\vec{q}_{j})$
and $(j,\vec{q}_{j})\rightarrow(k,\vec{q}_{k})$, then
$(i,\vec{q}_{i})\rightarrow(k,\vec{q}_{k})$). Since this observation does not
require us to use any information about other vertices in the graph besides
the set $\\{(i,\vec{q}_{i}),(i,\vec{q}_{i}+1),(k,\vec{q}_{k})\\}$, by using a
separate processor for each pair of vertices, we can place all edges in the
graph simultaneously. Here, we give an example of a payment rejection graph
for a specific valuation profile.

Example of Payment Rejection Graph. Consider the following instance $I$. The
value in the $i$’th row and $j$’th column is the value agent $i$ has for item
$j$. The envy-freeable allocation $X$ is the following: agent 1 gets item 3,
agent two gets item 2, and agent 3 gets item 1. In this example, the vertex
$(1,0)$ would be in the set $F$. This is because agent 1 initially envies
agent 2 and to ensure that this payment is rejected, we add it to $F$.
Finally, in the payment rejection graph, we have only included the most
informative edges.

$\displaystyle I=\begin{bmatrix}1&3&2\\\ 0&1&0\\\ 2&0&2\\\ \end{bmatrix}$

Figure 2: The Payment Rejection Graph for Instance $I$ given above.

For this example, the first envy-eliminating payment vector corresponds to
selecting the vertices $\\{(1,1),(2,0),(3,1)\\}$. If we pay agent 1 and agent
3 one dollar each, we will eliminate envy from the allocation. We have not
included all edges for clarity.

The algorithm boils down to computing directed reachability from some specific
vertices in the constructed payment rejection graph. We identify which
vertices will not be a part of any envy-eliminating payment vector initially,
and then follow edges from these vertices. These vertices are of the form
$(i,0)$ where there is some other vertex $(j,0)$ where
$v_{i}(X_{i})<v_{i}(X_{j})$. Agent $i$ must be paid and so vertex $(i,0)$
_will_ be rejected. To find all vertices that are reachable from initially
rejected vertices, we take the transitive closure of $G_{p}$, which can be
done efficiently in parallel [13]. Vertices that are reachable from any
initially rejected vertex will be marked as rejected. Then, we find the
minimum payment component for each agent using a parallel reduction operator.
If there is no minimum component (i.e all vertices along some agent’s payment
row have been rejected), then we output “No satisfying vector”. If all agents
have a valid payment, we output the envy-eliminating payment vector $\vec{q}$.
Since edges in $G_{p}$ correspond exactly to a constraint in $C$, all
constraints can be added to $G_{p}$ simultaneously in parallel. Now, the
algorithm identifies the first envy-eliminating payment vector that respects
these constraints. As a direct result, we get an NC algorithm when $\Delta$ is
bounded by a polynomial of $n$ and $m$. The formal description of the
algorithm is given in Algorithm 2. The proof of Theorem 12 is an immediate
implication of the following two lemmas.

Algorithm 2 Parallel Payment Rejection Algorithm

1:Envy-Freeable Allocation $X$, $v_{i}(X_{j})~{}\forall i,j\in\mathcal{N}$,
$v_{i}~{}\forall i\in\mathcal{N}$

2:Constrained Envy-Eliminating Payment Vector $\vec{q}$

3:var G: Payment Rejection Graph

4:for all $(i\in[n],j\in[m\Delta])$ in parallel do $\triangleright$ 1\.
Creating The Payment Rejection Graph

5: Create node $(i,j)$ in $G$

6:for all $((i,j)\in V,(k,l)\in V~{}|~{})$ in parallel do

7: if $v_{i}(X_{i})+j<v_{i}(X_{k})+(l+1)$ then

8: Add edge $(k,l)\rightarrow(i,j)$ to $G$ $\triangleright$ Extra Constraints
can be Added Here

9:var F: Set of initially envious agents

10:for all $(i\in[n],j\in[n])$ in parallel do $\triangleright$ 2\. Identify
initially envious agents, $F$

11: if $v_{i}(X_{i})<v_{i}(X_{j})$ then

12: Add $(i,0)$ to $F$

13:$G_{T}=\textit{TransitiveClosure}(G=(V,E_{T}))$ $\triangleright$ 3\.
Transitive Closure on Rejection Edges

14:for all $v\in F$ in parallel do

15: for all $v^{\prime}\in V$ s.t $v\rightarrow v^{\prime}\in E_{T}$ do

16: Mark $v^{\prime}$ as “Rejected” $\triangleright$ 4\. Rejecting Vertices

17:for all $(i\in[n])$ in parallel do $\triangleright$ 5\. Find Minimum Vertex
for Each Agent

18: $\vec{q}_{i}=argmin_{j\in[m\Delta]}\\{(i,j)~{}|~{}(i,j)~{}\textit{not
``Rejected"}\\}$

19: if $\vec{q}_{i}=\textit{null}$ then

20: Exit and return “No satisfying vector”

21:return: $\vec{q}$

######  Lemma 5.

Algorithm 2 runs in $O(\log^{2}(mn\Delta))$ time using
$O(n^{3}m^{3}\Delta^{3})$ processors.

###### Proof.

Since our algorithm runs in steps, it suffices to show that each step takes a
polylogarithmic (in $m$, $n$, and $\Delta$) amount of time and uses a
polynomial (in $m$, $n$, and $\Delta$) number of processors.

In step one, we create the payment rejection graph. The first for loop takes
$O(1)$ time using $nm\Delta$ processors to create each node. The second for
loop takes $O(1)$ time using a separate processor for each pair of vertices in
$G$. This requires $(nm\Delta)^{2}$ processors in total.

In step two, we compute the set of initially envious agents, $F$. By using a
separate processor for each pair $i$ and $j$ of states that are of the form
$(i,0)$ and $(j,0)$, we can complete the for loop to compute the set of
initially envying agents in $O(1)$ time using $O(n^{2})$ processors in total.

In step three, we take the transitive closure of the edges in $G$. We cite
[13] for a detailed discussion on parallel transitive closure techniques. It
is well known that taking the transitive closure of a graph on $n$ nodes takes
$O(\log^{2}n)$ time using $O(n^{3})$ processors in the CREW PRAM model. Our
graph has $nm\Delta$ nodes, so this transitive closure step takes
$O(\log^{2}nm\Delta)$ time using $O(n^{3}m^{3}\Delta^{3})$ processors.

In step four, we mark all vertices that are reachable from $F$ as rejected.
This set can have size at most $nm\Delta$. Thus, by using a separate processor
for each vertex, we can check if it is reachable from $F$ and mark it as
needed in $O(1)$ time using $O(nm\Delta)$ processors.

In step five, we find the minimum viable vertex for each agent. We will use a
parallel reduction operator to find the minimum viable vertex for each agent.
Note that if at the end of this process, some agent does not have a valid
payment as the final minimum unrejected vertex, this means there is no payment
that satisfies the imposed set of constraints and also eliminates envy. In
this case, the algorithm outputs “No satisfying vector”. We need $O(nm\Delta)$
processors total and this step will take $O(\log m\Delta)$ time.

In summary, to find the overall time complexity and processor requirements for
our algorithm, we need to single out the step with the largest time and
processor costs. Step 3 is the most expensive step in our algorithm. So, our
overall runtime is $O(\log^{2}nm\Delta)$ time and we require
$O(n^{3}m^{3}\Delta^{3})$ processors. ∎

######  Lemma 6.

Algorithm 2 computes a constraint-satisfying and envy-eliminating payment
vector.

###### Proof.

Let $\vec{q}$ be the payment vector output of Algorithm 2. Suppose $\vec{q}$
is not envy-eliminating. $\vec{q}$ is a set of vertices chosen from the
payment rejection graph where we select one vertex from each row. Thus,
$\vec{q}=\\{(1,\vec{q}_{1}),(2,\vec{q}_{2}),\dots,(n,\vec{q}_{n})\\}$. If
$\vec{q}$ is not envy-eliminating, then there exist some $i,j\in\mathcal{N}$
where $i\neq j$ and: $v_{i}(X_{i})+\vec{q}_{i}<v_{i}(X_{j})+\vec{q}_{j}$.
Since, we have $\vec{q}_{j}$ as $j$’s payment, we know that we rejected the
vertex $(j,\vec{q}_{j}-1)$. However, since we have that
$v_{i}(X_{i})+\vec{q}_{i}<v_{i}(X_{j})+\vec{q}_{j}$, it must be that there is
an edge $(j,\vec{q}_{j}-1)\rightarrow(i,\vec{q}_{i})$ as this is exactly the
requirement for there to be an edge between two vertices in the payment
rejection graph. Since $(j,\vec{q}_{j}-1)$ was rejected and there is an edge
$(j,\vec{q}_{j}-1)\rightarrow(i,\vec{q}_{i})$, it must be that
$(i,\vec{q}_{i})$ was rejected as well.

Suppose $\vec{q}$ is not constraint-satisfying. This means there is some
$(i,\vec{q}_{i})\in\vec{q}$ that violates a constraint. User-added constraints
are in the form of edges from one vertex to another in the payment rejection
graph. Suppose there was a constraint of the form
$(j,\vec{q}_{j})\rightarrow(i,\vec{q}_{i})$ that is not satisfied. This means
that $(j,\vec{q}_{j})$ was rejected and yet $(i,\vec{q}_{i})$ was not.
However, since we take the transitive closure of all edges in the payment
rejection graph and $(j,\vec{q}_{j})$ was rejected we know that
$(i,\vec{q}_{i})$ is also in the neighborhood of some vertex in $F$ and will
also be rejected. As a result, we know that $(i,\vec{q}_{i})$ cannot be part
of the output payment vector. ∎

######  Corollary 3.

The problem of finding an envy-eliminating and constraint-satisfying payment
vector is in NC if $\Delta=\max_{i,j}v_{i,j}$ is polynomial in $n$ and $m$.

##  8 Conclusion

Our results show that many problems in fair division admit efficient parallel
solutions. Our main contributions are efficient parallel fair division
algorithms for allocating indivisible goods to restricted additive agents,
finding constrained payment vectors along with envy-freeable allocations under
the subsidy model, and finding fair allocations for up to three agents. Our
hardness result shows that the traditional Round-Robin EF1 algorithm cannot be
directly translated to the parallel setting. We leave open many interesting
research directions. Is the problem of finding any EF1 allocation CC-Hard? Are
any problems in fair division P-Complete [10]? Can we give _deterministic_
parallel algorithms for restricted additive fair division?

## References

  * ABFRF [15] Haris Aziz, Simina Brânzei, Aris Filos-Ratsikas, and Søren Kristoffer Stiil Frederiksen.  The adjusted winner procedure: Characterizations and equilibria.  In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, pages 454–460. AAAI Press / International Joint Conferences on Artificial Intelligence, July 2015.  24th International Joint Conference on Artificial Intelligence 2015, IJCAI 2015 ; Conference date: 25-07-2015 Through 31-07-2015.
  * AKS [83] M. Ajtai, J. Komlós, and E. Szemerédi.  An 0(n log n) sorting network.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 1–9, New York, NY, USA, 1983. Association for Computing Machinery.
  * AV [20] Nima Anari and Vijay V Vazirani.  Planar graph perfect matching is in nc.  Journal of the ACM (JACM), 67(4):1–34, 2020.
  * BDN+ [20] Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, and Adrian Vetta.  One dollar each eliminates envy.  In Proceedings of the 21st ACM Conference on Economics and Computation, EC ’20, page 23–39, New York, NY, USA, 2020. Association for Computing Machinery.
  * BKV [18] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 557–574, New York, NY, USA, 2018. Association for Computing Machinery.
  * BT [96] Steven J Brams and Alan D Taylor.  A procedure for divorce settlements.  Mediation Quarterly, 13(3):191–205, 1996.
  * CKM+ [19] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  ACM Trans. Econ. Comput., 7(3), sep 2019.
  * Fri [93] Eric J. Friedman.  The complexity of allocating resources in parallel: Upper and lower bounds.  In Complexity in Numerical Optimization, pages 107–127. WORLD SCIENTIFIC, July 1993.
  * GG [19] Vijay K. Garg and Rohan Garg.  Parallel algorithms for predicate detection.  In Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN ’19, page 51–60, New York, NY, USA, 2019. Association for Computing Machinery.
  * GHR [95] Raymond Greenlaw, H James Hoover, and Walter L Ruzzo.  Limits to Parallel Computation: P-Completeness Theory.  Oxford University Press, 06 1995.
  * Hal [35] P. Hall.  On representatives of subsets.  Journal of the London Mathematical Society, s1-10(1):26–30, 1935\.
  * HS [19] Daniel Halpern and Nisarg Shah.  Fair division with subsidy.  In Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings, page 374–389, Berlin, Heidelberg, 2019. Springer-Verlag.
  * JáJ [92] Joseph F. JáJá.  An Introduction to Parallel Algorithms.  Addison-Wesley, 1992.
  * Kar [93] David R Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In SODA, volume 93, pages 21–30, 1993.
  * KR [90] Richard M. Karp and Vijaya Ramachandran.  Chapter 17 - parallel algorithms for shared-memory machines.  In Jan Van Leeuwen, editor, Algorithms and Complexity, Handbook of Theoretical Computer Science, pages 869–941. Elsevier, Amsterdam, 1990.
  * LCY [11] Dai Tri Man Lê, Stephen A Cook, and Yuli Ye.  A formal theory for the complexity class associated with the stable marriage problem.  In Computer Science Logic (CSL’11)-25th International Workshop/20th Annual Conference of the EACSL. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2011.
  * LMMS [04] 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, EC ’04, page 125–131, New York, NY, USA, 2004. Association for Computing Machinery.
  * MS [92] Ernst W. Mayr and Ashok Subramanian.  The complexity of circuit value and network stability.  Journal of Computer and System Sciences, 44(2):302–323, 1992.
  * MVV [87] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 345–354, New York, NY, USA, 1987. Association for Computing Machinery.
  * OPS [19] Hoon Oh, Ariel D. Procaccia, and Warut Suksompong.  Fairly allocating many goods with few queries.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019.
  * ZG [20] Xiong Zheng and Vijay K. Garg.  Parallel and Distributed Algorithms for the Housing Allocation Problem.  In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.