# Dividing Bads is Harder than Dividing Goods:
On the Complexity of Fair and Efficient Division of Chores

Bhaskar Ray Chaudhury
<EMAIL_ADDRESS>MPI for Informatics, Saarland Informatics Campus,
Graduate School of Computer Science, Saarbrücken, Germany Jugal Garg
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign. Supported by
NSF Grant CCF-1942321 (CAREER) Peter McGlaughlin
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign Ruta Mehta
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign. Supported by
NSF Grant CCF-1750436 (CAREER)

###### Abstract

We study the chore division problem where a set of agents needs to divide a
set of chores (bads) among themselves fairly and efficiently. We assume that
agents have linear disutility (cost) functions. Like for the case of goods,
_competitive division_ is known to be arguably the best mechanism for the bads
as well. However, unlike goods, there are multiple competitive divisions with
very different disutility value profiles in bads. Although all competitive
divisions satisfy the standard notions of fairness and efficiency, some
divisions are significantly fairer and efficient than the others. This raises
two important natural questions: Does there exist a competitive division in
which no agent is assigned a chore that she hugely dislikes? Are there simple
sufficient conditions for the existence and polynomial-time algorithms
assuming them?

We investigate both these questions in this paper. We show that the first
problem is strongly NP-hard. Further, we derive a simple sufficient condition
for the existence, and we show that finding a competitive division is PPAD-
hard assuming the condition. These results are in sharp contrast to the case
of goods where both problems are strongly polynomial-time solvable. To the
best of our knowledge, these are the first hardness results for the chore
division problem, and, in fact, for any economic model under _linear_
preferences.

##  1 Introduction

We consider the chore division problem where a set of $n$ agents needs to
divide $m$ divisible chores (bads) among themselves in a _fair_ and
_efficient_ manner. We assume that agents have linear disutility (cost)
functions, i.e., each agent $i$ has a disutility $d(i,j)>0$ for a unit amount
of chore $j$, and her disutility for an allocation in which $X_{ij}$ amount of
chore $j$ is assigned to her is $\sum_{j}d(i,j)X_{ij}$.

A division based on _competitive equilibrium_ is arguably the best mechanism
for this problem due to its remarkable fairness and efficiency guarantees; we
refer to the seminal papers of Bogomolnaia et al. [BMSY17, BMSY19] for an
elaborate discussion. Competitive equilibrium is a central solution concept in
economics, where prices and allocation are such that demand meets supply when
each agent gets her most preferred assignment. Two most ideal economic models
to study competitive division of chores are Fisher (fixed incomes) and
Exchange. An exchange model is like a barter system, where each agent comes
with an initial endowment of chores and exchanges them with others to minimize
her disutility function. Fisher is a special case of exchange model where each
agent has a fixed proportion of each chore. Competitive Equilibrium with Equal
Incomes (CEEI) [Var74] is a further special case of Fisher where each agent
has the same endowment.

The vast majority of work in fair division focuses on the case of _disposable_
goods that agents enjoy or at least can throw away at no cost. The equilibrium
computation problem is well-understood in the case of goods. For the exchange
model, even though an equilibrium may not always exist, there is a simple
(polynomial-time) necessary and sufficient condition for the existence
[Gal76], convex programming formulations [Jai07, DGV16], and polynomial-time
algorithms [Jai07, Ye07, DM15, DGM16, GV19]. On the other hand, for the Fisher
model, an equilibrium always exists, and there are further specialized convex
programs [EG59, Shm09, CDG+17] and algorithms [DPSV08, Orl10, Vég12, Vég14] in
addition to the ones for the exchange model.

However, many situations contain undesirable bads (e.g., house chores and job
shifts). Clearly, chores are _nondisposable_ and must be allocated.
Bogomolnaia et al. [BMSY17, BMSY19] showed that the chore division problem is
quite different than the case of goods; namely, there are multiple
disconnected sets of equilibria with different disutility value profiles. They
also conjectured that the computational problem is likely to be more difficult
in this case; however, neither polynomial-time algorithms nor hardness results
have been obtained so far. Polynomial-time algorithms are known only for the
special case of constantly many agents (or chores) [BS19, GM20]. Although
these algorithms are obtained for the Fisher model, they easily extend to the
exchange as well.

Let us now consider an example where two agents need to divide two chores with
unit supply each, and agents have the same endowment. Assume that the
disutility values are: $d(1,1)=d(2,2)=1;d(1,2)=d(2,1)=L$, where $L\gg 1$.
There are three competitive divisions in this case:

$X^{1}=\left[\begin{array}[]{ll}1&0\\\ 0&1\end{array}\right],\ \ \ \ \
X^{2}=\left[\begin{array}[]{ll}1&\tfrac{L-1}{2L}\\\
0&\tfrac{L+1}{2L}\end{array}\right],\ \ \text{ and }\ \
X^{3}=\left[\begin{array}[]{ll}\tfrac{L+1}{2L}&0\\\
\tfrac{L-1}{2L}&1\end{array}\right]\enspace.$

The disutility value profiles at these divisions are
$(1,1),(\tfrac{L+1}{2},\tfrac{L+1}{2L})$, and
$(\tfrac{L+1}{2L},\tfrac{L+1}{2})$ respectively. Observe that as $L$
approaches infinity, one agent’s disutility value approaches infinity in the
last two divisions ($X^{2}$ and $X^{3}$). Although they all satisfy the
standard fairness and efficiency properties, namely _no envy_ ,
_proportionality_ , _Pareto efficiency_ , and so on, one would still want to
use the first division that is clearly significantly fairer and efficient
among the three. Hence, a important natural question is:

Question 1. Does there exist a competitive division where no agent $i$ is
allocated a chore $j$ that she _hugely dislikes_ , i.e., for which $d(i,j)$ is
greater than equal to a given threshold $\tau$?

In the above example, for any $\tau>1$ the answer is “yes”, otherwise “no”.
This leads to another natural question:

Question 2. Are there simple sufficient conditions for the existence? And, can
we compute a competitive division in polynomial-time under them?

In this paper, we investigate both these questions for the exchange model. We
show that answering the first question is strongly NP-hard, even in the CEEI
setting. Further, we derive a simple sufficient condition for the existence,
and for them, we show that finding a competitive division is PPAD-hard. These
results are in sharp contrast to the case of goods where both problems are
strongly polynomial-time solvable.111While dividing goods, the analogous
question is to not allocate a good to any agent who likes it very little. It
can be achieved by setting all the utility values less than or equal to the
threshold $\tau$ to zero. We can check existence as well as compute
equilibrium in strongly polynomial time [Gal76, DGV16, GV19]. To the best of
our knowledge, these are the first hardness results for the chore division
problem, and, in fact, for any economic model under _linear_ preferences.

###  1.1 Model and Notation

In this section, we introduce the most general problem of _Chore Division_ and
then certain special variants of it. In an instance of chore division, we have
a set $A=\langle a_{1},a_{2},\dots,a_{n}\rangle$ of agents and a set
$B=\langle b_{1},b_{2},\dots,b_{m}\rangle$ of _divisible_ chores. Each agent
$a_{i}$ has some initial endowment of chores. Let $w(a_{i},b_{j})$ denote
$a_{i}$’s endowment of chore $b_{j}$. Intuitively, agent $a_{i}$ wants
$w(a_{i},b_{j})$ units of chores to be done (by herself or other agents in the
instance). Also, each agent $a_{i}$ has a linear disutility function that
captures the amount of disutility she has for all possible chores that can be
allocated to her: $\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{ij}$, where
$d(a_{i},b_{j})$ denote the $a_{i}$’s disutility for one unit of chore $b_{j}$
and $X_{ij}$ denote the amount of chore $b_{j}$ that agent $a_{i}$ does. For
convenience, we also refer to the disutility function $d(\cdot,\cdot)$ and the
endowment function $w(\cdot,\cdot)$ as the disutility matrix and endowment
matrix respectively.

Given price vector $p=\langle
p(b_{1}),p(b_{2}),\dots,p(b_{m})\rangle\in\mathbb{R}^{m}_{\geq 0}$, where
$p(b_{j})$ denotes the price of chore $b_{j}$ (the amount of money that any
agent doing one unit of the chore will be paid), agent $a_{i}$ needs to earn
($\sum_{j\in[m]}w(a_{i},b_{j})\cdot p(b_{j})$) in order to pay to get her own
chores done. She can earn this amount by doing other chores, while minimizing
her disutility – this defines her optimal bundle (or optimal chore set).

  * •

Optimal bundle. For agent $a_{i}\in A$, $\langle
X_{i1},X_{i2},\dots,X_{im}\rangle$ is her optimal bundle if it minimizes
$\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{ij}$ subject to the constraint
$\sum_{j\in[m]}X_{ij}\cdot p(b_{j})\geq\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})$.

It is easy to see that in her optimal bundle agent $a_{i}$ gets assigned only
those chores that minimizes her disutility per dollar (buck) earned. Formally,

$\forall j\in[m],\ \ X_{ij}>0\ \ \Rightarrow\ \
\tfrac{d(a_{i},b_{j})}{p(b_{j})}\leq\tfrac{d(a_{i},b_{j^{\prime}})}{p(b_{j^{\prime}})}\
\ \forall j^{\prime}\in[m].$

Price vector $p$ is said to be at competitive equilibrium (CE) if all chores
are completely assigned when every agent gets her optimal bundle, i.e.,
$\sum_{i\in[n]}X_{ij}=\sum_{i\in[n]}w(a_{i},b_{j}),\ \forall j\in[m]$. Our
focus in this paper is on efficient competitive equilibrium where no agent is
assigned a chore for which her disutility is greater than or equal to a
threshold $\tau$. Formally, this problem can be defined as follows:

######  Problem 1.

(Chore Division)

Given: A set $A=\langle a_{1},a_{2},\dots,a_{n}\rangle$ of agents, set
$B=\langle b_{1},b_{2},\dots,b_{m}\rangle$ of bads/chores, disutility function
$d:A\times B\rightarrow(0,\infty)$, an endowment function $w:A\times
B\rightarrow\mathbb{R}_{\geq 0}$, and a threshold $\tau$.
Find: Price vector $p=\langle
p(b_{1}),p(b_{2}),\dots,p(b_{m})\rangle\in\mathbb{R}^{m}_{\geq 0}$ and
allocation $X\in\mathbb{R}^{n\times m}_{\geq 0}$ are such that,

  1. 1.

$X_{ij}>0$ only if $d(a_{i},b_{j})<\tau$ and
$\tfrac{d(a_{i},b_{j})}{p(b_{j})}\leq\tfrac{d(a_{i},b_{j^{\prime}})}{p(b_{j^{\prime}})}$
for all $j^{\prime}\in[m]$,

  2. 2.

$\sum_{j\in[m]}X_{ij}\cdot p(b_{j})=\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})$ for all $i\in[n]$, and

  3. 3.

$\sum_{i\in[n]}X_{ij}=\sum_{i\in[n]}w(a_{i},b_{j})$ for all $j\in[m]$.

A _competitive equilibrium_ is a tuple $\langle p,X\rangle$ satisfying the
above constraints.

Observe that the equilibrium prices are scale invariant: if $p$ is an
equilibrium price vector then so is $\alpha\cdot p$ for any positive scalar
$\alpha$. Furthermore, at equilibrium $p(b_{j})>0$ for each chore $j$,
otherwise no agent would be willing to do it.

Approximate Competitive Equilibrium. For an $\epsilon>0$, a
$(1-\epsilon)$-competitive equilibrium is the tuple $\langle p,X\rangle$ that
satisfy the first two conditions above, and the third condition approximately:

$(1-\epsilon)\cdot\sum_{i\in[n]}w(a_{i},b_{j})\leq\sum_{i\in[n]}X_{ij}\leq\frac{1}{(1-\epsilon)}\sum_{i\in[n]}w(a_{i},b_{j})\mbox{
for all }j\in[m].$

A competitive equilibrium $\langle p,X\rangle$ has many desirable properties
like envy-freeness and Pareto optimality in the chore division with equal
earnings [BMSY17]. We briefly mention the similar properties that a
competitive equilibrium satisfies in the context of the more general problem
of chore division.

  * •

_Weighted envy freeness:_ An allocation $X$ is said to be _envy free_ is for
every pair of agents $i$ and $i^{\prime}$, agent $i$’s disutility for her own
bundle $\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{ij}$ is not higher than her
disutility for $a_{i^{\prime}}$’s bundle: $\sum_{j\in[m]}d(a_{i},b_{j})\cdot
X_{i^{\prime}j}$:

$\displaystyle\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{ij}$
$\displaystyle\leq\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{i^{\prime}j}\enspace.$

Weighted envy freeness is a generalized notion of envy freeness. For any two
agents $a_{i}$ and $a_{i^{\prime}}$, we have that agent $a_{i}$’s disutility
for its own bundle $\langle X_{i1},\dots,X_{im}\rangle$, scaled down by the
cost of the chores in her initial endowment is at most as high as her
disutility for $a_{i^{\prime}}$’s optimal bundle $\langle
X_{i^{\prime}1},\dots,X_{i^{\prime}m}\rangle$ scaled down by the cost of the
chores in $a_{i^{\prime}}$’s initial endowment:

$\displaystyle\frac{\sum_{j\in[m]}d(a_{i},b_{j})\cdot
X_{ij}}{\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(j)}\leq\frac{\sum_{j\in[m]}d(a_{i},b_{j})\cdot
X_{i^{\prime}j}}{\sum_{j\in[m]}w(a_{i^{\prime}},b_{j})\cdot p(j)}\enspace.$

Intuitively, a “fair share of disutility” of any agent is the total cost of
chores she brings (her total initial endowment): higher the cost of the chores
she brings, larger is her share of disutility. A competitive equilibrium
ensures that every agent $a_{i}$ feels that she receives her fair share of
disutility compared to all other agents.

  * •

_Pareto optimality:_ There is no other allocation $Y\in\mathbb{R}^{n\times
m}_{\geq 0}$ such that disutility of all the agents is at most as high as in
$X$ and at least one agent has strictly less disutility in $Y$, i.e.,
$\sum_{j\in[m]}d(a_{i},b_{j})\cdot Y_{ij}\leq\sum_{j\in[m]}d(a_{i},b_{j})\cdot
X_{ij}$ for all $i\in[n]$ with at least one strict inequality.

Analogous to the notion of Fisher model in the scenario where we divide only
goods (see [BS05]), we define the notion of _Chore Division with Fixed
Earnings_ , where every agent has to earn a fixed amount of money by doing
chores with minimum disutility to price ratio. While in the chore division
(Definition 1), the amount an agent needs to earn depends on the prices of
chores she owns. It is without loss of generality to assume that one unit of
each chore has to be done by scaling the disutility values appropriately.

######  Problem 2.

(Chore Division with Fixed Earnings)

Given: A set $A=\langle a_{1},a_{2},\dots,a_{n}\rangle$ of agents, set
$B=\langle b_{1},b_{2},\dots,b_{m}\rangle$ of bads/chores, disutility function
$d:A\times B\rightarrow(0,\infty)$, and an earning function
$e:A\rightarrow\mathbb{R}_{\geq 0}$, and a threshold $\tau>0$.
Find: Price vector $p=\langle
p(b_{1}),p(b_{2}),\dots,p(b_{m})\rangle\in\mathbb{R}^{m}_{\geq 0}$ and
allocation $X\in\mathbb{R}^{n\times m}_{\geq 0}$ such that,

  1. 1.

$X_{ij}>0$ only if $d(a_{i},b_{j})<\tau$ and
$\tfrac{d(a_{i},b_{j})}{p(b_{j})}\leq\tfrac{d(a_{i},b_{j^{\prime}})}{p(b_{j^{\prime}})}$
for all $j^{\prime}\in[m]$,

  2. 2.

$\sum_{j\in[m]}X_{ij}\cdot p(b_{j})=e(a_{i})$ for all $i\in[n]$, and

  3. 3.

$\sum_{i\in[n]}X_{ij}=1$ for all $j\in[m]$.

Tuple $\langle p,X\rangle$ satisfying the above is a competitive equilibrium.

Analogously a $(1-\epsilon)$-CE satisfies (1), (2) as is, and (3)
approximately.

Observe that Problem 2 can be modeled as a special case of Problem 1. Given an
instance $I=\langle A,B,d(\cdot,\cdot),e(\cdot)\rangle$ of Problem 2, we can
construct an instance $I^{\prime}=\langle
A,B,d(\cdot,\cdot),w(\cdot,\cdot)\rangle$ of Problem 1 such that
$w(a_{i},b_{j})=e(a_{i})$ for all $b_{j}\in B$. Since the equilibrium price
vector $p=\langle p(b_{1}),p(b_{2}),\dots,p(b_{m})\rangle$ is scale-invariant,
we can assume without loss of generality that $\sum_{j\in[m]}p(b_{j})$ $=1$.
One can verify now that at every competitive equilibrium of $I^{\prime}$ we
have $\sum_{j\in[m]}X_{ij}\cdot p(b_{j})=\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})=e(a_{i})\cdot\sum_{j\in[m]}p(b_{j})=e(a_{i})$ for all $i\in[n]$.
Since all the other conditions that need to be satisfied by the equilibrium
price vector at $I^{\prime}$ and $I$ are identical, we have that every
competitive equilibrium in $I^{\prime}$ is also a competitive equilibrium in
$I$. _Therefore all the hardness results that apply for chore division with
fixed earnings (Problem 2), will automatically apply to chore division
(Problem 1) as well._

Chore Division with Equal Earnings. A special case of Problem 2 (and
consequently Problem 1) is the _Chore Division with Equal Earnings_ where we
have $e(a_{i})=1$ for all $i\in[n]$. Analogous notions to chore division with
equal earnings, in the context of goods is _Competitive Equilibrium with Equal
Incomes_ (CEEI) [Var74]. CEEI has been extensively studied in the scenario of
dividing goods in the fair division community.

###  1.2 Technical Overview

In this section, we sketch the main techniques and ideas used to prove our
results in later sections.

####  1.2.1 NP-Hardness of Checking Existence

We first show that there are very simple instances in chore division that does
not admit a competitive equilibrium.

Example 1.  Consider a scenario with two agents $a_{1}$ and $a_{2}$, and two
chores $b_{1}$ and $b_{2}$. We have $w(a_{i},b_{j})=1$ for all $i,j\in[2]$,
and $d(a_{1},b_{1})=d(a_{2},b_{1})=1$, $d(a_{1},b_{2})=\tau\gg 2$ and
$d(a_{2},b_{2})=2$. Let $p(b_{1})$ and $p(b_{2})$ be the prices of the chores
at a competitive equilibrium. Observe that since $d(a_{1},b_{2})=\tau$,
$a_{1}$ earns her entire money from $b_{1}$. Therefore, $2\cdot p(b_{1})\geq
p(b_{1})+p(b_{2})$, implying that $p(b_{1})\geq p(b_{2})$. In that case,
observe that the disutility to price ratio of $b_{1}$ is strictly less than
that of $b_{2}$ for $a_{2}$:
$\tfrac{d(a_{2},b_{1})}{p(b_{1})}=\tfrac{1}{p(b_{1})}<\tfrac{2}{p(b_{1})}\leq\tfrac{2}{p(b_{2})}=\tfrac{d(a_{2},b_{2})}{p(b_{2})}$.
Thus, none of the agents is willing to do chore $b_{2}$, and therefore it
remains unassigned, a contradiction.

Observe that this example is an instance of chore division with equal
earnings. It is a natural question to ask whether an instance admits a
competitive equilibrium. In the analogous context of dividing goods (linear
exchange model), there exists polynomial-time verifiable necessary and
sufficient conditions [DGV16] for an instance to admit a competitive
equilibrium. However, this seems not the case for chore division and
surprisingly this problem turns out to be intractable. To this end, we show
the first result of our paper,

######  Theorem 3.

Determining whether an instance of chore division with fixed earnings admits a
competitive equilibrium is strongly NP-hard.

In fact, we can also show the same hardness for finding an
$(\tfrac{11}{12}+\delta)$-competitive equilibrium for any $\delta>0$ for chore
division with equal earnings too (all the details of the reduction are
presented in Section 2).

####  1.2.2 Instances that Admit a Competitive Equilibrium

##### Sufficiency Conditions.

The hard instances constructed to prove Theorem 3 have similar structure in
disutility matrix as Example 1.2.1. In particular, the non-existence is
primarily attributed to the fact that there is a classification of the agents
into two groups: _rigid_ and _flexible_. The rigid agents have small
disutility towards some chores (let us call them _easy_ chores) and have
disutility of $\tau$ for some chores (we call them _hard_ chores) while the
_flexible_ agents have small disutility towards the easy chores and high (but
still $<\tau$) disutility towards the hard chores. Since the flexible agents
need to do the hard chores entirely, it may not be possible to have a
competitive equilibrium, as the prices of the hard chores need to be high (for
them to have small disutility to price ratio) and sometimes it may be higher
than the stipulated/fixed earning222the sum of prices of the chores owned by
flexible agents in the case of Chore Division (Problem 1).of the flexible
agents. Therefore, we look into instances that do not have such a structure in
the disutility matrix; in particular let us define the _disutility graph_ of
an instance as the bipartite graph $D=(A\cup B,E_{D})$ containing the agents
$A$ as one vertex set and the chores $B$ as the other, and there exists an
edge from agent $a\in A$ to chore $b\in B$ if and only if $d(a,b)<\tau$. Our
first sufficiency condition is that,

Condition 1: $D$ is a disjoint union of complete bipartite graphs
$D_{1},D_{2},\dots,D_{d}$, for some $d\geq 1$.

Observe that if an instance satisfies Condition 1, then there exists no global
partitioning of the agents into groups of rigid and flexible agents: for every
pair of agents, the set of chores towards which they have a disutility of less
than $\tau$ is either identical or disjoint. We remark that this itself is a
sufficient condition to guarantee the existence of competitive equilibrium in
the context of chore division with fixed earnings (Problem 2): We break the
instance into $[d]$ sub-instances formed by the agents $A_{i}$ and the chores
$B_{i}$ for all $i\in[d]$. Note that in any competitive equilibria agents in
$A_{i}$ will not earn any money from the chores in $B_{i^{\prime}}$ for all
$i\neq i^{\prime}$. Therefore, it suffices to show that there exists
competitive equilibria in each sub instance formed by $A_{i}$ and $B_{i}$ for
all $i\in[d]$. Bogomolnaia et al. [BMSY17] show that a competitive equilibria
always exists in chore division with fixed earnings if the disutility graph of
the instance is a complete bipartite graph. Unfortunately, this condition
alone is not sufficient to guarantee the existence of a competitive
equilibrium in the context of general chore division (Problem 1). Consider the
following simple example:

Example 2.  We have two agents $a_{1}$ and $a_{2}$ and two chores $b_{1}$ and
$b_{2}$. Let us assume $w({a_{1},b_{1}})=1$, $w({a_{1},b_{2}})=\tfrac{1}{2}$,
$w({a_{2},b_{1}})=0$, and $w({a_{2},b_{2}})=\tfrac{1}{2}$. Also, suppose
$d(a_{1},b_{1})=d(a_{2},b_{2})=1$ and $d(a_{1},b_{2})=d(a_{2},b_{1})=\tau$.
Note that the disutility graph $D$ is the union of two disjoint complete
bipartite graphs, namely
$D_{1}=(\left\\{a_{1}\right\\}\cup\left\\{b_{1}\right\\},\left\\{(a_{1},b_{1})\right\\})$
and
$D_{2}(\left\\{a_{2}\right\\}\cup\left\\{b_{2}\right\\},\left\\{(a_{2},b_{2})\right\\})$.
However, we do not have any competitive equilibrium as the earning of $a_{2}$
will be half of the price of $b_{2}$ and thus $a_{2}$ can never do more than
half of the chore $b_{2}$. Also, $a_{1}$ will not do any of chore $b_{2}$ as
she has disutility of $\tau$ for the same. Therefore, $b_{2}$ can not be fully
assigned.

Thus, we need more conditions to guarantee the existence of a competitive
equilibrium. To this end, we define the _exchange graph_ of an instance as a
graph $W=([d],E_{W})$. We have $(i,j)\in E_{W}$ if and only if for every chore
$b$ in the component $D_{j}$ of the disutility matrix, there is an agent $a\in
D_{i}$ such that $w({a,b})>0$ 333Intuitively, agents in the component $D_{j}$
are willing to do chores brought by the agents in $D_{i}$.. We now propose our
second sufficiency condition.

Condition 2: $W$ is strongly connected.

With this, we state the second main result of our paper.

######  Theorem 4.

All instances of chore division that satisfy Conditions 1 and 2, admit a
competitive equilibrium.

##### Existence under Sufficiency Conditions.

We now briefly sketch the ideas behind our proof of existence (Theorem 4) and
also highlight some crucial barriers that we overcome. Like most equilibrium
existence results [Nas51, AD54], our proof uses a fixed-point theorem. Given a
function or a correspondence $\phi$ from $D$ to $D$, a fixed-point theorem
ensures existence of $x\in D$ such that $f(x)=x$ or $x\in f(x)$ respectively,
if $\phi$ satisfies continuity-like properties, and $D$ is convex and compact
[Bro11, Kak41].

The known existence proofs in the context of dividing goods, say
$g_{1},\dots,g_{m}$, defines fixed-point formulations that operate on a
simplex as the domain for price vectors [AD54, Max97]. That is
$\Delta_{n}=\\{p\ |\ p(g_{j})\geq 0$ for all $j\in[m]$, and
$\sum_{j\in[m]}p(g_{j})=1\\}$. Given prices, it computes optimal bundles of
agents and adjust prices based on excess demand, i.e., demand minus supply.

This approach immediately fails for the chore division problem due to the
issue of infeasible optimal bundle under this price domain. Here is why:
Recall at prices $p$, an optimal bundle of agent $a_{i}$ minimizes her
disutility $\sum_{j\in[m]}d(a_{i},b_{j})\cdot X_{ij}$ subject to

  * $(a)$

she earns at least the payment she needs to make for her endowment, i.e.,
$\sum_{j\in[m]}X_{ij}\cdot p(b_{j})\geq\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})$, and

  * $(b)$

$X_{ij}>0$ only if $d(a_{i},b_{j})<\tau$.

Consider a price vector $p\in\Delta_{n}$ such that for a particular component
$D_{k}=(A_{k}\cup B_{k},E_{k})$ in the disutility graph we have the price of
every chore in $B_{k}$ to be zero. And, there is an agent $a_{i}\in A_{k}$
such that $\sum_{j\in[m]}w(a_{i},b_{j})\cdot p(b_{j})>0$. Note that the
optimal bundle set for $a_{i}$ is empty here since under condition $(b)$
above, condition $(a)$ becomes infeasible. That is, all the chores where
$a_{i}$ has a disutility of less than $\tau$ have zero prices and thus $a_{i}$
will never be able to earn enough money to match
$\sum_{j\in[m]}w(a_{i},b_{j})\cdot p(b_{j})$. This issue does not arise in the
goods only case because there condition $(a)$ becomes “agent spends only as
much as she earns from her endowment” which essentially puts an upper bound on
her spending reversing the inequality, and then all $X_{ij}$’s being $0$ is
always feasible.

_In order to avoid the issue of “zero prices”, we add more constraints to
domain of the price vectors_. The domain of our fixed-point formulation is
defined by the price vectors $p=\langle p(b_{1}),\dots,p(b_{m})\rangle$ (where
each $p(b_{j})$ is the price of the chore $b_{j}$) and allocations $X=\langle
X_{11},X_{12},\dots,X_{nm}\rangle$ (where each $X_{ij}\geq 0$ indicates the
consumption of chore $b_{j}$ by agent $a_{i}$) such that,

  * •

$p(b_{j})\geq 0$ for all $j\in[m]$, and $\sum_{j\in[m]}p(b_{j})=1$, and

  * •

$\sum_{a_{i}\in A_{k}}\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})=\sum_{b_{j}\in B_{k}}p(b_{j})$ for each connected component
$D_{k}=(A_{k}\cup B_{k},E_{k})$ of the disutility graph, and

  * •

for all $i,j$, we have $0\leq X_{ij}\leq M$ for some sufficiently large $M$.

Let $P$ denote the set of all prices and $\mathbf{X}$ denote the set of all
allocations that satisfy the above conditions. First observe that for any
$p\in P$ we cannot have all prices of a component $D_{k}$ of the disutility
graph to be zero: Without loss of generality, let us assume that the sum of
prices of the chores in the components $D_{k}$ for all $k\in[\ell]$ are zero
and the sum of prices of the chores in all other components ($D_{k}$ for all
$k\in[d]\setminus[\ell]$) are non-zero. Note that since
$\sum_{j\in[m]}p(b_{j})=1$, there is at least one component where the sum of
prices of the chores is non-zero and thus $[d]\setminus[\ell]\neq\emptyset$.
Also, note that for all $k\in[\ell]$ we have $\sum_{a_{i}\in
A_{k}}\sum_{j\in[m]}w(a_{i},b_{j})\cdot p(b_{j})=\sum_{b_{j}\in
B_{k}}p(b_{j})=0$ (by the third constraint in the definition of $P$). Since
our instance satisfies Condition 2, we have that there exists an edge in the
exchange graph $W=([d],E_{W})$ from a $k\in[\ell]$ to a
$k^{\prime}\in[d]\setminus[\ell]$. This implies that for each chore in
$D_{k^{\prime}}$ (in particular for the chore with a non-zero price), there
exists an agent in $D_{k}$ with some positive endowment of that chore, further
implying that $\sum_{a_{i}\in A_{k}}\sum_{j\in[m]}w(a_{i},b_{j})\cdot
p(b_{j})>0$, which is a contradiction. Therefore, we cannot have all the
prices of any component $D_{k}$ in the disutility graph to be zero. This
resolves the issue of “zero prices” and thereby ensures feasibility of the
optimal bundle sets (Lemma 21). Now the crucial task is to define a
“continuous” map that maintains the extra conditions on the price space.

Let $S=\cup_{p\in P}\cup_{X\in\mathbf{X}}\langle p,X\rangle$. In order to
capture competitive equilibria at fixed-points we define a _correspondence_
$\phi:S\rightarrow 2^{S}$ that satisfies the following properties: it maps any
$\langle p,X\rangle$ to all $\langle q,X^{p}\rangle$ where,

  * •

the price vector $q$ is such that $q\in P$ and for all components
$D_{k}=(A_{k}\cup B_{k},E_{k})$ of the disutility graph, we have

$\displaystyle\frac{q(b_{j})}{q(b_{j^{\prime}})}$
$\displaystyle=\frac{p(b_{j})+\mathit{max}(\sum_{i\in[n]}w(a_{i},b_{j})-\sum_{i\in[n]}X_{ij},0)}{p(b_{j^{\prime}})+\mathit{max}(\sum_{i\in[n]}w(a_{i},b_{j^{\prime}})-\sum_{i\in[n]}X_{ij^{\prime}},0)},$
(1)

for all chores $b_{j}$ and $b_{j^{\prime}}$ in $B_{k}$.

  * •

$X^{p}\in\mathbf{X}$ is an optimal bundle set at the prices $p$: For every
agent $a_{i}$, we have $\langle X^{p}_{i1},\dots,X^{p}_{im}\rangle$ to be the
optimal demand bundle for $a_{i}$ at prices $p$, if and only if, $\langle
X^{p}_{i1},\dots,X^{p}_{im}\rangle$ minimizes the total disutility
$\sum_{j\in[m]}d(a_{i},b_{j})\cdot X^{p}_{i,j}$ of agent $a_{i}$ subject to

    * –

$X^{p}_{ij}>0$ only if $d(a_{i},b_{j})<\tau$, and

    * –

the earning constraint $\sum_{j\in[m]}X^{p}_{ij}\cdot
p(b_{j})\geq\sum_{j\in[m]}w(a_{i},b_{j})\cdot p(b_{j})$.

At the first glance, it may not even be clear that why such a correspondence
can be defined: In particular, finding the price vector $q$ that satisfies the
properties as mentioned above. However, we do manage to construct such a
correspondence $\phi$ and show that it has at least one fixed-point in Section
3. Before we sketch the construction, let us first discuss how the above
properties are important to show that the fixed-points of $\phi$ correspond to
competitive equilibrium.

Consider any fixed point of $\phi$, i.e., $\langle p,X\rangle$ such that
$\langle p,X\rangle\in\phi(\langle p,X\rangle)$. Let $r_{j}(X)$ denote the
amount of chore $b_{j}$ left undone under $X$, i.e.,
$r_{j}(X)=\mathit{max}(\sum_{i\in[n]}w(a_{i},b_{j})-\sum_{i\in[n]}X_{ij},0)$.
We have $q=p$ and $X^{p}=X$, where $q$ and $X^{p}$ are constructed from $p$
and $X$ as above. Thus, every agent earns her money from the chores in her
optimal bundle (as $X=X^{p}$) and if $X^{p}$ is not a competitive equilibrium,
then the only reason is because some chore $b_{j}$ is not completed, i.e.,
$r_{j}(X)>0$. This also implies that there is some chore $b_{j^{\prime}}$ that
is overdone
($\sum_{i\in[n]}w(a_{i},b_{j^{\prime}})-\sum_{i\in[n]}X_{ij^{\prime}}<0$,
implying $r_{j^{\prime}}(X)=0$), as the total earning of the agents is at
least the total prices of the chores (by the definition of $\mathbf{X}^{p}$).
Therefore, we have
$\tfrac{q(b_{j})}{q(b_{j^{\prime}})}=\tfrac{p(b_{j})+r_{j}(X)}{p(b_{j^{\prime}})+r_{j^{\prime}}(X)}>\tfrac{p(b_{j})}{p(b_{j^{\prime}})+r_{j^{\prime}}(X)}=\tfrac{p(b_{j})}{p(b_{j^{\prime}})}$,
implying that $q\neq p$, which is a contradiction.

Now, the main challenge (and also the main bulk of our effort) is to show that
such a correspondence $\phi$ can be defined. That is, to get the price vector
$q\in\mathbb{R}^{m}_{\geq 0}$ that satisfy the ratio property as outlined in
(1), and all the constraints that define the price space $P$, especially the
constraint that for every component $D_{k}$ in the disutility graph, the total
price of chores owned by the agents in $A_{k}$ equals the total price of the
chores in $B_{k}$. For this, we first compute $q^{\prime}(b_{j})$’s that
satisfy the ratio property, but may not be in price space $P$. Then, for each
component taking its total price as a variable, we define parameterized $q$
from $q^{\prime}$ that preserves price ratios of $q^{\prime}$. Now the goal is
to find values of the variables once we replace them in $q$ we get $q\in P$.
In other words, $q$ satisfy all the component-wise price constraints of domain
$P$.

This condition essentially gives a linear system of equations. Let
$M\in\mathbb{R}^{d\times d}$ denote the matrix of this linear system. Then,
our goal becomes to find a non-negative vector $v\in\mathbb{R}^{d}$ in the
null space of $M$. It is not obvious why such a vector should exist. Our high-
level approach to show the same is as follows: We can equivalently express the
linear system of equations $M\cdot v=0$ as $M^{\prime}\cdot v=v$, where
$M^{\prime}=M+I$, where $I$ is the identity matrix. We show that if we define
a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ as
$f(v)=M^{\prime}\cdot v$, then $f$ maps the $d$-dimensional simplex
$\Delta_{d}$ to itself. Restricting $f$ to only the simplex, we get a
continuous map $f:\Delta_{d}\rightarrow\Delta_{d}$ and therefore it has a
fixed-point by the Brouwer’s fixed-point theorem. At every fixed-point $v$ we
have $M^{\prime}\cdot v=v$ implying $M\cdot v=0$. Since $v\in\Delta_{d}$, we
get the vector we needed.

Finally, to apply the Kakutani’s fixed point theorem, we need to show that our
correspondence has a closed graph (analogous to continuity for a function) and
$\phi(\langle p,X\rangle)$ is non-empty and convex. Since defining the
correspondence involves multiple steps, this does not follow trivially. Once
we prove this in Lemma 33 in Section 3, we get the existence of a fixed-point
of $\phi$, and thereby the existence of a competitive equilibrium. We refer
the reader to Section 3 for a detailed formal discussion.

####  1.2.3 Hardness of Determining Equilibrium under Sufficiency Conditions

Recall from Section 1.2.2 that the NP-hardness of Chore division crucially
uses the structure of rigid and flexible agents. However, this structure in
the disutility matrix is completely removed if we concentrate on instances
satisfying Conditions 1 and 2, mentioned in Section 1.2.2. We show that even
under these sufficiency conditions, chore division is still intractable. We
now mention our third main technical result:

######  Theorem 5.

Chore division, restricted to all instances that satisfy Conditions 1 and 2,
is PPAD-hard.

We show the PPAD-hardness by reduction from normalized polymatrix game
(defined below), which is known to be PPAD-hard [CPY17].

######  Problem 6.

(Normalized Polymatrix Game) [CPY17]
Given: A $2n\times 2n$ rational matrix $\mathbf{M}$ with every entry in
$[0,1]$ and $\mathbf{M}_{i,2j-1}+\mathbf{M}_{i,2j}=1$ for all $i\in[2n]$ and
$j\in[n]$ .
Find: Equilibrium strategy vector $x\in\mathbb{R}^{2n}_{\geq 0}$ such that
$x_{2i-1}+x_{2i}=1$ and

$\displaystyle
x^{T}\cdot\mathbf{M}_{*,{2i-1}}>x^{T}\cdot\mathbf{M}_{*,2i}+\tfrac{1}{n}\implies
x_{2i}=0.$ $\displaystyle
x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}\implies
x_{2i-1}=0.$

where $M_{*,k}$ represents the $k^{\mathit{th}}$ column of the matrix
$\mathbf{M}$.

Given an instance $I=\langle\mathbf{M}\rangle$ of the polymatrix game, we will
now create an instance of chore division $E(I)=\langle A\cup
B,d(\cdot,\cdot),w(\cdot,\cdot)\rangle$ such that given any competitive
equilibrium in $E(I)$, we can determine in polynomial time, an equilibrium
strategy vector $x$ for $I$. We note that our reduction can be extended to
work even in the restricted setting of
$(1-\tfrac{1}{\textup{poly}(n)})$-competitive equilibria. However, for
simplicity we stick to the exact competitive equilibria in our reduction.
Next, we give a brief sketch of the proof, while the formal proof with all the
details is in Section 4.

##### Sketch of the Reduction.

The key properties that our hard instance $E(I)$ exhibit are _pairwise equal
endowments_ , _fixed earning_ , _price equality_ , _price regulation_ and
_reverse ratio amplification_ (we will give a precise definition of these
properties shortly). These techniques (constructing hard instances exhibiting
these properties) have been used earlier to prove PPAD-hardness for the
exchange model with only goods when agents have constant elasticity of
substitution (CES) utilities [CPY17] and even for the Fisher model when agents
have separable piecewise linear concave (SPLC) utilities [CT09]. _However, in
the context of chore division, we are able to obtain these gadgets (in
particular the reverse ratio-amplification gadget) even when agents have
linear disutility functions (dividing goods when agents have linear utility
functions is tractable)_.

We now give a brief overview of the reduction: Let us consider two sets of
chores, namely $B_{1}=\left\\{b^{1}_{1},b^{1}_{2},\dots,b^{1}_{2n}\right\\}$
and $B_{2}=\left\\{b^{2}_{1},b^{2}_{2},\dots,b^{2}_{2n}\right\\}$. For all
$i,j\in[2n]$ we define agents $a_{i,j}$ such that agent $a_{i,j}$ brings
$\mathbf{M}_{i,j}$ units of chore $b^{2}_{i}$. The disutilities are as
follows:

$\displaystyle d(a_{i,2j-1},b^{1}_{2j-1})$ $\displaystyle=(1-\alpha)$ and
$\displaystyle d(a_{i,2j-1},b^{1}_{2j})$ $\displaystyle=(1+\alpha)$
$\displaystyle d(a_{i,2j},b^{1}_{2j-1})$ $\displaystyle=(1+\alpha)$ and
$\displaystyle d(a_{i,2j},b^{1}_{2j})$ $\displaystyle=(1-\alpha),$

for some infinitesimally small $\alpha>0$. Agents $a_{i,2j-1}$ and $a_{i,2j}$
have disutility more than $\tau$ for all other chores. Our instance also has
agents $a^{\prime}_{1},a^{\prime}_{2},\dots a^{\prime}_{2n}$ such that for
each $i\in[2n]$, we have,

$\displaystyle d(a^{\prime}_{2i-1},b^{1}_{2i-1})$ $\displaystyle=(1-\alpha)$
and $\displaystyle d(a^{\prime}_{2i-1},b^{1}_{2i})$ $\displaystyle=(1+\alpha)$
$\displaystyle d(a^{\prime}_{2i},b^{1}_{2i-1})$ $\displaystyle=(1+\alpha)$ and
$\displaystyle d(a^{\prime}_{2i},b^{1}_{2i})$ $\displaystyle=(1-\alpha).$

Our instance $E(I)$ of chore division has additional agents and chores to
ensure the following five crucial properties at equilibrium, however, none of
the other agents in $E(I)$ have disutility less than $\tau$ towards the chores
in $B_{1}$.

  * •

_Pairwise equal endowments:_ In $E(I)$, the total endowment of chore
$b^{k}_{2i-1}$ equals the total endowment of chore $b^{k}_{2i}$ for all
$k\in[2]$. Also the total endowments of each chore is $\mathcal{O}(n)$.

  * •

_Fixed earning:_ In any competitive equilibrium, for each $i\in[2n]$, we have
the total earning of agent $a^{\prime}_{i}$ is
$(1-\beta)\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,i})$.

  * •

_Price equality:_ In any competitive equilibrium, the sum of prices of chores
$b^{k}_{2i-1}$ and $b^{k}_{2i}$ is the same for all $i\in[n]$ and $k\in[2]$.
Since the prices of chores at a competitive equilibrium is scale invariant, we
can assume further, without loss of generality, that for all $i\in[n]$, we
have $p(b^{1}_{2i-1})+p(b^{1}_{2i})=p(b^{2}_{2i-1})+p(b^{2}_{2i})=2$.

  * •

_Price regulation:_ In any competitive equilibrium, for all $i\in[2n]$ we have

$\displaystyle\frac{1-\alpha}{1+\alpha}\leq\frac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}\leq\frac{1+\alpha}{1-\alpha}$
and
$\displaystyle\frac{1-\beta}{1+\beta}\leq\frac{p(b^{2}_{2i-1})}{p(b^{2}_{2i})}\leq\frac{1+\beta}{1-\beta},$

for some infinitesimally small $\beta\gg{n^{2}\cdot\alpha}$.

  * •

_Reverse ratio amplification:_ In any competitive equilibrium, for all
$i\in[2n]$, if
$\tfrac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\tfrac{1+\alpha}{1-\alpha}$, then we
have $\tfrac{p(b^{2}_{2i-1})}{p(b^{2}_{2i})}=\tfrac{1-\beta}{1+\beta}$ and
similarly when
$\tfrac{p(b^{1}_{2i-1})}{p(b^{1}_{2i})}=\tfrac{1-\alpha}{1+\alpha}$, then we
have $\tfrac{p(b^{2}_{2i-1})}{p(b^{2}_{2i})}=\tfrac{1+\beta}{1-\beta}$.

Our instance $E(I)$ satisfies both Conditions 1 and 2 of Section 3. As a
result, it admits a competitive equilibrium. Given that a competitive
equilibrium has to satisfy the above properties, we now show how we can use
prices at the competitive equilibrium to obtain a Nash equilibrium strategy
vector for the polymatrix game in polynomial time. Given a competitive
equilibrium price vector $p$, construct vector $x$ as follows.

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

We will now show that $x$ is the desired Nash equilibrium strategy vector for
instance $I$ of the polymatrix game, i.e., it satisfies conditions of Problem
6. To this end, first observe that since our instance satisfies price equality
we have that $p(b^{2}_{2i-1})+p(b^{2}_{2i})=2$ for all $i\in[n]$. Again, since
our instance satisfies price regulation, we also have for all $i\in[n]$,
$\tfrac{1-\beta}{1+\beta}\leq\tfrac{p(b^{2}_{2i-1})}{p(b^{2}_{2i})}\leq\tfrac{1+\beta}{1-\beta}$,
implying that $p(b^{k}_{i})\geq 1-\beta$ for all $i\in[2n]$. Therefore,
$x_{i}\geq 0$ for all $i\in[2n]$.

Also note that we have
$x_{2i-1}+x_{2i}=\tfrac{p(b^{2}_{2i-1})+p(b^{2}_{2i})-2(1-\beta)}{2\cdot\beta}=\tfrac{2\beta}{2\beta}=1$
(by the price equality property we have $p(b^{2}_{2i-1})+p(b^{2}_{2i})=2$) for
all $i\in[n]$. Now, we 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 symmetric condition is similar. Let us
assume that
$x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}$.
Observe that the agents that have a disutility of $(1-\alpha)$ towards chore
$b^{1}_{2i}$ are $\left\\{\cup_{j\in[2n]}a_{j,2i}\right\\}\cup
a^{\prime}_{2i}$, and that their total earning is

$\displaystyle=\sum_{j\in[2n]}\mathbf{M}_{j,2i}\cdot
p(b^{2}_{j})+(1-\beta)\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})$ (fixed
earning) $\displaystyle=\sum_{j\in[2n]}\mathbf{M}_{j,2i}\cdot(2\beta\cdot
x_{j}+(1-\beta))+(1-\beta)\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})$
(substituting $p(b^{2}_{j})$) $\displaystyle=\sum_{j\in[2n]}2\beta\cdot
x_{j}\cdot\mathbf{M}_{j,2i}+(1-\beta)\cdot\sum_{j\in[2n]}\mathbf{M}_{j,2i}+(1-\beta)\cdot(2n-\sum_{j\in[2n]}\mathbf{M}_{j,2i})$
$\displaystyle=2\beta x^{T}\cdot\mathbf{M}_{*,2i}+2n\cdot(1-\beta).$

Similarly, the total earning of the agents that have a disutility of
$(1-\alpha)$ towards $b^{1}_{2i-1}$ is $2\beta
x^{T}\cdot\mathbf{M}_{*,2i-1}+2n\cdot(1-\beta)$. Observe that the agents with
disutility $(1-\alpha)$ towards $b^{1}_{2i}$ can earn all their money only
from either $b^{1}_{2i}$ or $b^{1}_{2i-1}$ (as these are the only chores
towards which they have finite disutility). Also note that the total endowment
of both $b^{1}_{2i-1}$ and $b^{1}_{2i}$ is $cn$ for some $c\in\mathcal{O}(1)$
(as our instance also satisfies pairwise equal endowments). Now if, the agents
$\left\\{\cup_{j\in[2n]}a_{j,2i}\right\\}\cup a^{\prime}_{2i}$ earn their
money entirely from $b^{1}_{2i}$, then we will have
$p(b^{1}_{2i})\geq\tfrac{1}{cn}\cdot(2\beta
x^{T}\cdot\mathbf{M}_{*,2i}+2n\cdot(1-\beta))$ and
$p(b^{1}_{2i-1})\leq\tfrac{1}{cn}\cdot(2\beta
x^{T}\cdot\mathbf{M}_{*,2i-1}+2n\cdot(1-\beta))$. Since,
$x^{T}\cdot\mathbf{M}_{*,{2i}}>x^{T}\cdot\mathbf{M}_{*,2i-1}+\tfrac{1}{n}$. we
have
$p(b^{1}_{2i})>p(b^{1}_{2i-1})+\tfrac{1}{n}\cdot\tfrac{2}{cn}\beta=\tfrac{2\beta}{cn^{2}}$.
Again, since $\beta\gg n^{2}\cdot\alpha$, we have that
$\tfrac{p(b^{1}_{2i})}{p(b^{1}_{2i-1})}>\tfrac{1+\alpha}{1-\alpha}$, which is
a contradiction, as our construction satisfies the price regulation property.
Therefore, the agents that have a disutility of $(1-\alpha)$ towards
$b^{1}_{2i}$ should also earn some positive units of money from
$b^{1}_{2i-1}$. But this is only possible if
$\tfrac{p(b^{1}_{2i})}{p(b^{1}_{2i-1})}=\tfrac{1-\alpha}{1+\alpha}$. Since our
instance also satisfies the reverse ratio amplification property, we have that
$\tfrac{p(b^{2}_{2i})}{p(b^{2}_{2i-1})}=\tfrac{1+\beta}{1-\beta}$. Since
$p(b^{2}_{2i})+p(b^{2}_{2i-1})=2$ by price equality property, we have that
$p(b^{2}_{2i-1})=1-\beta$. Therefore we have,

$\displaystyle x_{2i-1}$
$\displaystyle=\frac{(1-\beta)-(1-\beta)}{2\cdot\beta}$ $\displaystyle=0.$

A very similar argument shows that when
$x^{T}\cdot\mathbf{M}_{*,{2i-1}}>x^{T}\cdot\mathbf{M}_{*,2i}+\tfrac{1}{n}$,
then $x_{2i}=0$. A more elaborate discussion of the proof, where we give
complete construction and prove that the instance exhibits all the properties,
is in Section 4.

###  1.3 Further Related Work

The fair division literature is too vast to survey here, so we refer to the
excellent books [BT96, RW98, Mou03] and a recent survey article [Mou19], and
restrict attention to previous work that appears most relevant.

Most of the work in fair division is focused on allocating goods with a few
exceptions of chores [Su99, AS14, BT96, RW98]. Recent seminal papers of
Bogomolnaia et al. [BMSY17, BMSY19] consider the case of mixed manna that
contains both goods and bads. For the goods case, competitive equilibrium
maximizes the Nash welfare, i.e., geometric mean of agents’ utilities. In case
of chores (or mixed manna), [BMSY17] shows that critical points of the
geometric mean of agents’ disutilities on the (Pareto) efficiency frontier are
the competitive equilibrium profiles.

The fair allocation of _indivisible_ items is also an intensely studied
problem for the case when all items are goods with a few recent exceptions
[ARSW17, ACL19b, HL19, ACL19a, ACIW19, SS19]. Since the standard notions of
fairness such as envy-freeness are not applicable, alternate notions have been
defined and studied for this case; see [LMMS04, Bud11, CKM+16, PR18, CGM20,
GHS+18, GKK20] for a subset of notable work and references therein. The Nash
welfare continues to serve as a major focal point in this case as well, for
which approximation algorithms have been obtained under several classes of
utility functions including linear [CG15, CDG+17, AGSS17, AMGV18, BKV18,
GHM18, CCG+18].

##### Organization of the Paper.

We present our three main results in the upcoming sections. Section 2 contains
the NP-hardness of chore division with fixed earnings (and equal earnings).
Section 3 contains the sufficiency conditions under which a competitive
equilibrium always exists and the proof of existence. Finally, Section 4
contains the PPAD-hardness of finding a competitive allocation even under the
sufficiency conditions.

##  2 Complexity of Determining Existence of Efficient Equilibrium

In this section, we show that finding a $(\tfrac{11}{12}+\delta)$-competitive
equilibrium for any $\delta>0$ in chore division with fixed earnings (Problem
2) and consequently chore division (Problem 1) is strongly NP-hard. Later, in
the section we also show how to modify our instance to obtain NP-hardness for
finding a $(\tfrac{11}{12}+\delta)$-competitive equilibrium even in chore
division with equal earnings. We show that any polynomial time algorithm that
determines whether an instance admits a $(\tfrac{11}{12}+\delta)$-competitive
equilibrium in chore division with fixed earnings implies that 3-SAT is
solvable in polynomial time. To this end, we recall the 3-SAT problem:

######  Problem 7.

(3-SAT)
Given: A set of variables $X=\left\\{x_{1},x_{2},\dots,x_{n}\right\\}$ and a
set of clauses $\mathbf{C}=\left\\{C_{1},C_{2},\dots,C_{m}\right\\}$ where
each clause is a disjunction of exactly three _literals_ 444A literal is a
variable or the negation of a variable.
Find: An assignment $A:X\rightarrow\left\\{T,F\right\\}$ such that all the
clauses are _satisfied_ 555A clause $C_{r}=\ell_{1}\vee\ell_{2}\vee\ell_{3}$
($\ell_{i}$ is a literal) is satisfied if and only if $A(\ell_{i})=T$ for at
least one $i\in[3]$. or output that no such assignment exists.

Given any instance $I=\langle X,\mathbf{C}\rangle$ of 3-SAT, we will create an
instance $E(I)$ of chore division such that there exists an efficient
competitive equilibrium in $E(I)$ if and only if there exists an assignment
$A$ that satisfies all the clauses in $\mathbf{C}$ in $I$. We first briefly
sketch the intuition, before we move to the construction of the gadgets
required for our reduction.

##### Several Disconnected Equilibria.

We sketch a very simple scenario that could arise in chore division with fixed
earnings: Consider an instance with two agents $a_{1}$ and $a_{2}$ with a
fixed earning of one unit each. The disutility values are given below where
$a_{1}$ has a disutility of $1$ for $b_{1}$ and $3$ for $b_{2}$, while $a_{2}$
has a disutility of $\tau$ for $b_{1}$ and $1$ for $b_{2}$.

$\displaystyle\begin{array}[]{@{\hspace{1ex}}c@{\hspace{1ex}}||@{\hspace{1ex}}c@{\hspace{1ex}}|@{\hspace{1ex}}c@{\hspace{1ex}}|@{\hspace{1ex}}c@{\hspace{1ex}}|}\hskip
4.30554pt\lx@intercol\hfil\hfil\hskip 4.30554pt\vrule\vrule\hskip
4.30554pt&b_{1}\hfil\hskip 4.30554pt\vrule\hskip 4.30554pt&b_{2}\hfil\hskip
4.30554pt\vrule\hskip 4.30554pt\\\\[2.15277pt] \hline\cr\hskip
4.30554pt\lx@intercol\hfil a_{1}\hfil\hskip 4.30554pt\vrule\vrule\hskip
4.30554pt&1\hfil\hskip 4.30554pt\vrule\hskip 4.30554pt&3\hfil\hskip
4.30554pt\vrule\hskip 4.30554pt\\\\[2.15277pt] \hline\cr\hskip
4.30554pt\lx@intercol\hfil a_{2}\hfil\hskip 4.30554pt\vrule\vrule\hskip
4.30554pt&\tau\hfil\hskip 4.30554pt\vrule\hskip 4.30554pt&1\hfil\hskip
4.30554pt\vrule\hskip 4.30554pt\\\\[2.15277pt] \end{array}$

Let $p=\langle p(b_{1}),p(b_{2})\rangle$ be an equilibrium price vector. Also,
throughout this section we use the notation ${\mathit{MPB}}_{a}$ to denote the
_minimum pain per buck_ bundle for agent $a$ at the prices $p$: a chore
$b\in{\mathit{MPB}}_{a}$ if and only if
$\tfrac{d(a,b)}{p(b)}\leq\tfrac{d(a,b^{\prime})}{p(b^{\prime})}$ for all other
chores $b^{\prime}$ in the instance. Observe that this small instance exhibits
exactly two competitive equilibria:

  * •

The first competitive equilibrium is when both $p(b_{1})$ and $p(b_{2})$ are
set to 1. Note that only ${\mathit{MPB}}_{a_{1}}=\left\\{b_{1}\right\\}$ and
${\mathit{MPB}}_{a_{2}}=\left\\{b_{2}\right\\}$. Thus $a_{1}$ earns her entire
one unit of money from $g_{1}$ and $a_{2}$ earns her entire one unit of money
from $g_{2}$.

  * •

The second competitive equilibrium is when $a_{1}$ earns from both $b_{1}$ and
$b_{2}$. For this we set $p(b_{1})$ to $1/2$ and $p(b_{2})$ to $3/2$. Note
that $MPB_{a_{1}}=\left\\{b_{1},b_{2}\right\\}$ and
${\mathit{MPB}}_{a_{2}}=\left\\{b_{2}\right\\}$. Under these prices, $a_{2}$
earns her entire money by doing $2/3$ of $b_{2}$, and $a_{1}$ earns her money
by doing all of $b_{1}$ and $1/3$ of $b_{2}$.

Also, observe that there exists no competitive equilibrium at any other set of
prices (in particular all price vectors that can be expressed as a convex
combination of (1,1) and (1/2,3/2)). This is a striking difference to the
scenario with only goods to divide, where all competitive equilibrium exists
at a unique price vector. Now, let us introduce another agent $a_{3}$ and
another chore $b_{3}$ in the instance. Let us say that $a_{3}$ has a fixed
earning of one unit, and both agents $a_{1}$ and $a_{2}$ have a disutility of
$\tau$ towards $b_{3}$. We now discuss two scenarios that may arise depending
on $a_{3}$’s disutility towards the chores

  1. 1.

$a_{3}$ has a disutility of $1$ towards $b_{3}$ and $b_{2}$ and $\tau$ towards
$b_{1}$.

  2. 2.

$a_{3}$ has a disutility of $1$ towards $b_{3}$, $\tfrac{1}{2}$ towards
$b_{1}$ and $\tau$ towards $b_{2}$.

We will now show that, at a competitive equilibrium, in the first scenario
$b_{2}\notin{\mathit{MPB}}_{a_{1}}$ and in the second scenario
$b_{2}\in{\mathit{MPB}}_{a_{1}}$, suggesting that we need to carefully choose
the _local_ equilibrium among the agents $a_{1}$, $a_{2}$ and chores $b_{1}$
and $b_{2}$. Let $p(b_{1})$, $p(b_{2})$ and $p(b_{3})$ denote the prices of
chores at an equilibrium. Note that since both $a_{1}$ and $a_{2}$ have a
disutility of $\tau$ for $b_{3}$, they only earn money from $b_{1}$ and
$b_{2}$. Thus $p(b_{1})+p(b_{2})\geq 2$. Note that in both scenarios $b_{3}$
should be in ${\mathit{MPB}}_{a_{3}}$ as $a_{3}$ is the only agent with
disutility less than $\tau$ towards it. Now,

  * •

In the first scenario, we need to have
$\tfrac{d(a_{3},b_{3})}{p(b_{3})}\leq\tfrac{d(a_{3},b_{3})}{p(b_{3})}$ or
equivalently $\tfrac{1}{p(b_{3})}\leq\tfrac{1}{p(b_{2})}$, implying that
$p(b_{3})\geq p(b_{2})$. This in turn implies that

$\displaystyle p(b_{2})+2$ $\displaystyle\leq p(b_{2})+(p(b_{1})+p(b_{2}))$
(as $p(b_{1})+p(b_{2})\geq 2$) $\displaystyle\leq p(b_{1})+p(b_{2})+p(b_{3})$
(as $p(b_{2})\leq p(b_{3})$) $\displaystyle=3.$

Thus we have $p(b_{2})\leq 1$, implying that $p(b_{1})\geq 1$. Therefore, we
can conclude that $b_{2}\notin{\mathit{MPB}}_{a_{1}}$ as the disutility to
price ratio of $b_{1}$ is strictly less than that of $b_{2}$ for agent
$a_{1}$.

  * •

In the second scenario, we need to have
$\tfrac{d(a_{3},b_{3})}{p(b_{3})}\leq\tfrac{d(a_{3},b_{1})}{p(b_{1})}$, we
have $\tfrac{1}{p(b_{3})}\leq\tfrac{1}{2p(b_{1})}$, implying that
$p(b_{3})\geq 2p(b_{1})$. This in turn implies that

$\displaystyle 2p(b_{1})+2$ $\displaystyle\leq 2p(b_{1})+(p(b_{1})+p(b_{2}))$
(as $p(b_{1})+p(b_{2})\geq 2$) $\displaystyle\leq p(b_{1})+p(b_{2})+p(b_{3})$
(as $2p(b_{1})\leq p(b_{3})$) $\displaystyle=3.$

Thus we have $p(b_{1})\leq\tfrac{1}{2}$, implying that
$p(b_{2})\geq\tfrac{3}{2}$. Therefore, we conclude that
$b_{2}\in{\mathit{MPB}}_{a_{1}}$.

Thus, as mentioned earlier, depending on the valuations of the agents outside
the local sub-instance, a careful selection of the local equilibrium (among
the two disjoint local equilibria) among the agents $a_{1}$, $a_{2}$ and
chores $b_{1}$ and $b_{2}$ is necessary. We will now show that when there are
$n$ such local sub-instances (resulting in $2^{n}$ disjoint equilibria),
choosing the correct combination of the local equilibria becomes intractable.

###  2.1 Variable Gadgets

For each variable $x_{i}$, we introduce two agents $a_{1}^{i}$ and $a_{2}^{i}$
and two chores $b_{1}^{i}$ and $b_{2}^{i}$. We set

$\displaystyle d(a_{1}^{i},b_{1}^{i})$ $\displaystyle=1,$ $\displaystyle
d(a_{1}^{i},b_{2}^{i})$ $\displaystyle=3,$ $\displaystyle
d(a_{2}^{i},b_{1}^{i})$ $\displaystyle=\tau,$ $\displaystyle
d(a_{2}^{i},b_{2}^{i})$ $\displaystyle=1.$

See Figure 1 for an illustration. We set the earnings of both $a_{1}^{i}$ and
$a_{2}^{i}$ to be one, i.e., $e(a_{1}^{i})=e(a_{2}^{i})=1$. Also, for all
$i\in[n]$ agents $a^{i}_{1}$ and $a^{i}_{2}$ have a disutility of $\tau$ for
all other goods in the instance (that have been introduced and will be
introduced by clause gadgets in the next section).

###  2.2 Clause Gadgets

For each clause $C_{r}=(\ell_{i}\vee\ell_{j}\vee\ell_{k})$, where $\ell_{i}$
is either the variable $x_{i}$ or its negation $\neg x_{i}$, we introduce four
agents $n_{i}^{r}$, $n_{j}^{r}$, $n_{k}^{r}$ and $\mathbf{n}^{r}$, and three
chores $m_{i}^{r}$, $m_{j}^{r}$, and $m_{k}^{r}$. We define the disutility of
the agents as follows: For each literal $\ell_{i}$, if

  * •

$\ell_{i}=x_{i}$, then,

$\displaystyle d(n_{i}^{r},b_{2}^{i})$ $\displaystyle=1$ and $\displaystyle
d(n_{i}^{r},m_{i}^{r})$ $\displaystyle=\varepsilon$ $\displaystyle
d(\mathbf{n}^{r},b_{2}^{i})$ $\displaystyle=1$ and $\displaystyle
d(\mathbf{n}^{r},m_{i}^{r})$ $\displaystyle=\varepsilon.$

for some $0<\varepsilon\ll 1$, but $\tfrac{1}{\varepsilon}\in\mathcal{O}(1)$.

  * •

$\ell_{i}=\neg x_{i}$, then,

$\displaystyle d(n_{i}^{r},b_{1}^{i})$ $\displaystyle=\tfrac{2}{3}$ and
$\displaystyle d(n_{i}^{r},m_{i}^{r})$ $\displaystyle=\tfrac{4\varepsilon}{3}$
$\displaystyle d(\mathbf{n}^{r},b_{1}^{i})$ $\displaystyle=\tfrac{2}{3}$ and
$\displaystyle d(\mathbf{n}^{r},m_{i}^{r})$
$\displaystyle=\tfrac{4\varepsilon}{3}.$

For all other agents and chores pair, the disutility is $\tau$. See Figure 1
for an illustration. We set
$e(n_{i}^{r})=e(n_{j}^{r})=e(n_{k}^{r})=\varepsilon$ and
$e(\mathbf{n}^{r})=\\#(C_{r})\cdot(\tfrac{\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(\varepsilon)-\varepsilon^{\prime}$,
where $\\#(C_{r})$ is the number of literals in $C_{r}$ that are not negations
of variables and $\overline{\\#}(C_{r})$ is the number of literals in $C_{r}$
that are negations of variables 666This implies that
$\\#(C_{r})+\overline{\\#}(C_{r})=3$, and
$\varepsilon^{\prime}<\tfrac{\varepsilon}{2}$ (the exact value of
$\varepsilon^{\prime}$ will depend on $\delta$ 777Reminder to what $\delta$
is: recall that we are trying to show the hardness of determining whether an
instance admits a $(\tfrac{11}{12}+\delta)$-competitive equilibrium or not.
and will be made clear in the proof of Lemma 10). We make a small claim about
the total earning requirements for the agents $n_{i}^{r}$, $n_{j}^{r}$,
$n_{k}^{r}$ and $\mathbf{n}^{r}$.

$\scriptstyle{a^{i}_{1}}$$\scriptstyle{a^{i}_{2}}$$\scriptstyle{b^{i}_{1}}$$\scriptstyle{b^{i}_{2}}$$\scriptstyle{1}$$\scriptstyle{1}$$\mathbf{\scriptstyle{3}}$$\scriptstyle{a^{j}_{1}}$$\scriptstyle{a^{j}_{2}}$$\scriptstyle{b^{j}_{1}}$$\scriptstyle{b^{j}_{2}}$$\scriptstyle{1}$$\scriptstyle{1}$$\mathbf{\scriptstyle{3}}$$\scriptstyle{a^{k}_{1}}$$\scriptstyle{a^{k}_{2}}$$\scriptstyle{b^{k}_{1}}$$\scriptstyle{b^{k}_{2}}$$\scriptstyle{1}$$\scriptstyle{1}$$\mathbf{\scriptstyle{3}}$$\scriptstyle{n^{r}_{i}}$$\scriptstyle{n^{r}_{j}}$$\scriptstyle{n^{r}_{k}}$$\scriptstyle{m^{r}_{i}}$$\scriptstyle{m^{r}_{j}}$$\scriptstyle{m^{r}_{k}}$$\mathbf{\scriptstyle{\varepsilon}}$$\scriptstyle{\tfrac{4\varepsilon}{3}}$$\scriptstyle{\varepsilon}$$\mathbf{\scriptstyle{1}}$$\mathbf{\scriptstyle{\tfrac{2}{3}}}$$\mathbf{\scriptstyle{1}}$$\scriptstyle{\mathbf{n}^{r}}$${\scriptstyle{\varepsilon}}$${\scriptstyle{\tfrac{4\varepsilon}{3}}}$${\scriptstyle{\varepsilon}}$$\mathbf{\scriptstyle{1}}$$\mathbf{\scriptstyle{\tfrac{2}{3}}}$$\mathbf{\scriptstyle{1}}$
Figure 1: Illustration of the variable gadgets corresponding to $x_{i}$,
$x_{j}$ and $x_{k}$, and the clause gadget $C_{r}=(x_{i}\vee\neg x_{j}\vee
x_{k})$. The red squared nodes represent the agents and the green circle nodes
represent the chores. Only disutility values less than $\tau$ have been
indicated. The disutility edges from agents in the variable gadgets are
outlined by blue edges. The disutility edges from agents $n^{r}_{\ell}$ for
$\ell\in\left\\{i,j,k\right\\}$ are outlined by orange edges and the
disutility edges from agent $\mathbf{n}^{r}$ are outlined by black edges.
Thicker disutility edges have a higher disutility than the thinner disutility
edges of the same color.

######  Claim 8.

For each clause $C_{r}=\ell_{i}\vee\ell_{j}\vee\ell_{k}$ in $I$, we have
$e(n_{i}^{r})+e(n_{j}^{r})+e(n_{k}^{r})+e(\mathbf{n}^{r})=\\#(C_{r})\cdot(\tfrac{3\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(2\varepsilon)-\varepsilon^{\prime}$

###### Proof.

We have,

$\displaystyle e(n_{i}^{r})+e(n_{j}^{r})+e(n_{k}^{r})+e(\mathbf{n}^{r})$
$\displaystyle=3\varepsilon+\\#(C_{r})\cdot(\tfrac{\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(\varepsilon)-\varepsilon^{\prime}$
$\displaystyle=(\\#(C_{r})+\overline{\\#}(C_{r}))\varepsilon+\\#(C_{r})\cdot(\tfrac{\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(\varepsilon)-\varepsilon^{\prime}$
$\displaystyle=\\#(C_{r})\cdot(\tfrac{3\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(2\varepsilon)-\varepsilon^{\prime}\qed$

We now show how to map any allocation in $E(I)$ to an assignment of variables
in $I$. Consider any _earning_ $f$ under some prices $p$ in $E(I)$. If agent
$i$ does $X_{ij}$ amount of chore $j$, then $f(i,j)=X_{ij}\cdot p(j)$.

_If agent $a_{1}^{i}$ does some of chore $b_{2}^{i}$, i.e.,
$f({a_{1}^{i},b_{2}^{i}})>0$, then we set $x_{i}$ to $F$ and if
$f({a_{1}^{i},b_{2}^{i}})=0$, then we set $x_{i}$ to $T$._

We now make some basic observations.

######  Observation 9.

Let $p$ be the prices of chores and $f$ the the money allocation corresponding
to a competitive equilibrium in $E(I)$. Consider any clause
$C_{r}=(\ell_{i}\vee\ell_{j}\vee\ell_{k})$. Then,

  1. 1.

if $\ell_{i}=x_{i}$ and $f({a_{1}^{i},b_{2}^{i}})>0$ then
$p({m_{i}^{r}})\geq\tfrac{3\varepsilon}{2}$, and

  2. 2.

if $\ell_{i}=\neg x_{i}$ and $f({a_{1}^{i},b_{2}^{i}})=0$, then
$p({m_{i}^{r}})\geq 2\varepsilon$.

###### Proof.

We first prove part 1. If $f({a_{1}^{i},b_{2}^{i}})>0$, then $b_{2}^{i}\in
MPB_{a_{1}^{i}}$, implying that
$\tfrac{d(a_{1}^{i},b_{2}^{i})}{p(b_{2}^{i})}\leq\tfrac{d(a_{1}^{i},b_{1}^{i})}{p(b_{1}^{i})}$.
Therefore, we have that
$p(b_{2}^{i})\geq\tfrac{d(a^{i}_{1},b^{i}_{2})}{d(a^{i}_{1},b^{i}_{1})}\cdot
p(b^{i}_{1})=3p(b_{1}^{i})$. Also, note that since agents $a_{1}^{i}$ and
$a_{2}^{i}$ have disutility less than $\tau$ only for chores $b_{1}^{i}$ and
$b_{2}^{i}$, they will only earn from chores $b_{1}^{i}$ and $b_{2}^{i}$. This
implies that $p(b_{1}^{i})+p(b_{2}^{i})\geq e(a_{1}^{i})+e(a_{2}^{i})=2$.
Also, since $p(b_{2}^{i})\geq 3p(b_{1}^{i})$ we have that
$p(b_{2}^{i})\geq\tfrac{3}{2}$. Now, observe that the only agents who have
disutility less than $\tau$ towards $m_{i}^{r}$ are the agents $n_{i}^{r}$ and
$\mathbf{n}^{r}$. Since $\ell_{i}=x_{i}$, both $n_{i}^{r}$ and
$\mathbf{n}^{r}$ have a disutility of 1 towards $b_{2}^{i}$ and $\varepsilon$
towards $m_{i}^{r}$. Therefore, for $m_{i}^{r}$ to be in either
${\mathit{MPB}}_{n_{i}^{r}}$ or ${\mathit{MPB}}_{\mathbf{n}^{r}}$, we need
$\tfrac{\varepsilon}{p(m_{i}^{r})}\leq\tfrac{1}{p(b_{2}^{i})}\leq\tfrac{2}{3}$.
This implies that $p(m_{i}^{r})\geq\tfrac{3\varepsilon}{2}$.

The proof of part 2 is very similar. Note that agent $a_{1}^{i}$ has
disutility less than $\tau$ for only chores $b_{1}^{i}$ and $b_{2}^{i}$. If
$f(a_{1}^{i},b_{2}^{i})=0$, then she only earns by doing chore $b_{1}^{i}$,
implying that $p(b_{1}^{i})\geq e(a_{1}^{i})=1$. Similar to the proof in part
1, observe that the only agents who have disutility less than $\tau$ towards
$m_{i}^{r}$ are the agents $n_{i}^{r}$ and $\mathbf{n}^{r}$. Since
$\ell_{i}=\neg x_{i}$, both $n_{i}^{r}$ and $\mathbf{n}^{r}$ have a disutility
of $\tfrac{2}{3}$ towards $b_{1}^{i}$ and $\tfrac{4\varepsilon}{3}$ towards
$m_{i}^{r}$. Therefore, for $m_{i}^{r}$ to be in either
${\mathit{MPB}}_{n_{i}^{r}}$ or ${\mathit{MPB}}_{\mathbf{n}^{r}}$, we need
$\tfrac{4\varepsilon}{3p(m_{i}^{r})}\leq\tfrac{2}{3p(b_{1}^{i})}\leq\tfrac{2}{3}$
(as $p(b^{1}_{i})\geq 1$). This implies that $p(m_{i}^{r})\geq 2\varepsilon$.∎

######  Lemma 10.

If there is no satisfying assignment to the instance $I=\langle
X,\mathbf{C}\rangle$ of 3-SAT, then $E(I)$ does not admit any
$(\tfrac{11}{12}+\delta)$-competitive equilibrium for any $\delta>0$.

###### Proof.

We prove by contradiction. Assume otherwise and let $p$ be the equilibrium
prices of chores and $f$ be the corresponding money allocation. Recall the
mapping from an equilibrium allocation to the assignment of variables: For
each $i\in[n]$ if $f(a_{1}^{i},b_{2}^{i})>0$, then we set $x_{i}$ to $F$ and
if $f(a_{1}^{i},b_{2}^{i})=0$, then we set $x_{i}$ to $T$. Since $I$ admits no
satisfying assignment, there exists a clause
$C_{r}=\ell_{i}\vee\ell_{j}\vee\ell_{k}$ which is unsatisfied. For every
literal $\ell_{i}\in C_{r}$ such that $\ell_{i}=x_{i}$, note that $x_{i}$ is
$F$. Therefore, we have that $f(a_{1}^{i},b_{2}^{i})>0$. This implies that
$p(m_{i}^{r})\geq\tfrac{3\varepsilon}{2}$ (by Observation 9). Similarly for
every literal $\ell_{i}$ in $C_{r}$ such that $\ell_{i}=\neg x_{i}$, note that
$x_{i}$ is $T$. Therefore, we have that $f(a_{1}^{i},b_{2}^{i})=0$, implying
that $p(m_{i}^{r})\geq 2\varepsilon$ (by Observation 9). We write the price of
chore $m^{r}_{i}$, $p(m^{r}_{i})$ as
$\tfrac{3\varepsilon}{2}+\delta(m^{r}_{i})$ if $\ell_{i}=x_{i}$ and
$2\varepsilon+\delta(m^{r}_{i})$ if $\ell_{i}=\neg x_{i}$, where
$\delta(m^{r}_{i})$ is the deviation of the price of $m^{r}_{i}$ from its
lower bound. Therefore, we have
$p(m_{i}^{r})+p(m_{j}^{r})+p(m_{k}^{r})=\\#(C_{r})\cdot(\tfrac{3\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(2\varepsilon)+\delta(m^{r}_{i})+\delta(m^{r}_{j})+\delta(m^{r}_{k})$.
Note that the only agents who have disutility less than $\tau$ for chores
$m_{i}^{r}$, $m_{j}^{r}$ and $m_{k}^{r}$ are the agents $n_{i}^{r}$,
$n_{j}^{r}$, $n_{k}^{r}$ and $\mathbf{n}^{r}$. However, by Claim 8, we have
that
$e(n_{i}^{r})+e(n_{j}^{r})+e(n_{k}^{r})+e(\mathbf{n}^{r})=\\#(C_{r})\cdot(\tfrac{3\varepsilon}{2})+\overline{\\#}(C_{r})\cdot(2\varepsilon)-\varepsilon^{\prime}$
which is strictly less that the sum of prices of chores $m_{i}^{r}$,
$m_{j}^{r}$ and $m_{k}^{r}$. In particular we have,
$\sum_{h\in\left\\{i,j,k\right\\}}p(m^{r}_{h})-(\sum_{h\in\left\\{i,j,k\right\\}}e(n^{r}_{h})+e(\mathbf{n}^{r}))=\varepsilon^{\prime}+\sum_{h\in\left\\{i,j,k\right\\}}\delta(m^{r}_{h})$.
Therefore, there exists at least one chore $m^{r}_{h^{\prime}}$ such that the
difference between the total price of the chore and the total money earned
from the chore by the agents is
$\tfrac{\varepsilon^{\prime}+\sum_{h\in\left\\{i,j,k\right\\}}\delta(m^{r}_{h})}{3}\geq\tfrac{\varepsilon^{\prime}+\delta(m^{r}_{h^{\prime}})}{3}$.
Thus, the portion of chore $m^{r}_{h^{\prime}}$ left undone is at least,

$\displaystyle=\tfrac{\varepsilon^{\prime}+\delta(m^{r}_{h^{\prime}})}{3\cdot
p(m^{r}_{h^{\prime}})}$
$\displaystyle\geq\tfrac{\varepsilon^{\prime}+\delta(m^{r}_{h^{\prime}})}{3\cdot(2\varepsilon+\delta(m^{r}_{h^{\prime}}))}$
(as $p(m^{r}_{h^{\prime}})$ is either
$\tfrac{3\varepsilon}{2}+\delta(m^{r}_{h^{\prime}})$ or
$2\varepsilon+\delta(m^{r}_{h^{\prime}})$)
$\displaystyle\geq\tfrac{\varepsilon^{\prime}}{3\cdot(2\varepsilon)}$
$\displaystyle\text{(as $\varepsilon^{\prime}<\frac{\varepsilon}{2}$)}.$

Since our reduction works for any choice of
$\varepsilon^{\prime}<\tfrac{\varepsilon}{2}$, we can choose an
$\varepsilon^{\prime}$ such that
$\tfrac{\varepsilon^{\prime}}{(6\varepsilon)}>\tfrac{1}{12}-\delta$, implying
that we do not have a $(\tfrac{11}{12}+\delta)$-competitive equilibrium, which
is a contradiction. ∎

######  Lemma 11.

If there exists a satisfying assignment to the instance $I=\langle
X,\mathbf{C}\rangle$ of 3-SAT, then $E(I)$ admits a competitive equilibrium.

###### Proof.

Consider any satisfying assignment in $I$. We now show how to construct the
prices $p$ and the money allocation $f$ corresponding to a competitive
allocation. We will ensure that only the agents in the variable gadgets earn
from the chores in the variable gadgets and the agents in the clause gadgets
earn only from the chores in the clause gadgets.

##### Prices and Allocation of Chores in Variable Gadgets.

For each variable $x_{i}$,

  * •

If $x_{i}=T$, then we set $p(b_{1}^{i})=1$ and $p(b_{2}^{i})=1$.

  * •

If $x_{i}=F$, then we set $p(b_{1}^{i})=\tfrac{1}{2}$ and
$p(b_{2}^{i})=\tfrac{3}{2}$.

Since the agents in the variable gadgets have disutility less than $\tau$ only
for some goods in the variable gadgets (and have disutility of $\tau$ for
every good in the clause gadget) we can already define their optimal bundles
(${\mathit{MPB}}$ bundles). If $x_{i}=T$, then observe that
${\mathit{MPB}}_{a_{1}^{i}}=\left\\{b_{1}^{i}\right\\}$ and
${\mathit{MPB}}_{a_{2}^{i}}=\left\\{b_{2}^{i}\right\\}$. Thus agent
$a_{1}^{i}$ earns $1$ unit of money from doing chore $b_{1}^{i}$ entirely and
agent $a_{2}^{i}$ earns $1$ unit of money by doing chore $b_{2}^{i}$ entirely.
When $x_{i}=F$, then observe that
${\mathit{MPB}}_{a_{1}^{i}}=\left\\{b_{1}^{i},b_{2}^{i}\right\\}$ and
${\mathit{MPB}}_{a_{2}^{i}}=\left\\{b_{2}^{i}\right\\}$. Thus agent
$a_{1}^{i}$ earns $1$ unit of money from doing chore $b_{1}^{i}$ entirely and
$b_{2}^{i}$ partly and agent $a_{2}^{i}$ earns $1$ unit of money by doing
chore $b_{2}^{i}$ partly. Now we make an immediate, simple observation:

######  Observation 12.

When $x_{i}=T$, then $f(a_{1}^{i},b_{2}^{i})=0$ and when $x_{i}=F$, we have
$f(a_{1}^{i},b_{2}^{i})>0$.

Observe that all the local sub-instances corresponding to the variable gadgets
have cleared. It suffices to show that there exists a competitive equilibrium
for local sub-instances corresponding to the clause gadgets. We now look into
the agents and chores in the clause gadget.

##### Prices and Allocation of Chores in Clause Gadgets.

Consider a clause $C_{r}=\ell_{i}\vee\ell_{j}\vee\ell_{k}$. Therefore, let
$S_{r}\subseteq\left\\{\ell_{i},\ell_{j},\ell_{k}\right\\}$ be the literals
that evaluate to $T$ 888A literal $\ell_{i}=x_{i}$ evaluates to $T$ if $x_{i}$
is set to $T$ and the literal $\ell_{i}=\neg x_{i}$ evaluates to $T$ when
$x_{i}$ is set to $F$. and
$U_{r}\subseteq\left\\{\ell_{i},\ell_{j},\ell_{k}\right\\}$ be the set of
literals that evaluate to $F$ under the assignment $X$. Since $X$ is a
satisfying assignment, at least one of the literals will evaluate to $T$ and
thus $\lvert S_{r}\rvert\geq 1$ and $\lvert U_{r}\rvert\leq 2$. Let
$\\#(S_{r})$ and $\\#(U_{r})$ be the number of literals in $S_{r}$ and $U_{r}$
respectively that are not negations of variables and similarly let
$\overline{\\#}(S_{r})$ and $\overline{\\#}(U_{r})$ be the number of literals
that are negations of variables in $S_{r}$ and $U_{r}$ respectively. Let
$\alpha_{r}$ be a scalar such that

$\displaystyle\alpha_{r}\cdot(\\#(U_{r})\cdot\tfrac{3\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(2\varepsilon))=\lvert
U_{r}\rvert\cdot\varepsilon+e(\mathbf{n}^{r})$ (3)

We now set the prices of the chores in the clause gadgets. Consider any clause
$C_{r}=\ell_{i}\vee\ell_{j}\vee\ell_{k}$ in $I$ (with $S_{r}$ and $U_{r}$
defined appropriately). For every literal $\ell_{\theta}\in S_{r}$, set,

$p(m_{\theta}^{r})=\left\\{\begin{array}[]{ll}\varepsilon&\text{ if
}\ell_{\theta}=\neg x_{\theta},\\\ \varepsilon&\text{ if
}\ell_{\theta}=x_{\theta}\text{ and }U_{r}\neq\emptyset,\\\
\varepsilon+\frac{e(n^{r})}{\\#(S_{r})}&\text{ if
}\ell_{\theta}=x_{\theta}\text{ and }U_{r}=\emptyset.\\\ \end{array}\right.$

For every $\ell_{\theta}\in U_{r}$, set

$p(m_{\theta}^{r})=\left\\{\begin{array}[]{ll}\alpha_{r}\cdot(\frac{3\varepsilon}{2})&\text{
if }\ell_{\theta}=x_{\theta}\\\ \alpha_{r}\cdot(2\varepsilon)&\text{ if
}\ell_{\theta}=\neg x_{\theta}.\\\ \end{array}\right.$

We will now show that under the above prices for the chores in the clause
gadgets, we can determine a money flow where all the clause agents earn all of
their money from their optimal bundles and all the clause chores will be
completed. We distinguish two cases, depending on whether $U_{r}=\emptyset$ or
not,

##### Case $U_{r}\neq\emptyset$:

In this case, we first observe that $\alpha_{r}$ is strictly larger than $1$:

######  Observation 13.

We have well defined scalar $\alpha_{r}>1$.

###### Proof.

Since we are in the case where $U_{r}\neq 0$, we have
$\\#(U_{r})\cdot\tfrac{3\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(2\varepsilon)>0$,
thus $\alpha_{r}$ is well defined. For the claim of the lemma, it suffices to
show that $\lvert
U_{r}\rvert\cdot\varepsilon+e(\mathbf{n}^{r})>\\#(U_{r})\cdot\tfrac{3\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(2\varepsilon)$.
To this end,

$\displaystyle\lvert U_{r}\rvert\cdot\varepsilon+e(\mathbf{n}^{r})$
$\displaystyle=(\\#(U_{r})+\overline{\\#}(U_{r}))\cdot\varepsilon+e(\mathbf{n}^{r})$
$\displaystyle=(\\#(U_{r})+\overline{\\#}(U_{r}))\cdot\varepsilon+\\#(C_{r})\cdot\tfrac{\varepsilon}{2}+\overline{\\#}(C_{r})\cdot(\varepsilon)-\varepsilon^{\prime}\enspace.$
(4)

Since the literals that are not negations of variables in $U_{r}$ are also not
negations of variables in $C_{r}$ we have $\\#(U_{r})\leq\\#(C_{r})$. By a
similar argument we also have
$\overline{\\#}(U_{r})\leq\overline{\\#}(C_{r})$. Since $\lvert
U_{r}\rvert\leq 2$ we also have
$\\#(U_{r})+\overline{\\#}(U_{r})<\\#(C_{r})+\overline{\\#}(C_{r})$, implying
that either $\\#(U_{r})<\\#(C_{r})$ or
$\overline{\\#}(U_{r})<\overline{\\#}(C_{r})$. Therefore, we have that
$\\#(C_{r})\cdot\tfrac{\varepsilon}{2}+\overline{\\#}(C_{r})\cdot(\varepsilon)\geq\\#(U_{r})\cdot\tfrac{\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(\varepsilon)+\tfrac{\varepsilon}{2}$.
Plugging this inequality in (2.2), we have

$\displaystyle\lvert U_{r}\rvert\cdot\varepsilon+e(\mathbf{n}^{r})$
$\displaystyle\geq(\\#(U_{r})+\overline{\\#}(U_{r}))\cdot\varepsilon+\\#(U_{r})\cdot\tfrac{\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(\varepsilon)+\tfrac{\varepsilon}{2}-\varepsilon^{\prime}$
$\displaystyle>(\\#(U_{r})+\overline{\\#}(U_{r}))\cdot\varepsilon+\\#(U_{r})\cdot\tfrac{\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(\varepsilon)$
$\displaystyle(\text{as $\varepsilon^{\prime}<\tfrac{\varepsilon}{2}$})$
$\displaystyle=\\#(U_{r})\cdot\tfrac{3\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(2\varepsilon)\enspace.\qed$

We will now characterize the optimal bundles (${\mathit{MPB}}$ chores) for
each agents under the set prices.

######  Observation 14.

For each literal $\ell_{\theta}\in S_{r}$, we have
$m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$.

###### Proof.

We consider the cases, whether the $\ell_{\theta}=x_{\theta}$ or
$\ell_{\theta}=\neg x_{\theta}$.

  * •

$\ell_{\theta}=x_{\theta}$: Note that the only other chore (other than
$m_{\theta}^{r}$) for which agent $n_{\theta}^{r}$ has disutility less than
$\tau$ is chore $b_{2}^{\theta}$. Since $\ell_{\theta}\in S_{r}$, this means
that $x_{\theta}=T$ and therefore we have $p(b_{2}^{\theta})=1$. Now observe
that,

$\displaystyle\frac{d(n_{\theta}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}$
$\displaystyle=\frac{\varepsilon}{\varepsilon}$ $\displaystyle=1$
$\displaystyle=\frac{d(n_{\theta}^{r},b_{2}^{\theta})}{p(b_{2}^{\theta})}\enspace.$

Therefore $m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$.

  * •

$\ell_{\theta}=\neg x_{\theta}$: Note that the only other chore (other than
$m_{\theta}^{r}$) for which agent $n_{\theta}^{r}$ has disutility less than
$\tau$ is chore $b_{1}^{\theta}$. Since $\ell_{\theta}\in S_{r}$, this means
that $x_{\theta}=F$ and therefore we have $p(b_{1}^{\theta})=\tfrac{1}{2}$.
Now observe that,

$\displaystyle\frac{d(n_{\theta}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}$
$\displaystyle=\frac{4\varepsilon}{3\varepsilon}$ $\displaystyle=\frac{4}{3}$
$\displaystyle=\frac{2}{3\cdot\tfrac{1}{2}}$
$\displaystyle=\frac{d(n_{\theta}^{r},b_{1}^{\theta})}{p(b_{1}^{\theta})}\enspace.$

Therefore, $m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$. ∎

This implies that for all literals $\ell_{\theta}$ in $S_{r}$, the agent
$n_{\theta}^{r}$ will earn her entire money of $\varepsilon$ by doing the
chore $\ell_{\theta}$ entirely. Therefore, now we only need to look at the
agents $n_{\theta}^{r}$ and chores $m_{\theta}^{r}$ where $\ell_{\theta}\in
U_{r}$. To this end we observe that,

######  Observation 15.

For each literal $\ell_{\theta}\in U_{r}$, we have
$m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$ and
$m_{\theta}^{r}\in{\mathit{MPB}}_{\mathbf{n}^{r}}$.

###### Proof.

We first show that $m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$. We make
a distinction based on whether $\ell_{\theta}=x_{\theta}$ or
$\ell_{\theta}=\neg x_{\theta}$.

  * •

$\ell_{\theta}=x_{\theta}$: In this case we have
$p(m_{\theta}^{r})=\alpha_{r}\cdot(\tfrac{3\varepsilon}{2})$. Note that the
only other chore (other than $m_{\theta}^{r}$) for which agent
$n_{\theta}^{r}$ has disutility less than $\tau$ is chore $b_{2}^{\theta}$.
Since $\ell_{\theta}\in U_{r}$, this means that $x_{\theta}=F$ and therefore
we have $p(b_{2}^{\theta})=\tfrac{3}{2}$. Now observe that,

$\displaystyle\frac{d(n_{\theta}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}$
$\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{\varepsilon}{\tfrac{3\varepsilon}{2}}$
$\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{2}{3}$ (5)
$\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{d(n_{\theta}^{r},b_{2}^{\theta})}{p(b_{2}^{\theta})}$
$\displaystyle<\frac{d(n_{\theta}^{r},b_{2}^{\theta})}{p(b_{2}^{\theta})}\enspace.$
$\displaystyle(\text{as $\alpha_{r}>1$ by Observation\leavevmode\nobreak\
\ref{alphaislarge}})$

  * •

$\ell_{\theta}=\neg x_{\theta}$: In this case we have
$p(m_{\theta}^{r})=\alpha_{r}\cdot(2\varepsilon)$. Note that the only other
chore (other than $m_{\theta}^{r}$) for which agent $n_{\theta}^{r}$ has
disutility less than $\tau$ is chore $b_{1}^{\theta}$. Since $\ell_{\theta}\in
U_{r}$, this means that $x_{\theta}=T$ and therefore we have
$p(b_{1}^{\theta})=1$. Now observe that,

$\displaystyle\frac{d(n_{\theta}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}$
$\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{4\varepsilon}{3\cdot
2\varepsilon}$ $\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{2}{3}$ (6)
$\displaystyle=\frac{1}{\alpha_{r}}\cdot\frac{d(n_{\theta}^{r},b_{1}^{\theta})}{p(b_{1}^{\theta})}$
$\displaystyle<\frac{d(n_{\theta}^{r},b_{1}^{\theta})}{p(b_{1}^{\theta})}\enspace.$
$\displaystyle(\text{as $\alpha_{r}>1$ by Observation\leavevmode\nobreak\
\ref{alphaislarge}})$

Thus in both cases we have $m_{\theta}^{r}\in{\mathit{MPB}}_{n_{\theta}^{r}}$.

We will now show that $m_{\theta}^{r}\in{\mathit{MPB}}_{\mathbf{n}^{r}}$ as
well. We do this by showing that the disutility to price ratio of the chores
$m_{\theta}^{r}$, when $\ell_{\theta}\in U_{r}$, is minimum for the agent
$\mathbf{n}^{r}$. _To this end, first crucially observe that from ( 5) and
(6), irrespective of whether $\ell_{\theta}=x_{\theta}$ or $\ell_{\theta}=\neg
x_{\theta}$, we have
$\frac{d(n_{\theta}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}=\tfrac{1}{\alpha_{r}}\cdot\tfrac{2}{3}$_.
Also, note that the disutility profile agent $\mathbf{n}^{r}$ has for chore
$m_{\theta}^{r}$ and the chores in the variable gadget of $x_{\theta}$
($b^{\theta}_{1}$ and $b^{\theta}_{2}$) is identical to the disutility profile
of agent $n_{\theta}^{r}$ for the same set of chores. Therefore, for all
$\ell_{\theta}\in U_{r}$ we have
$\frac{d(\mathbf{n}^{r},m_{\theta}^{r})}{p(m_{\theta}^{r})}=\frac{1}{\alpha_{r}}\cdot\frac{2}{3}$
(irrespective of whether $\ell_{\theta}=x_{\theta}$ or $\ell_{\theta}=\neg
x_{\theta}$) which is also strictly less than both
$\frac{d(\mathbf{n}^{r},b_{2}^{\theta})}{p(b_{2}^{\theta})}$ and
$\frac{d(\mathbf{n}^{r},b_{1}^{\theta})}{p(b_{1}^{\theta})}$. We now look at
disutility to price ratio that agent $\mathbf{n}^{r}$ has for chores in
$S_{r}$. Observe that for all $\ell_{\beta}\in S_{r}$ we have
$p(m_{\beta}^{r})=\varepsilon$ and
$d(\mathbf{n}^{r},m_{\beta}^{r})\geq\varepsilon$ (as the disutility is
$\varepsilon$ if $\ell_{\beta}=x_{\beta}$ and is $\tfrac{4\varepsilon}{3}$ if
$\ell_{\beta}=\neg x_{\beta}$ ). This implies that for all $\ell_{\beta}\in
S_{r}$ we have $\frac{d(\mathbf{n}^{r},m_{\beta}^{r})}{p(m_{\beta}^{r})}\geq
1>\tfrac{2}{3}>\tfrac{1}{\alpha_{r}}\cdot\tfrac{2}{3}$ (as $\alpha_{r}>1$ by
Observation 13). Therefore, the disutility to price ratio of the chores
$m^{r}_{\theta}$, when $\ell_{\theta}\in U_{r}$, for agent $\mathbf{n}^{r}$ is
$\tfrac{1}{\alpha_{r}}\cdot\tfrac{2}{3}$ which is at most the disutility to
price ratio of all the chores for which $\mathbf{n}^{r}$ has a disutility of
less than $\tau$. Therefore, we have $\bigcup_{\ell_{\theta}\in
U_{r}}m_{\theta}^{r}\subseteq{\mathit{MPB}}_{\mathbf{n}^{r}}$. ∎

Now that we have identified the ${\mathit{MPB}}$ chores for all the agents in
the clause gadgets, we are ready to show the money flow allocation. We set

$\displaystyle f(n_{\theta}^{r},m_{\theta}^{r})$ $\displaystyle=\varepsilon$
(for all $\ell_{\theta}\in S_{r}$) $\displaystyle
f(\mathbf{n}^{r},m_{\theta}^{r})$
$\displaystyle=p(m_{\theta}^{r})-\varepsilon\enspace.$ (for all
$\ell_{\theta}\in U_{r}$)

All agents spend on their corresponding ${\mathit{MPB}}$ chores. Observe that
for all $\ell_{\theta}\in S_{r}$, the agents $n_{\theta}^{r}$ earn their money
of $\varepsilon$ by doing chore $m_{\theta}^{r}$ completely. Now, for all
$\ell_{\theta}\in U_{r}$, the agents $n_{\theta}^{r}$ earn their money of
$\varepsilon$ by doing chore $m_{\theta}^{r}$ partially. The agent
$\mathbf{n}^{r}$ earns her entire money by completing whatever is left of the
chores in $\bigcup_{\ell_{\theta}\in U_{r}}m_{\theta}^{r}$. It only suffices
to show that agent $\mathbf{n}^{r}$ earns exactly $e(\mathbf{n}^{r})$. To this
end, we observe that the total money earned by $\mathbf{n}^{r}$ is

$\displaystyle\sum_{\ell_{\theta}\in U_{r}}f(\mathbf{n}^{r},m_{\theta}^{r})$
$\displaystyle=\sum_{\ell_{\theta}\in U_{r}}(p(m_{\theta}^{r})-\varepsilon)$
$\displaystyle=\alpha_{r}\cdot(\\#(U_{r})\cdot\tfrac{3\varepsilon}{2}+\overline{\\#}(U_{r})\cdot(2\varepsilon))-\lvert
U_{r}\rvert\cdot\varepsilon$ $\displaystyle=e(\mathbf{n}^{r})\enspace.$
$\displaystyle(\text{by\leavevmode\nobreak\ \eqref{alphadef})}$

Therefore, we have an allocation where the agents in the corresponding
variable gadgets earn their money by completing the chores in the variable
gadgets and the agents in the clause gadget earn their entire money by
completing the chores in the clause gadgets. This concludes the proof for the
case $U_{r}\neq\emptyset$.

##### Case $U_{r}=\emptyset$:

In this case we have that all the literals in the clause $C_{r}$ belongs to
the set $S_{r}$. Therefore, for all the literals $\ell_{\theta}$ occurring in
$C_{r}$, we have,

$p(m_{\theta}^{r})=\left\\{\begin{array}[]{ll}\varepsilon&\text{ if
}\ell_{\theta}=\neg x_{\theta},\\\
\varepsilon+\frac{e(n^{r})}{\\#(S_{r})}&\text{ if }\ell_{\theta}=x_{\theta}\\\
\end{array}\right.$

Like earlier, we will identify the ${\mathit{MPB}}$ chores for all the clause
gadget agents and then will outline a money flow allocation where every agent
earns all her money and all the chores are completed. We first look into the
agents $n^{r}_{\theta}$. Very similar to Observation 14, we can claim that
$m^{r}_{\theta}\in{\mathit{MPB}}_{n^{r}_{\theta}}$ with a very similar
argument as the one used in the proof of Observation 14: The agent
$n^{r}_{\theta}$ has disutility less than $\tau$ only for chores
$m^{r}_{\theta}$, $b^{\theta}_{2}$ if $\ell_{\theta}=x_{\theta}$, and only for
chores $m^{r}_{\theta}$ and $b^{\theta}_{1}$ if $\ell_{\theta}=\neg
x_{\theta}$, and the price of the chore $p(m^{r}_{\theta})$ is at least
$\varepsilon$ (it is more if $\ell_{\theta}=x_{\theta}$), while the prices of
chores $b^{1}_{\theta}$ and $b^{2}_{\theta}$ are the same as in Observation
14.

Now we look into the agent $\mathbf{n}^{r}$. Since the disutility profile of
agent $\mathbf{n}^{r}$ is identical to that of $n^{r}_{\theta}$ when
restricted to chores $b^{\theta}_{1}$, $b^{\theta}_{2}$ and $m^{r}_{\theta}$,
we can conclude that the disutility to price ratio of $m^{r}_{\theta}$ for
$\mathbf{n}^{r}$ is at most that of chores $b^{\theta}_{1}$ and
$b^{\theta}_{2}$. Now observe that the disutility to price ratio of all chores
$m^{r}_{\theta}$ for $\mathbf{n}^{r}$ where $\ell_{\theta}=x_{\theta}$ is
$\tfrac{d(\mathbf{n}^{r},m^{r}_{\theta})}{p(m^{r}_{\theta})}=\tfrac{\varepsilon}{p(m^{r}_{\theta})}\leq
1$ (as $p(m^{r}_{\theta})=\varepsilon+\tfrac{e(\mathbf{n}^{r})}{\\#(S_{r})}$),
while the disutility to price ratio all chores $m^{r}_{\theta}$ for
$\mathbf{n}^{r}$ where $\ell_{\theta}=\neg x_{\theta}$ is
$\tfrac{d(\mathbf{n}^{r},m^{r}_{\theta})}{p(m^{r}_{\theta})}=\tfrac{4\varepsilon}{3p(m^{r}_{\theta})}>1$
(as $p(m^{r}_{\theta})=\varepsilon$). Since $\mathbf{n}^{r}$ has a disutility
of less than $\tau$ only for the chores in the clause gadget of $C_{r}$ and
the chores in the corresponding variable gadgets, we can claim that
$\bigcup_{\left\\{\theta\mid\ell_{\theta}=x_{\theta}\right\\}}m^{r}_{\theta}\subseteq{\mathit{MPB}}_{\mathbf{n}^{r}}$.
Now, that we have identified the ${\mathit{MPB}}$ chores for the agents in the
clause gadget, we outline a money flow,

$\displaystyle f(n_{\theta}^{r},m_{\theta}^{r})$ $\displaystyle=\varepsilon$
(for all $\ell_{\theta}$) $\displaystyle f(\mathbf{n}^{r},m_{\theta}^{r})$
$\displaystyle=p(m_{\theta}^{r})-\varepsilon\enspace.$ (for all
$\ell_{\theta}=x_{\theta}$)

All the agents spend on their corresponding ${\mathit{MPB}}$ chores. Observe
that for all $\ell_{\theta}$, the agents $n_{\theta}^{r}$ earn their entire
money of $\varepsilon$ by doing chore $m_{\theta}^{r}$ (partially if
$\ell_{\theta}=x_{\theta}$ and completely when $\ell_{\theta}=\neg
x_{\theta}$). The agent $\mathbf{n}^{r}$ earns her entire money by completing
whatever is left of the chores in
$\bigcup_{\left\\{\theta\mid\ell_{\theta}=x_{\theta}\right\\}}m_{\theta}^{r}$.
It only suffices to show that agent $\mathbf{n}^{r}$ earns exactly
$e(\mathbf{n}^{r})$. To this end, we observe that the total money earned by
$\mathbf{n}^{r}$ is

$\displaystyle\sum_{\left\\{\theta\mid\ell_{\theta}=x_{\theta}\right\\}}f(\mathbf{n}^{r},m_{\theta}^{r})$
$\displaystyle=\sum_{\left\\{\theta\mid\ell_{\theta}=x_{\theta}\right\\}}(p(m_{\theta}^{r})-\varepsilon)$
$\displaystyle=\\#(S_{r})\cdot\bigg{(}\varepsilon+\frac{e(\mathbf{n}^{r})}{\\#(S_{r})}-\varepsilon\bigg{)}$
$\displaystyle=e(\mathbf{n}^{r}).$

Therefore, we have an allocation where the agents in the variable gadgets earn
their money by completing the chores in the variable gadgets and the agents in
the clause gadgets earn their entire money by completing the chores in the
clause gadgets. This concludes the proof for the case $U_{r}=\emptyset$. ∎

This brings us to the main result of this section.

######  Theorem 16.

Determining an $(\tfrac{11}{12}+\delta)$-competitive equilibrium, for any
$\delta>0$, in chore division with fixed earnings is strongly NP-hard.

###### Proof.

Given any instance $I=\langle X,\mathbf{C}\rangle$ of 3-SAT, in polynomial
time we can construct an instance $E(I)$ of chore division comprising of all
variable gadgets and clause gadgets. Also, observe all the entries in the
disutility matrix $d(\cdot,\cdot)$ and the money vector $e(\cdot)$ are
constants (Thus all input parameters can be expressed with polynomial bit size
in unary notation). Lemma 10 implies that we have a
$(\tfrac{11}{12}+\delta)$-competitive equilibrium only if $I$ is satisfiable
and Lemma 11 implies that if $I$ is satisfiable, then $E(I)$ admits a
competitive equilibrium (and thus also a $(\tfrac{11}{12}+\delta)$-competitive
equilibrium). ∎

######  Remark 17.

Note that every instance of chore division with fixed earnings $\langle
A,B,d(\cdot,\cdot),e(\cdot)\rangle$, where $e(a)$ is an integer for all $a\in
A$, can be transformed into an instance $I^{\prime}=\langle
A^{\prime},B,d^{\prime}(\cdot,\cdot)\rangle$ of chore division with equal
incomes (where $e(a)=1$ for all $a\in A^{\prime}$) by creating $e(a)$ many
identical copies (having the exact same disutility profile) of the agent $a\in
A$ (the good set remains unchanged): Every $\alpha$-competitive equilibrium in
$I^{\prime}$ will also be an $\alpha$-competitive equilibrium in $I$. Observe
that in our instance $E(I)$, we can scale the earning functions of all the
agents by some large scalar $\gamma(\varepsilon,\varepsilon^{\prime})$ to make
the earnings of the agents integral. Again, since $e(a)\in\mathcal{O}(1)$ and
$\tfrac{1}{\varepsilon},\tfrac{1}{\varepsilon^{\prime}}\in\mathcal{O}(1)$, we
have $\lvert A^{\prime}\rvert=\mathcal{O}(\lvert A\rvert)$ and all the input
parameters of $A^{\prime}$ (all entries in the disutility matrix
$d^{\prime}(\cdot,\cdot)$) can be expressed with polynomial bit size in unary
notation. _Therefore, finding an $(\tfrac{11}{12}+\delta)$-competitive
equilibrium, for any $\delta>0$, in chore division with equal incomes is also
strongly NP-hard._

##  3 Sufficiency Conditions for the Existence of Equilibrium

In this section, we formulate certain conditions that if any instance of chore
division satisfies, will admit a competitive equilibrium. The reader is
encouraged to read Section 1.2.2 to get an overall picture of the results,
ideas and techniques used in this section.

Recall that in all the instances that we construct to show non-existence of
competitive equilibrium, we crucially use the following structure in the
disutility matrix: there are agent sets $A_{1}$ and $A_{2}$ and sets of chores
$B_{1}$ and $B_{2}$ such that agents in $A_{1}$ have disutility of less than
$\tau$ for all chores in $B_{1}$, but disutility of more than $\tau$ for all
chores in $B_{2}$; However, agents in $A_{2}$ have disutility of less than
$\tau$ for some chores in $B_{1}$ and all chores in $B_{2}$. Therefore, we now
look into instances which do not have such structure in the disutility matrix.
To this end, we define the _disutility graph_ of an instance as the bipartite
graph $D=(A\cup B,E_{D})$ containing the agents $A$ as one vertex set and the
chores $B$ as the other and there exists an edge from agent $a\in A$ to chore
$b\in B$ if and only if $d(a,b)<\tau$. Our first sufficiency condition is
that,

Condition 1: $D$ is a disjoint union of complete bipartite graphs
$D_{1},D_{2},\dots,D_{d}$ for some $d\geq 1$.

Observe that the above condition is violated by all the examples in Section
1.2.1 and the instance $E(I)$ in Section 2. Recall that we showed in Section
1.2.2 that Condition 1 alone is not sufficient for chore division (it is
sufficient for chore division with fixed earnings (Problem 2)). To this end,
we define the _exchange graph_ of an instance as a graph $W=([d],E_{W})$. We
have $(i,j)\in E_{W}$ if and only if for every chore $b$ in the component
$D_{j}$ of the disutility matrix, there is an agent $a\in D_{i}$ such that
$w_{a,b}>0$. We now propose our second sufficiency condition.

Condition 2: $W$ is strongly connected.

Let $\mathcal{I}$ denote all the instances of chore division that satisfy
Condition 1 and Condition 2. We now show that all instances in $\mathcal{I}$
admit a competitive equilibrium. Consider any instance $I=\langle
D,W\rangle\in\mathcal{I}$ such that $D=\cup_{i\in[d]}D_{i}$ where each
$D_{i}=(A_{i}\cup B_{i},E_{D_{i}})$ is a complete bipartite graph, disjoint
from $D_{i^{\prime}}$ ($i^{\prime}\neq i$). For ease of notation:

  * •

We represent our set $A$ of $n$ agents as $[n]$ and the set $B$ of $m$ chores
as $[m]$.

  * •

We also write $p_{j}$ to denote the price of chore $j$ and $w_{i,j}$ to
represent the agent $i$’s initial endowment of chore $j$.

  * •

Lastly, we also assume without loss of generality that the total endowment of
each chore is one: $\sum_{i\in[n]}w_{i,j}=1$.

Now, we briefly introduce some basic definitions and concepts required to
prove the existence of competitive equilibrium.

##### Normalized Prices and Bounded Allocations.

A price vector $p=\langle p_{1},p_{2},\dots,p_{m}\rangle$ is called a
_normalized price vector_ if

  * •

$p_{j}\geq 0$ for all $j\in[m]$,

  * •

$\sum_{j\in[m]}p_{j}=1$, and

  * •

$\sum_{i\in A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p_{j}=\sum_{j\in B_{k}}p_{j}$ for
each component $D_{k}$ in the disutility graph (sum of prices of chores in
$D_{k}$ equals the sum of total money of the agents in $D_{k}$).

Let $P$ be the set of all normalized price vectors. We first show that the set
$P$ is non-empty.

######  Observation 18.

We have $P\neq\emptyset$.

###### Proof.

Here we will make use of a general fact that will be useful for a proof later
as well.

######  Fact 19.

Let $Z\in\mathbb{R}^{n\times n}$ be a square matrix such that $Z_{ij}\geq 0$
for all $j\neq i$ (all the non-diagonal entries of $Z$ are non-negative) and
$\sum_{i\in[n]}Z_{ij}=0$ for all $j\in[n]$ (column sums are zero), then there
exists a vector $t\in\mathbb{R}^{n}_{\geq 0}$ such that
$\sum_{i\in[n]}t_{i}=1$ and $Z\cdot t=0$.

The proof of this fact can be found at the end of this section. Using this
fact, we will outline a proof that $P$ is non-empty. For each component
$D_{k}$ of the disutility matrix we pick a chore $b_{k}\in B_{k}$ and we set
$p_{j}=0$ for all $j\in B_{k}\setminus\left\\{b_{k}\right\\}$. Note that to
show that $P$ is non-empty, it suffices to show that there exists a vector
$p^{\prime}=\langle p^{\prime}_{1},p^{\prime}_{2},\dots,p^{\prime}_{d}\rangle$
(intuitively each $p^{\prime}_{k}$ corresponds to the price of chore $b_{k}\in
B_{k}$, i.e., $p_{b_{k}}$) such that $p^{\prime}_{k}\geq 0$ for all $k\in[d]$,
$\sum_{k\in[d]}p^{\prime}_{k}=1$ and we have,

$\displaystyle\sum_{i\in
A_{k}}\sum_{{k^{\prime}}\in[d]}w_{i,b_{k^{\prime}}}\cdot
p^{\prime}_{k^{\prime}}-p^{\prime}_{k}$ $\displaystyle=0$ for all $k\in[d]$
(7)

Let $W$ be the coefficient matrix of the system of equations in (7), i.e.,
$W\cdot p^{\prime}=0$ represents the system of equations in (7). Observe that
$W_{kk^{\prime}}=\sum_{i\in A_{k}}w_{i,b_{k^{\prime}}}$ if $k\neq k^{\prime}$
and $W_{kk}=\sum_{i\in A_{k}}w_{i,b_{k}}-1$. Therefore the non-diagonal
entries of $W$ are non-negative and also note that the column sum is zero:

$\displaystyle\sum_{k\in[d]}M_{kk^{\prime}}$
$\displaystyle=\sum_{k\in[d]}\sum_{i\in A_{k}}w_{i,b_{k^{\prime}}}-1$
$\displaystyle=\sum_{i\in[n]}w_{i,b_{k^{\prime}}}-1$ $\displaystyle=1-1$
(total endowment is one) $\displaystyle=0.$

Therefore $W$ satisfies all the conditions in Fact 19. Therefore, by Fact 19
there exists a $p^{\prime}\in\mathbb{R}^{d}_{\geq 0}$, such that
$\sum_{k\in[d]}p^{\prime}_{d}=1$ and $W\cdot p^{\prime}=0$. Therefore, $P$ is
non-empty. ∎

Since $P$ is defined by a set of linear equalities and inequalities, $P$ is
closed and convex too. Additionally, since $p\in\mathbb{R}^{m}_{\geq 0}$ and
$\sum_{j\in[m]}p_{j}=1$ for all $p\in P$, $P$ is compact. We now make a small
observation about any $p\in P$ that will be useful later.

######  Observation 20.

Consider any $p\in P$. For all $k\in[d]$, we have that the total price of
chores in a component is strictly larger than zero: $\sum_{j\in
B_{k}}p_{j}>0$.

###### Proof.

We prove this by contradiction. Assume otherwise and let $\ell\in[d]$ be such
that $\sum_{j\in B_{\ell}}p_{j}=0$. Since $p\in P$, we have $\sum_{i\in
A_{\ell}}\sum_{j\in[m]}w_{i,j}\cdot p_{j}=0$ as well. Consider any
$\ell^{\prime}\in[d]$ such that $(\ell,\ell^{\prime})\in E_{W}$ (recall that
$E_{W}$ is the edge set of the exchange graph $W$). By Condition 2, we have
that for each chore $b\in B_{\ell^{\prime}}$, there is an agent $a\in
A_{\ell}$ such that $w_{a,b}>0$. Therefore, the only way $\sum_{i\in
A_{\ell}}\sum_{j\in[m]}w_{i,j}\cdot p_{j}=0$ is if all the prices of the
chores in $B_{\ell^{\prime}}$ is $0$. This implies that if the sum of prices
of the chores in any component $D_{\ell}$ is zero, then the sum of prices of
the chores in all the components $D_{\ell^{\prime}}$ such that
$(\ell,\ell^{\prime})\in E_{W}$ is also zero. Since the exchange graph $W$ is
strongly connected, a repeated application of this argument will imply that
sum of prices of all chores is zero for every component, which is a
contradiction as we have $\sum_{j\in[m]}p_{j}=1$. ∎

An allocation $X\in\mathbb{R}_{\geq 0}^{n\times m}$, is called a _bounded
allocation_ if each $X_{ij}$ (quantifies the amount of chore $j$ allocated to
agent $i$) is non-negative and is at most
$m\cdot\tfrac{d_{\mathit{max}}}{d_{\mathit{min}}}$, where $d_{\mathit{max}}$
and $d_{\mathit{min}}$ refer to the largest and smallest entry less than
$\tau$ in the disutility matrix. Let $\mathbf{X}$ be the set of all bounded
allocations. Observe that the set $\mathbf{X}$ is non-empty, convex and
compact. Also, we have that $P$ is non-empty, convex and compact. We define a
compact, convex and non-empty subset of $\mathbb{R}^{(m+nm)}$,
$S=\bigcup_{p\in P}\bigcup_{X\in\mathbf{X}}\langle p,X\rangle$ 999We abuse
notation slightly here: $\langle p,X\rangle$ refers to the
$(m+nm)$-dimensional vector $\langle
p_{1},p_{2},\dots,p_{m},X_{11},X_{12},\dots,X_{nm}\rangle$..

##### Correspondence $\phi$.

Our goal is to define a _correspondence_ or equivalently a _set valued
function_ $\phi:S\rightarrow 2^{S}$, such that $\phi$ has at least one fixed
point and any fixed point of $\phi$ will correspond to competitive
equilibrium. We will first show some properties that if satisfied by $\phi$,
then $\phi$ will have at least one fixed point and any fixed point of $\phi$
will correspond to a competitive equilibrium. Then, we will define a $\phi$
that satisfies these properties.

##### Properties.

We first make some basic definitions that will help us to state the
properties. We call a bounded allocation $Y\in\mathbf{X}$ an _optimal
allocation at the price vector $p$_ if and only if,

  * •

$Y_{ij}>0$ only if $d(i,j)<\tau$,
$\tfrac{d(i,j)}{p_{j}}\leq\tfrac{d(i,\ell)}{p_{\ell}}$ for all $\ell\in[m]$,
and

  * •

$\sum_{j\in[m]}Y_{ij}\cdot p_{j}=\sum_{j\in[m]}w_{i,j}\cdot p_{j}$ for all
$i\in[n]$.

Let $\mathbf{X}^{p}\subseteq\mathbf{X}$ denote the set of all optimal
allocations at the price vector $p$. Right now, it may not be immediately
clear that $\mathbf{X}^{p}$ is non-empty. However, we show that this is indeed
the case, as agents are allowed to consume goods to a significant extent
($Y_{ij}$ is allowed to be as large as
$m\cdot\tfrac{d_{\mathit{max}}}{d_{\mathit{min}}}$).

######  Lemma 21.

For all $p\in P$, we have $\mathbf{X}^{p}\subseteq\mathbf{X}$ and
$\mathbf{X}^{p}\neq\emptyset$.

###### Proof.

By definition $\mathbf{X}^{p}\subseteq\mathbf{X}$. Therefore, it suffices to
show that it is non-empty. Consider any $p\in P$. Consider any agent $a\in
A_{k}$ (recall that $A_{k}$ is the set of agents that belong to the component
$D_{k}$ of the disutility graph). Let
$\mathbf{w}(a)=\sum_{j\in[m]}w_{a,j}\cdot p_{j}$. If $\mathbf{w}(a)=0$, then
we set $Y_{aj}=0$ for all $j\in[m]$ and we trivially have
$\sum_{j\in[m]}Y_{aj}\cdot p_{j}=\sum_{j\in[m]}w_{a,j}\cdot p_{j}=0$ and
$\langle Y_{a1},\dots,Y_{am}\rangle$ is an optimal bundle for agent $a$ at
$p$. So assume that $\mathbf{w}(a)>0$. Since $p\in P$, we have that the sum of
prices of the chores in $D_{k}$, $\sum_{j\in B_{k}}p_{j}=\sum_{i\in
A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p_{j}\geq\sum_{j\in[m]}w_{aj}\cdot
p_{j}=\mathbf{w}(a)$. This implies that there is at least one chore $b\in
B_{k}$ such that $p_{b}\geq\tfrac{\mathbf{w}(a)}{m}$. Let $b^{\prime}$ be a
chore such that $d(a,b^{\prime})<\tau$,
$\tfrac{d(a,b^{\prime})}{p_{b^{\prime}}}\leq\tfrac{d(a,\ell)}{p_{\ell}}$ for
all $\ell\in[m]$. This implies that
$\tfrac{d(a,b^{\prime})}{p_{b^{\prime}}}\leq\tfrac{d(a,b)}{p_{b}}$. Therefore,
we have that

$\displaystyle p_{b^{\prime}}$
$\displaystyle\geq\frac{d(a,b^{\prime})}{d(a,b)}\cdot p_{b}$
$\displaystyle\geq\frac{d_{\mathit{min}}}{d_{\mathit{max}}}\cdot p_{b}$
$\displaystyle\geq\frac{d_{\mathit{min}}}{md_{\mathit{max}}}\cdot\mathbf{w}(a).$

We set $Y_{ab^{\prime}}=\tfrac{\mathbf{w}(a)}{p_{b^{\prime}}}$. Observe that
$Y_{ab^{\prime}}\leq m\cdot\tfrac{d_{\mathit{max}}}{d_{\mathit{min}}}$.
Therefore, $Y$ is a bounded allocation. Also, note that each agent $a$ earns
her entire money of $\mathbf{w}(a)$ by doing
$\tfrac{\mathbf{w}(a)}{p_{b^{\prime}}}$ amount of chore $b^{\prime}$ such that
$d(a,b^{\prime})<\tau$,
$\tfrac{d(a,b^{\prime})}{p_{b^{\prime}}}\leq\tfrac{d(a,\ell)}{p_{\ell}}$ for
all $\ell\in[m]$. Thus, $Y$ is an optimal bundle also. Therefore,
$\mathbf{X}^{p}\neq\emptyset$. ∎

We are now ready to define the properties of $\phi$. For any point $\langle
p,X\rangle\in S$, consider any point $\langle
p^{\prime},X^{\prime}\rangle\in\phi(\langle p,X\rangle)$. Then,

  * •

Property $\mathbf{P}_{1}$: $X^{\prime}\in\mathbf{X}^{p}$ and $p^{\prime}\in
P$.

  * •

Property $\mathbf{P}_{2}$: For any two agents $i$ and $j$ that belong to the
same component of the disutility graph $D$ (say $i$, $j\in A_{k}$), and
$p_{j}\neq 0$, we have

$\displaystyle\frac{p^{\prime}_{i}}{p^{\prime}_{j}}$
$\displaystyle=\frac{p_{i}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
i},0)}{p_{j}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell j},0)}.$

.

  * •

Property $\mathbf{P}_{3}$: $\phi(\langle p,X\rangle)$ is non-empty and convex.

  * •

Property $\mathbf{P}_{4}$: $\phi$ has a _closed graph_ 101010A correspondence
$\phi:X\rightarrow 2^{Y}$ has a _closed graph_ if for all sequences
$\left\\{x_{n}\right\\}_{n\in\mathbb{N}}$ and
$\left\\{y_{n}\right\\}_{n\in\mathbb{N}}$, with $x_{n}\in X$ and
$y_{n}\in\phi(x_{n})$ for all $n$, such that $x_{n}\rightarrow x$ and
$y_{n}\rightarrow y$, we have $y\in\phi(x)$..

We will now show that any correspondence $\phi$ that satisfies
$\mathbf{P}_{1}$, $\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and $\mathbf{P}_{4}$ will
have at least one fixed point and any fixed point will correspond to
competitive equilibrium. We first show that $\phi$ has a fixed point.

######  Lemma 22.

Consider any correspondence $\phi$ that satisfies properties $\mathbf{P}_{1}$,
$\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and $\mathbf{P}_{4}$. $\phi$ has a fixed
point.

###### Proof.

By property $\mathbf{P}_{1}$ we have that if $\langle
p^{\prime},X^{\prime}\rangle\in\phi(\langle p,X\rangle)$, then $\langle
p^{\prime},X^{\prime}\rangle\in S$ (as $p^{\prime}\in P$ and
$X^{\prime}\in\mathbf{X}^{p}\subseteq\mathbf{X}$). Therefore,
$\phi:S\rightarrow 2^{S}$. The set $S$ is non-empty, compact and convex.
Furthermore, by properties $\mathbf{P}_{3}$ and $\mathbf{P}_{4}$, we have that
$\phi(\langle p,X\rangle)$ is non-empty and convex, and $\phi$ has a closed
graph. Therefore, by Kakutani’s fixed point theorem, $\phi$ has a fixed point.
∎

Now we show that any fixed point of a correspondence $\phi$ that satisfies
properties $\mathbf{P}_{1}$, $\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and
$\mathbf{P}_{4}$ gives a competitive equilibrium.

######  Lemma 23.

Consider any correspondence $\phi$ that satisfies properties $\mathbf{P}_{1}$,
$\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and $\mathbf{P}_{4}$. Consider any fixed
point $\langle p,X\rangle$ of $\phi$. Then $\langle p,X\rangle$ is a
competitive equilibrium.

###### Proof.

Consider any fixed point $\langle p,X\rangle\in\phi(\langle p,X\rangle)$. By
property $\mathbf{P}_{1}$ it follows that $X\in\mathbf{X}^{p}$. Now, it
suffices to show that we have $p_{j}>0$ for all $j\in[m]$ and
$\sum_{i\in[n]}X_{ij}=1$ for all chores $j\in[m]$. We first show that
$p_{j}>0$ for all $j\in[m]$. We prove this by contradiction. Let us assume
that there is some chore $b$ in some component $D_{\ell}$ of the disutility
graph such that $p_{b}=0$. Note that by Observation 20, there is at least one
chore $b^{\prime}\in B_{\ell}$ such that $p_{b^{\prime}}>0$. This implies that
for all agents $i\in A_{\ell}$, we have
$\tfrac{d(i,b^{\prime})}{p_{b^{\prime}}}<\tfrac{d(i,b)}{p_{b}}$. Therefore, we
have that $X_{ib}=0$ for all $i\in A_{\ell}$ and also for all $i\in[n]$ (as
$X_{i\ell}>0$ only if $d(i,\ell)<\tau$ and for all agents in $[n]\setminus
A_{k}$ we have $d(i,b)\geq\tau$), implying $\sum_{\ell\in[n]}X_{\ell b}=0$.
Now observe that,

$\displaystyle\frac{p^{\prime}_{b}}{p^{\prime}_{b^{\prime}}}$
$\displaystyle=\frac{p_{b}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b},0)}{p_{b^{\prime}}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell b^{\prime}},0)}$
(by property $\mathbf{{P}_{2}}$)
$\displaystyle=\frac{0+1}{p_{b^{\prime}}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b^{\prime}},0)}$ $\displaystyle\neq 0$
$\displaystyle=\frac{p_{b}}{p_{b^{\prime}}}.$

This implies that $p^{\prime}\neq p$, which is a contradiction to $\langle
p,X\rangle$ being a fixed point.

Therefore, we have $p_{j}>0$ for all $j\in[m]$. We now show that
$\sum_{i\in[n]}X_{ij}=1$ for all $j\in[m]$. We prove this also by
contradiction. So assume otherwise and for some chore $b\in B_{k}$ we have
$\sum_{i\in[n]}X_{ib}>1$ (or $\sum_{i\in[n]}X_{ib}<1$). Note that, since $p\in
P$, for the component $D_{k}$ of the disutility graph, we have,

$\displaystyle\sum_{j\in B_{k}}p_{j}$ $\displaystyle=\sum_{i\in
A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p_{j}.$ (8)

Also, since $X\in\mathbf{X}^{p}$, for every agent $i\in A_{k}$, we have
$\sum_{j\in[m]}w_{i,j}\cdot p_{j}=\sum_{j\in[m]}X_{ij}\cdot p_{j}=\sum_{j\in
B_{k}}X_{ij}\cdot p_{j}$. Substituting $\sum_{j\in[m]}w_{i,j}\cdot p_{j}$ as
$\sum_{j\in B_{k}}X_{ij}\cdot p_{j}$ in (8) we have,

$\displaystyle\sum_{j\in B_{k}}p_{j}$ $\displaystyle=\sum_{i\in
A_{k}}\sum_{j\in B_{k}}X_{ij}\cdot p_{j}$
$\displaystyle=\sum_{i\in[n]}\sum_{j\in B_{k}}X_{ij}\cdot p_{j}$
$\displaystyle=\sum_{j\in B_{k}}p_{j}\cdot(\sum_{i\in[n]}X_{ij})\enspace.$

Therefore, if $\sum_{i\in[n]}X_{ib}>1$ (or $\sum_{i\in[n]}X_{ib}<1$) for some
$b\in B_{k}$, then there exists a $b^{\prime}\in B_{k}$ such that
$\sum_{i\in[n]}X_{ib^{\prime}}<1$ (or $\sum_{i\in[n]}X_{ib^{\prime}}>1$). This
would imply that $\frac{p_{b}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b},0)}{p_{b^{\prime}}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b^{\prime}},0)}<\tfrac{p_{b}}{p_{b^{\prime}}}$ when $\sum_{i\in[n]}X_{ib}>1$
and $\frac{p_{b}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b},0)}{p_{b^{\prime}}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b^{\prime}},0)}>\tfrac{p_{b}}{p_{b^{\prime}}}$ when $\sum_{i\in[n]}X_{ib}<1$,
which is a contradiction (as
$\frac{p_{b}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b},0)}{p_{b^{\prime}}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
b^{\prime}},0)}=\tfrac{p_{b}}{p_{b^{\prime}}}$ if $\langle p,X\rangle$ is a
fixed point by property $\mathbf{P}_{2}$). ∎

Now, it suffices to show that there exists a correspondence $\phi$ that
satisfies all the four properties to show the existence of competitive
equilibrium for every instance $I\in\mathcal{I}$. To this end, we first define
a correspondence $\phi$ and show that it satisfies all the four properties.

##### Finding a Correspondence $\phi$ that Satisfies all the Properties.

Given a $p\in P$ and $X\in\mathbf{X}$, we define the vector $q=\langle
q_{1},q_{2},\dots,q_{m}\rangle$ such that

$\displaystyle q_{j}=p_{j}+\mathit{max}(1-\sum_{i\in[n]}X_{ij},0)\enspace.$
(9)

We will now outline a system of linear equations that needs to be satisfied by
a vector
$\tilde{p}=\langle\tilde{p}_{1},\tilde{p}_{2},\dots,\tilde{p}_{d}\rangle$
(recall that $d$ is the number of components in the disutility graph $D$). So
think of each $\tilde{p}_{i}$ as a variable now. As of now, let us think of
each $\tilde{p}_{k}$ as the sum of prices of the chores in the component
$D_{k}$ and $\tfrac{q_{j}}{Q_{k}}\cdot\tilde{p}_{k}$ as the price of each
chore $j\in B_{k}$, where $Q_{k}=\sum_{j\in B_{k}}q_{j}$. We make a small
observation about $Q_{k}$, which will be useful later.

######  Claim 24.

For all $k\in[d]$, we have $Q_{k}>0$.

###### Proof.

Each $q_{j}$ is at least as large as $p_{j}$, implying $Q_{k}=\sum_{j\in
B_{k}}q_{j}\geq\sum_{j\in B_{k}}p_{j}$ and by Observation 20 we have
$\sum_{j\in B_{k}}p_{j}>0$. ∎

With these prices ($\tilde{p}_{1},\tilde{p}_{2},\dots,\tilde{p}_{d}$) in mind,
for each component $D_{k}$ of $D$, we write the equation (variables being
$\bigcup_{k\in[d]}\tilde{p}_{k}$) that represents the total money the agents
earn in the component equals the total prices of the chores in the same
component.

$\displaystyle\sum_{i\in A_{k}}\sum_{k^{\prime}\in[d]}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\frac{q_{j}}{Q_{k^{\prime}}}\cdot\tilde{p}_{k^{\prime}}-\tilde{p}_{k}$
$\displaystyle=0\enspace.$ (10)

We represent the system of equations in (10) as

$\displaystyle M\cdot\tilde{p}=\mathbf{0}\enspace.$ (11)

First observe that every entry of the matrix $M$ is bounded: This is primarily
due to the fact that $Q_{k}>0$ for all $k\in[d]$.

######  Observation 25.

We have $M_{kk^{\prime}}\geq 0$ as long as $k\neq k^{\prime}$ (every non-
diagonal entry of $M$ is non-zero) and $\sum_{k\in[d]}M_{kk^{\prime}}=0$ for
all $k^{\prime}\in[d]$ (column sums are zero).

###### Proof.

We first carefully look at any column $M_{*k^{\prime}}$ of $M$. Note that for
all $k\neq k^{\prime}$, we have, $M_{kk^{\prime}}=\sum_{i\in A_{k}}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\tfrac{q_{j}}{Q_{k^{\prime}}}$. We have
$M_{kk}=\sum_{i\in A_{k}}\sum_{j\in B_{k}}w_{i,j}\cdot\tfrac{q_{j}}{Q_{k}}-1$.
Therefore, every non-diagonal entry in $M$ is non-negative. Now we just need
to show that $\mathbf{1}^{T}\cdot M_{*k^{\prime}}=0$. Observe,

$\displaystyle\mathbf{1}^{T}\cdot M_{*k^{\prime}}$
$\displaystyle=\sum_{k\in[d]}\sum_{i\in A_{k}}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\tfrac{q_{j}}{Q_{k^{\prime}}}-1$
$\displaystyle=\tfrac{1}{Q_{k^{\prime}}}\cdot\sum_{j\in
B_{k^{\prime}}}q_{j}\cdot\sum_{k\in[d]}\sum_{i\in A_{k}}w_{i,j}-1$
$\displaystyle=\tfrac{1}{Q_{k^{\prime}}}\cdot\sum_{j\in
B_{k^{\prime}}}q_{j}\cdot\sum_{i\in[n]}w_{i,j}-1$
$\displaystyle=\tfrac{1}{Q_{k^{\prime}}}\cdot\sum_{j\in
B_{k^{\prime}}}q_{j}-1$ $\displaystyle=0.$

This shows that $\mathbf{1}^{T}\cdot M=\mathbf{0}^{T}$. ∎

We first make some observations about the solution to the system of equations
in (11) (and consequently (10)). Observe that $M$ satisfies all the conditions
in Fact 19. Therefore, we have

######  Observation 26.

There exists a solution to the system of equations in (11) such that
$\tilde{p}_{j}\geq 0$ for all $j\in[d]$ and $\sum_{j\in[d]}\tilde{p}_{j}=1$.

We are now ready to define the correspondence. Given any $\langle
p,X\rangle\in S$, we determine the vector $q$ as in (9). Observe that $q$ is a
function of $p$ and $X$. Hence, from now on, for clarity we would write the
vector $q$, the scalars $Q_{k}$ for all $k\in[d]$ as $q(p,X)$ and $Q_{k}(p,X)$
respectively. Let $\tilde{P}(p,X)\subseteq 2^{R^{d}_{\geq 0}}$ be the set of
all vectors that satisfy the conditions in Observation 26. For each
$\tilde{p}\in\tilde{P}(p,X)$, we define the vector
$\overline{p}(\tilde{p})=\langle\overline{p}_{1}(\tilde{p}),\dots,\overline{p}_{m}(\tilde{p})\rangle$
as follows: For every chore $j$ that lies in the component $D_{k}$ of the
disutility graph $D$, we define

$\displaystyle\overline{p}_{j}(\tilde{p})=\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}\enspace.$

Let
$\overline{P}(p,X)=\left\\{\overline{p}(\tilde{p})\mid\tilde{p}\in\tilde{P}(p,X)\right\\}$.
Given any $\langle p,X\rangle\in S$, we define,

$\displaystyle\phi(\langle
p,X\rangle)=\left\\{\langle\overline{p},X^{\prime}\rangle\mid\overline{p}\in\overline{P}(p,X)\text{
and }X^{\prime}\in\mathbf{X}^{p}\right\\}\enspace.$

For the rest of this section, we will now show that $\phi$ satisfies
properties $\mathbf{P}_{1}$, $\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and
$\mathbf{P}_{4}$.

#####  $\phi$ satisfies properties $\mathbf{P}_{1}$, $\mathbf{P}_{2}$,
$\mathbf{P}_{3}$ and $\mathbf{P}_{4}$.

######  Lemma 27.

$\phi$ satisfies property $\mathbf{P}_{1}$.

###### Proof.

We need to show that $p^{\prime}\in P$ and
$X^{\prime}\in\mathbf{X}^{p}\subseteq\mathbf{X}$. Note that by the definition
of $\phi$ we have $X^{\prime}\in\mathbf{X}^{p}\subseteq\mathbf{X}$. Therefore,
we only need to show that $p^{\prime}\in P$. Given $p$ and $X$ let $q(p,X)$ be
the vector obtained as in (9) and let $Q_{k}(p,X)=\sum_{j\in B_{k}}q_{j}(p,X)$
be the scalars for all $k\in[d]$. Then $p^{\prime}=\overline{p}(\tilde{p})$
for some $\tilde{p}\in\tilde{P}(p,X)$. Now we make three claims which show
that $p^{\prime}\in P$.

######  Claim 28.

We have $p^{\prime}_{j}\geq 0$ for all $j\in[m]$.

###### Proof.

Let us consider any chore $j$ that belongs to the component $D_{k}$ in the
disutility matrix.

$\displaystyle p^{\prime}_{j}$ $\displaystyle=\overline{p}_{j}(\tilde{p})$
$\displaystyle=\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}\enspace.$

Observe from the definition of $q(p,X)$ in (9) that $q_{\ell}\geq 0$ for all
$\ell\in[m]$. Also, from the definition of the vector $\tilde{p}$, we have
$\tilde{p}_{\ell}\geq 0$ for all $\ell\in[d]$. This implies that
$p^{\prime}_{j}\geq 0$. ∎

######  Claim 29.

We have $\sum_{j\in[m]}p^{\prime}_{j}=1$.

###### Proof.

We have
$\sum_{j\in[m]}p^{\prime}_{j}=\sum_{j\in[m]}\overline{p}_{j}(\tilde{p})=\sum_{k\in[d]}\sum_{j\in
B_{k}}\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}=\sum_{k\in[d]}\tilde{p}_{k}=1$.
∎

######  Claim 30.

For each component $D_{k}$ of the disutility graph, we have $\sum_{i\in
A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p^{\prime}_{j}=\sum_{j\in
B_{k}}p^{\prime}_{j}$.

###### Proof.

We have,

$\displaystyle\sum_{i\in A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p^{\prime}_{j}$
$\displaystyle=\sum_{i\in
A_{k}}\sum_{j\in[m]}w_{i,j}\cdot\overline{p}_{j}(\tilde{p})$
$\displaystyle=\sum_{i\in A_{k}}\sum_{k^{\prime}\in[d]}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\frac{q_{j}(p,X)}{Q_{k^{\prime}}(p,X)}\cdot\tilde{p}_{k^{\prime}}\enspace.$

Since $\tilde{p}$ satisfies (11) and therefore also (10), we have $\sum_{i\in
A_{k}}\sum_{k^{\prime}\in[d]}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\frac{q_{j}(p,X)}{Q_{k^{\prime}}(p,X)}\cdot\tilde{p}_{k^{\prime}}=\tilde{p}_{k}$.
Therefore, we have

$\displaystyle\sum_{i\in A_{k}}\sum_{j\in[m]}w_{i,j}\cdot p^{\prime}_{j}$
$\displaystyle=\tilde{p}_{k}$ $\displaystyle=\sum_{j\in
B_{k}}\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$
$\displaystyle=\sum_{j\in B_{k}}\overline{p}_{j}(\tilde{p})$
$\displaystyle=\sum_{j\in B_{k}}p^{\prime}_{j}.\qed$

This shows that $p^{\prime}\in P$ and completes the proof. ∎

######  Lemma 31.

$\phi$ satisfies property $\mathbf{P}_{2}$.

###### Proof.

Consider any $\langle p^{\prime},X^{\prime}\rangle\in\phi(\langle
p,X\rangle)$. Let $i,j$ be two chores in the component $D_{k}$ of the
disutility graph such that $p^{\prime}_{j}\neq 0$. Since
$p^{\prime}_{j}=\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}\neq 0$, we
have $\tilde{p}_{k}\neq 0$. Now observe that,

$\displaystyle\frac{p^{\prime}_{i}}{p^{\prime}_{j}}$
$\displaystyle=\frac{\overline{p}_{i}(\tilde{p})}{\overline{p}_{j}(\tilde{p})}$
$\displaystyle=\frac{\frac{q_{i}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}}{\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}}$
$\displaystyle=\frac{q_{i}(p,X)}{q_{j}(p,X)}$ $\displaystyle(\text{as
$Q_{k}(p,X)\neq 0$ and $\tilde{p}_{k}\neq 0$})$
$\displaystyle=\frac{p_{i}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell
i},0)}{p_{j}+\mathit{max}(1-\sum_{\ell\in[n]}X_{\ell j},0)}\enspace.$
$\displaystyle(\text{by definition of $q(p,X)$ in\leavevmode\nobreak\
\eqref{qdefinition}})$

∎

######  Lemma 32.

$\phi$ satisfies property $\mathbf{P}_{3}$.

###### Proof.

We first show that $\mathbf{X}^{p}$ is convex. Consider $Y\in\mathbf{X}^{p}$
and $Y^{\prime}\in\mathbf{X}^{p}$. Let $Y^{\prime\prime}=\lambda\cdot
Y+(1-\lambda)\cdot Y^{\prime}$ for some $\lambda\in[0,1]$. First observe that
$0\leq\mathit{min}(Y_{ij},Y^{\prime}_{ij})\leq
Y^{\prime\prime}_{ij}\leq\mathit{max}(Y_{ij},Y^{\prime}_{ij})\leq
m\cdot\tfrac{d_{\mathit{max}}}{d_{\mathit{min}}}$. Therefore,
$Y^{\prime\prime}\in\mathbf{X}$. Also, notice that we have $Y_{ij}>0$ only if
$d(i,j)<\tau$ and $\tfrac{d(i,j)}{p_{j}}\leq\tfrac{d(i,{\ell})}{p_{\ell}}$ for
all $\ell\in[m]$. Therefore, we also have $Y^{\prime}_{ij}>0$ only if
$d(i,j)<\tau$ and $\tfrac{d(i,j)}{p_{j}}\leq\tfrac{d(i,{\ell})}{p_{\ell}}$ for
all $\ell\in[m]$. Lastly we have,

$\displaystyle\sum_{j\in[m]}Y^{\prime\prime}_{ij}\cdot p_{j}$
$\displaystyle=\sum_{j\in[m]}(\lambda\cdot Y_{ij}+(1-\lambda)\cdot
Y^{\prime}_{ij})\cdot p_{j}$
$\displaystyle=\lambda\cdot(\sum_{j\in[m]}Y_{ij}\cdot
p_{j})+(1-\lambda)\cdot(\sum_{j\in[m]}Y^{\prime}_{ij}\cdot p_{j})$
$\displaystyle=\lambda\cdot\sum_{j\in[m]}w_{i,j}\cdot
p_{j}+(1-\lambda)\cdot\sum_{j\in[m]}w_{i,j}\cdot p_{j}$
$\displaystyle=\sum_{j\in[m]}w_{i,j}\cdot p_{j}\enspace.$

Thus, $Y^{\prime\prime}\in\mathbf{X}^{p}$. Therefore, $\mathbf{X}^{p}$ is
convex and non-empty (by Lemma 21).

We now show that $\overline{P}(p,X)$ is convex and non-empty. By Observation
26, we have that $\tilde{P}(p,X)$ is non-empty and therefore $\overline{P}$ is
also non-empty. To show that it is convex, consider two price vectors $t$ and
$t^{\prime}$ in $\tilde{P}(p,X)$. To show convexity, we need to show that
$\lambda\cdot\overline{p}(t)+(1-\lambda)\cdot\overline{p}(t^{\prime})$ is in
$\overline{P}$ for all $\lambda\in[0,1]$. Note that for all $j\in[m]$, that
belongs to the component $D_{k}$ in the disutility graph, we have

$\displaystyle\lambda\cdot\overline{p}_{j}(t)+(1-\lambda)\cdot\overline{p}_{j}(t^{\prime})=\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot(\lambda\cdot
t_{j}+(1-\lambda)\cdot t^{\prime}_{j})\enspace.$

Thus it suffices to show that $\lambda\cdot t+(1-\lambda)\cdot
t^{\prime}\in\tilde{P}(p,X)$. This is true as $\tilde{P}(p,X)$ is defined by a
set of linear equalities and inequalities, and therefore is convex.

Therefore, we have that both the sets $\overline{P}(p,X)$ and $\mathbf{X}^{p}$
are non-empty and convex. thus, $\phi(\langle p,X\rangle)$ is also non-empty
and convex as it is the Cartesian product of $\overline{P}(p,X)$ and
$\mathbf{X}^{p}$. ∎

######  Lemma 33.

$\phi$ satisfies property $\mathbf{P}_{4}$.

###### Proof.

Consider a sequence $\langle p^{n},X^{n}\rangle$ that converges to $\langle
p^{*},X^{*}\rangle$ and $\langle p^{n},X^{n}\rangle\in S$ for all $n$.
Similarly, consider the sequence $\langle r^{n},Y^{n}\rangle$ that converges
to $\langle r^{*},Y^{*}\rangle$ such that $\langle
r^{n},Y^{n}\rangle\in\phi(\langle p^{n},X^{n}\rangle)$ for all $n$. To show
that $\phi$ has a closed graph, we need to show that $\langle
r^{*},Y^{*}\rangle\in\phi(\langle p^{*},X^{*}\rangle)$. To show that, $\langle
r^{*},Y^{*}\rangle\in\phi(\langle p^{*},X^{*}\rangle)$, we need to show,

  1. 1.

$r^{*}\in\overline{P}(p^{*},X^{*})$, and

  2. 2.

$Y^{*}\in\mathbf{X}^{p^{*}}$.

##### Proving $r^{*}\in\overline{P}(p^{*},X^{*})$:

We first outline the necessary and sufficient condition for any vector
$p^{\prime}$ to be in $\overline{P}(p,X)$, as this will be useful for our
proof.

######  Observation 34.

$p^{\prime}\in\overline{P}(p,X)$ if and only if

  1. 1.

$p^{\prime}\in P$, and

  2. 2.

for each chore $j$ in component $D_{k}$, we have
$p^{\prime}_{j}=\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\sum_{j\in
B_{k}}p^{\prime}_{j}$.

###### Proof.

We first show the “if” direction. For each component $D_{k}$ of the disutility
graph, let $\tilde{p}_{k}=\sum_{j\in B_{k}}p^{\prime}_{j}$. Then for each
chore $j\in B_{k}$, we have
$p^{\prime}_{j}=\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$. Let
$\tilde{p}=\langle\tilde{p}_{1},\dots,\tilde{p}_{d}\rangle$. To show that
$p^{\prime}\in\overline{P}(p,X)$, it suffices to show that
$\tilde{p}\in\tilde{P}(p,X)$. To this end, observe that
$\tilde{p}_{k}=\sum_{j\in B_{k}}p^{\prime}_{j}\geq 0$ as $p^{\prime}_{j}\geq
0$ for all $j\in[m]$ (as $p^{\prime}\in P$). Furthermore,
$\sum_{k\in[d]}\tilde{p}_{k}=\sum_{j\in[m]}p^{\prime}_{j}=1$ (as
$p^{\prime}\in P$). Now, to show $\tilde{p}\in\tilde{P}(p,X)$ it suffices to
show that $\tilde{p}$ satisfies the system of equations in (11) or
equivalently those in (10). To this end, since $p^{\prime}\in P$, for each
component $D_{k}$ we have,

$\displaystyle\sum_{i\in A_{k}}\sum_{j\in[m]}w_{i,j}\cdot
p^{\prime}_{j}=\sum_{j\in B_{k}}p^{\prime}_{j}\enspace.$

Or equivalently,

$\displaystyle\sum_{i\in A_{k}}\sum_{k^{\prime}\in[d]}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot p^{\prime}_{j}=\sum_{j\in
B_{k}}p^{\prime}_{j}\enspace.$

Substituting every $p^{\prime}_{j}$ as
$\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$ where chore $j$ is in the
component $D_{k}$ we have,

$\displaystyle\sum_{i\in A_{k}}\sum_{k^{\prime}\in[d]}\sum_{j\in
B_{k^{\prime}}}w_{i,j}\cdot\frac{q_{j}(p,X)}{Q_{k}(p,X)}\tilde{p}_{k^{\prime}}=\tilde{p}_{k}\enspace.$

Therefore, $\tilde{p}_{k}$ satisfies (10). Thus $\tilde{p}\in\tilde{P}(p,X)$.

Now we show the “only if” direction. So assume
$p^{\prime}\in\overline{P}(p,X)$. Then, by Claims 28, 29 and 30 we have that
$p^{\prime}\in P$. Also by the definition of $\overline{P}(p,X)$, we also have
that there exists a vector
$\tilde{p}=\langle\tilde{p}_{1},\dots,\tilde{p}_{d}\rangle$ such that for all
$j\in[m]$ we have
${p}^{\prime}_{j}=\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$ where
$D_{k}$ is the component in the disutility graph containing chore $j$. So it
just suffices to show that $\tilde{p}_{k}=\sum_{j\in B_{k}}p^{\prime}_{j}$ for
all $k\in[d]$. Now observe that,

$\displaystyle\sum_{j\in B_{k}}p^{\prime}_{j}$ $\displaystyle=\sum_{j\in
B_{k}}\frac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$
$\displaystyle=\frac{\sum_{j\in
B_{k}}q_{j}(p,X)}{Q_{k}(p,X)}\cdot\tilde{p}_{k}$
$\displaystyle=\tilde{p}_{k}.\qed$

Now we make an observation about the continuity of the functions $q(p,X)$ and
$Q_{k}(p,X)=\sum_{j\in B_{k}}q_{j}(p,X)$ for all $k\in[d]$. Given $p$ and $X$,
let $q(p,X)$ be the vector obtained as in (9). Observe that $q(p,X)$ is a
continuous function in $p$ and $X$ for all $p\in P$ and $X\in\mathbf{X}$. As a
result, even $Q_{k}(p,X)$ is a continuous function in $p$ and $X$ for all
$k\in[d]$. We are now ready to show that $r^{*}\in\overline{P}(p^{*},X^{*})$.

The $r^{*}$ is the limit of the sequence $r^{n}$. Since for all $n$, $\langle
r^{n},Y^{n}\rangle\in\phi(\langle p^{n},X^{n}\rangle)$, we can conclude that
each $r^{n}\in P$. Since the set $P$ is compact (and therefore closed), we
have that $r^{*}\in P$ as well. Now, by Observation 34 it suffices to show
that for each chore $j$ in component $D_{k}$, we have
$r^{*}_{j}=\tfrac{q_{j}(p^{*},X^{*})}{Q_{k}(p^{*},X^{*})}\cdot\sum_{j^{\prime}\in
B_{k}}r^{*}_{j^{\prime}}$. Again, since every
$r^{n}\in\overline{P}(p^{n},X^{n})$, we have for each chore $j$ in component
$D_{k}$,
$r^{n}_{j}=\tfrac{q_{j}(p^{n},X^{n})}{Q_{k}(p^{n},X^{n})}\cdot\sum_{j^{\prime}\in
B_{k}}r^{n}_{j^{\prime}}$. Let
$f_{j}(r,p,X)=r_{j}-\tfrac{q_{j}(p,X)}{Q_{k}(p,X)}\cdot\sum_{j^{\prime}\in
B_{k}}r_{j^{\prime}}$. Observe that for all $j\in[m]$ the limit of the
sequence $h^{n}_{j}=f_{j}(r^{n},p^{n},X^{n})$, $h^{*}_{j}$ is zero (as
$h^{n}_{j}$ is zero for all $n$). Again, since $q(p,X)$ and $Q_{k}(p,X)$ (for
all $k\in[d]$) are continuous functions in $p\in P$ and $X\in\mathbf{X}$, and
$Q_{k}(p,X)>0$ (for all $k\in[d]$) by Claim 24 for all $p\in P$ and
$X\in\mathbf{X}$, we can conclude that $f_{j}(r,p,X)$ is well defined and also
a continuous function in $p$, $X$ and $r$ for all $j\in[m]$. Thus the limit of
the sequence $h^{n}_{j}=f_{j}(r^{n},p^{n},X^{n})$ is
$h^{*}_{j}=f_{j}(r^{*},p^{*},X^{*})=r^{*}_{j}-\tfrac{q_{j}(p^{*},X^{*})}{Q_{k}(p^{*},X^{*})}\cdot\sum_{j^{\prime}\in
B_{k}}r^{*}_{j^{\prime}}$. Since we know that $h^{*}_{j}=0$ for all $j\in[m]$,
we can conclude that for all $j\in[m]$, we have
$r^{*}_{j}-\tfrac{q_{j}(p^{*},X^{*})}{Q_{k}(p^{*},X^{*})}\cdot\sum_{j\in
B_{k}}r^{*}_{j}=0$, implying
$r^{*}_{j}=\tfrac{q_{j}(p^{*},X^{*})}{Q_{k}(p^{*},X^{*})}\cdot\sum_{j\in
B_{k}}r^{*}_{j}$.

##### Proving $Y^{*}\in\mathbf{X}^{p^{*}}$:

To show $Y^{*}\in X^{p^{*}}$, we need to show, for every agent $i$,

  1. 1.

$Y^{*}_{ij}>0$ only if
$\tfrac{d(i,j^{\prime})}{p^{*}_{j}}\leq\tfrac{d(i,j)}{p^{*}_{j^{\prime}}}$ for
all $j^{\prime}\in[m]$, and

  2. 2.

$\sum_{j\in[m]}w_{i,j}\cdot p^{*}_{j}=\sum_{j\in[m]}Y^{*}_{ij}\cdot
p^{*}_{j}$.

We first show part 1 by contradiction, Assume that there exists $i$, $j$ and
$j^{\prime}$ such that $Y^{*}_{ij}>\beta>0$ and
$\tfrac{d(i,j)}{p^{*}_{j}}>\tfrac{d(i,j^{\prime})}{p^{*}_{j^{\prime}}}(1+\delta)$
for some $\delta>0$. Since $p^{*}\in P$, by Observation 20 we have that there
is at least one chore in each component with a non-zero price, and therefore,
we can assume without loss of generality that $p^{*}_{j^{\prime}}>0$. Let
$\varepsilon>0$ be such that
$\varepsilon\ll\mathit{min}(\beta,\tfrac{d(i,j)\cdot
p^{*}_{j^{\prime}}-(1+\delta)\cdot d(i,j^{\prime})\cdot
p^{*}_{j}}{(1+\delta)\cdot d(i,j^{\prime})+d(i,j)})$. Such an $\varepsilon$
exists as $\tfrac{d(i,j)\cdot p^{*}_{j^{\prime}}-(1+\delta)\cdot
d(i,j^{\prime})\cdot p^{*}_{j}}{(1+\delta)\cdot d(i,j^{\prime})+d(i,j)}>0$ for
all values of $p^{*}_{j}$: when $p^{*}_{j}=0$, then $\tfrac{d(i,j)\cdot
p^{*}_{j^{\prime}}}{(1+\delta)\cdot d(i,j^{\prime})+d(i,j)}>0$ as
$p^{*}_{j^{\prime}}>0$ and when $p^{*}_{j}>0$, then $d(i,j)\cdot
p^{*}_{j^{\prime}}-(1+\delta)\cdot d(i,j^{\prime})\cdot p^{*}_{j}>0$ as
$\tfrac{d(i,j)}{p^{*}_{j}}>(1+\delta)\cdot\tfrac{d(i,j)}{p^{*}_{j^{\prime}}}$.
Since $Y^{n}$ converges to $Y^{*}$ and $p^{n}$ converges to $p^{*}$, we know
that there exists an $n_{0}\in\mathbb{N}$ be such that for $n>{n}_{0}$ we have
$|Y^{*}_{ij}-Y_{ij}|<\varepsilon$ and $|p^{*}_{j}-p^{n}_{j}|<\varepsilon$ and
$|p^{*}_{j^{\prime}}-p^{n}_{j^{\prime}}|<\varepsilon$. It can be verified
easily that for our choice of $\varepsilon$ we have $Y^{n}_{ij}>0$, and
$\tfrac{d(i,j)}{p^{n}_{j}}>\tfrac{d(i,j)}{p^{n}_{j^{\prime}}}$, for all
$n>n_{0}$, which implies that $Y^{n}\notin\mathbf{X}^{p^{n}}$, which is a
contradiction.

We also prove part 2 by contradiction. Assume that $\sum_{j\in[m]}w_{i,j}\cdot
p^{*}_{j}-\sum_{j\in[m]}Y^{*}_{ij}\cdot p^{*}_{j}=\delta$ for some non-zero
$\delta$. Since $Y^{n}$ converges to $Y^{*}$ and $p^{n}$ converges to $p^{*}$,
we know that for every $\varepsilon>0$, there exists an $n_{0}\in\mathbb{N}$
be such that for $n>{n}_{0}$ we have $|Y^{*}_{ij}-Y_{ij}|<\varepsilon$ and
$|p^{*}_{j}-p^{n}_{j}|<\varepsilon$ for all $j\in[m]$. Therefore, by choosing
a sufficiently small $\varepsilon$ we can ensure that
$\sum_{j\in[m]}w_{i,j}\cdot p^{n}_{j}-\sum_{j\in[m]}Y^{n}_{ij}\cdot
p^{n}_{j}\neq 0$, for all $n>n_{0}$, which would imply that
$Y^{n}\notin\mathbf{X}^{p^{n}}$, which is a contradiction. ∎

We are now ready to state the main result of this section

######  Theorem 35.

Every instance $I\in\mathcal{I}$ admits a competitive efficient allocation.

###### Proof.

We defined a correspondence $\phi$ that satisfies properties $\mathbf{P}_{1}$,
$\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and $\mathbf{P}_{4}$ by Lemmas 27, 31, 32
and 33. By Lemma 22 we have that any correspondence that satisfies the
properties $\mathbf{P}_{1}$, $\mathbf{P}_{2}$, $\mathbf{P}_{3}$ and
$\mathbf{P}_{4}$ has a fixed point. Finally, by Lemma 23, any fixed point of
this correspondence will correspond to competitive equilibrium in $I$.
Therefore, our correspondence $\phi$ has at least one fixed point and this
fixed point corresponds to a competitive equilibrium. ∎

##### Proof of Fact 19:

Recall Fact 19.

######  Fact.

Let $Z\in\mathbb{R}^{n\times n}$ be a square matrix such that $Z_{ij}\geq 0$
for all $j\neq i$ (all the non-diagonal entries of $Z$ are non-negative) and
$\sum_{i\in[n]}Z_{ij}=0$ (column sums are zero), then there exists a vector
$t\in\mathbb{R}^{n}_{\geq 0}$ such that $\sum_{i\in[n]}t_{i}=1$ and $Z\cdot
t=0$.

###### Proof.

Let $\lambda\gg\mathit{max}_{i,j\in[n]}(Z_{ij})$. Let
$Z^{\prime}=\tfrac{1}{\lambda}Z$. Observe that every $t$ that satisfies
$Z^{\prime}\cdot t=0$, also satisfies $Z\cdot t=0$ and vice versa. Also, each
entry in the matrix $Z^{\prime}$ has absolute value is less than one. Let
$Z^{\prime\prime}=(Z^{\prime}+I)$ where $I$ is the identity matrix. Note that
every entry in the matrix $Z^{\prime\prime}$ is non-negative. Also every $t$
that satisfies $Z^{\prime\prime}\cdot t=t$, also satisfies $Z^{\prime}\cdot
t=0$ and therefore also satisfies $Z\cdot t=0$ and vice versa. From here on,
we will be dealing with the following system of equations

$\displaystyle Z^{\prime\prime}\cdot t=t\enspace.$ (12)

We first observe that the matrix $Z^{\prime\prime}$ is column stochastic: For
all $j\in[n]$, we have

$\displaystyle\sum_{i\in[n]}Z^{\prime\prime}_{ij}$
$\displaystyle=\sum_{i\in[n]}(\frac{1}{\lambda}\cdot Z_{ij}+I_{ij})$
$\displaystyle=\sum_{i\in[n]}\frac{1}{\lambda}\cdot Z_{ij}+1$
$\displaystyle=0+1$ $\displaystyle(\text{Column sums are zero in $Z$})$
$\displaystyle=1\enspace.$

Now, let $R=\left\\{r\in\mathbb{R}^{n}_{\geq
0}\mid\sum_{j\in[n]}r_{j}=1\right\\}$. Observe that the set $R$ is non-empty,
convex and compact. We first make a small claim.

######  Claim 36.

Let $r^{\prime}=Z^{\prime\prime}\cdot r$. If $r\in R$ then $r^{\prime}\in R$.

###### Proof.

Since every entry in the matrix $Z^{\prime\prime}$ and every component of the
vector $r$ is non-negative, we also have that every component of $r^{\prime}$
is also non-negative: $r^{\prime}_{j}\geq 0$ for all $j\in[d]$. Now observe
that

$\displaystyle\sum_{j\in[n]}r^{\prime}_{j}$ $\displaystyle=\mathbf{1}^{T}\cdot
r^{\prime}$ $\displaystyle=\mathbf{1}^{T}\cdot Z^{\prime\prime}\cdot r$
$\displaystyle=\mathbf{1}^{T}\cdot r$ $\displaystyle(\text{as
$Z^{\prime\prime}$ is column stochastic})$ $\displaystyle=\sum_{j\in[m]}r_{j}$
$\displaystyle=1.$

Thus, $r^{\prime}\in R$. ∎

We define $f:\mathbb{R}\rightarrow\mathbb{R}$ such that
$f(r)=Z^{\prime\prime}\cdot r$. Observe that $f$ is also continuous. Thus, by
Brouwer’s fixed point theorem there is a $t\in R$, such that $f(t)=t$ or
equivalently $Z^{\prime\prime}\cdot t=t$. ∎

##  4 Hardness of Finding Equilibrium under Sufficiency Conditions

In this section, we show that chore division may still be intractable even for
the instances that satisfy Conditions 1 and 2 mentioned in Section 3. We show
that it is PPAD-hard to find a competitive equilibrium on instances that
satisfy Conditions 1 and 2 in Section 3. We will show that any polynomial time