\section{Introduction}

\begin{comment}
The competitive equilibrium notion, also known as market or Walrasian equilibrium, is a key economic concept, which models the allocation of resources at the steady state in competitive economies. The paradigmatic model is the pure exchange economy, where a set of agents come to the market, each bringing a bundle of goods for sale. 
The goods have prices posted on them and the agents sell their goods at those prices and use the money obtained to purchase other goods that they need.
Competitive equilibria are outcomes---each consisting of a vector of prices for the goods and allocations for the agents---where supply and demand are perfectly balanced and the market is said to clear. Competitive equilibria exist under mild conditions in exchange economies with divisible goods and satisfy very strong fairness and efficiency properties \cite{BS00,AD54,Walras74}. In particular, every competitive equilibrium leads to a Pareto optimal \footnote{An allocation is Pareto optimal {\fed (or economically efficient)} if there is no other allocation in which all the agents are at least as happy and at least one agent is strictly happier.} allocation of the resources, and every Pareto optimal allocation can be supported in a competitive equilibrium.
\end{comment}

\begin{comment}
{\fed The first paragraph reads nicely but seems to me too general (as if it is an encyclopedia article). There some other issues:
	\begin{itemize}
		\item  it is not fully precise (What is a "competitive economy"? It is not a well-defined term, did you mean a "perfect competition"? None of the mentioned papers touch any fairness issues.)
		\item the connection between general equilibrium theory and fair division (where we have no money) remained opaque.
	\end{itemize}
 I suggest to reshape the beginning of the Intro the following way (my wording is far from ideal, but I hope that it clarifies the logic of what (and why) we did for the reader):
\end{comment}

The competitive equilibrium notion, also known as market or Walrasian equilibrium,  is a key economic concept that models the allocation of resources at the steady state of an economy when supply equals demand. The economic theory of general equilibrium originated from the ideas of Walras \cite{Walras74} and became mathematically rigorous since the work of Arrow-Debreu \cite{AD54}, who proved existence of equilibrium under mild conditions.
	
Our work is motivated by applications of competitive equilibrium to the problem of fair allocation of resources among agents with different tastes, when monetary compensations are not allowed. This extremely fruitful connection between the theory of general equilibrium and economic design was pioneered by Varian \cite{Varian74}. The idea was to give each agent a unit amount of ``virtual'' money and equalize demand and supply: find  prices and an allocation such that when each agent spends her money on the most preferred bundles she can afford, all the resources are bought and all the money is spent. This rule is called the competitive equilibrium from equal incomes (CEEI) or the \emph{the competitive rule}.

The resulting allocation has the remarkable fairness property of envy-freeness, since all the agents have equal budgets and select their most preferred bundles, and is Pareto optimal.\footnote{An allocation is Pareto optimal if there is no other allocation in which all the agents are at least as happy and at least one agent is strictly happier.} Due to its desirable properties, the competitive rule has been suggested as a mechanism for allocating goods in real markets, with applications ranging from cloud computing~\cite{DGMVY18} and dividing rent~\cite{spliddit} to assigning courses among university students~\cite{B11}. 

 The market considered by Varian is known in the computer science literature as the Fisher market~(named after Irving Fisher, the 18th century economist, see~\cite{BS00}).
The properties of the Fisher market were studied in an extensive body of literature discovering both algorithms for computing equilibria and hardness results (see, e.g.,~\cite{EG} and Chapter 5 of~\cite{AGT_book}).

\begin{comment}
{\fed [[]This list of 11 (by which principle have you picked them?) references without any comments does not look informative. 
Instead of expanding discussion here, perhaps we can mention all the references in the Literature section instead? 

Also none of the papers of Gale and Eisenberg address the algorithmic issues directly. Perhaps, keeping just \cite{EG} as a source of Eisenberg-Gale problem is enough. Why do we need all \cite{gale,EG,Ga76}?]]}
\end{comment}

For allocating goods, the Fisher market has beautiful structural properties.
For a large class of utilities\footnote{Homogeneity and convexity of {\fed utilities} are enough.}, the
equilibria of the Fisher market are captured by the Eisenberg-Gale convex program~\cite{EG}, which maximizes the product of individual utilities\footnote{The product of utilities is known as {\fed  the Nash product or the} Nash social welfare from {\fed the axiomatic theory of  bargaining}~\cite{Nash50}. Beyond the Fisher market, it balances the individual happiness and collective well-being in many different problems, e.g., \cite{caragiannis2016unreasonable,conitzer2017fair}.}. By the convexity of this problem, the competitive rule is single valued (i.e. the utilities are unique) and can be computed efficiently for important classes of preferences, such as {\fed given by} additive utilities, using standard gradient descent methods. 


\paragraph{Allocation of Bads (Chores).} The literature on resource allocation has largely neglected the study of \emph{bads}, also known as \emph{chores}, which are items that the agents do not want to consume, such as doing housework, or that represent liabilities, such as owing a good to someone. 

\smallskip

While at first sight, the same principles should apply in the problem of allocating chores as when allocating goods, it turns out that the problem of allocating chores is more complex. The competitive rule for chores was defined and studied in a sequence of papers~\cite{BMSY17,BMSY_SCW} that considered the analog of Fisher markets for chores and analyzed their properties. Even in the case of additive utilities, the competitive rule for chores is no longer single valued, the equilibrium allocations form a disconnected set, and can be obtained as critical points of the Nash social welfare on the Pareto frontier of the set of feasible utilities~\cite{BMSY17}. The problem of allocating chores is thus not convex and the  usual techniques for finding competitive allocations based on linear/convex programming such as primal/dual, ellipsoid, and interior point methods, do not apply.

\smallskip

The existing work on the competitive allocation of chores~\cite{BMSY17,BMSY_SCW} left open the question of computing competitive allocations for more than two agents with additive utilities\footnote{For two agents, a simple procedure for finding competitive allocations is described in~\cite{BMSY_SCW}. It uses the one-dimensional structure of Pareto optimal allocations, which can be ordered from allocations preferred by the first agent to preferred by the second: a specific feature of the two-agent case.}, which we address in this paper. 





\paragraph{Our Contribution.} We study the problem of allocating chores in the basic setting of additive utilities. We have a set $[n] = \{1, \ldots, n\}$ of agents and a set $[m] = \{1, \ldots, m\}$ of divisible chores (which may alternatively be seen as indivisible chores that can be allocated in a randomized way). The utilities of the agents are given by a matrix $\vec{v} \in \mathbb{R}_{<0}^{n\times m}$ such that $v_{i,j}$ is the {\fed (negative)} value of agent $i$ for chore $j$. Allocations are defined in the usual way and the utilities are additive over the allocations. 

\smallskip

We {\fed allow agents to have different budgets} represented by a vector $\vec{b} \in \mathbb{R}_{<0}^n$, which can be seen as virtual currency for acquiring chores; in particular, the budget of an agent denotes how much of a ``duty'' that agent has\footnote{Most of the literature on fair division  assumes that agents are equal in their rights, the case captured by equal budgets. It turns out that allowing unequal budgets is convenient even if in our problem agents have equal rights: see agent-item duality in Section~\ref{sect_compute_Pareto} or budget-rounding in Section~\ref{sect_indiv}. }. For example, if an agent works full time while another agent only works half of the time, then this can be modeled with budgets $-1$ and $-0.5$, respectively. Note the budgets are negative to indicate that they represent a liability.

\medskip

Our main result states that:
\begin{quote}
\noindent \emph{{Finding all the outcomes of the competitive rule is a computationally tractable problem}}
\end{quote} when either the number of agents or the number of chores is bounded. In particular, our algorithm runs in strongly polynomial time.


\begin{theorem}[\textbf{Main Theorem, Divisible Chores}]
Consider any chore division problem $(\vec{v}, \vec{b})$ with $n$ agents and $m$ chores, where $\vec{v}\in \mathbb{R}_{<0}^{n\times m}$ is a matrix of {\fed values}  and $\vec{b}\in \mathbb{R}_{<0}^n$ a vector of budgets. If $n$ or $m$ is fixed, then
	\begin{itemize}
		\item the set of all competitive utility profiles
		\item {\fed a set of competitive allocations and price vectors such that for any competitive utility profile there is an allocation with this utility profile in the set}

	
	
	\end{itemize}
	can be computed using  $O\left(m^{\frac{n(n-1)}{2}+3}\right)$ operations, if  $n$ is fixed, or $O\left(n^{\frac{m(m-1)}{2}+3}\right)$, for fixed $m$. This gives an algorithm that runs in strongly polynomial time.
\end{theorem}

\textbf{\emph{Remarks}}. Getting access to the whole equilibrium set in polynomial time is crucial for fair division applications, where having the whole set of equilibria allows one to reason about which outcome to pick for a given instance and to decide on the tradeoffs between different properties, such as maximizing welfare, individual fairness guarantees, etc., among which there may be tension. Since different equilibria favor different agents there is a question of picking the best outcome among the set of all equilibria. Bogomolnaia et al.~\cite{BMSY17} suggested picking the median equilibrium (with probability $1$ there is an odd number of equilibria) in case of two agents. The chance that such a selection can be computed without finding the whole set seems negligible. Alternatively, one can select the most egalitarian equilibrium or ask the agents to vote which equilibrium to select.  


\newpage

\textbf{\emph{Our method and existing techniques}.}
The basic difficulty for allocating chores is that the competitive rule has disconnected equilibria. The only known approach for finding disconnected equilibria was applied to goods~\cite{DK08,Tardos} and uses a complex tool from computational algebraic geometry (see, e.g., the work on cell enumeration in \cite{Basu} and \cite{SafeyElDin2007,Jeronimo2010} for probabilistic algorithms) in order to reduce the search space to a polynomial number of structures. 

Our algorithm provides the first explicit construction (without cell enumeration) and 
thus answers an open problem of \cite{DK08}. Our construction has clear economic meaning: the Pareto frontier can be computed by enumerating its faces (or equivalently Pareto optimal demand structures) in polynomial time.

The idea used to compute the Pareto frontier is to recover that of an $n$-agent problem from its projections to two-agent sub-problems. We use a few other novel tricks: 
an agent-item duality to cover both cases of finite $n$ and $m$ (note that the work of \cite{DK08} needs two separate proofs), explicit formulas for recovering the competitive utility profile if the demand structure is known, and new structural results for the set of Pareto optimal allocations. 
We believe that our approach is applicable to other disconnected economies.


\begin{comment}
\begin{itemize}
	\item chores $\Rightarrow$ disconnected equilibria
	\item the only alternative approach to disconnected equilibria  (references DK and Tardos) was applied to goods and uses a complicated tool from comp alg geom (references from Skype) in order to reduce the search space to a polynomial number of structures. 
	{\bf (we don't even need to say that this technique is applicable to chores)}
	\item Our algorithm provides the first simple explicit construction (without cell enumeration) and 
	thus answers an open problem of DK08. 
	
	We achieve this use an economic insight about the structure of Pareto-frontier 
	
	
    \item We use a few other novel tricks: 
    agents-items duality to cover both cases of finite $n$ and $m$ (note that DK08 need two separate proofs); explicit formulas for recovering competitive utility if the demand structure is known; new structural results for the  set of PO allocations
    
	
	\item We believe that our approach is applicable to other disconnected economies (discuss in Conclusions).
\end{itemize}




One of the most relevant previous works on the computation of competitive equilibria for goods is the paper of \cite{DK08}, which applies a cell decomposition of the space of price vectors and bounds the number of cells using techniques from computational algebraic geometry, thus obtaining an algorithm for computing competitive equilibria when the number of goods is fixed. Abstract cell decomposition can be adapted to handle chores; however \cite{DK08} left open the question of obtaining explicit constructions (instead of enumerating all the cells via brute force search). Our work provides an explicit construction with clear economic meaning: the Pareto frontier can be computed by enumerating its faces (or equivalently Pareto optimal demand structures) in polynomial time. The idea used to compute the Pareto frontier is to recover the Pareto frontier of an $n$-agent problem from its projections to two-agent sub-problems.

\end{comment}

\medskip

\textbf{\emph{Overview of the algorithm}}. Our main theorem is based on the following observation: computing competitive allocations for chores becomes easy if the Pareto frontier is known. Then every face of the frontier is easy to check for containing a competitive allocation and the intuition comes from numerical methods: the solution to a constrained optimization problem is easy to find if we know the set of active constraints. We show that for a competitive division of chores, the Pareto frontier can be computed in polynomial time in the number of items $m$ for a fixed number of agents $n$ or in polynomial time in $n$ for fixed $m$. This implies a polynomial algorithm for computing all competitive utility profiles. 

\smallskip





{\fed Faces of the Pareto frontier are encoded using the language of consumption graphs.} The consumption graph of an  allocation is obtained by tracing  an edge between an agent and a chore whenever the agent consumes some fraction of that chore. Then the first step of the algorithm is to generate a so called ``rich'' family of graphs, which contains consumption graphs of all Pareto optimal allocations\footnote{For non-degenerate $\vec{v}$ (all  matrices except a subset of measure zero) the set of all ``Pareto optimal'' consumption graphs has polynomial size. In order to capture the degenerate case we are forced to define a rich set in a more complex way.}. {\fed Such a family contains a graph for each competitive allocation in addition to possibly containing other graphs that do not correspond to competitive allocations.} In the second step, we generate a ``candidate'' utility profile for each graph in the family by recovering the explicit formula for the utility assuming that the  given graph is a consumption graph of a competitive allocation. In the third step, {\fed we adapt the technique from~\cite{devanur2002market}} to check if the utility profile considered is in fact competitive by studying the amount of flow in an auxiliary maximum flow problem.

\medskip

\textbf{\emph{Indivisible chores.}} Finally, we also show how to find approximately fair allocations for {indivisible} chores in polynomial time, for fairness notions such as weighted envy-freeness and weighted proportionality. For indivisible chores, the corresponding relaxations of these fairness notions are weighted envy-freeness up to removal of a chore from a bundle and addition of another chore to another bundle (weighted-EF$_1^1$) and weighted proportionality up to one chore (weighted-Prop$1$). 

These results become an immediate corollary of Theorem~1 and the technique from the recent work \cite{barman2018} that showed how to round a divisible competitive allocation with goods in order to get an approximately fair and Pareto optimal indivisible allocation.

To the best of our knowledge, no algorithms for the approximately-fair and efficient allocation of indivisible chores were known.


	
	
	 
	 
 
	

\paragraph{Organization of the paper.} Section 2 formalizes the model and defines the competitive rule and its properties. In Section 3 we give the main theorem and describe the main phases of the algorithm. In Section 4 we study the Pareto frontier and show how to compute a rich family of allocation graphs. In Section 5 we obtain explicit formulas for competitive utility profiles when the consumption graph is known. In Section 6 we check that a given utility profile is competitive, recovering an allocation and prices. We conclude with Section 7, which shows how to obtain approximately fair allocations for indivisible chores.

\begin{comment}
\begin{itemize}
	\item Motivation: Market equilibrium is a key economic concept => computational issues are important and attracted a lot of attention. + there is practical motivation inspired by application to fair division 
	\item Fair division. Competitive Rule is mysterious: the most fair and efficient among cardinal mechanisms, but usually non-constructive => practical applications are limited and rise algorithmic questions.
	\begin{itemize}
		Applications (courses, Spliddit, Kelly's proportional fairness). 
		Importance of additive preferences for practice: easy to report 
		
		\item Subsection: New results on chores (house chores). Non-convexity, multiplicity
	\end{itemize}


	\item Our contribution: the algorithm for computing CR for chores. The second example of an algorithm for ``non-convex'' markets (the first one is by Tardos et al)
	Basic ideas of the construction.
	
	\item Organization of the paper
	
	\item Literature review.\begin{itemize}
		\item Known approaches to computing CR: detailed discussion. 
		
		\item Indivisibilities: extension of CR (Babaioff); fairness of MNP (Caragianis et al 2017) + polynomial algorithm for utilities on the lattice; NP-hardness of MNP in general case and approximation polynomial algorithms. 
		
		
		\item Other related results: strategic behavior, link between bargaining and competitive FD: Nash (1951) for goods; S.Hart and others for chores (non-convex bargaining) 
		
	\end{itemize} 
	

\end{itemize}


{\com 	Here I put some unsorted blocks of text that can be used in the intro, if you find them appropriate. Kill them if you don't.}



This note is based on the following observation: computing competitive allocations becomes easy if the Pareto frontier is known. Then every face of the frontier is easy to check for containing a competitive allocation.The intuition comes from numerical methods: the solution to a constrained optimization is easy to find if we know the set of active constraints\footnote{Example by Nisarg Shah: a Nash equilibrium of a game is easy to compute via LP if we know supports of equilibrium strategies, but it is PPAD if we do not.}. We show that for fair division of chores, the Pareto frontier can be computed in polynomial time in the number of items $|A|$ for a fixed number of agents $|N|$ or in polynomial time in $|N|$ for fixed $|A|$. This implies a polynomial  algorithm for computing \emph{all} competitive utility profiles.

The question of computing of market equilibrium attracted a lot of attention in last two decades. 
Apart from being a key economic concept that describes a steady-state of the market, when prices are such that the demand equals the supply, it finds at first glance unexpected applications in the theory and practice of fair division.


Importance to have a polynomial algorithms for objects defined non-constructively \cite{Papadimitriou_inefficient}.



Dynamics, converging to equilibrium. Tatonement-based procedures work in practice but may fail to converge (see Budish?). First Convergence results are obtained in \cite{{Cheung}}, but the algorithm is neither exact nor polynomial). Proportional response approach by Zhang???

Convex-optimization. Approximate polynimial algorithm via interior point methods.....

Combinatorial (primal-dual) algorithms....

All these algorithms work for the economies that satisfy either explicit (see ...) or implicit (see algorithm of Jeng for Arrow-Debreu) convexity assumption. As a corollary, none of the mentioned algorithms is applicable to the situation when equilibria form a disconnected set, (i.e., when the competitive rule becomes multivalued). This corresponds to constrained economies (i.e., preferences are satiated or there are some constraints on individual consumption). In economic literature it is known that for such economies the competitive correspondence may become multivalued (see ??\cite{Gjerstad}??). 

Computing CE in such economies was mentioned in ????I will find a reference???? as an open problem. The first example of such an algorithm was obtained in \cite{Tardos} for the assignment problem, where .....



FD with chores was almost avoided in the literature. Extension of CR to chores by Bogomolnaia et al 2017: fair and efficient rule. In contrast to Egalitarian rule 

 Sharp difference in properties for goods/chores:
--- for goods CE solves a convex problem of Eisenberg and Gale: it maximizes the Nash product (Eisenberg and Gale ?????)  => uniqueness, robustness (Megiddo and Vazirani), polynomial approximate algorithms based on gradient decent or primal/dual approach(??????), polynomial exact algorithm (Vazirani 2007)

--- for chores CE picks all the critical points (local minima, local maxima, or saddle points) of the Nash product on the efficient frontier => not a convex problem => multiplicity of allocations (Bogomolnaia et al 2018, to appear in SCW) + no algorithms for computing the outcome of CE: gradient methods do not work for non-convex problems and the approach of Vazirani is based on the internal monotonicity (????) which disappears in case of chores.

From Jain "Arrow Debreu market equilibrium" about implicit convexity:
There is no duality theory used in these papers. [27] does not use any convex program
(although, in hindsight, there is a convex program similar to the Eisenberg–Gale
convex program). The situation of [12] is the same as [27]; [12] does not use any
convex program, though again in hindsight there is a convex program. [28] uses a
convex program but does not really use any duality theorem.


Competitive rule is known as the most attractive rule to divide goods: it is envy-free and efficient, solves a convex optimization problem (Eisenberg-Gale ).
Bogomolnaia et al. (2017) \cite{BMSY2017} defined a version of the Competitive Rule for chores. This rule was introduced by Varian~\cite{Varian} to divide goods


For more than 50 years CS literature was trying to avoid local critical points...

For two agents, a simple algorithm for computing the set of competitive allocations was proposed in\cite{BMSY_SCW}The case $|N|=2$ is specific because the Pareto frontier $\F^*$ has a simple ``one-dimensional'' and each face of $\F^*$  can be checked for carrying a competitive allocation using FOCs of criticality, which take especially simple form in this case.

Our results show that this scheme is applicable in general case $|N|>2$ though the simplicity vanishes: computing the Pareto frontier in polynomial time becomes a non-trivial problem.
and even when the Pareto frontier is known we need new insights into the structure of competitive allocations to compute them.

\subsection{Our Results}
Our main results as as follows.
TODO: {\color{blue} I will add here the main theorems.}
\end{comment}

\subsection{Related Work}\label{subsect_literature}

\paragraph{Algorithmic results for goods.} The problem of finding polynomial time algorithms for objects defined non-constructively has been a major research focus in the algorithmic game theory literature and beyond \cite{Ppad_inefficient}.  {\fed Positive results} were obtained for important special cases, such as computing Nash equilibria in zero-sum games and competitive equilibria in exchange economies with additive {\fed utilities}, as well as negative (hardness) results for the corresponding problems in general-sum games and economies with non-additive {\fed utilities}.

\medskip

\emph{\textbf{The case of ``convex'' economies: }} In particular, the search for algorithms for computing competitive equilibria has brought a flurry of efficient algorithms for finding equilibria in diverse market scenarios (see, e.g., primal-dual type algorithms in \cite{devanur2002market,CDSYao04}, network flow type algorithms in \cite{orlin,vegh2012strongly,vegh2012concave}, convex programming formulations for {\fed Fisher markets and their extensions such as Eisenberg-Gale  markets}~\cite{BrunoVICALP04,Codenotti05,homothetic,Jain07}, auction-based algorithms in \cite{auction.gross}) as well as computational hardness results (see, e.g. \cite{CSVY,Chen.plc,EY07,LeonFIXP}).

The polynomial time algorithms in these works are designed for economies that satisfy implicit or explicit convexity assumptions. For example, in the case of Fisher markets, the competitive equilibrium solves the Eisenberg-Gale convex program~\cite{EG} for a large class of utilities, maximizing the Nash product (i.e., the geometric mean of the utilities weighted by the budgets of the agents). Moreover, the equilibrium is unique, robust ~\cite{MV07} (i.e., small errors in the observation of the market parameters do not change the competitive allocation by much), and admits polynomial time approximation algorithms based on gradient descent methods as well as exact algorithms (see, e.g., Chapters 5 and 6 in ~\cite{AGT_book}). 
In contrast, in the case of chores, there is a multiplicity of equilibria and no robustness guarantee: the set of equilibria admits no continuous selections~\cite{BMSY17}.

Dynamic processes in markets have also been studied, such as tatonement (see, e.g., \cite{CCD13} for a general class of markets containing Eisenberg-Gale markets), and proportional response dynamics in Fisher markets \cite{Zhang,BDX11,WZ07} and production markets \cite{BMN18}.





\medskip

\emph{\textbf{Non-convex economies and disconnected sets of equilibria: }} None of the methods mentioned above are applicable to the situation when the competitive equilibria form a disconnected set, that is, when the competitive rule becomes multivalued { (as in the case of chores)}. This situation corresponds to constrained economies, such as when preferences are satiated or there are some constraints on individual consumption\footnote{Note that an economy with chores can be reduced to a constrained economy with goods, see \cite{BMSY17} and Section~\ref{sect_conclusions}}. In the economic literature it is known that for such economies the competitive correspondence may become multivalued (see, e.g., \cite{Gjerstad}), which was observed to be problematic from the point of view of finding competitive equilibria; for example, in \cite{vegh2012concave} polynomial time algorithms are not obtained precisely in cases where economies admit multiple disconnected equilibria.


There are very few examples of efficient algorithms for computing competitive equilibria for non-convex economies. In ~\cite{DGMVY18}, a polynomial time algorithm is given for markets with covering constraints, where the utilities are satiated but the equilibria form a connected, yet non-convex set. The work of~\cite{DK08} gives a polynomial time algorithm for computing competitive equilibria when either the number of agents {\fed or goods} is fixed based on the cell enumeration technique. The work of~\cite{Tardos}  {\fed extends the approach of~\cite{DK08} to the fair assignment problem of~\cite{HZ}: there the utilities are} piecewise-linear concave functions, but are {\fed neither separable nor monotone,} and do not satisfy gross substitutability; their study {\fed also} gives a polynomial time algorithm  when either the number of agents or the number of goods is fixed. 

{\fed \paragraph{Fair division of an inhomogeneous  chore.}    
 Allocation of chores also appears in works on fair cake-cutting (dividing a divisible inhomogeneous resource). This literature typically ignores Pareto optimality focusing exclusively on fairness. 
}








Examples of chore division in this line of work include the fair chore division model posed by ~\cite{Gardner}, which can be seen as identical to the cake cutting problem except that the item to be partitioned is a heterogeneous bad. Peterson and Su~\cite{PS02,PS98} design envy-free chore division protocols. These protocols were improved by ~\cite{DFMY18}, who obtained a bounded envy-free chore division {\fed method} for any number of agents. \cite{HS15} consider the fair division of chores with connected pieces and bound the loss in social welfare due to fairness. 
\cite{segal2018fairly} studies the envy-free division of a cake when some parts have been burned in the oven (i.e., the value densities can be positive, negative, or zero anywhere) and showed the existence of connected envy-free allocations for three players {\fed using a topological approach based on an analog of Sperner's lemma}. In a follow-up work, \cite{meunier2018envy} show the existence of connected envy-free allocations when the number of players is a prime or equal to four.

\paragraph{Relaxed fairness notions for indivisible items.} The literature on fair division of indivisible goods has studied several fairness notions, such as envy-freeness up to one good (EF1) ~\cite{LMMS04}, proportionality up to one good (Prop1), envy-freeness up to any good (EFX), max-min fair share ~\cite{B11}, and (approximate) competitive equilibrium. Envy-freeness up to one good roughly means that no agent $i$ envies the bundle of another agent $j$ after the best item has been dropped from $j$'s bundle. Proportionality up to one good is similarly defined. These two fairness notions can be {\fed miraculously} obtained by maximizing the Nash social welfare, which  also  guarantees Pareto optimality~\cite{CKMP+16}. It is open whether or not EFX allocations always exist (see, e.g., \cite{PR18}).

The max-min fair share is a fairness notion inspired from cake cutting protocols and requires that each agent gets a value at least as high as the one he can guarantee by preparing first $n$ bundles and letting the other players choose the best $n-1$ of these bundles. This optimization problem induces a max-min value $\alpha_i$ for each player and the question is whether there exists an allocation where each agent has utility at least $\alpha_i$. While such allocations may not exist ~\cite{PW14}, approximations are possible; in particular, there always exists an allocation in which all the agents get two thirds of their max-min value ~\cite{PW14}, and this can be computed in polynomial time~\cite{AMNS15}.

~\cite{ARSW17} study the fair allocation of multiple indivisible chores using the max-min share solution concept, showing that such allocations do not always exist and computing one (if it exists) is strongly NP-hard; these findings are complemented by a polynomial 2-approximation algorithm. \cite{aziz2018fair} consider the problem of fair allocation of a mixture of  goods and chores and design several  algorithms for finding fair {\fed (but not necessarily Pareto optimal)} allocations in this setting. {\fed \cite{aziz2019strategyproof} consider mechanisms robust to strategic manipulations.}

Finally, the competitive rule and various relaxations (such as those obtained by removing the budget clearing requirement, allowing item bundling, or using randomization) can also be used to allocate indivisible goods. These have been studied for various classes of utilities from the point of view of existence of fair solutions and their computation in~\cite{B11,FGL13,BHM15,OPR16,BLM16,barman2018,BNT19}. Closest to ours is the work by \cite{barman2018}, which considers Fisher markets with indivisible goods and shows how to compute an allocation that is Prop1 and Pareto optimal in strongly polynomial time. We build on these results to obtain a theorem for chores.



\begin{comment}
\textbf{Algorithms}: usual cases:
\begin{itemize}

\item Importance to have a polynomial algorithms for objects defined non-constructively \cite{Papadimitriou_inefficient}.
\item Dynamics, converging to equilibrium. Tatonement-based procedures work in practice but may fail to converge (see Budish?). First Convergence results are obtained in \cite{{Cheung}}, but the algorithm is neither exact nor polynomial). Proportional response approach by Zhang???
\item Convex-optimization. Approximate polynimial algorithm via interior point methods.....
\item Combinatorial (primal-dual) algorithms....
\item All these algorithms work for the economies that satisfy either explicit (see ...) or implicit (see algorithm of Jeng for Arrow-Debreu) convexity assumption. As a corollary, none of the mentioned algorithms is applicable to the situation when equilibria form a disconnected set, (i.e., when the competitive rule becomes multivalued). This corresponds to constrained economies (i.e., preferences are satiated or there are some constraints on individual consumption). In economic literature it is known that for such economies the competitive correspondence may become multivalued (see ??\cite{Gjerstad}??). 
\end{itemize}

\textbf{Algorithms for non-convex economies:}
\begin{itemize}
	\item Computing CE in such economies was mentioned in ????I will find a reference???? as an open problem. The first example of such an algorithm was obtained in \cite{Tardos} for the assignment problem, where .....
	\item FD with chores was almost avoided in the literature. Extension of CR to chores by 
	\item for goods CE solves a convex problem of Eisenberg and Gale: it maximizes the Nash product (Eisenberg and Gale ?????)  => uniqueness, robustness (Megiddo and Vazirani), polynomial approximate algorithms based on gradient decent or primal/dual approach(??????), polynomial exact algorithm (Vazirani 2007)
	
	\item for chores CE picks all the critical points (local minima, local maxima, or saddle points) of the Nash product on the efficient frontier => not a convex problem => multiplicity of allocations (Bogomolnaia et al 2018, to appear in SCW) + no algorithms for computing the outcome of CE: gradient methods do not work for non-convex problems and the approach of Vazirani is based on the internal monotonicity (????) which disappears in case of chores.
	
	\item From Jain "Arrow Debreu market equilibrium" about implicit convexity:
	There is no duality theory used in these papers. [27] does not use any convex program
	(although, in hindsight, there is a convex program similar to the Eisenberg–Gale
	convex program). The situation of [12] is the same as [27]; [12] does not use any
	convex program, though again in hindsight there is a convex program. [28] uses a
	convex program but does not really use any duality theorem.
	
	\item Competitive rule is known as the most attractive rule to divide goods: it is envy-free and efficient, solves a convex optimization problem (Eisenberg-Gale ).
	Bogomolnaia et al. (2017) \cite{BMSY2017} defined a version of the Competitive Rule for chores. This rule was introduced by Varian~\cite{Varian} to divide goods
\end{itemize}

For more than 50 years CS literature was trying to avoid local critical points...

For two agents, a simple algorithm for computing the set of competitive allocations was proposed in\cite{BMSY_SCW}The case $|N|=2$ is specific because the Pareto frontier $\F^*$ has a simple ``one-dimensional'' and each face of $\F^*$  can be checked for carrying a competitive allocation using FOCs of criticality, which take especially simple form in this case.

Our results show that this scheme is applicable in general case $|N|>2$ though the simplicity vanishes: computing the Pareto frontier in polynomial time becomes a non-trivial problem.
and even when the Pareto frontier is known we need new insights into the structure of competitive allocations to compute them.

	 Literature review.
\begin{itemize}
	\item Known approaches to computing CR: detailed discussion. 
	\item Indivisibilities: extension of CR (Babaioff); fairness of MNP (Caragianis et al 2017) + polynomial algorithm for utilities on the lattice; NP-hardness of MNP in general case and approximation polynomial algorithms. 
	\item Other related results: strategic behavior, link between bargaining and competitive FD: Nash (1951) for goods; S.Hart and others for chores (non-convex bargaining) 
\end{itemize} 

\end{comment}

\section{Preliminaries}

There is a set $[n] = \{1, \ldots, n\}$ of agents and a set $[m] = \{1, \ldots, m\}$ of divisible non-disposable chores (bads) to be distributed among the agents. 

\smallskip

A \emph{bundle} of chores is given by a vector $\vec{x} = (x_1, \ldots, x_m)\in \mathbb{R}_+^{m}$, where $x_j$ represents the amount of chore $j$ in the bundle\footnote{Another interpretation of an amount $x_j$ of good $j$ is the amount of time doing the chore $j$ or the probability of getting it.}. W.l.o.g., there is one unit of each chore.\footnote{Given an arbitrary division problem, one can rescale the utilities to obtain an equivalent problem where the total amount of each chore is one unit.} An \emph{allocation} $\vec{z}=(\vec{z}_i)_{i\in [n]}$ is a set of bundles where agent $i$ receives bundle $\vec{z}_i$ and all the chores are distributed: $\sum_{i=1}^n z_{i,j} =1 $ for each $j \in [m]$. 

\smallskip

The agents have additive utilities specified through a matrix $\vec{v} \in \mathbb{R}_{<0}^{n \times m}$, where\footnote{We write $\mathbb{R}_{+},\mathbb{R}_{>0},\mathbb{R}_{-},\mathbb{R}_{<0}$ for vectors with non-negative, strictly-positive, non-positive, and strictly negative components, respectively; {\fed to distinguish vectors and scalars  bold font is used.}} $v_{i,j} < 0$ represents the value of agent $i$ for consuming one unit of chore $j$. The utility of agent $i$ in an allocation $\vec{z}$ is $u_i(\vec{z}_i) = \sum_{j =1}^m v_{i,j} \cdot z_{i,j}$. The vector of utilities at an allocation $\vec{z}$ is $\vec{u}(\vec{z}) = (u_1(\vec{z}_1), \ldots, u_n(\vec{z}_n))$.

\medskip 

The set of \emph{all } allocations will be denoted by $\F$ and the set of all feasible utility profiles by $\mathcal{U}(\vec{v})$. These are utilities for which there exists an allocation in which the utilities are realized, i.e., $\mathcal{U}(\vec{v}) = \{\vec{w} \in\mathbb{R}^n\mid \exists \; \vec{z} \in\F : \ \vec{w}=\vec{u}(\vec{z})\}$. We note that both the set of all allocations---$\F$---and the set of feasible utility profiles---$\mathcal{U}(\vec{v})$---are convex polytopes. 

\medskip

In general, the agents may have different duties with respect to the chores, which we will model through different (negative) budgets. Formally, each agent $i$ will be endowed with a budget $b_i < 0$.
For example, a situation where the problem of allocating chores with unequal budgets may arise is when a manager assigns tasks to two workers, Alice and Bob. If Alice works full time while Bob works part time
(say 50\%), then it is reasonable that Bob has the right to work half as much than as his colleague Alice. This corresponds to budgets $b_{Alice} = -1$ and $b_{Bob} = -2$.

\begin{definition}
{\fed A chore division problem $(\vec{v}, \vec{b})$ is a pair of a matrix of values $\vec{v}\in \mathbb{R}_{<0}^{n\times m}$ and budgets $\vec{b}\in \mathbb{R}_{<0}^n$.} 
\end{definition}



\subsection{The Competitive Rule}

\medskip


Given a vector $\vec{p} = (p_1, \ldots, p_m)\in \mathbb{R}_{<0}^m$, where $p_j$ represents the price of a chore $j$, the price of a bundle $\vec{x}= (x_1, \ldots, x_m)$ of chores is given by
$p(\vec{x}) = \sum_{j=1}^m p_j \cdot x_j$.

\begin{definition}[Competitive Allocation]\label{CRdef}

	An allocation $\vec{z} = (\vec{z}_1, \ldots, \vec{z}_n)$ for a chore division problem $(\vec{v}, \vec{b})$ with strictly negative matrix of values and budgets is \emph{competitive} if and only if there exists a vector of prices $\vec{p} = (p_1, \ldots, p_m)\in \mathbb{R}_{<0}^m$ such that for each $i \in [n]$:

	\begin{itemize}
		\item Agent $i$'s bundle maximizes its utility among all bundles within its budget: $u_i(\vec{z}_i) \geq u_i(\vec{x})$, for each bundle $\vec{x}$ with $p(\vec{x}) \leq b_i$.
	
	
	\end{itemize}
\end{definition}

\begin{comment}
Unlike in the Fisher market framework, for the problem of allocating chores the budgets and prices will be negative.

Recall that when the items are goods, competitive allocations are realized at feasible allocations that maximize the Nash product: 
$$\prod_{i \in N} u_i(\vec{z}_i)^{b_i}.$$
However, the problem of allocating chores is very different from that of allocating goods. A first attempt to find the equivalent of the competitive allocation of goods for chores would be to minimize the product of disutilities: $$\prod_{i\in N} | u_i(\vec{z}_i) |^{b_i}.$$ This method can be immediately seen to be flawed: a trivial solution is obtained by giving all the chores to one agent, which is very unfair for any set of non-zero budgets. A second attempt is to maximize the product of disutilities weighted by the budgets. Unfortunately, when the agents have equal duties \footnote{This is the equivalent of equal rights when the items are goods.} this approach can give allocations that are not Pareto efficient and are dominated by the equal division $z_{i,j} = 1/n$, for each chore $j$ and agent $i$. {\fed This paragraph shows that max(min)imizing the Nash product does not lead to a \emph{fair} and \emph{efficient} allocation. But the connection between fairness \& efficiency and CR was not discussed yet...}

Instead, we will study allocations obtained by posting prices on the chores and having the agents purchase their favorite bundles at those prices given their initial budgets.
\end{comment}

Unlike the Fisher market framework for allocating goods, in the case of chores, all the prices and budgets are negative.
We also note that Definition~\ref{CRdef} is designed for chores that have strictly negative value for all the agents. Chores for which some agents have value zero can be handled separately as follows.

\medskip

\begin{remark}[Chores with Zero Utilities]
Suppose there exists at least one chore $j \in [m]$ for which some agent $i$ has utility zero. Let $S = \{j \in [m] \mid \exists i \in [n] \; \mbox{s.t.} \; v_{i,j} = 0\}$ be the set of such chores.  

Then each chore in $S$ can be allocated to an agent that is indifferent to it while not affecting the utility of any agent.
Moreover, this allocation can be implemented through the competitive rule by  setting the price of each chore $j \in S$ to zero. 
\end{remark}

\medskip



For a given matrix $\vec{v}$ of values and vector $\vec{b}$ of budgets, we denote the set of all competitive allocations by $\mathrm{CA}(\vec{v},\vec{b})$ and the set of all competitive utility profiles by $\mathrm{CU}(\vec{v},\vec{b})$, where we have $\mathrm{CU}(\vec{v},\vec{b})= \{\vec{u}(\vec{z}) \mid \vec{z}\in \mathrm{CA}(\vec{v},\vec{b}))\}.$ 
\begin{definition}[Pareto Optimality]
	An allocation $\vec{z}$ is \emph{Pareto optimal} if there is no other allocation $\vec{z}'$ in which $u_i(\vec{z}_i')\geq u_i(\vec{z}_i)$ for every agent $i\in [n]$ and the inequality is strict for at least one agent.
\end{definition}

\begin{definition}[Weighted Envy-Freeness]
	An allocation $\vec{z}$ is \emph{weighted-envy-free} with weights $\beta\in \mathbb{R}_{>0}^n$  if for every pair of agents $i,i' \in [n]$, the following inequality holds:
	$\frac{u_i(\vec{z}_i)}{\beta_i} \geq \frac{u_i(\vec{z}_{i'})}{\beta_{i'}}.$
\end{definition}
We denote by $\F^*(\vec{v})$ and $\mathcal{U}^*(\vec{v})$ the set of all Pareto optimal allocations and corresponding utility profiles, respectively.

The competitive rule satisfies both Pareto optimality and weighted-envy-freeness with weights $\beta_i= |b_i|$.
Weighted-envy-freeness holds since agent $i$ can afford a fraction of $|b_i|/|b_j|$ from the bundle of any agent $j$. For Pareto optimality, see Theorem~\ref{cor_welf}.








\medskip

\paragraph{\textbf{\textit{Geometry of the Competitive Rule and Non-convexity.}}}
In the case of goods, the competitive rule can be implemented via the \emph{Eisenberg-Gale} optimization problem (see, e.g., Chapter 5 in \cite{AGT_book}): an allocation $\vec{z}$ is competitive if and only if the product of utilities at $\vec{z}$ weighted by the budgets is maximized. That is, the product $\prod_{i=1}^n \left|u_i(\vec{z}_i)\right|^{|b_i|}$ is maximized, where  the maximum is taken over all feasible allocations $\vec{z}$. This problem has a convex programming formulation and can be solved efficiently using standard gradient descent methods.

	


\medskip

The product $\mathcal{N}_{\vec b}(\vec{u})=\prod_{i=1}^n \left|u_i\right|^{|b_i|}$ is known as the \emph{Nash product} or the \emph{Nash social welfare}.

\medskip

In the case of chores, an analogue of the Eisenberg-Gale characterization was found in~\cite{BMSY17}.
\begin{theorem}[Bogomolnaia, Moulin, Sandomirskiy, Yanovskaya \cite{BMSY17}]\label{th_geom}
Consider a chore division problem $(\vec{v}, \vec{b})$.
A feasible allocation $\vec{z}$ is competitive if and only if the utility profile $\vec{u}(\vec{z})$ 
\begin{itemize}
\item belongs to the set $\mathcal{U}^*(\vec{v})\cap \mathbb{R}_{<0}^n$ of strictly negative points on the Pareto frontier, and 
\item is a critical point of the Nash product $\mathcal{N}_{\vec{b}}$ on the feasible set of utilities $\mathcal{U}(\vec{v})$.
\end{itemize}
\end{theorem}



Recall that a point $x$ is called critical for a smooth function $f$ on a convex set $K$ if the tangent hyperplane to the level curve of $f$ at $x$ is a supporting hyperplane for $K$. Local maxima, local minima, and saddle points of $f$ on the boundary of $K$ are examples of critical points.

In~\cite{BMSY17}, the theorem is proved for the case of equal budgets, but the same proof works for arbitrary strictly negative budgets. A sketch of the proof is contained in the Appendix (see Proposition~\ref{prop_characterizations_of_CA}  together with other characterizations of competitive allocations).


\begin{remark}
We note that none of the global extrema of the Nash product are competitive: global minima correspond to unfair allocations, where at least one agent receives no chores and hence the Nash product at such allocations is zero; the global maximum lies on the anti-Pareto frontier and therefore it is not Pareto optimal.
Thus, it is unclear how to use global optimization methods to compute the outcome of the competitive rule. 
\end{remark}

\begin{comment}
{\ed 
\begin{example}
 Consider the following example borrowed from~\cite{BMSY_SCW} (LATER WE WILL PICK ANOTHER EXAMPLE (WITH UNEQUAL BUDGETS?) OR AT LEAST UPDATE THE FIGURE). There are two agents with equal budgets, two chores with utilities given by the following matrix $\vec{v}$ (rows are agents, columns are chores):
$$\vec{v} = \left(\begin{array}{cc} 1 & 2 \\  3 &1 \end{array}\right)$$
There are three competitive allocations with disutility profiles depicted on Figure~\ref{fig1}. The  allocations and prices are
$$
\begin{array}{ccc}
z_{1} & 1 & 1/4 \\ 
z_{2} & 0 & 3/4 \\ 
p & 2/3 & 4/3%
\end{array}\qquad 
\begin{array}{ccc}
z_{1} & 1 & 0 \\ 
z_{2} & 0 & 1 \\ 
p & 1 & 1%
\end{array}\qquad 
\begin{array}{ccc}
z_{1} & 2/3 & 0 \\ 
z_{2} & 1/3 & 1 \\ 
p & 3/2 & 1/2%
\end{array}%
$$
\begin{figure}[h!]
	\centering

	{\includegraphics[width=6cm, clip=true]{3comp_alloc.pdf}}
	\caption{Multiple competitive disutility profiles~(blue dots).}
	\label{fig1}
\end{figure}
\end{example}
On Figure~\ref{fig1} we see that the level curves of the Nash product (dotted hyperbolas) and the feasible set are not separated by a hyperplane. This shows that the problem of computing the CR is \emph{non-convex}: competitive utility profiles are \emph{local extrema} of the Nash product on the feasible set frontier: the blue corner is the local minimum and the two points on faces are local maxima.  

We see there can be \emph{many competitive utility profiles}, and thus the set of all competitive allocation can be \emph{disconnected}. The issue of multiplicity is discussed in Section~\ref{results_and_discussion}.
}
\end{comment}

\begin{example}\label{ex_1}
 Two agents are dividing two chores and values are given by 
 $$\vec{v}= \left(\begin{array}{cc} -1 & -8 \\  -1 & -2 \end{array}\right);$$
 rows correspond to  agents and columns to chores. Both agents hate the second chore but the second agent finds it less painful compared to the first chore than agent $1$ . Assume that budgets are $\vec{b}=(-1, -2)$ (i.e., the second agent is entitled to twice as much work as agent $1$). Elementary computations show that there are two competitive allocations
 $$\vec{z^1}=\left(\begin{array}{cc} 1 & 0 \\  0 & 1 \end{array}\right) \  \mbox{with prices} \ \vec{p}^1=(-1,-2) \ \mbox{ and } \ \vec{z^2}=\left(\begin{array}{cc} 1 & \frac{1}{4} \\  0 & \frac{3}{4} \end{array}\right) \  \mbox{with } \ \vec{p}^2=\left(-\frac{1}{3},-\frac{8}{3}\right).$$
These allocations are weighted-envy free: agent $1$ prefers his allocation to $\frac{1}{2}$ of the allocation of the second agent, while agent $2$ thinks that his bundle is better than the doubled bundle of agent~$1$.

The feasible set $\mathcal{U}(\vec{v})$ and utility profiles of the two competitive allocations are depicted in Figure~~\ref{fig1} together with the level curves of the Nash product $|u_1|\cdot |u_2|^2$. 
We see that the level curves of the Nash product (dotted hyperbolas) and the feasible set are not separated by a straight line and thus the competitive allocations are not global extrema of the Nash product:  the utility profile $\vec{u}(\vec{z}^2)$ is the local maximum of the product on the Pareto frontier while the corner of the feasible set, $\vec{u}(\vec{z}^1)$, is a stationary point:  neither local minimum nor maximum.

This example illustrates that the problem of computing competitive allocations is \emph{non-convex}; there can be \emph{many competitive utility profiles}, and in particular the set of competitive allocations can be \emph{disconnected}. 
\begin{figure}[h!]
	\centering
	\vskip -0.5 cm
   {\includegraphics[width=9cm, clip=true, trim=0cm 7.5cm 0cm 6cm]{fig1.pdf}}
   \caption{Competitive utility profiles (blue dots) for Example~\ref{ex_1}. The corner corresponds to $\vec{z}^1$ and the profile inside the face is $\vec{u}(\vec{z}^2)$.}
   	\label{fig1}
\end{figure}
\end{example}




\subsection{Corollaries of Geometric Characterization. Existence and Welfare Theorems}
Theorem~\ref{th_geom}  does not give any recipe for computing outcomes of the competitive rule but allows one to analyze its properties. 
The first corollary of Theorem~\ref{th_geom} is the existence of competitive allocations. Indeed, there is at least one critical point of $\mathcal{N}_{\vec{b}}$ on the Pareto frontier: the one where the level curve of $\mathcal{N}_{\vec{b}}$, given by the equation $\left\{\vec{u} \in \mathbb{R}_{<0}^n: \ \mathcal{N}_{\vec{b}}(\vec{u})=C\right\}$, first touches the Pareto frontier, when we decrease $C$ from large to small values. The corresponding competitive allocation maximizes the Nash product \emph{over all Pareto optimal allocations} (see \cite{BMSY17} for  details of the construction). 
\medskip

The second corollary of Theorem~\ref{th_geom} is that both welfare theorems hold.
\begin{theorem}[Welfare Theorems]\label{cor_welf}
The first and the second welfare theorems hold:
\begin{enumerate}
	\item Any competitive allocation is Pareto optimal;
	\item For any Pareto optimal  allocation $\vec{z}$ at which the utilities are strictly negative, there exist budgets $\vec{b}\in \mathbb{R}_{<0}^n$ such that $\vec{z}$ is competitive with respect to $\vec{b}$.
\end{enumerate}
\end{theorem}
\begin{proof}
By Theorem~\ref{th_geom}, the utility profile of a competitive allocation belongs to $\mathcal{U}^*$, which yields the first item. To prove the second one, note that since $\mathcal{U}$ is a convex polytope and $\vec{u}(\vec{z})$ belongs to its boundary, we can trace a hyperplane $h$ supporting $\mathcal{U}$ at $\vec{u}(\vec{z})$. By Theorem~\ref{th_geom}, it is enough to show that there is a vector of budgets $\vec{b}$, such that $h$ is a tangent hyperplane to the level curve of $\mathcal{N}_{\vec{b}}$ at $\vec{u}(\vec{z})$. This condition is satisfied if the gradient of $\ln (\mathcal{N}_{\vec{b}})$ is orthogonal to $h$ at $\vec{u}$. The gradient is $(|b_i|/|u_i(\vec{z}_i)|)_{i\in [n]}.$ If $h$ is given by the equation  $\left\{V:\ \langle \tau, V\rangle =C\right\}$, the vector $\tau $ is orthogonal to $h$ and thus it is enough to select $b_i=-|\tau_i| \cdot |u_i(\vec{z}_i)|$.  
\end{proof}
 A third corollary of Theorem~\ref{th_geom} is that whether a given allocation is competitive or not can be determined by its utility profile.
\begin{corollary}[Pareto-indifference]\label{corr_Pareto_indiff}
Let $(\vec{v}, \vec{b})$ be a chore division instance.
	If $\vec{z}$ is a competitive allocation and $\vec{z}'$ is another feasible allocation with the same utility profile (that is, $\vec{u}(\vec{z})=\vec{u}(\vec{z'})$), then $\vec{z}'$ is also a competitive allocation for $(\vec{v}, \vec{b})$.
\end{corollary} 


\section{\textbf{Computing the Competitive Rule for Chores}}\label{results_and_discussion}
	
In this section we formulate the main algorithmic result of the paper, discuss its implications and limitations, and present a high-level overview of the algorithm.

\smallskip

Our main result states that 
\emph{finding all the outcomes of the competitive rule is a computationally tractable problem when either the number of agents or the number of chores is bounded.}
Our algorithm runs in strongly polynomial time.

\smallskip

\begin{theorem}\label{main}
Suppose one of the parameters, the number of agents $n$ or the number of chores $m$, is fixed. Then for any tuple $(\vec{v}, \vec{b})$, where $\vec{v}\in \mathbb{R}_{<0}^{n\times m}$ is a matrix of values and $\vec{b}\in \mathbb{R}_{<0}^n$ a vector of budgets,
\begin{itemize}
	\item the set $\mathrm{CU}(\vec{v},\vec{b})$ of all competitive utility profiles
	\item{\fed a set of pairs $(\vec{z},\vec{p})$ such that the allocation $\vec{z}$ is competitive with the price vector $\vec{p}$ and for any $\vec{u}\in \mathrm{CU}(\vec{v},\vec{b})$ there is a pair such that $\vec{u}(\vec{z})=\vec{u}$ }


\end{itemize}
can be computed using  $O\left(m^{\frac{n(n-1)}{2}+3}\right)$ operations, if  $n$ is fixed, or $O\left(n^{\frac{m(m-1)}{2}+3}\right)$, for fixed $m$. This gives an algorithm that runs in strongly polynomial time.\footnote{Such an algorithm makes a polynomial (in $n$ or  $m$, depending on which of the parameters is fixed) number of elementary operations (multiplication, addition, comparison, etc). If the input of the problem ($\vec{v}$ and $\vec{b}$) consists of rational numbers in binary representation, then 
the amount of memory used by the algorithm is bounded by a polynomial in the length of the input. For basics of complexity theory, see~\cite{AB07}.}
\end{theorem}


\paragraph{\textit{\textbf{What if both $n$ and $m$ are large?}}} Theorem~\ref{main} cannot be improved when both $n$ and $m$ are large. It is known ~\cite{BMSY_SCW} that the number of competitive utility profiles can be as large as $2^{\min\{n,m\}}-1$; thus even listing all competitive utility profiles can take exponential time if both $n$ and $m$ are large. 

Theorem~\ref{main} implies that for bounded  $n$ or $m$,  the number of competitive utility profiles is at most polynomial in the free parameter, which is itself an interesting complement to the exponential lower bound from~\cite{BMSY_SCW}. As a byproduct of the construction, we get explicit upper bounds (a combination of Corollary~\ref{cor_number_of_CU_fixed_n} and~\ref{cor_number_of_CU_fixed_m} below).

\begin{corollary}
The number of competitive utility profiles is at most 
$$\min\left\{\left(2m+1\right)^{\frac{n(n-1)}{2}},\ \left(2n+1\right)^{\frac{m(m-1)}{2}}\right\}.$$ 
\end{corollary}

{\fed However the exponential multiplicity of competitive allocations} does not prohibit the existence of an algorithm that finds \emph{one} competitive allocation in polynomial time when both $n$ and $m$ are large.

\smallskip

\begin{open*}
Is it possible to compute \emph{one competitive utility profile} in time polynomial in $n+m$?  If such an algorithm exists, it will give a ``computational'' answer to the ``economic'' question posed in~\cite{BMSY17}: finding a single-valued selection of the competitive rule with attractive properties.
\end{open*}

\paragraph{\textit{\textbf{Computing All Competitive Allocations}}} Theorem~\ref{main} ensures that all competitive utility profiles will be enumerated but does not guarantee finding all the allocations  for each such utility profile. 
It turns out that here the result cannot be improved without restricting the class of preferences. 

In Subsection~\ref{subsect_nondegenerate}, we define the class of non-degenerate matrices of values $\vec{v}$ that contain all the matrices except those that satisfy certain algebraic equations. In particular, a random matrix with respect to any continuous measure on $\mathbb{R}_{-}^{n \times m}$ is non-degenerate with probability~$1$.

In the case of non-degenerate instances, for each Pareto optimal utility profile $\vec{u}$, there is exactly one feasible allocation $\vec{z}$ with $\vec{u}=\vec{u}(\vec{z})$ (see Subsection~\ref{subsect_nondegenerate}) and therefore the algorithm from Theorem~\ref{main} outputs \emph{all competitive allocations}.

However, for degenerate problems, the set $\mathcal{Z}_{\vec{u}}$ of all feasible allocations $\vec{z}$ with $\vec{u}(\vec{z})=\vec{u}$ can be a polytope with an exponential number of vertices even if $n$ or $m$ are fixed and therefore, for general problems, there is no hope of listing even all the extreme points of the set of competitive allocations with given $\vec{u}(\vec{z})=\vec{u}$ (see Example~\ref{ex_degenerate}). 
	
\subsection{The algorithm}\label{subsect_algorithm}
Here  we describe the main ideas and the general structure of the algorithm from Theorem~\ref{main}. The ideas are then developed in subsequent sections.


\paragraph{\textit{Consumption Graphs and Rich Families}} For a feasible allocation $\vec{z}$, we associate the \emph{consumption graph}
 $G_{\vec{z}}$. This is a non-oriented bipartite graph with parts $[n]$ and $[m]$, where an agent $i \in [n]$ and a chore $j \in [m]$ are connected by an edge if and only if $z_{i,j}>0$.

\medskip

The algorithm is inspired by two observations developed in Sections~\ref{sect_recover_U} and~\ref{sect_check_compet} respectively: 
\begin{itemize}
	\item a competitive utility profile can be recovered via explicit formulas if we know the consumption graph of a corresponding competitive allocation, but do not know the allocation itself.
	\item a utility profile can be efficiently checked for competitiveness; an allocation and price vector are obtained as a byproduct.  
\end{itemize}

\begin{definition}[Rich family of graphs]
	Consider a chore division instance $(\vec{v}, \vec{b})$. A family of bipartite graphs $\mathcal{G}$ is called \emph{rich} if  
	for any competitive utility profile $\vec{u} \in \mathrm{CU}(\vec{v}, \vec{b})$ there is a competitive allocation $\vec{z}$ with $\vec{u}(\vec{z})=\vec{u}$ such that the consumption graph $G_{\vec{z}}$ belongs to the family $\mathcal{G}$.
\end{definition}

\subsubsection{How the algorithm works} The algorithm consists of three phases: 

\begin{description}
	\item[  \emph{Phase 1:}] \emph{Generate a rich family of graphs $\mathcal{G}$} (Section~\ref{sect_compute_Pareto}): If either $n$ or $m$ is fixed, then the set of ``maximal weighted welfare'' (MWW) graphs\footnote{The set of maximal weighted welfare graphs is formally defined in Section~\ref{sect_compute_Pareto}.} is rich and can be enumerated in polynomial time.  
	\item[  \emph{Phase 2:}] \emph{Compute a ``candidate'' utility profile for each graph from $\mathcal{G}$} (Section~\ref{sect_recover_U}): For all $G\in \mathcal{G} $ we apply the formula from Proposition~\eqref{prop_recover_z} as if we know that $G$ is a consumption graph of some competitive allocation $\vec{z}$. As a result, we get a ``candidate'' profile $\vec{u}$ which is
	\begin{itemize}
	\item a competitive utility profile $\vec{u}=\vec{u}(\vec{z})$ if there exists a competitive allocation $\vec{z}$ such that $G_{\vec{z}}=G$
	\item some vector from $\mathbb{R}_{<0}^n$ (not necessary feasible), if no competitive allocation has $G$ as the consumption graph. 
	\end{itemize}
	\item[  \emph{Phase 3:}] \emph{Check each ``candidate'' profile $\vec{u}$ for competitiveness} (Section~\ref{sect_check_compet}): A utility profile $\vec{u}$ is competitive if there is a flow of a large enough magnitude in an auxiliary maximum flow problem. For competitive $\vec{u}$ a maximum flow gives a competitive allocation $\vec{z}$ with $\vec{u}=\vec{u}(\vec{z})$ and the corresponding vector of prices can be constructed using explicit formulas (Lemma~\ref{lm_price_net_utilities}).
\end{description}
\subsubsection{Rich family of graphs as a parameterization of the Pareto frontier}
Generating  a rich family of graphs is the most important part of the algorithm and also its complexity bottleneck. Indeed,  during the second phase, the algorithm cycles over graphs $G\in \mathcal{G}$ and thus the size of the family $\mathcal{G}$ determines the number of iterations (each of which takes polynomial time) and hence the running time.  

We get the following trade-off:  family $\mathcal{G}$ must be rich enough to discover all competitive profiles, but be computable in polynomial time (in particular it must contain at most a polynomial number of graphs). 
 
\begin{example*}
	The set of all bipartite graphs with parts $[n]$ and $[m]$ is rich, but contains an exponential number of elements and thus leads to an exponential-time algorithm. This exponential algorithm is easier to implement and for small division problems (say, three agents and five chores) it is a reasonable choice to use.
\end{example*}
The insight for a smaller rich family comes from the First Welfare Theorem~(Theorem~\ref{cor_welf}): the set of consumption graphs of all efficient allocations is clearly rich. However, for degenerate problems, this set can have exponential size; see Example~\ref{ex_degenerate}, where the set of consumption graphs corresponding to one particular Pareto optimal utility profile $U$ contains an exponential number of elements.

We modify this idea by considering a set $\mathrm{MWW}(\vec{v})$ of \emph{maximal weighted welfare (MWW)} graphs (defined in Section~\ref{sect_compute_Pareto}). This set of graphs, closely related to maximal bang per buck (MBB) graphs (see, e.g., ~\cite{AGT_book,devanur2002market} and Subsection~\ref{subsect_fixed_m}), encodes faces of the Pareto frontier (Lemma~\ref{lm_faces_and_MWW}).

The set $\mathrm{MWW}(\vec{v})$  has polynomial size and can be computed in polynomial time even for degenerate problems, if one of parameters $n$ or $m$ is fixed. Computing $\mathrm{MWW}(\vec{v})$ can be interpreted as computing the Pareto frontier itself and thus is of independent interest.


\subsubsection{{\textit{Runtime}}} 
The size of a rich set of graphs $\mathcal{G}$ and the time needed to compute it determine the time complexity of the algorithm. 
Indeed, by Corollaries~\ref{cor_complexity_recover_U} and~\ref{cor_complexity_U_is_compet}, the number of operations needed for the last two phases of the algorithm is bounded by
$|\mathcal{G}|\cdot \left(O\big(nm(n+m)\big)+O\big(n^2m^2(n+m)\big)\right)$.

In Section~\ref{sect_compute_Pareto}, we construct a superset $\mathcal{G}$  of $\mathrm{MWW}(\vec{v})$ with $|\mathcal{G}|$  bounded both by $\left(2m+1\right)^{\frac{n(n-1)}{2}}$ and  by $\left(2n+1\right)^{\frac{m(m-1)}{2}}$. We show
that $\mathcal{G}$ can be computed in $O\big(m^{\frac{n(n-1)}{2}+1}\big)$ operations for fixed $n$ or in $O\big(n^{\frac{m(m-1)}{2}+1}\big)$ for fixed $m$  
 (see Proposition~\ref{prop_superset} for fixed $n$ and Subsection~\ref{subsect_fixed_m} for fixed $m$).
 Thus the whole algorithm runs in polynomial time and the number of operations is bounded by $O\left(m^{\frac{n(n-1)}{2}+3}\right)$ for fixed $n$ or by $O\left(n^{\frac{m(m-1)}{2}+3}\right)$ for fixed $m$. 

\section{Geometry of the Pareto frontier. Computing rich families of bipartite graphs.}\label{sect_compute_Pareto}

A rich family of graphs represents possible  demand structures for competitive allocations and is the main ingredient for  finding competitive utility profiles. The goal of this section is to construct an algorithm for enumerating a rich family of  graphs in polynomial time if either $n$ or $m$ is fixed. 

We define the family of maximal weighted welfare (MWW) graphs which encode faces of the Pareto frontier, show that it is rich, and construct a polynomial algorithm enumerating a superset of all such graphs. 

We begin with several useful characterizations of Pareto optimality, define MWW graphs and explore their relation with faces of the Pareto frontier, prove richness of the family and then proceed with computational issues. 
For fixed $n$, the algorithm is built via reduction to a simple two-agent case. For fixed $m$, we use an agent-item  duality inspired by the Second Welfare Theorem. This duality also shows a relation between MWW graphs and minimal pain per buck (MPB) graphs.
\subsection{Criteria of Pareto optimality: no profitable trading cycles, maximization of weighted utilitarian welfare, and MWW graphs}
In this auxiliary subsection, we reformulate Pareto optimality using various languages which turn out to be useful afterwards.

\paragraph{\textbf{\textit {Profitable trading cycles.}}}
Consider a path $\P=(i_1,j_1,i_2,j_2,\ldots,i_{L}, j_{L},i_{L+1})$, where $L\geq1$, in a complete $([n],[m])$-bipartite digraph.  We define the product of disutilities along the path as
\begin{equation}\label{eq_product}
\pi(\P)=\prod_{k=1}^{L}\frac{|v_{i_k, j_k}|}{|v_{i_{k+1}, j_k}|}.
\end{equation}
A path $\P$ is a cycle if $i_{L+1}=i_1$; a cycle is \emph{simple} if no agent $i_k$ and no chore $j_k$ enter the cycle twice. 

Consider an allocation $\vec{z}$ and a cycle $\mathcal C=(i_1,j_1,\ldots,i_{L+1}=i_1)$, where $L\geq 2$, such that each agent $i_k$ consumes some fraction of chore $j_k$ (i.e., $z_{i_k,j_k}>0$) for $k=1, \ldots,L$. We say that $\mathcal C$ is a \emph{profitable trading cycle} for $\vec{z}$ if $\pi(\mathcal C)>1$. 

\paragraph{\textbf{\textit{Weighted utilitarian welfare and MWW graphs}}}
Consider a vector of weights $\tau\in \mathbb{R}_{>0}^n$ and define the \emph{weighted utilitarian welfare} of an allocation $\vec{z}$ as 
$$W_\tau(\vec{z})=\sum_{i\in [n]}\tau_i \cdot u_i(\vec{z}_i).$$

\begin{definition}[Maximal Weighted Welfare Graph]
Let $\tau \in \mathbb{R}_{>0}^n$ be a vector of weights. 
Consider the $([n],[m])$-bipartite graph such that agent $i \in [n]$ and chore $j \in [m]$ are linked if $$\tau_i \cdot |v_{i,j}|\leq \tau_{i'} \cdot |v_{i',j}| \; \; \mbox{ for each agent } i' \in [n].$$ 
We call this 
the \emph{Maximal Weighted Welfare (MWW)} graph and denote it by $G_\tau=G_\tau(\vec{v})$.
\end{definition}

\smallskip

\noindent The set of all MWW-graphs is denoted by $$\mathrm{MWW}(\vec{v})=\bigcup_{\tau\in \mathbb{R}_{>0}^n} G_\tau(\vec{v}).$$


\begin{proposition}\label{prop_crit_efficiency}
Let $\vec{v} \in \mathbb{R}^{n \times m}_{<0}$ be a matrix of values and $\vec{z}$ a feasible allocation. Then the following statements are equivalent:
\begin{enumerate}
	\item the allocation $\vec{z}$ is Pareto optimal 
	\item there are no simple profitable trading cycles\footnote{Similar characterizations of Pareto optimality are known for the house-allocation problem of ~\cite{shapley}, where $n$ indivisible goods (houses) are allocated among $n$ agents  with ordinal preferences, one to one. See~\cite{abdulkadirouglu2003school} for ex-post efficiency and~\cite{bogomolnaia2001new} for SD-efficiency (aka ordinal efficiency).}
	\item there exists a vector of weights $\tau\in \mathbb{R}_{>0}^n$ such that the consumption graph $G_{\vec{z}}$ is a subgraph of a maximal weighted welfare graph $G_\tau(\vec{v})$
	\item there exists a vector of weights $\tau\in \mathbb{R}_{>0}^n$ such that $\vec{z}$ maximizes the weighted utilitarian welfare $W_\tau$ over all feasible allocations\footnote{The link between Pareto optimal allocations and welfare maximization has a simple geometric origin and holds for any problem with convex set $\mathcal{U}$ of feasible utility profiles. For any point $U$ at the boundary,  we can trace a hyperplane $h$ supporting $\mathcal{U}$. Hence, any $U$ on the boundary maximizes  the linear form $\langle \tau, V\rangle$ over $V\in \mathcal{U}$, where $\tau$ is a normal vector to $h$. Thus, the Pareto frontier of $\mathcal{U}$ corresponds to $\tau$ with positive components.}.
\end{enumerate}
\end{proposition}
For a more general cake-cutting setting, analogs of items~2,3,4 constitute Sections  8, 10, and 7 of \cite{barbanel2005geometry};  the link between Pareto optimality and weighted utilitarian welfare is classic, see~\cite{Varian74}.

In contrast to the analogous results from~\cite{barbanel2005geometry}, Proposition~\ref{prop_crit_efficiency} has a short proof. 

\begin{proof}
We will show the implications $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(4)\Rightarrow(1)$.

\begin{itemize}
\item $(1)\Rightarrow(2):$ Let us show that if there is a simple profitable trading cycle $\mathcal C=(i_1,j_1, \ldots, i_{L+1}=i_1)$, then we can find a Pareto-improvement $\vec{z}'$ of the allocation $\vec{z}$. Indeed, transfer $\varepsilon_k$ amount of $j_k$ from $i_k$ to $i_{k+1}$ where the ratio of $\varepsilon_k$ and $\varepsilon_{k+1}$ comes from the condition that all agents $i_{k+1}$, $k=1, \ldots, {L-1}$ are indifferent between $\vec{z}$ and $\vec{z}'$: $v_{i_{k+1}, j_{k}}\cdot \varepsilon_{k}=v_{i_{k+1}, j_{k+1}}\cdot \varepsilon_{k+1}$. These conditions define epsilons up to a multiplicative constant which can be selected small enough to guarantee feasibility. Profitability of $\mathcal C$ implies that agent $i_1$ is strictly better off: $\varepsilon_L \cdot v_{i_{1},j_L}- \varepsilon_1 \cdot v_{i_{1},j_1}=\varepsilon_L \cdot v_{i_{1},j_L}(1-\pi(\mathcal C))<0$ and thus $\vec{z}'$ dominates $\vec{z}$.

\item $(2)\Rightarrow(3):$ Let $i_1$ be an agent with a non-empty bundle $\vec{z}_{i_1}\ne \vec{0}$. Set its weight to $\tau_{i_1}=1$. For other agents $i$ define $\tau_i$ as $\max \; \pi(\P_{i_1, i})$ where the maximum is taken over all paths $\P_{i_1, i}=(i_1,j_1,\ldots,j_{L},i_{L+1}=i)$ connecting $i_1$ and $i$ such that $z_{i_k, j_k}>0$ for all $k=1,\ldots,L$. {\fed The set of such paths is non-empty: for example, it contains a path $(i_1,j_1,i)$ for any chore $j_1$ with $z_{i_1,j_1}>0$.} By statement $(2)$, eliminating cycles in $\P_{i_1,i}$ can only increase $\pi$ and thus the maximum is finite and is attained on an acyclic path. 

Consider the consumption graph $G_{\vec{z}}$ and let $i \in [n]$ and $j \in [m]$ be an agent and a chore that are 
connected by an edge in $G_{\vec{z}}$. We show that they are also connected in $G_\tau$. For this we must check that $\tau_i \cdot |v_{i,j}|\leq \tau_{i'} \cdot |v_{i',j}|$ for each agent $i'$. Consider an optimal path $\P^*_{i_1, i}$ and extend it to a path $\P_{i_1, i'}$ by adding two extra vertices $j$ and $i'$. By definition of $\tau$ we get
$$\tau_{i'}\geq \pi(\P_{i_1, i'})=\pi(\P^*_{i_1, i})\cdot\frac{|v_{i,j}|}{|v_{i',j}|}=\tau_i\cdot \frac{|v_{i,j}|}{|v_{i',j}|}$$
which is equivalent to the desired inequality.

\item $(3)\Rightarrow(4):$  Statement $(3)$ ensures that each chore $j$ is given to an agent $i$ with the lowest weighted disutility $\tau_i \cdot |v_{i,j}|$. Therefore, $\vec{z}$ has the maximal weighted welfare $W_\tau$ among all feasible allocations.

\item $(4)\Rightarrow(1):$ If $\vec{z}'$ Pareto dominates $\vec{z}$, then $W_\tau(\vec{z}')>W_{\tau}(\vec{z})$. Thus, the maximizer of $W_\tau$ is undominated, which gives Pareto optimality.
\end{itemize}
\end{proof}


If the consumption graph $G_{\vec{z}}$ contains a cycle $\mathcal C$ with $\pi(\mathcal C)<1$, then by inverting the order of vertices we get a profitable trading cycle. Therefore, statement $(2)$ of the proposition implies the following corollary. 
\begin{corollary}\label{cor_unit_cycles}
If an allocation $\vec{z}$ is Pareto optimal and its corresponding consumption graph $G_{\vec{z}}$ contains a cycle $\mathcal C$, then $\pi(\mathcal C)=1$.
\end{corollary}
In other words, $G_{\vec{z}}$ can have cycles only for matrices of values $\vec{v}$ satisfying certain algebraic equations. This observation is known (see the proof of Lemma~1 in \cite{BMSY_SCW})
and motivates us to consider non-degenerate problems, where no such equations hold. It turns out that such non-degenerate problems have better algorithmic properties  (see Subsection~\ref{subsect_nondegenerate} {\fed and~\cite{FedorErel2019}}).

\subsection{ Richness of the MWW family. Encoding faces of the  Pareto frontier by MWW-graphs.}


Recall that a collection of $([n],[m])$-bipartite graphs is \emph{rich} for a division problem  $(\vec{v},\vec{b})$ if
for any competitive utility profile $\vec{u}\in\mathrm{CU}(\vec{v},\vec{b})$ there is a competitive allocation $\vec{z}$, such that $\vec{u}(\vec{z})=\vec{u}$ and the consumption graph $G_{\vec{z}}$ belongs to the collection.

By the first welfare theorem (Theorem~\ref{cor_welf}), any competitive allocation is Pareto optimal. Therefore, Proposition~\ref{prop_crit_efficiency} almost implies richness of the set of all MWW-graphs: indeed, by statement $(3)$ of the proposition, for any Pareto optimal allocation $\vec{z}$, there is a graph $G'\in \mathrm{MWW}(\vec{v})$ containing $G_{\vec{z}}$ as a \emph{subgraph}. However, $G_{\vec{z}}$ itself can be outside of $\mathrm{MWW}(\vec{v})$.

Showing richness requires finding a relation between MWW graphs and faces of the Pareto frontier.


\paragraph{\textbf{Bijection between faces of the Pareto frontier and MWW graphs.}} Consider the polytope $\mathcal{U}\subset \mathbb{R}^{n}$ of feasible utility profiles. If $h$ is a hyperplane touching the boundary of $\mathcal{U}$, then $\mathcal{U}\cap h$ is a \emph{face} of $\mathcal{U}$, see Figure~\ref{fig2}. This face may have arbitrary dimension from $0$ (a vertex) to $n-1$ (a proper face of maximal dimension); see \cite{Ziegler} for the introduction to geometry of polytopes. The Pareto frontier $\mathcal{U}^*$ is a union of faces. 

\smallskip

Assume that the hyperplane $h$ is given by the equation $\left\{ \vec{u} \in \mathbb{R}^n: \ \langle \tau, \vec{u} \rangle = C \right\}$ and fix the sign of $\tau$ in such a way that $\mathcal{U}$ is contained in the half-space $\langle \tau, \vec{x}\rangle \leq C$. Then $f$ has the following dual representation: it maximizes the linear form $\langle \tau, \vec{u} \rangle$ over $\vec{u} \in \mathcal{U}$. The converse is also true: the set of maximizers for any non-zero $\tau$ is a face. 


\begin{figure}[h!]
	\centering

	{\includegraphics[width=11cm, clip=true, trim=0cm 0cm 0cm 0cm]{faces_and_WUW.pdf}}
	\caption{One-dimensional face $f$ as the set $\vec{u} \in \mathcal{U}$  maximizing $\langle \tau, \vec{u} \rangle$  (left);  a zero-dimensional face, i.e.,  an extreme point (right). For faces $f$ of maximal dimension, the vector  $\tau$  is uniquely defined up to a multiplicative constant  while there is a continuum of $\tau$ for lower-dimensional faces (for a given face $f$, the set of $\tau$  forms the interior of the normal cone to $f$ depicted by the green region).}
	\label{fig2}
\end{figure}

\smallskip

Denote by $\mathcal{Z}_f$ the set of all allocations $\vec{z}$ corresponding to a face $f$, that is, $$\mathcal{Z}_f=\{\vec{z}\in\F\mid \vec{u}(\vec{z})\in f\}.$$
\begin{lemma}\label{lm_faces_and_MWW}
There is a bijection $f\leftrightarrow G_f$ between faces of the Pareto frontier and $\mathrm{MWW}(\vec{v})$. A feasible allocation $\vec{z}$ belongs to $\mathcal{Z}_f$ if and only if $G_{\vec{z}}$ is a subgraph of $G_f$. 
\end{lemma}
\begin{proof}
Statement $(3)$ of Proposition~\ref{prop_crit_efficiency} implies the result since there is a one-to-one correspondence between faces of $\mathcal{U}^*$ and solutions to  $\langle\tau, \vec{u} \rangle\to \max $, when $\tau$ ranges over $\mathbb{R}_{>0}^n$.
\end{proof}


\paragraph{\textbf{Richness.}} For any utility profile $\vec{u}$, consider the set $\mathcal{Z}_{\vec{u}}$ of all feasible allocations $\vec{z}$ with $\vec{u}(\vec{z})=\vec{u}$. \begin{lemma}\label{lm_efficient_graphs_are_rich_for_PO}
For any Pareto-optimal utility profile $\vec{u} \in \mathcal{U}^*$, there is a feasible allocation $\vec{z} \in \mathcal{Z}_{\vec{u}}$ such that $G_{\vec{z}}\in \mathrm{MWW}(\vec{v})$.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lm_efficient_graphs_are_rich_for_PO}]
If $\vec{u}$ is a vertex (i.e., a zero-dimensional face $f$), then consider $G_f\in \mathrm{MWW}(\vec{v})$ from Lemma~\ref{lm_faces_and_MWW} and pick any allocation $\vec{z}$ with $G_{\vec{z}}=G_f$. Then the lemma implies that $\vec{u}(\vec{z})=\vec{u}$ and we are done.

If $\vec{u}$ is not a vertex, then we can find a face $f\subset \mathcal{U}^*$ such that $\vec{u}$ is in its relative interior $f_{\mathrm{int}}$ (i.e., $\vec{u} \in f$ but not a boundary point of $f$). Indeed, consider some face $f'$ containing $\vec{u}$; if $\vec{u}$ is not in its relative interior, then we can find a face $f''$ of the boundary of $f'$ such that $\vec{u} \in f''$; since the new face has a smaller dimension, after a finite number of repetitions, we either find a desired face $f$ or find out that $\vec{u}$ is a vertex. 

Fix an auxiliary allocation $\vec{z}_{\max}$ with $G_{\vec{z}_{\max}}=G_f$. Then $\vec{u}(\vec{z}_{\max})\in f$ by Lemma~\ref{lm_faces_and_MWW}. Since $\vec{u} \in f_{\mathrm{int}}$, we can represent the utility profile $\vec{u}$ as $$\vec{u} = \varepsilon \cdot \vec{u}(z_{\max})+(1-\varepsilon) \cdot \vec{u}',$$ 
where the vector $\vec{u}'$ is given by
$$\vec{u}'=\frac{\vec{u}-\varepsilon \cdot \vec{u}(\vec{z}_{\max})}{1-\varepsilon}$$ which belongs to $f$ for $\varepsilon>0$ small enough. Consider an allocation $\vec{z}=\varepsilon \cdot \vec{z}_{\max}+(1-\varepsilon)\vec{z}'$, where $\vec{z}'\in\mathcal{Z}_{\vec{u}'}$. By the construction,  $\vec{u}(\vec{z})=\vec{u}$ and $G_{\vec{z}}=G_f\in \mathrm{MWW}(\vec{v})$.
\end{proof}
We get the following desired corollary. 
\begin{corollary}\label{cor_MWW_graphs_are_rich}
The set of graphs $\mathrm{MWW}(\vec{v})$  is rich. 
\end{corollary}
\begin{proof}
By the second welfare theorem (Theorem~\ref{cor_welf}) any competitive utility profile $\vec{u}$ is Pareto optimal. Thus, Lemma~\ref{lm_efficient_graphs_are_rich_for_PO} allows one to find a feasible allocation $z$ with $\vec{u}(z)=\vec{u}$ and $G_{\vec{z}}\in \mathrm{MWW}(\vec{v})$, which is competitive by the Pareto-indifference property (Corollary~\ref{corr_Pareto_indiff}). 
\end{proof}
{\fed \begin{remark}
		By the construction, the allocation $\vec{z}$ from Lemma~\ref{lm_efficient_graphs_are_rich_for_PO} has the maximal graph $G_{\vec{z}}$ w.r.t. subgraph-inclusion among allocations from $\mathcal{Z}_{\vec{u}}$. This gives an alternative interpretation of $\mathrm{MWW}(\vec{v})$ as the set of all consumption graphs of Pareto-optimal allocations that are maximal w.r.t. inclusion.
	\end{remark}
}

\subsection{Polynomial-time algorithm listing a superset of all MWW-graphs. Fixed number of agents via reduction to the $2$-agent case.}\label{subsect_alg_fix_n}
We explicitly construct $\mathrm{MWW}(\vec{v})$ for two agents and then use the construction to build a polynomial time algorithm which outputs a superset $\mathcal{G}(\vec{v})$ of $MWW(\vec{v})$ for arbitrary fixed $n$.

\paragraph{\textbf{Two agents.}}
For $n=2$ agents, the set of all MWW graphs has the following simple structure described in~\cite{BMSY_SCW} and also used in~\cite{aziz2018fair}. 
Reorder all the chores, from those that are relatively harmless to agent $1$ to those that are harmless to agent $2$: the ratios $|v_{1,j}|/|v_{2,j}|$ must be weakly increasing in $j=1,\ldots,m$.  As we see next, there are two types of graphs in $\mathrm{MWW}(\vec{v})$:
\begin{itemize}
\item \emph{$k/(k+1)$-split, for $k=0,1,\ldots,m$:}  agent $1$ is linked to all chores $1,\ldots,k$ (if any) and agent $2$ is linked to all remaining $k+1,\ldots,m$. No other edges exist.
\item \emph{$k$-cuts, for $k=1,\ldots,m$:} agent $1$ is linked to chores $1,\ldots,k-1$, agent $2$ to chores $k+1,\ldots,m$, and all chores $j$ for which $|v_{1,j}|/|v_{2,j}| = |v_{1,k}|/|v_{2,k}|$ are connected to both agents. No other edges exist.
\end{itemize}
\begin{figure}[h!]
	\centering
	\vskip -0.5 cm
	{\includegraphics[width=9cm, clip=true, trim=0cm 0cm 0cm 0cm]{MWW_graphs.pdf}}
	\caption{Examples of MWW graphs for the two-agent problem with $\frac{v_{1,3}}{v_{2,3}}=\frac{v_{1,4}}{v_{2,4}}$. Because of equal ratios, agents share bads $3$ and $4$ at the $4$-cut.}
	\label{fig3}
\end{figure}
\begin{lemma}
For two agents, any graph $G\in MWW(\vec{v})$ is either a $k/(k+1)$-split or a $k$-cut.\footnote{Geometrically $k/(k+1)$-splits correspond to vertices of the Pareto frontier and $k$-cuts to faces.} Any $k$-cut is contained in $\mathrm{MWW}(\vec{v})$. A $k/(k+1)$-split is contained in $\mathrm{MWW}(\vec{v})$ if and only if one of the following holds: $k=0$, or $k=m$, or $|v_{1,k}|/|v_{2,k}| < |v_{1,{k+1}}| / |v_{2,{k+1}}|$.
\end{lemma}
\begin{proof}
Consider an arbitrary graph $G_\tau$ from $MWW(\vec{v})$. Agent $1$ is linked to chores $j$ such that $\tau_1 \cdot |v_{1,j}|\leq \tau_2 \cdot |v_{2,j}|$ or equivalently to those chores from the ``prefix'' chores with $|v_{1,j}|/|v_{2,j}|\leq \tau_2 / \tau_1$. Similarly, an edge is traced between agent  $2$ and the ``postfix'' $|v_{1,j}| / |v_{2,j}|\geq \tau_2 / \tau_1$. Thus, if the ratio $\tau_2/\tau_1$ is equal to one of the values $|v_{1,k}| / |v_{2,k}|$, for $k=1,\ldots,m$, we get a split allocation and otherwise a cut.
\end{proof}

This lemma implies that for two agents, the set of all MWW graphs can be listed in polynomial time in $m$.

\begin{corollary}\label{cor_MWW_2agents}
For two agents, the set of all MWW graphs contains at most $2m+1$ graphs. All of them can be listed using  $O(m\cdot\log m)$  operations (time needed to sort the ratios) or $O(m)$ if chores are already sorted.
\end{corollary}

\paragraph{\textbf{More than two agents.}} For a division problem with $n\geq 3$ agents given by matrix $\vec{v}$,  consider $n(n-1)/2$ auxiliary two-agent problems, where a pair of agents $i \ne i'$ divides the whole set of chores $[m]$ between themselves (the corresponding $2\times m$ matrix $\vec{v}^{\{i,i'\}}$ is composed by the two rows $\vec{v_i}$ and $\vec{v_{i'}}$ of $\vec{v}$).

Pick an MWW graph $G^{\{i,i'\}}\in \mathrm{MWW}(\vec{v}^{\{i,i'\}})$ for each pair of agents  and construct a graph $G$ for the original problem by the following rule: there is an edge between agent $i$ and a chore $j$  if and only if this edge is presented in $G^{\{i,i'\}}$ for all agents $i'\ne i$.

By cycling over all combinations of graphs $G^{\{i,i'\}}$ we obtain a set $\mathcal{G}=\mathcal{G}(\vec{v})$ of graphs $G$.

\begin{proposition}\label{prop_superset}
The set $\mathcal{G}(v)$ constructed for an $n\times m$  matrix of values  $\vec{v}$ has the following properties:
\begin{itemize}
	\item it contains at most $(2m+1)^{\frac{n(n-1)}{2}}$ graphs
	\item for fixed $n\geq 3$, enumerating the elements of $\mathcal{G}(\vec{v})$ takes time $O\big(m^{\frac{n(n-1)}{2}+1}\big)$
	\item it contains the set  $\mathrm{MWW}(\vec{v})$  (and thus by Corollary~\ref{cor_MWW_graphs_are_rich}, $\mathcal{G}(\vec{v})$ is rich)
\end{itemize}
\end{proposition}
\begin{proof}
By Corollary~\ref{cor_MWW_2agents}, for each pair $\{i,i'\}$ there are at most $2m+1$ different graphs $G^{\{i,i'\}}$, thus at most $(2m+1)^{\frac{n(n-1)}{2}}$ combinations, and we get the first item. The same corollary implies that cycling 
over all combinations of $G^{\{i,i'\}}$ takes  $O\big(m^{\frac{n(n-1)}{2}}\big)$ which for $n\geq 3$ absorbs $O(m\log m)$, the time needed to sort the chores for each pair of agents. When a combination is given, $G$ can be constructed using $O(m)$ operations, yielding the second item.

It remains to check that any graph  $G_\tau(\vec{v})\in \mathrm{MWW}(\vec{v})$ is contained in $\mathcal{G}$. Let us find graphs $G^{\{i,i'\}}$ in the construction of $G$ such that $G=G_\tau(\vec{v})$. Pick $G^{\{i,i'\}}$ equal to $G_{(\tau_i,\tau_{i'})}\in\mathrm{MWW}(\vec{v}^{\{i,i'\}})$. Hence, $i$ is connected to $j$ in $G^{\{i,i'\}}$ iff $\tau_i \cdot v_{i, j}\geq \tau_{i'} \cdot v_{i',j}$. Therefore, an edge $(i,j)$ is traced in $G$ if and only if $\tau_i \cdot v_{i, j}\geq \tau_{i'} \cdot v_{i',j}$ for all $i'$, which by the definition of MWW graphs, is equivalent to $G=G_\tau(\vec{v})$.
\end{proof}

\begin{remark} Note that the set $\mathcal{G}$ may contain some clearly redundant elements: those where some chores are not connected to any agents (thus no feasible allocation corresponds to them), or where some agents consume no chores (hence no competitive allocation has such a consumption graph), or just consumption graphs of Pareto sub-optimal allocations. {Eliminating them may improve the performance of the algorithm in practice. Inefficient graphs can be found using item~2 from Proposition~\ref{prop_crit_efficiency}: inefficiency is equivalent to existence of a cycle with a  multiplicative weight above $1$ in an auxiliary bipartite graph; such cycles can be detected using, for example, a multiplicative version of the Bellman-Ford algorithm.}
\end{remark}
\smallskip

Proposition~\ref{prop_superset} and Lemma~\ref{lm_faces_and_MWW} imply an upper bound on the number of faces of the Pareto frontier. In Section~\ref{sect_recover_U} we show that there is at most one competitive utility profile per face and therefore get the following corollary.
\begin{corollary}\label{cor_number_of_CU_fixed_n}
The number of faces of the Pareto frontier and the number of competitive utility profiles (for a given vector of budgets $\vec{b}$) are both bounded by $(2m+1)^{\frac{n(n-1)}{2}}$.
\end{corollary}

\subsection{Algorithm for a fixed number of chores. Agent-item duality and the relation between MWW and  MPB graphs}\label{subsect_fixed_m}
A polynomial  algorithm for a fixed number of chores $m$ and large $n$ follows from the algorithm for fixed $n$  via the duality that allows one to exchange the roles of agents and chores. We interpret this duality as a repercussion  of the Second Welfare theorem and show that MWW graph of the dual problem is a \emph{minimal pain per buck (MPB)} graph.

\paragraph{\textbf{Agent-item duality via the Second Welfare Theorem.}} For a matrix of values $\vec{v}$ with $n$ agents and $m$ chores, consider the transposed matrix $\vec{v}^T$ where agents and chores exchanged their roles, so we have $m$ agents and $n$ chores. 

There is the natural bijection between bipartite graphs on $([n],[m])$ and $([m],[n])$ and we will not distinguish between them. We say that a bipartite graph $G$ on $([n],[m])$ has \emph{no lonely agents} if every agent $i$ is connected to at least one chore. By $\mathrm{MWW}_{non-lonely}(\vec{v})$ we denote the set of all MWW graphs with no lonely agents.

\begin{proposition}\label{prop_agent_items_duality}
For a matrix $\vec{v}$ of values with non-zero elements we have
$$\mathrm{MWW}_{non-lonely}(\vec{v})=\mathrm{MWW}_{non-lonely}(\vec{v}^T).$$
\end{proposition}

\begin{definition}[Minimal Pain Per Buck (MPB)]
For a matrix $\vec{v}$ of values and a price vector $\vec{p} \in \mathbb{R}_{<0}^m$, the \emph{minimal pain per buck} graph $G_{\vec{p}}(\vec{v})$
is constructed by tracing edges between each agent $i$ and all chores $j$ with minimum disutility/price ratio ${|v_{i,j}|}/{|p_j|}$. 
\end{definition}

In the case of goods, maximal bang per buck (MBB) graphs were introduced in \cite{devanur2002market} to capture the demand structure for competitive allocations as a function of prices. Indeed, if $\vec{z}$ is a competitive allocation for prices $\vec{p}$ and budgets $\vec{b}$, then $G_{\vec{z}}$ is a subgraph of $ G_{\vec{p}}(\vec{v})$ (see Lemma~\ref{lm_MBB} in the appendix).

An immediate corollary of the definitions is the relation between MWW and MPB graphs\footnote{Corollary~\ref{cor_MBB_MWW} allows one to interpret Proposition~\ref{prop_agent_items_duality} as a version of the Second Welfare Theorem: informally, it says that the class of MWW graphs (which encode the consumption structure of Pareto optimal allocation) coincides with the class of MPB graphs (which encode the consumption structure of competitive allocations).}.

\begin{corollary}\label{cor_MBB_MWW}
An MPB graph $G_{\vec{p}}(\vec{v})$  coincides with the MWW graph $G_\tau(\vec{v}^T)$, where $\tau_j=\frac{1}{|p_j|}$.
\end{corollary}
\begin{proof}[Proof of Proposition~\ref{prop_agent_items_duality}]
By the symmetry of the statement, it is enough to show the inclusion  $\mathrm{MWW}_{non-lonely}(\vec{v})\subset\mathrm{MWW}_{non-lonely}(\vec{v}^T).$
Pick a vector $\tau\in \mathbb{R}_{>0}^n$ such that the graph $G=G_\tau(\vec{v})$ has no lonely agents.  By Corollary~\ref{cor_MBB_MWW}, it is enough to find a price vector $\vec{p} \in \mathbb{R}_{<0}^m$ such that $G=G_\vec{p}(\vec{v})$.

 Consider an allocation $\vec{z}$ such that $G_{\vec{z}}=G$. By Proposition~\ref{prop_crit_efficiency}, $z$ is Pareto optimal and $\vec{u}=\vec{u}(\vec{z})\in \mathbb{R}_{<0}^n$ (here we use the fact that there are no lonely agents). By the Second Welfare Theorem, $\vec{z}$ is a competitive allocation for some $\vec{p} \in \mathbb{R}_{<0}^m$ and budgets $b_i=\tau_i \cdot u_i$ (see the proof of Theorem~\ref{cor_welf}). 

Therefore, $G_{\vec{z}}$ is a subgraph of $G_\vec{p}(\vec{v})$. Let us show that these two graphs coincide. Assume the converse: there is an edge $(i,j)$ in $G_\vec{p}(\vec{v})$ that is absent in $G_\tau(\vec{v})$. 
By the definition of MPB graphs we have 
$$\frac{|v_{i,j}|}{|p_j|}=\min_{c\in [m]} \frac{|v_{i,c}|}{|p_c|},$$
and the same equality holds for any agent $i'$ with $z_{i',j}>0$. Thus, $|v_{i,j}| \cdot b_i / p_b = u_i$ (because agent $i$ spends his budget $b_i$ on items with minimal disutility to price ratio) and similarly $|v_{i',j}| \cdot b_{i'} / p_j = u_{i'}$. We obtain the identity
$$\frac{v_{i,j} \cdot b_i}{u_i}=\frac{v_{i',j} \cdot b_{i'}}{u_{i'}}.$$

Taking into account the relation between $\vec{b}$ and $\tau$, we get $\tau_i \cdot v_{i,j}=\tau_{i'} \cdot v_{i',j}=\min_{i''} \tau_{i''} \cdot v_{i'',j}$ (the last equality follows from the definition of $G_\tau(\vec{v})$ and the fact that $z_{i,j}>0$). Thus, the edge $(i,j)$ must exist in $G_\tau(\vec{v})$. This is a contradiction, which completes the proof. 
\end{proof}
\subsubsection{Algorithmic consequences: fixed number of chores $m$} 
If the number of agents $n$ in a problem $(\vec{v},\vec{b})$ is large compared to $m$, we can use the following trick. 

Compute a superset $\mathcal{G}(\vec{v}^T)$ of $\mathrm{MWW}_{non-lonely}(\vec{v}^T)$, using the algorithm from Subsection~\ref{subsect_alg_fix_n}. For fixed $m$, it will take polynomial time in $n$. 
By Proposition~\ref{prop_agent_items_duality},  $\mathrm{MWW}_{non-lonely}(\vec{v}^T)$ coincides with  $\mathrm{MWW}_{non-lonely}(\vec{v})$ which is rich since the set of all MWW graphs is and any competitive allocation with non-zero budgets has no lonely agents. {\fed Thus, $\mathcal{G}(\vec{v}^T)$ is also rich.}

 The number of competitive utility profiles cannot exceed the number of graphs in a rich set. We obtain a mirror version of Corollary~\ref{cor_number_of_CU_fixed_n}.
\begin{corollary}\label{cor_number_of_CU_fixed_m}
The number of competitive utility profiles (for a given vector of  budgets $\vec{b}$) is at most $(2n+1)^{\frac{m(m-1)}{2}}$.
\end{corollary}

\section{Explicit formulas for competitive utility profiles when the consumption graph is known}\label{sect_recover_U}

Suppose we are given an $([n],[m])$-bipartite graph $G$, a matrix of values $\vec{v}\in\mathbb{R}_{<0}^{n\times m}$, and a vector of budgets $\vec{b}\in \mathbb{R}_{<0}^n$. Here we derive an explicit formula that expresses the vector $\vec{u}=\vec{u}(\vec{z})$ of utilities for a competitive allocation $\vec{z}$ with budgets $\vec{b}$ and the consumption graph $G_{\vec{z}}=G$, if such an allocation exists. If there is no such $\vec{z}$, the formula returns some vector $\vec{u} \in \mathbb{R}_{<0}^n$ {\fed that may not correspond to any allocation.}

\smallskip

The question of recovering $\vec{z}$ from $\vec{u}$ is considered in Section~\ref{sect_check_compet}.

\subsection{Influence of agents from the same connected component.} 
 If two agents $i$ and $i'$ share a chore $j$ at a competitive allocation $\vec{z}$, then their utilities are related (see item $(2)$ of Proposition~\ref{prop_characterizations_of_CA} from the appendix): 
\begin{equation}\label{eq_shared_chore}
\frac{v_{i,j} \cdot b_i}{u_i}=\frac{v_{i',j}\cdot b_{i'}}{u_{i'}}.
\end{equation}

This observation can be extended to agents from the same connected component of the consumption graph $G_{\vec{z}}$. Consider two of them, $i$ and $i'$, linked in $G_{\vec{z}}$ by a path 
$$\mathcal{P}_{i, i'}=(i=i_1,j_1,i_2,j_2,\ldots,j_{L},i_{L+1}=i').$$ 
We define the \emph{influence $\pi_{i, i'}$ of agent $i'$ on agent $i$} as the product $\pi(\mathcal{P}_{i, i'})$ of disutilities along the path; see \eqref{eq_product} for the formal definition of $\pi$.
We use convention $\pi_{i, i}=1$. 

The influence is well-defined: if there are different paths from $i$ to $i'$ all of them have the same product of disutilities because for any Pareto optimal allocation, the product along a cycle in $G_{\vec{z}}$ equals $1$ (Corollary~\ref{cor_unit_cycles}). 

By iteratively applying equation \eqref{eq_shared_chore}, we get the following result.
\begin{corollary}
For a competitive allocation $\vec{z}$ with budgets $\vec{b}$, and any agents $i $ and $i'$ from the same connected component of the consumption graph $G_{\vec{z}}$, the following identity holds 
\begin{equation}\label{eq_UiandUj}
\frac{u_i}{b_i}=\pi_{i,i'} \cdot \frac{u_{i'}}{b_{i'}}.
\end{equation}
\end{corollary}
\begin{remark}\label{rem_complexity_pi_i_to_j}
{\fed The influences $\pi_{i, i'}$ can be computed in strongly polynomial time using the depth-first search even if none of $n$ and $m$ are fixed. 

Note that if we compute $\pi_{i, i'}$ starting from a graph $G$ that does not correspond to any competitive allocation, $\pi_{i, i'}$ may depend on a path between $i$ and~$i'$. In this case, we assume that the algorithm can choose any of the paths. In any case, such graphs will be eliminated in the third phase of the algorithm (see next Section~\ref{sect_check_compet}).}
\end{remark}

\subsection{Recovering the competitive utility profile}
Given a graph $G$, denote by $n_j$ the number of agents linked to a chore $j$; this can be seen as the ``degree'' of $j$.

Consider an auxiliary allocation $\overline{\vec{z}}$ obtained by giving $1/n_j$ share of $j$ to each agent linked to $j$. If $n_j=0$ (in this case $G$ is not a consumption graph of any allocation $\vec{z}$), then the chore $j$ remains unallocated. Denote by $\overline{\vec{u}}$ the utility profile of $\overline{\vec{z}}$ and by $N^{i}$ the set of all agents from the connected component of $i$ in $G$. The following proposition gives an explicit formula for a competitive utility profile in terms of $G$.
\begin{proposition}\label{prop_recover_z}
Fix a division problem $(\vec{v},\vec{b})$ and a graph $G$. If there exists a competitive allocation $\vec{z}$ with the consumption graph $G_{\vec{z}} = G$, the following formula holds for $\vec{u} = \vec{u}(\vec{z})$
\begin{equation}
\label{eq_recovering_utilities}
u_i=\left(\frac{b_i}{\sum_{i'\in N^{i}} b_{i'}}\right) \cdot{\sum_{i'\in N^{i}}  \pi_{i, i'} \cdot \overline{u}_{i'}}.
\end{equation} 
\end{proposition}
\begin{proof}
Equations~\eqref{eq_UiandUj} determine competitive utilities for $i'\in N^{i}$ up to a common multiplicative factor. To find it, we need one more condition that relates components $(\vec{u}_{i'})_{i'\in N^i}$. 

Denote by $C^i$ the set of chores consumed by agents from $N^i$.
These agents spend all their budgets on $C^{i}$ and consume them fully. Therefore, we get the balance equation
\begin{equation}
\label{eq_balance}
\sum_{i'\in N^{i}} b_{i'} = \sum_{j\in C^{i}} p_j.
\end{equation}
Using the definition of $\overline{\vec{z}}$ and expressing $p_j$ by Lemma~\ref{lm_price_net_utilities}, we rewrite
the last sum as 
$$\sum_{i'\in N^{i}}\sum_{j\in C^i} p_j \cdot \overline{z}_{i',j}=\sum_{i'\in N^{i}}\sum_{j\in C^i} \frac{v_{i',j} \cdot b_{i'}}{u_{i'}} \cdot \overline{z}_{i',j}.$$
Taking the factor ${b_{i'}}/{u_{i'}}$ out of the internal sum, representing $u_{i'}$ by~\eqref{eq_UiandUj}, and comparing the first equation and the last one, we get that
$$\sum_{i'\in N^{i}} b_{i'} =\sum_{i'\in N^{i}}\frac{\pi_{i, i'}\cdot b_i}{u_i} \cdot \overline{u}_{i'}.$$
Writing $u_i$ using this equation, we obtain the required identity \eqref{eq_recovering_utilities}.
\end{proof}

\begin{corollary}\label{cor_complexity_recover_U}
{\fed For a given problem $(\vec{v},\vec{b})$ and a graph $G$, the candidate utility profile $\vec{u}$ can be computed using $O(nm(n+m))$ operations even if both $n$ and $m$ are free parameters. }\\ 
\emph{Indeed, in order to construct the matrix $\pi_{i,i'}$ of ``distances'', it is enough to find $\pi_{i_0,i}$ for a fixed $i_0$ in each connected component of $G$ (takes $O(nm(n+m))$ if Bellman-Ford algorithm for multiplicative weights is used) and then define $\pi_{i,i'}$ as $\frac{\pi_{i_0,i'}}{\pi_{i_0,i}}$. The connected component $N^{i_0}$ of agent $i_0$ can be discovered ``for free'' by the Belman-Ford algorithm while computing $\pi_{i_0,i}$. When all the ingredients are precomputed, finding $u_i$ by formula~\eqref{eq_recovering_utilities} takes $O(n)$ per agent.}
\end{corollary}


Note that if we use formula~\eqref{eq_recovering_utilities} starting from a graph $G$ that is not a consumption graph of a competitive allocation, then we may get an infeasible vector $\vec{u} \in \mathbb{R}_{<0}^n$.

\section{Checking that a given utility profile is competitive using variational characterization.  Recovering an allocation and prices.}\label{sect_check_compet}

In this section we consider the following problem. We are given a ``candidate'' utility profile $\vec{u}\in\mathbb{R}_{<0}^n$, a vector of budgets $\vec{b} \in \mathbb{R}_{<0}^n$ and a matrix of values $\vec{v}$ without zeros. 
We do not know whether $\vec{u}$ is feasible or not.

The goal is to check whether $\vec{u}$ can be represented as the utility profile $\vec{u}(\vec{z})$ at a competitive allocation $\vec{z}$ with budget vector $\vec{b}$ and, if the answer is positive, to find at least one such allocation and the corresponding vector of prices.

First we describe a characterization of competitive allocations as maximizers of weighted utilitarian welfare. This allows us to reduce the question about the existence of $\vec{z}$ to an analysis of an auxiliary maximum flow problem: $\vec{u}$ is a competitive utility profile if there is a flow of large enough magnitude, and this maximum flow immediately gives $\vec{z}$ {\fed as in \cite{devanur2002market}}.

\subsection{Variational characterization of competitive allocations}
For vectors $\vec{u}, \vec{b} \in \mathbb{R}_{<0}^n$, define the vector 
\begin{equation}\label{eq_tauUB}
\tau(\vec{u},\vec{b})=\left(\frac{b_i}{u_i}\right)_{i\in [n]}
\end{equation}
and consider the weighted utilitarian welfare at an allocation $\vec{y}$ with weights $\tau(\vec{u}, \vec{b})$; recall that this is given by $W_\tau(\vec{y})=\sum_{i\in [n]} \tau_i(\vec{u},\vec{b}) \cdot u_i(\vec{y}_i)$.


\begin{proposition}\label{prop_variational}
A feasible allocation $\vec{z}$ with $\vec{u}=\vec{u}(\vec{z})\in \mathbb{R}_{<0}^n$ is competitive for a chore division problem $(\vec{v}, \vec{b})$ if and only if $\vec{y}=\vec{z}$ maximizes $W_{\tau(\vec{u},\vec{b})}(\vec{y})$ over all feasible allocations $\vec{y}$.
\end{proposition}
{\fed Proposition~\ref{prop_variational} is known (see proof of Theorem~1 in~\cite{BMSY17}); for convenience we also prove it in the appendix (Proposition~\ref{prop_characterizations_of_CA}).}

This variational characterization has  a flavor of fixed points: it defines a competitive allocation $\vec{z}$ as a solution to an optimization problem depending on $\vec{u}(\vec{z})$. Hence it does not help to find $\vec{z}$, but allows one to check whether a given allocation is competitive or not.

\subsection{Maximum flow problem to check competitiveness of the utility profile $\vec{u}$ and recover the allocation $\vec{z}$}

An allocation $\vec{z}$ maximizes the weighted utilitarian welfare $W_{\tau(\vec{u},\vec{b})}$ if and only if $G_{\vec{z}}$ is a subgraph of $G_{\tau(\vec{u},\vec{b})}$ (see Proposition~\ref{prop_crit_efficiency}). Hence, Proposition~\ref{prop_variational} has the following corollary.

\smallskip

\begin{corollary}\label{cor_compet_u_1/2_MaxFlow}
A vector $\vec{u} \in \mathbb{R}_{<0}^n$ is a competitive utility profile for budgets $\vec{b} \in \mathbb{R}_{<0}^n$ and a matrix of values $\vec{v}$ if and only if there exists a feasible allocation $\vec{z}$ such that the following two conditions are satisfied:
\begin{enumerate}
	\item $\vec{u}=\vec{u}(\vec{z})$
	\item the consumption graph $G_{\vec{z}}$ is a subgraph of $G_{\tau(\vec{u},\vec{b})}$.
\end{enumerate}
Moreover, the set of all such $\vec{z}$ (if non-empty) coincides with the set of all competitive allocations with the utility profile $\vec{u}$.
\end{corollary}

The existence of $\vec{z}$ satisfying the conditions of Corollary~\ref{cor_compet_u_1/2_MaxFlow} can be checked by the following maximum flow problem. A similar construction has been described in~\cite{devanur2002market} for checking that the price-vector consists of equilibrium prices.

For each chore $j \in [m]$, denote the minimal weighted disutility by 
$$q_j = \min_{i \in [n]} \left|\frac{b_i \cdot v_{i,j}}{u_i}\right|.$$
Note that for competitive allocations, $q_j$ equals the absolute value of the price $p_j$ (Lemma~\ref{lm_price_net_utilities}).

Construct a network $N(\vec{v},\vec{u},\vec{b})$ by adding a source node $s$ and a terminal node $t$ to a complete bipartite graph with parts $([n],[m])$: the source $s$ is connected to all the agents $[n]$ and the terminal node $t$ is connected to all the chores $[m]$. The capacity of each edge $w(s,i), i\in [n]$ is $|b_i|$; for all edges $(i,j)$ we set $w(i,j)=+\infty$, if this edge exists in $G_{\tau(\vec{u},\vec{b})}$, and $w(i,j)=0$, otherwise (equivalently, edges not presented in $G_{\tau(\vec{u},\vec{b})}$ are not traced);  we set $w(j,t)=q_j$ for all edges $(j,t), j\in [m]$.
Note that no flow $\vec{F}$ in this network can exceed the amount $\sum_{i\in [n]} |b_i|$, which is the total capacity of all edges $(s,i)$. 
\bigskip

\begin{figure}[h!]
	\centering
	\vskip -0.5 cm
	{\includegraphics[width=7.5cm, clip=true, trim=0cm 0cm 0cm 0cm]{max_flow.pdf}}
	\caption{An example of a network $N(\vec{v},\vec{u},\vec{b})$.  Only edges from $G_{\tau(\vec{u},\vec{b})}$ are traced between agents and chores and these edges have a capacity of $\infty$; the capacity of an edge connecting the source $s$  and an agent $i$ is $|b_i|$, and the capacity of an edge from chore $j$ to the terminal node is $q_j$. If there is a competitive allocation $z\in \mathrm{CA}(\vec{v},\vec{b})$ with $G_\vec{z}$ being a subgraph of $G_{\tau(\vec{u},\vec{b})}$, then $q_j$ is equal to equilibrium price $p_j$ and the flow between agent $i$ and chore $j$ is $|p_j|z_{i,j}$, the absolute amount $i$ spends on $j$.}
	\label{fig4}
\end{figure}

\begin{proposition} \label{prop_MaxFlow}
A utility profile $\vec{u}$ is competitive if and only if the two following conditions are satisfied:
\begin{itemize}
	\item $\sum_{i\in [n]} |b_i|=\sum_{j\in [m]} q_j$
	\item a maximal flow $\vec{F}$ in $N(\vec{v},\vec{u},\vec{b})$ has magnitude $\sum_{i\in [n]} |b_i|$.
\end{itemize}
Any such flow defines a competitive allocation $\vec{z}=\vec{z}(\vec{F})$ with $\vec{u} = \vec{u}(\vec{z})$ by $z_{i,j}=F_{i,j}/q_j$ and vice versa.
\end{proposition} 
\begin{proof}
Consider a maximum flow $\vec{F}$ of magnitude $\sum_{i\in [n]} |b_i|=\sum_{j\in [m]} q_j$ and check that $\vec{z}(\vec{F})$ satisfies the conditions of Corollary~\ref{cor_compet_u_1/2_MaxFlow}. For all edges $e=(s,i),\  i\in [n]$ and $e=(j,t),\  j\in [m]$, we have $F_e=w(e)$ because the magnitude of $\vec{F}$ equals the capacity of the corresponding cuts. Therefore, 
$$\sum_{i\in [n]} z_{i,j}=\frac{1}{q_j}\sum_{i \in [n]} F_{i,j}= \frac{1}{q_j} F_{j,t}=1$$ 
for each chore $j$ and 
hence $\vec{z}$ is a feasible allocation. Now check that $\vec{u}(\vec{z})=\vec{u}$: 
$$u_i(\vec{z})=\sum_{j\in [m]} v_{i,j}\cdot z_{i,j}=\sum_{j\in [m]} \frac{v_{i,j}}{q_j} \cdot F_{i,j} =\sum_{j\in [m]} \frac{u_i}{|b_i|}\cdot F_{i,j}=\frac{u_i}{|b_i|}\sum_{j\in [m]} F_{i,j}=\frac{u_i}{|b_i|} \cdot F_{s,i}=u_i.$$
Therefore, the first condition of the corollary holds. The second one ($G_{\vec{z}}$ is a subgraph of $G_{\tau}$) is fulfilled automatically and thus $\vec{z}$ is a competitive allocation and $\vec{u}=\vec{u}(\vec{z})$ is a competitive utility profile.

We now check that if $\vec{z}$ is a competitive allocation and $\vec{u}=\vec{u}(\vec{z})$, then $\sum_{i\in [n]} |b_i|=\sum_{j\in [m]} q_j$ and there is a maximum flow $\vec{F}$ with magnitude $\sum_{i\in [n]} |b_i|$ given by $F_{i,j}=z_{i,j}q_j$. Indeed, as $\vec{z}$ is competitive, we have $q_j=-p_j$, where $\vec{p}$ is the competitive price vector (Lemma~\ref{lm_price_net_utilities}). Then 
the condition $\sum_{i\in [n]} |b_i|=\sum_{j\in [m]} q_j$ is satisfied because the amount of money spent equals the sum of prices. Consider a flow $\vec{F}$ that represents how much money (in absolute value) each agent $i$ spends on a particular chore $j$. Define $F_{s,i}$ as the total spending of $i$ which equals $|b_i|$
(and thus the flow saturates each edge $(s,i)$ and has the proper magnitude); $F_{i,j}=z_{i,j}|p_j|$ is the absolute value  of the amount  $i$ spends on $j$. Thus we have a balance equation $F_{s,i}=|b_i|=\sum_{j\in [m]} F_{i,j}$ and capacity constraints are satisfied since $G_{\vec{z}}$ is a subgraph of $G_{\tau(\vec{u},\vec{b})}$. For each chore $j$ the inflow $\sum_{i}F_{i,j}$ is the total number of money spent on $j$, which equals the absolute value of the  price $|p_j|$. Therefore defining $F_{j,t}=|p_j|$ we get a feasible flow of magnitude $\sum_{i\in [n]} |b_i|$ in $N(\vec{v},\vec{u},\vec{b})$.
\end{proof}	

\paragraph{\textbf{Algorithmic consequences.}} There are many efficient algorithms for solving maximum flow problems. For example, the Edmonds-Karp algorithm has linear runtime in the number of vertices in the network and quadratic in the number of edges~\cite{Tardos_book}. Proposition~\ref{prop_MaxFlow} and Lemma~\ref{lm_price_net_utilities} thus yield the following algorithmic corollary.

\begin{corollary}\label{cor_complexity_U_is_compet}
Given a chore division problem $(\vec{v}, \vec{b})$ and a vector $\vec{u} \in \mathbb{R}_{<0}^n$
\begin{itemize}
	\item it can be checked whether $\vec{u}$ is a competitive utility profile, and
	\item if the answer is positive, a competitive allocation $\vec{z}$ with $\vec{u}(\vec{z})=\vec{u}$  and the corresponding vector of prices $\vec{p}$ can be computed
\end{itemize}
in time $O((m+n)m^2n^2)$.
\end{corollary}

\subsection{Computing  \emph{all} competitive allocations}\label{subsect_nondegenerate}
For any feasible vector of utilities $\vec{u}\in \mathcal{U}$ the set  $\mathcal{Z}_{\vec{u}}$ of feasible allocations $\vec{z}$ with $\vec{u}(\vec{z})=\vec{u}$ is a convex polytope. Therefore, for given $\vec{v}$ and $\vec{b}$, the set of all competitive allocations $\mathrm{CA}(\vec{v},\vec{b})$ is a disjoint union of convex polytopes.

By computing a polytope $P$ we will assume enumerating a finite number of points $p_1,\ldots,p_k$ such that $P$ is their convex hull.

It turns out that the set of all competitive allocations can be computed efficiently for ``non-degenerate'' division problems but this task becomes computationally non-tractable for the set of degenerate  $\vec{v}$ having Lebesgue measure zero.

\paragraph{\textbf{General problems: enumerating all competitive allocations can be difficult.}}
Finding the set of \emph{all competitive allocations} is hard for a general division problem: for a fixed number of agents $n$ computing even one connected component of  $\mathrm{CA}(\vec{v},\vec{b})$ may take an exponential number of operations in $m$. Let us illustrate it by the following example.
\begin{example}\label{ex_degenerate}
Two agents divide the set $[m]$ of identical chores: $v_{i,j}=-1$ for all $i,j$. Budgets are equal. The set of feasible utilities $\mathcal{U}$ is the linear segment between $(-m,0)$ and $(0,-m)$. The only critical point of the Nash product $|u_1|\cdot|u_2|$ on this interval is the point $\vec{u}=\left(-\frac{m}{2},-\frac{m}{2}\right)$. The set of all competitive allocations is thus the convex hull of all  $\vec{z}$ with $z_{i,j}\in\{0,1\}$  such that each row of the matrix $\vec{z}$ has $m/2$  non-zero elements and each column has only one. The number of such matrices is given by a binomial coefficient $C_{m}^{{m}/{2}}$ which grows exponentially for large $m$.

Therefore, the set of all competitive allocations has an exponential number of extreme points and  enumerating them all takes at least an exponential number of operations.
\end{example}

\paragraph{\textbf{Non-degenerate division problems: finding all competitive allocations is easy.}} It turns out that the situation where there are many allocations corresponding to the same Pareto optimal utility profile $\vec{u}$ is extremely rare. As it was observed in~\cite{BMSY_SCW} (see Lemma~2 there), it can occur only if matrix $\vec{v}$ satisfies certain algebraic conditions.
\begin{proposition}\label{prop_nondegenerate}
Consider a matrix $\vec{v}$ with strictly negative entries. If for any cycle $\mathcal C$ in a complete bipartite graph the product $\pi(\mathcal C)\ne 1$ (the product $\pi$ is defined by formula~\eqref{eq_product}), then for any Pareto optimal utility profile $\vec{u}$ the set of corresponding allocations $\mathcal{Z}_{\vec{u}}$ is a singleton $\{\vec{z}\}$ and the allocation $\vec{z}$ has acyclic consumption graph $G_{\vec{z}}$.

If $\vec{v},\vec{u}$, and $G_{\vec{z}}$ are given, the allocation $\vec{z}$ can be recovered in strongly polynomial time {\fed (both $n$ and $m$ are free parameters).}
\end{proposition}
By Theorem~\ref{main}, the set of competitive utility profiles can be computed in strongly polynomial time for fixed $n$ or $m$. Combining this result with Proposition~\ref{prop_nondegenerate}, we see that for  $\vec{v}$ satisfying the conditions of the proposition, the set of all competitive allocations can also be computed in strongly polynomial time.
\begin{remark} {\fed If $n$ or $m$ are fixed, then we can check whether a given matrix $\vec{v}$ satisfies conditions of Proposition~\ref{prop_nondegenerate} in strongly polynomial time by inspecting each simple cycle (in a bipartite graph with parts $[n]$ and $[m]$ there are at most $(nm)^{\min\{n,m\}}$ of them\footnote{There are at most $n$ choices for the ``first'' vertex of a cycle, $m$ options for the second, $n-1$ options for the third plus one option to complete the cycle, etc. Therefore, there are not more than $(nm)^q$ cycles visiting each part of the graph at most $q$ times. For a simple cycle, $q$ cannot exceed the size of the smaller component. This leads to the upper bound $(nm)^{\min\{n,m\}}$ for the total number of simple cycles in a bipartite graph.}).
	
A multiplicative version of the Bellman-Ford algorithm for finding negative cycles gives a strongly polynomial algorithm if none of the parameters is fixed. }
\end{remark}
	\begin{comment}
Indeed it is enough to check simple cycles (each vertex is visited at most once). For a bipartite graph with components of sizes $n$ and $m$ the total number of simple cycles does not exceed\footnote{There are at most $n$ choices for the ``first'' vertex of a cycle, $m$ options for the second, $n-1$ options for the third plus one option to complete the cycle, etc. Therefore, there are not more than $(nm)^q$ cycles visiting each part of the graph at most $q$ times. For a simple cycle, $q$ cannot exceed the size of the smaller component. This leads to the upper bound $(nm)^{\min\{n,m\}}$ for the total number of simple cycles in a bipartite graph.} $(nm)^{{\min\{n,m}\}}$. Therefore each simple cycle $\mathcal C$ can be checked. The length of such a cycle does not exceed $2\min\{n,m\}$ and therefore checking $\pi(\mathcal C)\ne 1$ can also be done in strongly polynomial time.
\end{comment}
\begin{proof}[Proof of Proposition~\ref{prop_nondegenerate}.]
Any $\vec{z}\in \mathcal{Z}_{\vec{u}}$ has acyclic $G_{\vec{z}}$ because by Proposition~\ref{prop_crit_efficiency} (statement~$(2)$) any cycle we must have $\pi(\mathcal C)=1$ which violates the assumption on $\vec{v}$.

If $\vec{z}$ and $\vec{z}'$ are contained in $\mathcal{Z}_{\vec{u}}$, then $G_{\vec{z}}=G_{\vec{z'}}$ since otherwise $G_{\frac{\vec{z}+\vec{z}'}{2}}$ has a cycle (see Lemma~2 in \cite{BMSY_SCW} for a detailed argument).

Therefore, all allocations $z\in \mathcal{Z}_{\vec{u}}$ have the same consumption graph $G$. The proof is completed by the algorithm that takes $(\vec{v},\vec{u}=\vec{u}(\vec{z}))$ and an acyclic consumption graph $G=G_{\vec{z}}$ and outputs the unique  allocation $\vec{z}$\footnote{The  authors are grateful to Ekaterina Rzhevskaya for suggesting this algorithm.}:
\begin{itemize}
\item Since $G$ is acyclic, there is a leaf: a vertex with degree $1$. Pick such a leaf.
\begin{itemize}
\item If the leaf is a chore, then it must be allocated to an agent consuming it and then eliminated from $G$.
\item If the leaf is an agent $i$, denote by $\vec{y}_i$ the bundle of chores already allocated to $i.$  There is exactly  one chore $j$ linked to $i$ but not yet allocated to him.

 A share $z_{i,j}$ of $j$ must satisfy the condition $\vec{u}_i=\vec{u}_i(\vec{y}_i) + v_{i,j} z_{i,j}$. Define $\vec{z}_i$ as the union of $\vec{y}_i$ and $z_{i,j}$ the amount of $j$.

An agent $i$ is eliminated from $G$; the chore $j$ is eliminated if is already fully allocated.
\end{itemize}
\item The procedure is repeated until there are no vertices left in $G$.
\end{itemize}
Since all the decisions are dictated by $G$ and the condition $\vec{u}(\vec{z})=\vec{u}$, the allocation $z$ constructed by the algorithm is the unique element of $\mathcal{Z}_\vec{u}$.
\end{proof}




\section{Finding approximately-fair allocations of indivisible chores}\label{sect_indiv}
If items are indivisible, envy-free allocations may fail to exist (e.g., one item and two agents). This motivates considering relaxed fairness notions.

Recently \cite{barman2018} described how to round a divisible competitive allocation with goods in order to get an approximately fair  Pareto optimal indivisible allocation. Their approach extends word by word to the case of chores. We will describe the main ingredients and refer to the original paper for the details of construction.
\subsection{Relaxed fairness notions} An allocation $\vec{z}$ is indivisible if $z_{i,j}$ equals either $0$ or $1$. We will  identify an indivisible bundle $\vec{z}_i$ with the set of those chores that are consumed by $i$; this will allow us using a set-theoretic notation.  
\begin{definition}[weighted-EF$_1^1$] 
	For a weight vector $\beta\in \mathbb{R}_{>0}^n$, an indivisible allocation $\vec{z}$ of chores is envy-free up
	to removal of a chore from the first bundle and addition of another chore to the other bundle if for any pair of agents $i$ with non-empty bundle $\vec{z}_i$ and $i'$ there are two chores $j\in \vec{z}_i$ and $j'\in [m]$ such that 
	\begin{equation}\label{eq_EF11}
	\frac{u_i(\vec{z}_i\setminus\{j\})}{\beta_i}\geq  \frac{u_i(\vec{z}_{i'}\cup\{j'\})}{\beta_{i'}}.
	\end{equation}
\end{definition}
In the original definition for goods from \cite{barman2018}, an agent $i$ adds one item to his own bundle and throws away an item from the bundle of $i'$.

Another popular fairness property, Proportionality, claims that every agent must prefer his bundle to equal division. Its relaxed version was introduced  for the case of goods in~\cite{conitzer2017fair}. For chores we have a mirror-definition.
\begin{definition}[weighted-Prop$1$] 
	An indivisible allocation of chores $\vec{z}$ is weighted-proportional up to one chore  with a weight vector $\beta\in \mathbb{R}_{>0}^n$ if for each agent $i$ with non-empty bundle $\vec{z}_i$ there is a chore $j\in \vec{z}_i$ such that
	\begin{equation}\label{eq_prop1}
	u_i(\vec{z}_i\setminus\{j\}) \geq \frac{\beta_i}{\sum_{i'=1}^n \beta_{i'}} u_i([m]).
	\end{equation}
\end{definition}

\subsection{The result}
\begin{theorem}\label{prop_indiv}
	For any chore division problem $(\vec{v}, \vec{b})$, there exists an indivisible allocation $\vec{z}$ that is Pareto optimal in the divisible problem ($\vec{u}(\vec{z})\in\mathcal{U}^*$) and satisfies weighted-EF$_1^1$ and weighted-Prop$1$.
	
	If the number of agents $n$ or the number of chores $m$ is fixed, then such an allocation can be found in strongly polynomial time.	
\end{theorem}
Note that the algorithmic part of the proposition is non-trivial only for the case of fixed $n$ (for fixed $m$, the total number of indivisible allocations $n^m$ is polynomial in $n$ and thus the exhaustive search gives a strongly polynomial algorithm).

Theorem~\ref{prop_indiv} is a combination of Theorem~\ref{main} (algorithm for computing a divisible competitive allocation) and the following theorem, which is the straightforward modification of a similar result of \cite{barman2018} for goods.

\begin{theorem}[Barman and Krishnamurthy \cite{barman2018}]\label{th_Barman}
	For a given matrix of values $\vec{v}$ with $v_{i,j}<0$, a vector of budgets $\vec{b}\in \mathbb{R}_{<0}^n$, and a competitive  allocation $\vec{z}$ with a vector of prices $\vec{p}$, there exists an integral feasible allocation $\vec{z'}$ that  is competitive for the same vector of prices $\vec{p}$ and a new vector of budgets $\vec{b}'\in \mathbb{R}_{-}^n$ that is close to $\vec{b}$: 
	\begin{itemize}
		\item for each agent $i$ with non-empty $\vec{z}_i'$, there are chores $j\in \vec{z}'_i$ and $j'\in [m]$ such that 
		\begin{equation}\label{eq_budgets_are_close}
		b_i-|p_j|\leq b_i'\leq b_i+|p_{j'}|.
		\end{equation}
		\item for agents $i$ with empty $\vec{z}_i'$, there is a chore  $j'\in [m]$ such that 
		\begin{equation}\label{eq_budgets_are_close_zero}
		b_i < b_i'=0 < b_i+|p_{j'}|.
		\end{equation}
	\end{itemize}
	Allocation $\vec{z}'$ can be computed in strongly polynomial time.
\end{theorem}	
\begin{proof}
	The proof repeats the one for goods (Theorem~3.1 in \cite{barman2018}) without any changes. We briefly describe the two main steps:
	\begin{enumerate}
		\item The first step of the rounding procedure is to find a feasible allocation $\vec{z^\mathrm{acyc}}$ with $\vec{u}(\vec{z})=\vec{u}(\vec{z}^\mathrm{acyc})$ and acyclic consumption graph $G_{\vec{z}^\mathrm{acyc}}$. This can be done for any Pareto optimal allocation: each cycle in $G_\vec{z} $ can be broken by a cyclic exchange that leaves every agent indifferent (see Lemma~1 in~\cite{BMSY_SCW} and Proposition~\ref{prop_crit_efficiency}). Alternative  construction for competitive allocations can be found in \cite{barman2018}\footnote{Since every Pareto optimal allocation is competitive, the two approaches are equivalent.}.
		
		Note that for almost all matrices $\vec{v}$, this cycle-elimination step is redundant because a consumption graph of any Pareto optimal allocation $\vec{z}$ can contain no cycles (see Theorem~\ref{prop_indiv}).
		
		\item By Lemmas~\ref{lm_MBB} and~\ref{lm_price_net_utilities}, the allocation $\vec{z}^\mathrm{acyc}$ is competitive with the same  $\vec{p}$ and $\vec{b}$.
		
		The  allocation $\vec{z}^\mathrm{acyc}$  is rounded using the following procedure: 
		
		Start with a graph $G=G_{\vec{z}^\mathrm{acyc}}$. Fix an orientation of all edges by picking a ``root'' agent in each connected component of $G$ (thus making it a rooted tree) and orienting all edges from the root to leaves.
		\begin{itemize}
			\item[i)] If a chore $j$ is linked to only one agent $i$ in $G$, allocate $j$ to $i$ and eliminate $j$ from $G$. Repeat for all such chores. 
			\item[ii)] Pick a ``root'' agent $i$. Consider the set $\vec{y}_i$ of chores already allocated to $i$. 
			\begin{itemize}
				\item  While there is a chore $j'$ connected to $i$ such that $p_{j'}+\sum_{j\in \vec{y}_i}p_j  \geq b_i$, add $j'$ to $\vec{y}_i$ and eliminate $j'$ from $G$.
			\end{itemize}
			The final allocation $\vec{z}_i'$ of agent $i$ is set to be equal to $\vec{y}_i$; agent $i$ is eliminated from $G$. 
			\item[iii)] {\fed If there are ``root'' chores (former ``children'' of $i$), allocate them arbitrarily to their ``child'' agents and eliminate from $G$.}
		\end{itemize}
	   {\fed Steps ii)-iii) are repeated until there are no vertices left in $G$.}
	
	
		The resulting allocation $\vec{z}'$ is competitive with the vector of prices $\vec{p}$ and some budget $\vec{b}'$ with $b_i'=\sum_{j\in \vec{z}_i'}p_j$ because agent $i$ consumes only those items he consumed at the allocation $\vec{z}$ and thus MPB conditions are fulfilled (see Lemma~\ref{lm_MBB}). 
		
		By the construction, if $b_i<b_i'$ then there is always a chore $j'$ linked to $i$ in $G_{\vec{z}^\mathrm{acyc}}$ but not allocated to $i$ at $\vec{z}_i'$ and such that $b_i'-|p_{j'}|\leq b_i$; this gives the right-hand side of inequalities~\eqref{eq_budgets_are_close} and~\eqref{eq_budgets_are_close_zero}. Similarly, if $b_i> b_i'$, eliminating the last chore allocated to $i$ from his bundle changes the sign of the inequality thus giving the left-hand side of~\eqref{eq_budgets_are_close}. Remaining cases are verified similarly.
	\end{enumerate}
\end{proof}
Let us check that Theorems~\ref{th_Barman} and~\ref{main} together imply Theorem~\ref{prop_indiv}.
\begin{proof}[Proof of Theorem~\ref{prop_indiv}]
	By Theorem~\ref{main} we can compute a competitive  allocation $\vec{z}$ with the vector of budgets $\vec{b}=-\beta$ and  Theorem~\ref{th_Barman} shows that from $\vec{z}$ 
	we can build integral competitive allocation $\vec{z'}$ with a budget satisfying~\eqref{eq_budgets_are_close} and~\eqref{eq_budgets_are_close_zero}. This allocation is Pareto optimal by the first welfare theorem (Proposition~\ref{cor_welf}). 
	
	For EF$_{1}^{1}$, consider agents $i$ with non-empty $\vec{z}_i'$ and $i'$. By~\eqref{eq_budgets_are_close} we pick  $j\in \vec{z}_i'$ and $j'\in [m]$ such that $\sum_{c\in \vec{z}_i'\setminus\{j\}}p_c\geq -\beta_i$ and similarly $\sum_{c\in \vec{z}_{i'}'\cup\{j'\}}p_c\leq -\beta_j$. Therefore, a bundle $\frac{\beta_i}{\beta_j}(\vec{z}_{i'}'\cup\{j'\})\cup\{j\}$ has a lower price than $\vec{z}_i'$ and thus the inequality~\eqref{eq_EF11} follows from the fact that $i$ maximizes his utility among all bundles with a lower price. 
	
	To prove Prop$1$, note that the bundle $\frac{\beta_i}{\sum_{i'=1}^n \beta_{i'} }[m]$ has the price $-\beta_i$. By~\eqref{eq_budgets_are_close}, we can find $j\in \vec{z}_i'$ such that the price of $\vec{z}_i'\setminus\{j\}$ is higher than $-\beta_i$. Therefore,  $\frac{\beta_i}{\sum_{i'=1}^n \beta_{i'} }[m]\cup\{j\}$ is cheaper than $\vec{z}_i'$ and~\eqref{eq_prop1} follows since agent $i$ maximizes his utility on the budget constraint.
\end{proof}




\section{Concluding remarks}\label{sect_conclusions}

Our main contribution is the new approach for computing competitive allocations for economies, where the set of competitive allocations may be disconnected. 

\medskip 

Several directions remain open. First, it is not known whether one {\fed competitive allocation  of chores} can be computed in polynomial time {\fed if neither $n$ nor $m$ are fixed.} Second, we have seen that for economies with chores, computing all competitive utility profiles is not harder than computing the Pareto frontier. This could be an example of a general effect and we expect that the algorithm extends to other division problems, where the Pareto frontier can be computed in polynomial time.

\medskip

\textbf{Mixed Problems}. {\fed Extension of our approach to the case of goods is straightforward and is simpler, both conceptually and in implementation than existing algorithms.}
		
{\fed We expect that
	our approach generalizes to mixed problems  (with goods and chores) as well.}

\medskip

\textbf{Fair Assignment.} In the fair assignment problem, the set of feasible allocations is restricted to those that satisfy an additional ``lottery'' constraint: for any agent {\fed $i\in [n]$ we have $\sum_{j\in [m]} z_{i,j}=\frac{m}{n}$ (for $n=m$ this means that each agent $i$ receives a lottery on $[m]$).} The competitive rule for fair assignment was studied by~\cite{HZ} and almost forty years later, the first algorithm was proposed {\fed in~\cite{Tardos} with the same performance as  our algorithm for chores (polynomial in $n$ for fixed $m$ and in $m$ for fixed $n$).}

{\fed The algorithm  of~\cite{Tardos} is based on the ``black-box'' of the cell enumeration technique, while our approach could plausibly give an alternative explicit construction.} 

\medskip

\textbf{Other Constrained Economies.} {\fed An economy with chores can be reduced to a constrained economy with goods~\cite{BMSY17}: for each chore $j$ introduce an auxiliary good $\overline{j}=$``not doing $j$''; then there are $n-1$ units of $\overline{j}$ while no agent can consume more than one unit. This suggests that our approach may be applicable to computing the competitive rule in other constrained economies.}

{\fed For example,} agents may have individual caps on consumption of a particular item $z_{i,j}\leq C_{i,j}$ or may have caps on total consumption $\sum_{j\in [m]} z_{i,j}\leq C_i$. Computing competitive allocations in these settings is an open problem, which perhaps can be attacked using our approach.
The main question is: can we compute the Pareto frontier in polynomial time for these constrained problems like we do in Section~\ref{sect_compute_Pareto}?


\medskip

{\fed \textbf{Other applications.} The technique of computing the Pareto frontier seems to be a useful tool beyond applications to the competitive rule. 
It was recently used by~\cite{FedorErel2019} to construct fair Pareto optimal allocations with a minimal number of shared items.  

In general, the approach could be used for building efficient algorithms, when a certain objective function (e.g., social welfare or the number of shared goods) is to be minimized over the set of Pareto optimal allocations under fairness constraints.
}


\nocite{*}
\addcontentsline{toc}{section}{\protect\numberline{}References}%

\bibliographystyle{alpha}

