chore endowments, if not mentioned, are zero).

  * •

$k=1$: For each $i\in[2n]$ we have,

$\displaystyle w(a^{1}_{i},b^{1}_{i})$ $\displaystyle=n.$

Also, for each $i\in[n]$ we have

$\displaystyle
w(a^{\prime}_{2i-1},b^{1}_{2i-1})=w(a^{\prime}_{2i-1},b^{1}_{2i})$
$\displaystyle=\frac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i-1})$
$\displaystyle w(a^{\prime}_{2i},b^{1}_{2i-1})=w(a^{\prime}_{2i},b^{1}_{2i})$
$\displaystyle=\frac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i}).$

  * •

$2\leq k\leq K-1$: For each $i\in[n]$, we have,

$\displaystyle w(a^{k}_{2i-1},b^{k}_{2i-1})$ $\displaystyle=n$ and
$\displaystyle w(a^{k}_{2i},b^{k}_{2i})$ $\displaystyle=n$ $\displaystyle
w(\overline{a}^{k}_{i},b^{k}_{2i-1})$ $\displaystyle=\delta_{k}$ and
$\displaystyle w(\overline{a}^{k}_{i},b^{k}_{2i})$
$\displaystyle=\delta_{k}\enspace,$

where $\delta_{k}=\tfrac{n\cdot\alpha_{k}}{2}$. The reason behind the exact
choice of the value of $\delta_{k}$ will become explicit when we show that our
instance satisfies the reverse ratio amplification property in Section 5.2. As
of now, the reader is encouraged to think of it just as a small scalar.

  * •

$k=K$: For each $i\in[n]$ we have,

$\displaystyle w(a^{K}_{2i-1,j},b^{K}_{2i-1})$
$\displaystyle=\mathbf{M}_{2i-1,j}$ and $\displaystyle
w(a^{K}_{2i,j},b^{K}_{2i})$ $\displaystyle=\mathbf{M}_{2i,j}$ for all
$j\in[2n]$ $\displaystyle w(\overline{a}^{K}_{i},b^{K}_{2i-1})$
$\displaystyle=\delta_{K}$ and $\displaystyle
w(\overline{a}^{K}_{i},b^{K}_{2i})$ $\displaystyle=\delta_{K}\enspace,$

where $\delta_{K}=\tfrac{n\cdot\alpha_{K}}{2}$ (the reason behind the choice
of value will become explicit in Section 5.2).

#### Strongly Connected Economy Graph.

We now show that the economy graph $G$ of our instance is strongly connected.
For ease of explanation, we introduce the notion of _economy graph of
components_ $W=([d],E_{W})$, where there is an edge from $i\in[d]$ to
$j\in[d]$, if and only if, there is an agent $a\in{{\mathcal{D}}}_{i}$ that
has a positive endowment of some chore in $b\in{{\mathcal{D}}}_{j}$. We now
make a claim that strong connectivity of $W$ implies strong connectivity of
the economy graph $G$.

######  Claim 25.

If $W$ is strongly connected then $G$ is also strongly connected.

###### Proof.

Consider any two agents $a$ and $a^{\prime}$. Let $a\in{{\mathcal{D}}}_{i}$
and $a^{\prime}\in{{\mathcal{D}}}_{j}$.191919Note that $j$ could also be equal
to $i$. Consider any chore $b$ that agent $a$ has a positive endowment of and
let ${{\mathcal{D}}}_{i^{\prime}}$ be the component in the disutility graph
that contains $b$.202020Again, $i^{\prime}$ could also be equal to $i$. Then
since ${{\mathcal{D}}}_{i^{\prime}}$ is a biclique in our instance, every
agent in ${{\mathcal{D}}}_{i^{\prime}}$ has finite disutility for the chore
$b$. Therefore, every agent in ${{\mathcal{D}}}_{i^{\prime}}$ is reachable
from $a$ with an edge in the economy graph $G$. Now, since $W$ is strongly
connected, there is a path
$\ell_{1}\rightarrow\ell_{2}\rightarrow\dots\rightarrow\ell_{k}$ from
$\ell_{1}=i^{\prime}$ to $\ell_{k}=j$. Let $a_{\ell_{r}}$ be the agent in the
component ${{\mathcal{D}}}_{\ell_{r}}$, that has a positive endowment of some
chore in the component ${{\mathcal{D}}}_{\ell_{r+1}}$ for all $r\in[k-1]$.
Again, since each ${{\mathcal{D}}}_{\ell_{r}}$ is a biclique, every agent in
${{\mathcal{D}}}_{\ell_{r}}$ has a finite disutility for every chore in
${{\mathcal{D}}}_{\ell_{r}}$. Thus, there is an edge in the economy graph $G$
from $a_{\ell_{r}}$ to every agent in ${{\mathcal{D}}}_{\ell_{r}}$, in
particular there is an edge between $a_{\ell_{r}}$ and $a_{\ell_{r+1}}$ in
$G$. Thus, we have a path $a\rightarrow
a_{\ell_{1}}\rightarrow\dots\rightarrow a_{\ell_{k-1}}\rightarrow a^{\prime}$
in $G$. Therefore, if $W$ is strongly connected, then there is a path between
any two agents in $G$, implying that $G$ is also strongly connected. ∎

From here on, we show that $W$ is strongly connected. Observe that the
disutility graph consists of connected components ${{\mathcal{D}}}^{k}_{i}$
for $k\in[K]$ and $i\in[n]$. Also observe that every component
${{\mathcal{D}}}^{k}_{i}$ in the disutility graph comprises of exactly two
chores $b^{k}_{2i-1}$ and $b^{k}_{2i}$. Therefore, to show that there exists
an edge from component ${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$ to
${{\mathcal{D}}}^{k}_{i}$ in $W$, it suffices to show that
${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$ contains agents that own parts of
chores $b^{k}_{2i-1}$ and $b^{k}_{2i}$. We now outline the edges in our
exchange graph (see Figure 3):

  * •

For all $i\in[n]$, and $2\leq k\leq K$ there is an edge in $W$ from
${{\mathcal{D}}}^{k}_{i}$ to ${{\mathcal{D}}}^{k-1}_{i}$:
${{\mathcal{D}}}^{k}_{i}$ contains the agents $a^{k-1}_{2i-1}$ and
$a^{k-1}_{2i}$ that own parts of chores $b^{k-1}_{2i-1}$ and $b^{k-1}_{2i}$
respectively (see Figure 3).

  * •

For all $i\in[n]$, there is an edge in $W$ from ${{\mathcal{D}}}^{1}_{i}$ to
$D^{K}_{j}$ for all $j\in[n]$: Consider any $j\in[n]$. Observe that the
component ${{\mathcal{D}}}^{1}_{i}$ contains the agents $a^{K}_{2j-1,2i}$ and
$a^{K}_{2j,2i}$ and the agents $a^{K}_{2j-1,2i}$ and $a^{K}_{2j,2i}$ own parts
of chores $b^{K}_{2j-1}$ and $b^{K}_{2j}$ respectively (see Figure 3).

$\scriptstyle{D^{1}_{1}}$$\scriptstyle{D^{K}_{1}}$$\scriptstyle{D^{K-1}_{1}}$$\scriptstyle{D^{2}_{1}}$$\scriptstyle{D^{1}_{i}}$$\scriptstyle{D^{K}_{i}}$$\scriptstyle{D^{K-1}_{i}}$$\scriptstyle{D^{2}_{i}}$$\scriptstyle{D^{1}_{n}}$$\scriptstyle{D^{K}_{n}}$$\scriptstyle{D^{K-1}_{n}}$$\scriptstyle{D^{2}_{n}}$
Figure 3: Illustration of the strong connectivity of the economy graph of
components of our instance. Observe that all nodes are reachable from any
${{\mathcal{D}}}^{1}_{i}$ ($i\in[n]$). Also, from any arbitrary
${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$, the node
${{\mathcal{D}}}^{1}_{i^{\prime}}$ is reachable and since every node is
reachable from ${{\mathcal{D}}}^{1}_{i^{\prime}}$, every node is also
reachable from ${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$ as well. Therefore,
the economy graph of components is strongly connected.

Observe that all nodes are reachable from any ${{\mathcal{D}}}^{1}_{i}$
($i\in[n]$). Also, from any arbitrary
${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$, the node
${{\mathcal{D}}}^{1}_{i^{\prime}}$ is reachable and since every node is
reachable from ${{\mathcal{D}}}^{1}_{i^{\prime}}$, every node is also
reachable from ${{\mathcal{D}}}^{k^{\prime}}_{i^{\prime}}$ as well. Therefore,
the economy graph of components $W$, is strongly connected. Therefore, by
Claim 25 we have that,

$E(I)$ satisfies the condition $SC_{1}$ of Theorem 4.

Thus, $E(I)$ satisfies conditions of Theorem 4 and therefore admits a CE and
thereby a $(1-\epsilon)$-approximate CE for any $\epsilon\geq 0$ (see
Definition 3). Let $p(b^{k}_{i})$ denote the price of chore $b^{k}_{i}$ at an
$(1-\epsilon)$-approximate CE for

$\epsilon=\frac{\alpha_{1}}{200\cdot
n}<\frac{1}{n^{3c+1}}\Rightarrow\epsilon=O(1/n^{10}).$

We now prove that our instance satisfies the required properties of _pairwise
equal endowments_ , _(approximate) price equality_ , _(approximate) fixed
earning_ , _price regulation_ and _reverse ratio amplification_.

###  5.2 $E(I)$ Satisfies All the Properties (Approximately)

#### Pairwise Equal Endowments.

Here, we show that for all $i\in[n]$ and for all $k\in[K]$ the total endowment
of $b^{k}_{2i-1}$ equals the total endowment of $b^{k}_{2i}$ and the total
endowments of each chore in $E(I)$ is $\mathcal{O}(n)$.

######  Lemma 26.

For all $i\in[2n]$, the total endowments of chores $b^{k}_{2i-1}$ and
$b^{k}_{2i}$ is

  1. 1.

$n+n\cdot(1-\alpha_{K})$, if $k=1$. In particular, $a^{\prime}_{2i-1}$ and
$a^{\prime}_{2i}$ _together_ , own $n\cdot(1-\alpha_{K})$ units of chores
$b^{k}_{2i-1}$ and $b^{k}_{2i}$ each.

  2. 2.

$n+\delta_{k}$, if $2\leq k\leq K$.

###### Proof.

When $k=1$, the only agents that have positive endowments of $b^{1}_{2i}$ are
$a^{1}_{2i}$ (has an endowment of $n$ ) , $a^{\prime}_{2i}$ (has an endowment
of
$\tfrac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})$)
and $a^{\prime}_{2i-1}$(has an endowment of
$\tfrac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i-1})$).
Therefore, the total endowment of $b^{1}_{2i}$ from the agents
$a^{\prime}_{2i}$ and $a^{\prime}_{2i-1}$ is

$\displaystyle=\frac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})+\frac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i-1})$
$\displaystyle=\frac{1}{2}\cdot(1-\alpha_{K})\cdot(4n-\sum_{j\in[2n]}(\mathbf{M}_{j,2i}+\mathbf{M}_{j,2i-1})).$

Recall that $\mathbf{M}_{j,2i}+\mathbf{M}_{j,2i-1}=1$. Therefore, the total
endowment of $b^{1}_{2i}$ from the agents $a^{\prime}_{2i}$ and
$a^{\prime}_{2i-1}$ is

$\displaystyle=\frac{1}{2}\cdot(1-\alpha_{K})\cdot(4n-2n)$
$\displaystyle=(1-\alpha_{K})\cdot n.$

Therefore, the total endowment of chore $b^{1}_{2i}$ is
$n+n\cdot(1-\alpha_{K})$. A similar argument will show that the total
endowment of chore $b^{1}_{2i-1}$ is also $n+n\cdot(1-\alpha_{K})$ and that
agents $a^{\prime}_{2i-1}$ and $a^{\prime}_{2i}$ _together_ , own
$n\cdot(1-\alpha_{K})$ units of it.

When $2\leq k\leq K-1$, the only agents that have positive endowments of
$b^{k}_{2i}$ are $a^{k}_{2i}$ (has an endowment of $n$) and
$\overline{a}_{i}^{k}$ (has an endowment of $\delta_{k}$). Therefore, the
total endowment is $n+\delta_{k}$. A similar argument will show that the total
endowment of chore $b^{k}_{2i-1}$ is also $n+\delta_{k}$.

When $k=K$, the only agents that have positive endowments of $b^{K}_{2i}$ are
the agents $a_{2i,j}^{K}$ (has an endowment of $\mathbf{M}_{2i,j}$) for all
$j\in[2n]$ and the agent $\overline{a}^{K}_{i}$ (has an endowment of
$\delta_{K}$). Therefore, the total endowment of chore $b^{K}_{2i}$ is

$\displaystyle=\sum_{j\in[2n]}\mathbf{M}_{2i,j}+\delta_{K}$
$\displaystyle=\sum_{j\in[n]}(\mathbf{M}_{2i,2j-1}+\mathbf{M}_{2i,2j})+\delta_{K}$
$\displaystyle=\sum_{j\in[n]}1+\delta_{K}$ $\displaystyle=n+\delta_{K}$

A similar argument will show that the total endowment of chore $b^{K}_{2i-1}$
is also $n+\delta_{K}$. ∎

#### Price Equality.

Here we will show that the sum of prices of chores $b^{k}_{2i-1}$ and
$b^{k}_{2i}$ are almost same for all $i\in[n]$ and $k\in[K]$. Let us define

$\pi^{k}_{i}=p(b^{k}_{2i-1})+p(b^{k}_{2i}),\ \ \ \forall
i\in[n],k\in[K]\enspace.$

Here on we will use the properties of approximate CE (Definition 3). Recall
that, at an $(1-\epsilon)$-approximate CE, we have $(i)$ complete allocation
each chore, $(ii)$ every agent only consumes her minimum pain-per-buck chores,
and $(iii)$ every agent $i$ earns total price of her endowment up to
$(1\pm\epsilon)$ factor. And that, for two quantities $x$ and $y$, by
$x=(1\pm\epsilon)y$ we mean $(1-\epsilon)y\leq x\leq(1+\epsilon)y$. In
addition, now on

by $x=(1\pm\epsilon)^{d}y$ we mean $(1-\epsilon)^{d}y\leq
x\leq(1+\epsilon)^{d}y$.

######  Lemma 27.

For all $i,i^{\prime}\in[n]$ and for all $k,k^{\prime}\in[K]$, we have
$\pi^{k^{\prime}}_{i^{\prime}}=(1\pm O(n\epsilon))\pi^{k}_{i}$.

###### Proof.

Since $\epsilon<1/n$ it suffices to show that
$\pi^{k^{\prime}}_{i^{\prime}}=(1+\pm\epsilon))^{O(n)}\pi^{k}_{i}$. We show
this in two steps: First we show that for each $i\in[n]$, we have
$\pi^{(}k+1)_{i}=(1\pm\epsilon)^{2}\pi^{k}_{i}$ for all $k<K$, implying that
$\pi^{k^{\prime}}_{i}=(1\pm\epsilon))^{O(n)}\pi^{k}_{i}$ for all
$k,k^{\prime}\in[K]$.

Then we show that $(1-\epsilon)^{2}(\sum_{j\in[n]}\pi^{K}_{j})\leq
n\pi^{1}_{i}=(1\pm\epsilon)^{2}(\sum_{j\in[n]}\pi^{K}_{j})$ for all $i\in[n]$.
This together with the above imply that
$\pi^{1}_{i^{\prime}}\leq(1\pm\epsilon))^{O(n)}\pi^{1}_{i}$ for all
$i,j\in[n]$. Putting these together proves the lemma.

We first show $\pi^{(}k+1)_{i}\leq(1\pm\epsilon)^{2}\pi^{k}_{i}$ for all
$i\leq n,k<K$, wlog let $i=1$. Observe that the agents $a^{k}_{1}$,
$a^{k}_{2}$, $\overline{a}^{(k+1)}_{1}$ and chores $b^{(k+1)}_{1}$,
$b^{(k+1)}_{2}$ form the connected component ${{\mathcal{D}}}^{(k+1)}_{1}$ in
the disutility graph. That means these three agents earn all their money by
consuming only these two chores, and no one else consumes these chores. The
total money supply of these two chores is $(n+\delta_{(k+1)})\pi^{(k+1)}_{1}$.

As per Definition 3, at $(1-\epsilon)$-approximate CE, an agents earn as much
as the total price of their endowments up to $(1\pm\epsilon)$ factor. Now
since $\overline{a}^{(k+1)}_{1}$ owns $\delta_{(k+1)}$ units of both
$b^{(k+1)}_{1}$ and $b^{(k+1)}_{2}$ only, her total cost is
$\delta_{(k+1)}\pi^{(k+1)}_{1}$. Total price of chores owned by agents
$a^{k}_{1}$ and $a^{k}_{2}$ is $n\pi^{k}_{1}$. At equilibrium demand should be
equals supply, implying that,

$\begin{array}[]{ll}&(1-\epsilon)(\delta_{(k+1)}\pi^{(k+1)}_{1}+n\pi^{k}_{1})\leq(n+\delta_{(k+1)})\pi^{(k+1)}_{1}\leq(1+\epsilon)(\delta_{(k+1)}\pi^{(k+1)}_{1}+n\pi^{k}_{1})\\\
\Rightarrow&(1-\epsilon)n\pi^{k}_{1}-\epsilon\delta_{(k+1)}\pi^{(k+1)}_{1}\leq
n\pi^{(k+1)}_{1}\leq(1+\epsilon)n\pi^{k}_{1}+\epsilon\delta_{(k+1)}\pi^{(k+1)}_{1}\\\
\Rightarrow&\frac{(1-\epsilon)}{(1+\epsilon\delta_{(k+1)}/n)}\pi^{k}_{1}\leq\pi^{(k+1)}_{1}\leq\frac{(1+\epsilon)}{(1-\epsilon\delta_{(k+1)}/n)}\pi^{k}_{1}\\\
\Rightarrow&(1-\epsilon)^{2}\pi^{k}_{1}\leq\pi^{(k+1)}_{1}\leq(1+\epsilon)^{2}\pi^{k}_{1}\end{array}$

where the last implication follows from the fact that for $\epsilon<1/n$ we
have $(1-\epsilon)<\frac{1}{(1+\epsilon\delta_{(k+1)}/n)}$ and
$(1+\epsilon)<\frac{1}{(1-\epsilon\delta_{(k+1)}/n)}$.

We now show that $n\pi^{1}_{i}=(1\pm)\epsilon)^{2}\sum_{j\in[n]}\pi^{K}_{j}$:
This time, we look into the connected component ${{\mathcal{D}}}^{1}_{i}$ of
the disutility graph. We can claim that the agents $\\{a^{K}_{j,2i-1}\ |\
j\in[2n]\\}$, $\\{a^{K}_{j,2i}\ |\ j\in[2n]\\}$ and the agents
$a^{\prime}_{2i-1}$ and $a^{\prime}_{2i}$ earn all of their money at an
approximate CE from chores $b^{1}_{2i-1}$ and $b^{1}_{2i}$, and these are the
only agents who consume these two chores. Total money supply of these two
chores is $(n+n(1-\alpha_{K}))\pi^{1}_{i}$ (by Lemma 26)

Observe that the total endowment of agents $a^{\prime}_{2i-1}$ and
$a^{\prime}_{2i}$ is $n(1-\alpha_{K})$ units of chores $b^{1}_{2i-1}$ and
$b^{1}_{2i}$ only, and hence together they must earn
$n(1-\alpha_{K})\pi^{1}_{i}$ up to $(1\pm\epsilon)$. For agents
$\\{a^{K}_{j,2i-1}\ |\ j\in[2n]\\}$ and $\\{a^{K}_{j,2i}\ |\ j\in[2n]\\}$,
recall that each $a^{K}_{\ell,\ell^{\prime}}$ owns
$\mathbf{M}_{\ell,\ell^{\prime}}$ units of $b^{K}_{\ell}$. Therefore, together
they need to earn the following amount up to $(1\pm\epsilon)$ factor.

$\begin{array}[]{l}\sum_{j\in[2n]}\mathbf{M}_{j,2i}\cdot
p(b^{K}_{j})+\sum_{j\in[2n]}\mathbf{M}_{j,2i-1}\cdot p(b^{K}_{j})\\\
=\sum_{j\in[2n]}(\mathbf{M}_{j,2i}+\mathbf{M}_{j,2i-1})\cdot p(b^{K}_{j})\\\
=\sum_{j\in[2n]}p(b^{K}_{j})\ \ \text{(using
$\mathbf{M}_{j,2i-1}+\mathbf{M}_{j,2i}=1$)}\\\
=\sum_{j\in[n]}\pi^{K}_{j}\end{array}$

Again, equating supply with demand we get,

$\begin{array}[]{ll}&(1-\epsilon)(n(1-\alpha_{K})\pi^{1}_{i}+\sum_{j\in[n]}\pi^{K}_{j})\leq(n+n(1-\alpha_{K}))\pi^{1}_{i}\leq(1+\epsilon)(n(1-\alpha_{K})\pi^{1}_{i}+\sum_{j\in[n]}\pi^{K}_{j})\\\
\Rightarrow&(1-\epsilon)\sum_{j\in[n]}\pi^{K}_{j}-\epsilon(n(1-\alpha_{K})\pi^{1}_{i}\leq
n\pi^{1}_{i}\leq(1+\epsilon)\sum_{j\in[n]}\pi^{K}_{j}+\epsilon(n(1-\alpha_{K})\pi^{1}_{i}\\\
\Rightarrow&\frac{(1-\epsilon)}{(1+\epsilon(1-\alpha_{K}))}\sum_{j\in[n]}\pi^{K}_{j}\leq
n\pi^{1}_{i}\leq\frac{(1+\epsilon)}{(1-\epsilon(1-\alpha_{K}))}\sum_{j\in[n]}\pi^{K}_{j}\\\
\Rightarrow&(1-\epsilon)^{2}\sum_{j\in[n]}\pi^{K}_{j}<n\pi^{1}_{i}<(1+\epsilon)^{2}\sum_{j\in[n]}\pi^{K}_{j}\end{array}$

where the last implication follows from the fact that for
$\epsilon,\alpha_{K}<1/n$ we have
$(1-\epsilon)<\frac{1}{(1+\epsilon(1-\alpha_{K}))}$ and
$(1+\epsilon)>\frac{1}{(1-\epsilon(1-\alpha_{K}))}$. ∎

#### (Approximately) Fixed Earning.

Here, we show that in every CE, the earning of each agent $a^{\prime}_{i}$ for
$i\in[2n]$ is fixed up to $(1\pm O(n)\epsilon)$ factor. Note that
(approximate) CE prices are scale invariant.

######  Lemma 28.

Let $\min_{i\in[n],k\leq K}\pi^{i}_{k}=2$. Then for all $i\in[2n]$, we have
that the earning of agent $a^{\prime}_{i}$ is $(1\pm\epsilon
O(n))(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,i})$.

###### Proof.

Let $i=2i^{\prime}$. Then agent $a^{\prime}_{2i^{\prime}}$ owns
$\tfrac{1}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}})$
units of both chores $b^{1}_{2i^{\prime}-1}$ and $b^{1}_{2i^{\prime}}$. Since
the earning of any agent at an $(1-\epsilon)$-approximate CE equals the sum of
prices of chores she owns up to $(1\pm\epsilon)$ factor, we have that the
earning of agent $2i^{\prime}$ is

$\displaystyle=\frac{(1\pm\epsilon)}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}})\cdot(p(b^{1}_{2i^{\prime}-1})+p(b^{1}_{2i^{\prime}}))$
$\displaystyle=\frac{(1\pm\epsilon)}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}})\cdot\pi^{1}_{i^{\prime}}$
$\displaystyle=\frac{(1\pm\epsilon)}{2}\cdot(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}})\cdot
2(1\pm O(n)\epsilon)$ $\displaystyle\text{(by Lemma~{}\ref{price-equality})}.$
$\displaystyle=(1\pm
O(n)\epsilon)(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}}).$

Similarly, when $i=2i^{\prime}-1$ we can show that the total earning of agent
$a^{\prime}_{2i^{\prime}-1}$ is
$(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i^{\prime}-1})$. Thus
the total earning of any agent $a^{\prime}_{i}$ in a CE is $(1\pm
O(n)\epsilon)(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,i})$. ∎

#### Price Regulation.

Here, we show that for all $k\in[K]$ and $i\in[2n]$ the ratio of the prices of
chores $b^{k}_{2i-1}$ and $b^{k}_{2i}$ is bounded.

######  Lemma 29.

For all $k\in[K]$ and for all $i\in[n]$, we have
$\tfrac{1-\alpha_{k}}{1+\alpha_{k}}\leq\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}\leq\tfrac{1+\alpha_{k}}{1-\alpha_{k}}$.

###### Proof.

We prove the lower bound (
$\tfrac{1-\alpha_{k}}{1+\alpha_{k}}\leq\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}$)
by contradiction. The proof for the upper bound is symmetric. So assume that
$\tfrac{1-\alpha_{k}}{1+\alpha_{k}}>\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}$.
In that case, none of the agents in the connected component
${{\mathcal{D}}}^{k}_{i}$ will do any part of chore $b^{k}_{2i-1}$ (as the
disutility to price ratio of $b^{k}_{2i-1}$ will be strictly more than that of
$b^{k}_{2i}$). Since all the other agents have a disutility of $\infty$ for
$b^{k}_{2i-1}$, it will remain unallocated. Therefore, the current prices for
chores are not the prices corresponding to a CE, which is a contradiction. ∎

#### Reverse Ratio Amplification.

Lastly, we show the property that when the price of chore $b^{k}_{i}$ is at a
limit, then the price of chore $b^{k+1}_{i}$ is at the opposite limit, i.e.,
when $p(b^{k}_{i})=1+\alpha_{k}$, then we have $p(b^{k+1}_{i})=1-\alpha_{k+1}$
and similarly when $p(b^{k}_{i})=1-\alpha_{k}$, then we have
$p(b^{k+1}_{i})=1+\alpha_{k+1}$.

######  Lemma 30.

For all $1\leq k<K$ and $i\in[n]$, we have that,

  1. 1.

if
$\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}=\tfrac{1-\alpha_{k}}{1+\alpha_{k}}$,
then
$\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}=\tfrac{1+\alpha_{k+1}}{1-\alpha_{k+1}}$,
and

  2. 2.

if
$\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}=\tfrac{1+\alpha_{k}}{1-\alpha_{k}}$,
then
$\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}=\tfrac{1-\alpha_{k+1}}{1+\alpha_{k+1}}$.

###### Proof.

We just show the proof of part 1. The proof for part 2 is symmetric. Let us
assume that
$\tfrac{p(b^{k}_{2i-1})}{p(b^{k}_{2i})}=\tfrac{1-\alpha_{k}}{1+\alpha_{k}}$,
and that $p(b^{k}_{2i-1})+p(b^{k}_{2i})=2$ (using scale invariance of CE
prices). Then, $p(b^{k}_{2i-1})=1-\alpha_{k}$ and
$p(b^{k}_{2i})=1+\alpha_{k}$. From the proof of Lemma 27, we have that
$p(b^{k+1}_{2i-1})+p(b^{k+1}_{2i})=2(1\pm\epsilon)^{2}$ and by Lemma 29 we
have
$\tfrac{1-\alpha_{k+1}}{1+\alpha_{k+1}}\leq\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}\leq\tfrac{1+\alpha_{k+1}}{1-\alpha_{k+1}}$.
Therefore, $(1-\alpha_{k+1})(1-\epsilon)^{2}\leq
p(b^{k+1}_{2i-1}),p(b^{k+1}_{2i})\leq(1+\alpha_{k+1})(1+\epsilon)^{2}$.

Observe that agent $a^{k}_{2i}$ owns $n$ units of chore $b^{k}_{2i}$ and has
finite disutility only for the chores $b^{k+1}_{2i-1}$ and $b^{k+1}_{2i}$
($a^{k}_{2i}$ belongs in the connected component ${{\mathcal{D}}}^{k+1}_{i}$).
Since at a $(1-\epsilon)$-approximate CE, the total earning of agent
$a^{k}_{2i}$ equals the sum of prices of chores she owns up to
$(1\pm\epsilon)$ factor, we have that $a^{k}_{2i}$ earns $(1\pm\epsilon)n\cdot
p(b^{k}_{2i})=(1\pm\epsilon)n(1+\alpha_{k})$ amount of money from chores
$b^{k+1}_{2i-1}$ and $b^{k+1}_{2i}$. We claim that it suffices to show that
$a^{k}_{2i}$ earns some of her money from the chore $b^{k+1}_{2i-1}$: This
would immediately imply that
$\tfrac{d(a^{k}_{2i},b^{k+1}_{2i-1})}{p(b^{k+1}_{2i-1})}\leq\tfrac{d(a^{k}_{2i},b^{k+1}_{2i})}{p(b^{k+1}_{2i})}$,
further implying that
$\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}\geq\tfrac{1+\alpha_{k+1}}{1-\alpha_{k+1}}$.
However, by Lemma 29, we have that
$\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}\leq\tfrac{1+\alpha_{k+1}}{1-\alpha_{k+1}}$,
and thus we can conclude that
$\tfrac{p(b^{k+1}_{2i-1})}{p(b^{k+1}_{2i})}=\tfrac{1+\alpha_{k+1}}{1-\alpha_{k+1}}$.

For the rest of the proof, we show that $a^{k}_{2i}$ earns positive amount of
money from chore $b^{k+1}_{2i-1}$. We prove this by contradiction. So let us
assume that $a^{k}_{2i}$ earns all her money of at least
$(1-\epsilon)n\cdot(1+\alpha_{k})$, only from chore $b^{k+1}_{2i}$. We will
now show that the current prices of chores are not the prices corresponding to
a CE by distinguishing between two cases. Recall that
$\delta_{k}=\frac{n}{2}\alpha_{k}$ for all $k\in[K]$.

  * •

$p(b^{k+1}_{2i})>p(b^{k+1}_{2i-1})$: Observe that in this case, agent
$\overline{a}^{k+1}_{i}$ will also earn all of her money from $b^{k+1}_{2i}$
only (as the disutility to price ratio of $b^{k+1}_{2i}$ is strictly smaller
than that of $b^{k+1}_{2i-1}$). Therefore, we have that the total money agents
$a^{k}_{2i}$ and $\overline{a}^{k+1}_{i}$ earn from $b^{k+1}_{2i}$ is,

$\displaystyle\geq(1-\epsilon)(\pi^{k+1}_{i}\delta_{k+1}+n\cdot(1+\alpha_{k}))$
$\displaystyle\geq(1-\epsilon)(2(1-2\epsilon)\frac{n}{2}\alpha_{k+1}+n\cdot(1+\frac{2}{3}\cdot\alpha_{k+1})$
$\displaystyle\quad\quad(\text{as $\delta_{k+1}=\frac{n}{2}\alpha_{k+1}$,
$\alpha_{k+1}=\frac{3}{2}\cdot\alpha_{k}$, and $\pi^{k+1}_{i}\geq
2(1-2\epsilon)$})$
$\displaystyle=(1-\epsilon)\cdot(n(1+\alpha_{k+1})+\tfrac{2n}{3}\alpha_{k+1}-2\epsilon
n\alpha_{k+1})$
$\displaystyle=\frac{(1-\epsilon)}{(1+3\epsilon)}(1+3\epsilon)[(n+\tfrac{n}{2}\alpha_{k+1})(1+\alpha_{k+1})-\tfrac{n}{2}\alpha_{k+1}\tfrac{2n}{3}\alpha_{k+1}-2\epsilon
n\alpha_{k+1}]$
$\displaystyle=(1-\tfrac{4\epsilon}{(1+3\epsilon)})(1+3\epsilon)[(n+\delta_{k+1})(1+\alpha_{k+1})-\tfrac{n}{2}\alpha_{k+1}+\tfrac{2n}{3}\alpha_{k+1}-2\epsilon
n\alpha_{k+1}]$
$\displaystyle>(1+3\epsilon)(n+\delta_{k+1})(1+\alpha_{k+1})+(1+3\epsilon)n\alpha_{k+1}\left(\tfrac{2}{3}-\tfrac{1+\alpha_{k+1}}{2}-2\epsilon\right)-4\epsilon(4n)$
$\displaystyle\quad\quad(\text{as
$[(n+\delta_{k+1})(1+\alpha_{k+1})-\tfrac{n}{2}\alpha_{k+1}+\tfrac{2n}{3}\alpha_{k+1}-2\epsilon
n\alpha_{k+1}]<4n$})$
$\displaystyle>(1+\epsilon)^{2}(n+\delta_{k+1})(1+\alpha_{k+1})+n(\alpha_{k+1}(2/3-1/2-1/n)-16\epsilon)$
$\displaystyle>(1+\epsilon)^{2}(n+\delta_{k+1})(1+\alpha_{k+1})\ \ (\text{as
$\epsilon<\tfrac{\alpha_{k+1}}{192}$})$

However, total (money supply) price of $b^{k+1}_{2i}$ is at most
$(n+\delta_{k+1})p(b^{k+1}_{2i})\leq(n+\delta_{k+1})(1+\epsilon)^{2}(1+\alpha_{k+1})$
since it’s total endowment is $n+\delta_{k+1}$ by Lemma 26. This contradicts
demand equals supply for chore $b^{k+1}_{2i}$.

  * •

$p(b^{k+1}_{2i})\leq p(b^{k+1}_{2i-1})$: In this case,
$p(b^{k+1}_{2i})\leq(1+\epsilon)^{2}$. Since the total endowment of
$b^{k+1}_{2i}$ is $n+\delta_{k+1}$ by Lemma 26, the total (money supply) price
of chore $b^{k+1}_{2i}$ is $(1+\epsilon)^{2}(n+\delta_{k+1})$. Next we show
that this is strictly less than the demand from agent $a^{k}_{2i}$. Agent
$a^{k}_{2i}$ owns $n$ units of $b^{k}_{2i}$ and hence earns at least
$(1-\epsilon)n(1+\alpha_{k})$ at $(1-\epsilon)$-approximate CE.

$\displaystyle(1-\epsilon)n(1+\alpha_{k})$
$\displaystyle=\frac{(1-\epsilon)}{(1+3\epsilon)}(1+3\epsilon)n(1+\frac{2}{3}\alpha_{k+1})$
$\displaystyle=(1-\tfrac{4\epsilon}{(1+3\epsilon)}(1+3\epsilon)(n+\frac{n}{2}\alpha_{k+1}+\frac{n}{6}\alpha_{k+1})$
$\displaystyle>(1+3\epsilon)(n+\delta_{k+1})+\frac{n}{6}\alpha_{k+1})-4\epsilon(2n)$
$\displaystyle>(1+\epsilon)^{2}(n+\delta_{k+1})\ \ (\text{as
$\epsilon<\frac{\alpha_{k+1}}{48}$})\qed$

Since $K$ is even, a repeated application of Lemma 30 will yield the following
lemma,

######  Lemma 31.

We have,

  1. 1.

if
$\tfrac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\tfrac{1-\alpha_{1}}{1+\alpha_{1}}$,
then
$\tfrac{p(b^{K}_{2i-1})}{p(b^{K}_{2i})}=\tfrac{1+\alpha_{K}}{1-\alpha_{K}}$,
and

  2. 2.

if
$\tfrac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\tfrac{1+\alpha_{1}}{1-\alpha_{1}}$,
then
$\tfrac{p(b^{K}_{2i-1})}{p(b^{K}_{2i})}=\tfrac{1-\alpha_{K}}{1+\alpha_{K}}$.

Now that we have shown that our instance satisfies the desired properties of
pairwise equal endowments, (approximate) fixed earning, (approximate) price
equality, price regulation and reverse ratio amplification, we are ready to
outline how to determine the equilibrium strategy vector $x$ for the instance
$I$ of the polymatrix game, given the $(1-\epsilon)$-approximate CE prices of
the instance $E(I)$ of chore division:

$\displaystyle\forall i\in[n],\ \ $ $\displaystyle x_{2i-1}$
$\displaystyle=\frac{2p(b^{K}_{2i-1})-(1-\alpha_{K})\pi^{K}_{i}}{2\cdot\pi^{K}_{i}\cdot\alpha_{K}}$
$\displaystyle x_{2i}$
$\displaystyle=\frac{2p(b^{K}_{2i})-(1-\alpha_{K})\pi^{K}_{i}}{2\cdot\pi^{K}_{i}\cdot\alpha_{K}}$

It is clear that given the prices of chores at a CE, the equilibrium strategy
vector can be obtained in linear time. We will now show that $x$ is the
desired equilibrium strategy vector for instance $I$ of the polymatrix game.

######  Lemma 32.

$x=\langle x_{1},x_{2},\dots,x_{2n}\rangle$ is an equilibrium strategy vector
for the polymatrix game instance $I$.

###### Proof.

First, observe that since $\pi^{K}_{i}=p(b^{K}_{2i-1})+p(b^{K}_{2i})$ and our
instance satisfies price regulation (Lemma 29) we have that for all $i\in[n]$,
$(1-\alpha_{K})\frac{\pi^{K}_{i}}{2}\leq
p(b^{K}_{2i-1}),p(b^{K}_{2i})\leq(1+\alpha_{K})\frac{\pi^{K}_{i}}{2}$.
Therefore, for all $i\in[2n]$ $x_{i}\geq 0$ . Furthermore, for all $i\in[n]$
we have
$x_{2i-1}+x_{2i}=\tfrac{2p(b^{K}_{2i-1})+p(b^{K}_{2i})-2(1-\alpha_{K})\pi^{K}_{i}}{2\cdot\pi^{K}_{i}\cdot\alpha_{K}}=\tfrac{2\pi^{K}_{i}\alpha_{K}}{2\pi^{K}_{i}\alpha_{K}}=1$.

Now we will show that if
$x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}$,
then $x_{2i-1}=0$. The proof for the other symmetric condition will be
similar. So let us assume that
$x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}$.
Note that if $p(b^{K}_{2i-1})=(1-\alpha_{K})\frac{\pi^{K}_{i}}{2}$, then
$x_{2i-1}=0$. Hence, by Lemma 31 it suffices to show that
$\frac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\frac{1+\alpha_{1}}{1-\alpha_{1}}$.
Wlog, assume that $\pi^{1}_{i}=p(b^{1}_{2i-1})+p(b^{1}_{2i})=2$, implying
$(1-\alpha_{1})\leq p(b^{1}_{2i-1}),p(b^{1}_{2i})\leq(1+\alpha_{1})$. Next we
will show that if
$\frac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}<\frac{1+\alpha_{1}}{1-\alpha_{1}}$,
then $p(b^{1}_{2i})>(1+\alpha_{1})$, which is a contradiction. This will
complete the proof.

By Lemma 27 we have $2(1-O(n)\epsilon)\leq\pi^{K}_{i}\leq 2(1+O(n)\epsilon)$
for all $i\in[n]$. This implies, $p(b^{K}_{i})=(1\pm
O(n)\epsilon)(2x_{i}\alpha_{K}+(1-\alpha_{K}))$ for all $i\in[2n]$. Observe
that the agents that have a disutility of $1-\alpha_{1}$ towards chore
$b^{1}_{2i}$ are $\left\\{a^{K}_{j,2i}\ |\ j\in[2n]\right\\}\cup
a^{\prime}_{2i}$. Observe that at the given prices the sum of prices of chores
owned by these agents is,

$\displaystyle=\sum_{j\in[2n]}\mathbf{M}_{j,2i}\cdot
p(b^{K}_{j})+(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})\quad\quad(\text{by
Lemma~{}\ref{fixed-earning}})$
$\displaystyle\geq\sum_{j\in[2n]}\mathbf{M}_{j,2i}\cdot(1-O(n)\epsilon)(2\alpha_{K}\cdot
x_{j}+(1-\alpha_{K}))+(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})\quad\quad\text{(substituting
$p(b^{K}_{j})$)}$
$\displaystyle=(1-O(n)\epsilon)\sum_{j\in[2n]}2\alpha_{K}\cdot
x_{j}\cdot\mathbf{M}_{j,2i}+(1-\alpha_{K})(1-O(n)\epsilon)\cdot\sum_{j\in[2n]}\mathbf{M}_{j,2i}+(1-\alpha_{K})\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})$
$\displaystyle\geq(1-O(n)\epsilon)2\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i}+2n\cdot(1-\alpha_{K})-\epsilon
O(n^{2}).$

Similarly, the total earning of the agents that have a disutility of
$1-\alpha_{1}$ towards $b^{1}_{2i-1}$ is at most
$(1+O(n)\epsilon)2\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i-1}+2n\cdot(1-\alpha_{K})+\epsilon
O(n^{2})$. Observe that the agents with disutility $1-\alpha_{1}$ towards
$b^{1}_{2i}$ can earn all of their money only from the chores $b^{1}_{2i}$ or
$b^{1}_{2i-1}$ (as these are the only chores towards which they have finite
disutility). Also note that both chores $b^{1}_{2i-1}$ and $b^{1}_{2i}$ have
the same total endowment which is $n+n\cdot(1-\alpha_{K})$ by Lemma 26(part
1). Now if,
$\frac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}<\frac{1+\alpha_{1}}{1-\alpha_{1}}$,
then agents with disutility $1-\alpha_{1}$ towards $b^{1}_{2i}$ earn all of
their money entirely from $b^{1}_{2i}$ (they earn nothing from
$b^{1}_{2i-1}$). Since at $(1-\epsilon)$-approximate CE they earn at least
$(1-\epsilon)$ times price of their endowments, we have

$p(b^{1}_{2i})\geq(1-\epsilon)\tfrac{2(1-O(n)\epsilon)\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i}+2n\cdot(1-\alpha_{K})-\epsilon
O(n^{2})}{n+n\cdot(1-\alpha_{K})}$ (8)

Agents with disutility $1-\alpha_{1}$ towards $b^{1}_{2i-1}$ may earn from
both $b^{1}_{2i}$ and $b^{1}_{2i-1}$. Since they earn at most $(1+\epsilon)$
times price of their endowments, we have

$p(b^{1}_{2i-1})\leq(1+\epsilon)\tfrac{2(1+O(n)\epsilon)\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i-1}+2n\cdot(1-\alpha_{K})+\epsilon
O(n^{2})}{n+n\cdot(1-\alpha_{K})}$ (9)

Using the above two inequalities together with
$x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}$ we
will next show that $p(b^{1}_{2i})>(1+\alpha_{1})$.

$\displaystyle(n+n\cdot(1-\alpha_{K}))p(b^{1}_{2i})$
$\displaystyle\geq(1-\epsilon)\left[2(1-O(n)\epsilon)\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i}+2n\cdot(1-\alpha_{K})-\epsilon
O(n^{2})\right]$
$\displaystyle>(1-\epsilon)\left[2(1-O(n)\epsilon)\alpha_{K}x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{2(1-O(n)\epsilon)\alpha_{K}}{n}+2n(1-\alpha_{K})-\epsilon
O(n^{2})\right]$
$\displaystyle>(1-\epsilon)(1-O(n)\epsilon)^{2}\left[(1-\epsilon)(n+n(1-\alpha_{K}))p(b^{1}_{2i-1})-2n(1-\alpha_{K})-\epsilon
O(n^{2})+\frac{2\alpha_{K}}{n}\right.$ $\displaystyle\hskip
113.81102pt\left.+2n(1-\alpha_{K})-\frac{\epsilon
O(n^{2})}{(1-O(n)\epsilon)^{2}}\right]\quad\quad$ $\displaystyle\hskip
184.9429pt(\text{Using \eqref{eq:le-2} and $\tfrac{1}{(1+x)}>(1-x)$})$
$\displaystyle>(1-\epsilon)^{2}(1-O(n)\epsilon)\left[(n+n(1-\alpha_{K}))(1-\alpha_{1})+\frac{2\alpha_{K}}{n}-\epsilon
O(n^{2})(1+O(n)\epsilon)\right]$ $\displaystyle\quad\quad(\text{Using
$p(b^{1}_{2i-1})>(1-\alpha_{1})$ and $\tfrac{1}{(1-x)}<(1+2x)$})$
$\displaystyle\geq(1-O(n)\epsilon)\left[(n+n(1-\alpha_{K}))(1-\alpha_{1}+\frac{\alpha_{K}}{n^{2}}\right]+(1-O(n)\epsilon)\left[\frac{\alpha_{K}}{n}-\epsilon
O(n^{2})(1+O(n)\epsilon)\right]$
$\displaystyle>(1-O(n)\epsilon)(n+n(1-\alpha_{K})(1-\alpha_{1}+n\alpha_{1})\ \
(\text{as $\epsilon<\frac{\alpha_{1}}{4}\leq\frac{\alpha_{K}}{4n^{3}}$})$
$\displaystyle\geq(n+n(1-\alpha_{K}))(1+\alpha_{1})+(n+n(1-\alpha_{K}))(1+(n-2)\alpha_{1})$
$\displaystyle\hskip
113.81102pt-O(n)\epsilon(n+n(1-\alpha_{K})(1+(n-1)\alpha_{1})$
$\displaystyle>(n+n(1-\alpha_{K}))(1+\alpha_{1})$

The above implies $p(b^{1}_{2i})>(1+\alpha_{1})$ as aimed, which is a
contradiction to $p(b^{1}_{2i})\leq(1+\alpha_{1})$. Therefore, agents with
$(1-\alpha_{1})$ disutility towards $b^{1}_{2i}$ must be consuming both
$b^{1}_{2i}$ and $b^{1}_{2i-1}$. This is possible only if
$\frac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\frac{1+\alpha_{1}}{1-\alpha_{1}}$,
implying
$\frac{p(b^{K}_{2i-1})}{p(b^{K}_{2i})}=\frac{1-\alpha_{K}}{1+\alpha_{K}}$ by
Lemma 31 and thereby $p(b^{K}_{2i-1})=(1-\alpha_{K})\frac{\pi^{K}_{i}}{2}$.
Replacing this in the expression for $x_{2i-1}$ we get,

$\displaystyle x_{2i-1}$
$\displaystyle=\frac{2p(b^{K}_{2i})-(1-\alpha_{K})\pi^{K}_{i}}{2\cdot\pi^{K}_{i}\cdot\alpha_{K}}$
$\displaystyle=\frac{\pi^{K}_{i}(1-\alpha_{K})-(1-\alpha_{K})\pi^{K}_{i}}{2\cdot\alpha_{K}}$
$\displaystyle=0.$

A very similar argument will show that when
$x^{T}\cdot\mathbf{M}_{*,{2i-1}}>x^{T}\cdot\mathbf{M}_{*,2i}+\tfrac{1}{n}$,
then $x_{2i}=0$. Thus, $x=\langle x_{1},x_{2},\dots,x_{n}\rangle$ is a desired
Nash equilibrium strategy vector for the polymatrix game $I$. ∎

Note that, since $\epsilon=\frac{\alpha_{1}}{200n}$, we have
$\epsilon=\frac{1}{200n^{3c+1}}=\frac{1}{poly(n)}$. Thus, this immediately
implies the main result of this section, where the sufficiency conditions to
guarantee existence of CE are of Theorem 4.

######  Theorem 33.

Finding $(1-\frac{1}{poly(n)})$ approximate CE for chore division in the
exchange model is PPAD-hard even for instances satisfying conditions $SC_{1}$
and $SC_{2}$ of Theorem 4.

###### Proof.

We bring all the points together. Normalized polymatrix game is PPAD-hard
[CPY17]. Given an instance $I$ of the normalized polymatrix game, in
polynomial time we can determine the instance $E(I)$. $E(I)$ satisfies the
sufficiency conditions $SC_{1}$ and $SC_{2}$ of Theorem 4 and therefore admits
an exact as well as approximate CE. Given the prices at a
$(1-\frac{1}{poly(n)})$-approximate CE of $E(I)$, in polynomial time we can
determine the equilibrium strategy vector for the polymatrix game by Lemma 32.
Therefore, chore division is PPAD-hard even on instances that satisfy $SC_{1}$
and $SC_{2}$ of Theorem 4 sufficient to guarantee existence of CE. ∎

## References

  * [BCM22] Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta.  Polynomial time algorithms to find an approximate competitive equilibrium for chores.  In SODA, pages 2285–2302. SIAM, 2022.
  * [BKV18] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proc. 19th Conf. Economics and Computation (EC), pages 557–574, 2018.
  * [BMSY17] Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaia.  Competitive division of a mixed manna.  Econometrica, 85(6):1847–1871, 2017.
  * [BS19] Simina Branzei and Fedor Sandomirskiy.  Algorithms for competitive division of chores.  arXiv:1907.01766 (To appear in Mathematics of Operations Research), 2019\.
  * [CCPY22] Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis.  Computational hardness of the Hylland-Zeckhauser scheme.  In Proc. 33rd Symp. Discrete Algorithms (SODA), 2022.  To appear.
  * [CDDT09] Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng.  Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities.  In Proc. 50th Symp. Foundations of Computer Science (FOCS), pages 273–282, 2009.
  * [CDG+17] Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay Vazirani, and Sadra Yazdanbod.  Convex program duality, Fisher markets, and Nash social welfare.  In Proc. 18th Conf. Economics and Computation (EC), 2017.
  * [CGMM21] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  Competitive allocation of a mixed manna.  In Proc. 32nd Symp. Discrete Algorithms (SODA), 2021.
  * [CGMM22] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  On the existence of competitive equilibrium with chores.  In ITCS, volume 215 of LIPIcs, pages 41:1–41:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [CM18] Bhaskar Ray Chaudhury and Kurt Mehlhorn.  Combinatorial algorithms for general linear Arrow-Debreu markets.  In Proc. 38th Conf. Foundations of Software Tech. and Theoret. Comp. Sci. (FSTTCS), volume 122, pages 26:1–26:16, 2018.
  * [CMPV05] Bruno Codenotti, Benton McCune, Sriram Penumatcha, and Kasturi R. Varadarajan.  Market equilibrium for CES exchange economies: Existence, multiplicity, and computation.  In Proc. 25th Conf. Foundations of Software Tech. and Theoret. Comp. Sci. (FSTTCS), pages 505–516, 2005.
  * [Cor89] Bernard Cornet.  Linear exchange economies.  Technical report, Cahier Eco-Math, Université de Paris, 1989.
  * [CPY17] Xi Chen, Dimitris Paparas, and Mihalis Yannakakis.  The complexity of non-monotone markets.  Journal of the ACM (JACM), 64(3):1–56, 2017.
  * [CSVY06] Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, and Yinyu Ye.  Leontief economies encode two-player zero-sum games.  In Proc. 17th Symp. Discrete Algorithms (SODA), pages 659–667, 2006.
  * [CT09] Xi Chen and Shang-Hua Teng.  Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria.  In Proc. 20th Intl. Symp. Algorithms and Computation (ISAAC), pages 647–656, 2009.
  * [DGM16] Ran Duan, Jugal Garg, and Kurt Mehlhorn.  An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market.  In Proc. 27th Symp. Discrete Algorithms (SODA), pages 90–106, 2016.
  * [DGV16] Nikhil Devanur, Jugal Garg, and László Végh.  A rational convex program for linear Arrow-Debreu markets.  ACM Trans. Econom. Comput., 5(1):6:1–6:13, 2016.
  * [DM15] Ran Duan and Kurt Mehlhorn.  A combinatorial polynomial algorithm for the linear Arrow-Debreu market.  Inf. Comput., 243:112–132, 2015.
  * [DPSV08] Nikhil Devanur, Christos Papadimitriou, Amin Saberi, and Vijay Vazirani.  Market equilibrium via a primal–dual algorithm for a convex program.  J. ACM, 55(5), 2008.
  * [Eav76] B. Curtis Eaves.  A finite algorithm for the linear exchange model.  J. Math. Econom., 3:197–203, 1976.
  * [EG59] Edmund Eisenberg and David Gale.  Consensus of subjective probabilities: The Pari-Mutuel method.  Ann. Math. Stat., 30(1):165–168, 1959.
  * [Eis61] Edmund Eisenberg.  Aggregation of utility functions.  Management Sci., 7(4):337–350, 1961.
  * [EPS22] Soroush Ebadian, Dominik Peters, and Nisarg Shah.  How to fairly allocate easy and difficult chores.  In Proc. 21st Conf. Auton. Agents and Multi-Agent Systems (AAMAS), 2022.  To appear.
  * [FGHS21] John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani.  The complexity of gradient descent: CLS = PPAD $\cap$ PLS.  In Proc. 53rd Symp. Theory of Computing (STOC), pages 46–59, 2021\.
  * [Fuj80] Satoru Fujishige.  Lexicographically optimal base of a polymatroid with respect to a weight vector.  Mathematics of Operations Research, 5(2):186–196, 1980.
  * [Gal76] David Gale.  The linear exchange model.  Journal of Mathematical Economics, 3(2):205–209, l976.
  * [GHV21] Jugal Garg, Edin Husić, and László Végh.  Auction algorithms for market equilibrium with weak gross substitute demands.  In Proc. 38th Symp. Theoret. Aspects of Computer Science (STACS), volume 187, pages 33:1–33:19, 2021.
  * [GL91] Donald Goldfarb and Shucheng Liu.  An O(n${}^{\mbox{3}}$L) primal interior point algorithm for convex quadratic programming.  Math. Program., 49:325–340, 1991.
  * [GM20] Jugal Garg and Peter McGlaughlin.  Computing competitive equilibria with mixed manna.  In Proc. 19th Conf. Auton. Agents and Multi-Agent Systems (AAMAS), pages 420–428, 2020.
  * [GMQ22] Jugal Garg, Aniket Murhekar, and John Qin.  Fair and efficient allocations of chores under bivalued preferences.  In Proc. 36th Conf. Artif. Intell. (AAAI), 2022.  To appear.
  * [GMVY17] Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod.  Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria.  In STOC, pages 890–901, 2017.
  * [GP14] Jonathan R. Goldman and Ariel D. Procaccia.  Spliddit: unleashing fair division algorithms.  SIGecom Exchanges, 13(2):41–46, 2014.
  * [GV19] Jugal Garg and László A Végh.  A strongly polynomial algorithm for linear exchange markets.  In Proc. 51st Symp. Theory of Computing (STOC), 2019.
  * [HZ79] Aanund Hylland and Richard Zeckhauser.  The efficient allocation of individuals to positions.  J. Political Economy, 87(2):293–314, 1979.
  * [Jai07] Kamal Jain.  A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities.  SIAM J. Comput., 37(1):306–318, 2007.
  * [NP83] E I Nenakov and M E Primak.  One algorithm for finding solutions of the Arrow-Debreu model.  Kibernetica, 3:127–128, 1983.
  * [Orl10] James Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proc. 42nd Symp. Theory of Computing (STOC), pages 291–300, 2010.
  * [Shm09] Vadim Shmyrev.  An algorithm for finding equilibrium in the linear exchange model with fixed budgets.  J. Appl. Indust. Math., 3(4):505–518, 2009.
  * [Vég12] László Végh.  Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives.  In Proc. 44th Symp. Theory of Computing (STOC), pages 27–40, 2012\.
  * [Ye08] Yinyu Ye.  A path to the Arrow-Debreu competitive market equilibrium.  Math. Prog., 111(1-2):315–348, 2008.