text:
\section{Introduction}
The problem of fair division is concerned with allocating items to agents in a \textit{fair} and \textit{efficient} manner. Formally introduced by Steinhaus \cite{steinhaus}, fair division is an active area of research studied across fields like computer science and economics. Most work has focused on the fair division of \textit{goods}: items which provide non-negative \textit{value} (or utility) to the agents to whom they are allocated. However, several practical scenarios involve \textit{chores} (or bads). Chores are items which impose a \textit{cost} (or disutility) to the agent to whom they are allocated. For instance, household chores such as cleaning and cooking often need to be fairly distributed among members of the household. Likewise, teachers have to divide teaching load, stakeholders have to divide liabilities upon dissolution of a firm, etc. These examples highlight the importance of allocating \textit{chores} in a fair and efficient manner. Agencies responsible for designing such allocations must take into account the differences in preferences of agents in order for the allocation to be acceptable to all those involved.

Arguably, the most popular notion of fairness is envy-freeness (EF) \cite{foleyEF, VARIAN1974-efpo}, which requires that every agent weakly prefers the bundle of items allocated to them over the bundle of any other agent. When items are \textit{divisible}, i.e., can be shared among agents, EF allocations are known to exist. However, in the case of \textit{indivisible} items, EF allocations need not exist. For instance, while dividing one chore between two agents, the agent who is assigned the chore will envy the other. Since the fair division of indivisible items remains an important problem, several relaxations of envy-freeness have been defined, first in the context of goods, and later adapted to chores.

A widely studied relaxation of envy-freeness is \textit{envy-freeness up to one item} (EF1), defined by Budish~\cite{budish2011approxCEEI} in the context of goods. For chores, an allocation is said to be EF1 if for every agent, the envy disappears after removing one chore assigned to her. It is known that an EF1 allocation of chores exists and can be efficiently computed~\cite{lipton,bhaskar2020chores}. However, an EF1 allocation may be highly inefficient. Consider for example two agents $A_1$ and $A_2$ and two chores $j_1$ and $j_2$ where $A_i$ has almost zero cost for $j_i$ and high cost for the other chore. The allocation in which $j_1$ is assigned to $A_2$ and $j_2$ is assigned to $A_1$ is clearly EF1. However both agents incur high cost, which is highly inefficient. The allocation in which $j_i$ is assigned to $A_i$ is more desirable since it is both fair as well as efficient.

The standard notion of economic efficiency is Pareto optimality (PO). An allocation is said to be PO if no other allocation makes an agent better off without making someone else worse off. Fractional Pareto optimality (fPO) is a stronger notion requiring that no other fractional allocation makes an agent better off without making someone else worse off. Every fPO allocation is therefore PO, but not vice-versa.

An important question is whether the fairness and efficiency notions of EF1 and PO (or fPO) can be achieved in conjunction, and if so, can they be computed in polynomial-time. For the case of goods, Barman et al.~\cite{Barman18FFEA} showed that an EF1+PO allocation exists and can be computed in pseudo-polynomial time. Improving this result, Garg and Murhekar~\cite{murhekar2021aaai} showed that an EF1+fPO allocation can be computed in pseudo-polynomial time. For the case of chores, it is unclear whether EF1+PO allocations even exist, except for simple cases like identical valuations. Settling the existence of EF1+PO allocations (and developing algorithms for computing them) has turned out to be a challenging open problem.

In this paper, we present the first non-trivial results on the EF1+PO problem for chores. We study the class of \textit{bivalued} instances, where there are only two costs, i.e., for every agent a chore costs either $a$ or $b$, for two non-negative numbers\footnote{\label{footnote:binary}In fact, we can assume the two values are positive, since one of them being zero implies the setting is \textit{binary}, in which case computing an EF1+PO allocation is trivial by first assigning chores to agents which have 0 cost for them, and then allocating almost equal number of chores of cost 1 to everyone.} $a$ and $b$. Bivalued instances are a well-studied class in the fair division literature, we list several works in Section~\ref{sec:relatedwork}. In particular, Amanatidis et al.~\cite{amanatidis2020mnwefx} showed that allocations that are envy-free upto \textit{any} good (EFX), which generalizes EF1, can be efficiently computed for bivalued goods. Recently, Garg and Murhekar~\cite{garg2021sagt} showed that EFX+fPO allocations can be computed in polynomial-time for bivalued goods. Showing positive results for bivalued chores, our first result is:

\begin{result}
For bivalued instances with $n$ agents and $m$ indivisible chores, an EF1+fPO allocation exists and can be computed in $\poly{n,m}$-time.
\end{result}

Next, we study the problem of computing an EF+PO allocation of divisible chores. For goods, it is known that an EF+PO allocation always exists~\cite{VARIAN1974-efpo} and is in fact polynomial-time computable via the Eisenberg-Gale convex program~\cite{nisan2007agtbook}. This is done by computing the competitive equilibrium with equal incomes (CEEI). Here, the idea is to provide each agent with the same amount of fictitious money, and then find prices and an allocation of items such that all items are completely bought and each agent buys her most preferred bundle subject to her budget constraint. This is an example of a \textit{market} where demand (of agents) equals supply (of items), and is known as the Fisher market. For goods, there are polynomial-time algorithms for computing the competitive equilibrium (CE)~\cite{devanur2008mkteqb,orlin2010fisher,Vegh16}. For chores, the problem is harder: Bogomolnaia et al.~ \cite{bogomolnaia2017manna} showed that the CE rule can be non-convex, multi-valued and disconnected. Algorithms with exponential run-times are known for computing CE for chores~\cite{branzei2019choresceei,GargM20,chaudhury2020manna,GargHMS21}, but designing a polynomial-time algorithm is an open problem. Working towards this goal, our second result shows:

\begin{result}
For bivalued instances with $n$ agents and $m$ divisible chores, an EF+fPO allocation can be computed in $\poly{n,m}$-time.
\end{result}

\subsection{Further related work}\label{sec:relatedwork}

Barman et al.~\cite{Barman18FFEA} showed that for $n$ agents and $m$ goods, an EF1+PO allocation can be computed in time $\poly{n,m,V}$, where $V$ is the maximum utility value. Their algorithm first perturbs the values to a desirable form, and then computes an EF1+fPO allocation for the perturbed instance, which for a small-enough perturbation is EF1+PO for the original instance. Their approach is via \textit{integral market equilibria}, which guarantees fPO at every step, and the concept of price-envy-freeness up to one good (pEF1) which is a strengthening of EF1. Using similar tools, Garg and Murhekar~\cite{murhekar2021aaai} showed that an EF1+fPO allocation can be computed in $\poly{n,m,V}$-time. They also showed that an EF1+fPO allocation can be computed in $\poly{n,m}$-time for $k$-ary instances (agents have at most $k$ values for the goods) where $k$ is a constant. It may seem a natural idea to try and use these approaches for chores, however they do not extend easily. While our algorithm also uses integral market equilibria to obtain the fPO property and pEF1 for chores to argue about EF1, our algorithm and its analysis is much more involved and significantly different from previous works.

Bivalued preferences are a well-studied class in literature. The following results are for the goods setting. Aziz et al.~\cite{aziz2019PO} showed PO is efficiently verifiable for bivalued instances and coNP-hard for 3-valued instances; Aziz~\cite{aziz2020hyllandzeckhauser}, and Vazirani and  Yannakakis~\cite{vazirani2020} studied the Hylland-Zeckhauser scheme for probabilistic assignment of goods in bivalued instances; and Bogomolnaia and Moulin~\cite{bogomolnaia04dichotomous} studied matching problems with bivalued (dichotomous) preferences. More generally, instances with few values have also been studied: Barman et al.~\cite{barman2018binarynsw} showed that EF1+PO allocations can be computed for binary valuations; Babaioff et al.~\cite{babaioff21dichotomous} studied truthful mechanisms for dichotomous valuations; Golovin~\cite{Golovin2005MaxminFA} presented approximation algorithms and hardness results for computing max-min fair allocations in 3-valued instances;Bliem et al.~\cite{bliem2016param} studied fixed-parameter tractability for computing EF+PO allocations with parameter $n+z$, where $z$ is the number of values; and Garg et al.~\cite{garg09papers} studied leximin assignments of papers ranked by reviewers on a small scale, in particular they present an efficient algorithm for 2 ranks, i.e., ``high or low interest'' and show NP-hardness for 3 ranks. Such instances have also been studied in resource allocation contexts, including makespan minimization with 2 or 3 job sizes~\cite{woeginger,chakrabarty-makespan}.

The fairness notion of equitability requires that each agent get the same amount of utility or disutility.  Similar to EF1 and EFX, equitability up to one (resp. any) item (EQ1 (resp. EQX)) are relaxations of equitability. Using approaches inspired by \cite{Barman18FFEA}, pseudo-polynomial time algorithms for computing EQ1+PO allocations were developed for both goods~\cite{freeman2019eqxpo} and chores~\cite{freeman2020chores}. For bivalued goods, an EQX+PO allocation is polynomial time computable \cite{garg2021sagt}.

\section{Preliminaries}\label{sec:prelim}

\paragraph{Problem instance.}
A \textit{fair division instance} (of chores) is a tuple $(N,M,C)$, where $N = [n]$ is a set of $n\in\mathbb N$ agents, $M = [m]$ is a set of $m\in\mathbb N$ indivisible chores, and $C = \{c_1,\dots,c_n\}$ is a set of cost or disutility functions, one for each agent $i\in N$. Each cost function $c_i : M \rightarrow \mathbb{R}_{\ge 0}$ is specified by $m$ numbers $c_{ij}\in\mathbb R_{\ge0}$, one for each chore $j\in M$, which denotes the cost agent $i$ has for performing (receiving) chore $j$. We assume that the cost functions are additive, that is, for every agent $i \in N$, and for $S \subseteq M$, $c_i(S) = \sum_{j\in S} c_{ij}$. For notational ease, we write $c(S\setminus j)$ instead of $c(S\setminus \{j\})$.

We call a fair division instance $(N, M, C)$ a \textit{bivalued instance} if there exist $a,b\in \mathbb R_{\ge 0}$, with $a\ge b$, such that for all $i\in N$ and $j\in M$, $c_{ij} \in \{a,b\}$. That is, the cost of any chore to any agent is one of at most two given numbers. By scaling the costs, we can assume w.l.o.g. for bivalued instances that all costs $c_{ij} \in \{1,k\}$, where $k = a/b \ge 1$. Such a scaling is w.l.o.g., since our fairness and efficiency properties are scale-invariant. Given such an instance, we partition the set of chores into sets of low-cost chores $M_{low}$ and high-cost chores $M_{high}$:
\begin{itemize}
    \item $M_{low} = \{j\in M: \exists  i\in N \, \text{ s.t. } c_{ij} = 1 \}$, and
    \item $M_{high} = \{j\in M:\forall i\in N, \, c_{ij} = k \}$.
\end{itemize}
Further, we assume that both $a,b > 0$, since if $b=0$ then re-scaling the values transforms the instance into the simpler binary case, for which efficient algorithms are known (Footnote~\ref{footnote:binary}). We can additionally assume for bivalued instances that for every agent $i$, there is at least one chore $j$ s.t. $c_{ij} = 1$. This is w.l.o.g., since if $c_{ij}=k$ for all $j\in M$, then we can re-scale costs to set $c_{ij} = 1$ for all $j\in M$.

\paragraph{Allocation.} An \textit{allocation} $\mathbf{x}$ of chores to agents is an $n$-partition $(\mathbf{x}_1, \dots, \mathbf{x}_n)$ of the chores, where agent $i$ is allotted $\mathbf{x}_i \subseteq M$ and gets a total cost of $c_i(\mathbf{x}_i)$. A \textit{fractional allocation} $\mathbf{x} \in [0,1]^{n\times m}$ is a fractional assignment such that for each chore $j\in M$, $\sum_{i\in N} x_{ij} = 1$. Here, $x_{ij}\in[0,1]$ denotes the fraction of chore $j$ allotted to agent $i$.

\paragraph{Fairness notions.} An allocation $\mathbf{x}$ is said to be \textit{envy-free up to one chore} (EF1) if for all $i,h \in N$, there exists a chore $j\in \mathbf{x}_i$ such that $c_i(\mathbf{x}_i\setminus j) \le c_i(\mathbf{x}_h)$.

We say that an agent $i$ \textit{EF1-envies} an agent $h$ if for all $j\in \mathbf{x}_i$, $c_i(\mathbf{x}_i \setminus j) > c_i(\mathbf{x}_h)$, i.e., the EF1 condition between $i$ and $h$ is violated.

A (fractional) allocation $\mathbf{x}$ is said to be \textit{envy-free} if for all $i,h\in N$, $c_i(\mathbf{x}_i)\le c_i(\mathbf{x}_h)$. We say that an agent $i$ \textit{envies} an agent $h$ if $c_i(\mathbf{x}_i) > c_i(\mathbf{x}_h)$, i.e., the EF condition between $i$ and $h$ is violated.

\paragraph{Pareto-optimality.} An allocation $\mathbf{y}$ dominates an allocation $\mathbf{x}$ if $c_i(\mathbf{y}_i) \le c_i(\mathbf{x}_i), \forall i$ and there exists $h$ s.t. $c_h(\mathbf{y}_h) < c_h(\mathbf{x}_h)$. An allocation is said to be \textit{Pareto optimal} (PO) if no allocation dominates it. Further, an allocation is said to be fractionally PO (fPO) if no fractional allocation dominates it. Thus, a fPO allocation is PO, but not vice-versa.

\paragraph{Fisher markets.} A Fisher market or a \textit{market instance} is a tuple $(N,M,C,e)$, where the first three terms are interpreted as before, and $e=\{e_1,\dots,e_n\}$ is the set of agents' \textit{minimum payments}, where $e_i \ge 0$, for each $i\in N$. In this model, chores can be allocated fractionally. Given a payment vector, also called a \textit{price}\footnote{We refer to payments as prices for sake of similarity with the Fisher market model in the goods case.} vector, $\mathbf{p}=(p_1, \dots, p_m)$, each chore $j$ pays $p_j$ per unit of chore. Agents perform chores in exchange for payment. Given chore payments, each agent $i$ aims to obtain the set of chores that minimizes her total cost subject to her payment constraint, i.e., receiving a total payment of at least $e_i$.

Given a (fractional) allocation $\mathbf{x}$ with a price vector $\mathbf{p}$, the \textit{spending}\footnote{This is actually the \textit{earning} of agent $i$, but we refer to earning as spending for sake of similarity with the Fisher market model in the goods case.} of an agent $i$ under $(\mathbf{x},\mathbf{p})$ is given by $\mathbf{p}(\mathbf{x}_i) = \sum_{j\in M} p_jx_{ij}$. We define the \textit{bang-per-buck} ratio $\alpha_{ij}$ of chore $j$ for an agent $i$ as $\alpha_{ij} = c_{ij}/p_j$, and the \textit{minimum bang-per-buck} (mBB) ratio as $\alpha_i = \min_{j} \alpha_{ij}$. We define $\textrm{mBB}_i = \{j\in M : c_{ij}/p_j = \alpha_i \}$, called the \textit{mBB-set}, to be the set of chores that give mBB to agent $i$ at prices $\mathbf{p}$. We say $(\mathbf{x},\mathbf{p})$ is \textit{`on mBB'} if for all agents $i$ and chores $j$, $x_{ij} > 0  \Rightarrow j\in \textrm{mBB}_i$. For integral $\mathbf{x}$, this means that $\mathbf{x}_i\subseteq \textrm{mBB}_i$ for all $i\in N$.

A \textit{market equilibrium} or \textit{market outcome} is a (fractional) allocation $\mathbf{x}$ of the chores to the agents and set of prices $\mathbf{p}$ of the chores satisfying the following properties:

\begin{itemize}
\item the market clears, i.e., all chores are fully allocated. Thus, for all $j$, $\sum_{i\in N} x_{ij} = 1$,
\item each agent receives their minimum payment, for all $i\in N$, $\mathbf{p}(\mathbf{x}_i) = \sum_{j\in M} x_{ij} p_j = e_i$, and,
\item agents only receive chores that give them minimum bang-per-buck, i.e., $(\mathbf{x},\mathbf{p})$ is on mBB.
\end{itemize}

Given a market outcome $(\mathbf{x},\mathbf{p})$ with $\mathbf{x}$ integral, we say it is \textit{price envy-free up to one chore} (pEF1) if for all $i,h\in N$ there is a chore $j\in \mathbf{x}_i$ such that $\mathbf{p}(\mathbf{x}_i\setminus j) \le \mathbf{p}(\mathbf{x}_h)$. We say that an agent $i$ \textit{pEF1-envies} an agent $h$, if for all $j\in \mathbf{x}_i$, $\mathbf{p}(\mathbf{x}_i\setminus j) > \mathbf{p}(\mathbf{x}_h)$, i.e., the pEF1 condition between $i$ and $h$ is violated. For integral market outcomes on mBB, the pEF1 condition implies the EF1 condition.

\begin{lemma}\label{lem:pEF1impliesEF1}
Let $(\mathbf{x},\mathbf{p})$ be an integral market outcome on mBB. If $(\mathbf{x},\mathbf{p})$ is pEF1 then $\mathbf{x}$ is EF1 and fPO.
\end{lemma}
\begin{proof}
We first show that $(\mathbf{x},\mathbf{p})$ forms a market equilibrium for the Fisher market instance $(N,M,C,e)$, where for every $i\in N$, $e_i = \mathbf{p}(\mathbf{x}_i)$. It is easy to see that the market clears and each agent receives their minimum payment. Further $\mathbf{x}$ is on mBB as per our assumption. Now the fact that $\mathbf{x}$ is fPO follows from the First Welfare Theorem \cite{mas1995microeconomic}, which shows that for any market equilibrium $(\mathbf{x},\mathbf{p})$, the allocation $\mathbf{x}$ is fPO.

Since $(\mathbf{x},\mathbf{p})$ is pEF1, for all pairs of agents $i,h \in N$, there is some chore $j\in \mathbf{x}_i$ s.t. $\mathbf{p}(\mathbf{x}_i\setminus j)\le \mathbf{p}(\mathbf{x}_h)$. Since $(\mathbf{x},\mathbf{p})$ is on mBB, $\mathbf{x}_i \subseteq \textrm{mBB}_i$. Let $\alpha_i$ be the mBB-ratio of $i$ at the prices $\mathbf{p}$. By the definition of mBB, $c_i(\mathbf{x}_i\setminus j) = \alpha_i \mathbf{p}(\mathbf{x}_i\setminus j)$, and $c_i(\mathbf{x}_h) \ge \alpha_i \mathbf{p}(\mathbf{x}_h)$. Combining these implies $\mathbf{x}$ is EF1.
\end{proof}

Our Algorithm~\ref{alg:ef1po} begins with and maintains an integral market outcome $(\mathbf{x},\mathbf{p})$ on mBB\footnote{Note that although our algorithm only maintains the allocation $\mathbf{x}$ and prices $\mathbf{p}$, the associated Fisher market instance is always implicitly present by setting $e_i = \mathbf{p}(\mathbf{x}_i)$ as in the proof of Lemma~\ref{lem:pEF1impliesEF1}}, and modifies $\mathbf{x}$ and $\mathbf{p}$ appropriately to eventually arrive at an outcome $(\mathbf{x},\mathbf{p})$ on mBB where the pEF1 condition is satisfied. Lemma~\ref{lem:pEF1impliesEF1} then ensures that $\mathbf{x}$ is EF1+fPO.

We now define least spenders as agents with minimum spending, and big spenders as agents with maximum spending after the removal of their highest-priced chore.
\begin{definition}[Least and big spenders]\label{def:lsbs}
An agent $\ell \in \s{argmin}_{i\in N} \mathbf{p}(\mathbf{x}_i)$ is referred to as a \textit{least spender} (LS). An agent $b \in \s{argmax}_{i\in N} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i \setminus j)$ is referred to as a \textit{big spender} (BS).
\end{definition}

We break ties arbitrarily to decide a unique LS and BS. Together with Lemma~\ref{lem:pEF1impliesEF1}, the following lemma shows that in order to obtain an EF1 allocation, it is sufficient to focus on the pEF1-envy the big spender has towards the least spender.

\begin{lemma}\label{lem:BSenviesLS}
Let $(\mathbf{x},\mathbf{p})$ be an integral market outcome on mBB. If $\mathbf{x}$ is not EF1, then the big spender $b$ pEF1-envies the least spender $\ell$.
\end{lemma}
\begin{proof}
If $\mathbf{x}$ is not EF1, then Lemma~\ref{lem:pEF1impliesEF1} implies that $\mathbf{x}$ is not pEF1. Hence there is a pair of agents $i,h$ s.t. for every chore $j\in \mathbf{x}_i$, $\mathbf{p}(\mathbf{x}_i \setminus j) > \mathbf{p}(\mathbf{x}_h)$. By the definition of big spender, we know $\mathbf{p}(\mathbf{x}_b \setminus j') \ge \mathbf{p}(\mathbf{x}_i \setminus j)$, for every $j'\in \mathbf{x}_b$. By the definition of least spender, $\mathbf{p}(\mathbf{x}_i) \ge \mathbf{p}(\mathbf{x}_\ell)$. Putting these together we get $\mathbf{p}(\mathbf{x}_b \setminus j') > \mathbf{p}(\mathbf{x}_\ell)$ for every $j'\in \mathbf{x}_b$, implying that $b$ pEF1-envies $\ell$.
\end{proof}

Given a market outcome $(\mathbf{x},\mathbf{p})$ on mBB, we define the mBB graph to be a bipartite graph $G = (N,M,E)$ where for an agent $i$ and chore $j$, $(i,j)\in E$ iff $j\in \textrm{mBB}_i$. Further, an edge $(i, j)$ is called an \textit{allocation edge} if $j \in \mathbf{x}_i$, otherwise it is called an \textit{mBB} edge.

For agents $i_0,\dots,i_{\ell}$ and chores $j_1,\dots,j_{\ell}$, a path $P = (i_0, j_1, i_1, j_2, \dots, j_{\ell}, i_{\ell})$ in the mBB graph, where for all $1\le \ell' \le \ell$, $j_{\ell'} \in \mathbf{x}_{i_{\ell'-1}}\cap \textrm{mBB}_{i_{\ell'}}$, is called a \textit{special} path. We define the \textit{level} $\lambda(h; i_0)$ of an agent $h$ w.r.t. $i_0$ to be half the length of the shortest special path from $i_0$ to $h$, and to be $n$ if no such path exists. A path $P = (i_0, j_1, i_1, j_2, \dots, j_{\ell}, i_{\ell})$ is an \textit{alternating path} if it is special, and if $\lambda(i_0; i_0) < \lambda(i_1; i_0) < \dots < \lambda(i_\ell; i_0)$, i.e. the path visits agents in increasing order of their level w.r.t. $i_0$. Further, the edges in an alternating path alternate between allocation edges and mBB edges. Typically, we consider alternating paths starting from a big spender agent.

\begin{definition}[Component $C_i$ of a big spender $i$]\label{def:component}
For a big spender $i$, define $C_i^{\ell}$ to be the set of all chores and agents which lie on alternating paths of length $\ell$ starting from $i$. Call $C_i = \bigcup_{\ell} C_i^{\ell}$ the \textit{component} of $i$, i.e., the set of all chores and agents reachable from $i$ through alternating paths.
\end{definition}

\section{EF1+fPO allocation of indivisible chores}\label{sec:indivisible}
In this section, we present our main result:
\begin{theorem}\label{thm:indivisible}
Given a bivalued fair division instance $(N,M,C)$ of indivisible chores with all $c_{ij} \in \{a,b\}$ for some $a,b\in \mathbb{R}^+$, an EF1+fPO allocation can be computed in strongly polynomial-time.
\end{theorem}

We prove Theorem~\ref{thm:indivisible} by showing that our Algorithm~\ref{alg:ef1po} computes an EF1+fPO allocation in polynomial-time. To ensure smooth presentation, we defer some proofs to Appendix~\ref{app:indivisible}.

\subsection{Obtaining Initial Groups}\label{sec:makeinitgroups}
Recall that we can scale the costs so that they are in $\{1,k\}$, for some $k>1$. The first step of Algorithm~\ref{alg:ef1po} is to obtain a partition of the set $N$ of agents into \textit{groups} $N_1,\dots,N_R$ with desirable properties. For this, we use Algorithm~\ref{alg:MakeInitGroups} (called $\s{MakeInitGroups}$).

\begin{algorithm}[ht]
\caption{$\s{MakeInitGroups}$}\label{alg:MakeInitGroups}
\textbf{Input:} Fair division instance $(N,M,C)$ with $c_{ij}\in \{1,k\}$\\
\textbf{Output:} Integral alloc. $\mathbf{x}$, prices $\mathbf{p}$, agent groups $\{N_r\}_{r\in [R]}$
\begin{algorithmic}[1]
\State $(\mathbf{x},\mathbf{p}) \gets$ initial cost minimizing integral market allocation, where $p_j = c_{ij}$ for $j \in \mathbf{x}_i$.
\State $R\gets 1$, $N' \gets N$
\While{$N' \neq \emptyset$}
\State $b \gets \s{argmax}_{i \in N'} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$ \Comment{Big Spender}
\State $C_b \gets$ Component of $b$ \Comment{See Definition~\ref{def:component}}
\NoDo
\While{$\exists$ agent $i \in C_b$ s.t. $\forall j \in \mathbf{x}_b$, $\mathbf{p}(\mathbf{x}_b \setminus j) > \mathbf{p}(\mathbf{x}_i)$}
\ReDo
\State Let $(b, j_1, h_1, j_2, \dots, h_{\ell - 1}, j_\ell, i)$ be the shortest alternating path from $b$ to $i$
\State $\mathbf{x}_{h_{\ell - 1}} \gets \mathbf{x}_{h_{\ell - 1}} \setminus \{j_\ell\}$ \Comment{Chore transfer}
\State $\mathbf{x}_i \gets \mathbf{x}_i \cup \{j_\ell\}$
\State $b \gets \s{argmax}_{i\in N'} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$
\EndWhile
\State $H_R \gets C_b \cap (N' \cup \mathbf{x}_{N'})$ \Comment{Partial component}
\State $N_R \gets H_R \cap N$ \Comment{Agent group}
\State $N' \gets N' \setminus N_R$, $R\gets R+1$
\EndWhile
\State \Return $(\mathbf{x},\mathbf{p}, \{N_r\}_{r\in [R]})$
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:MakeInitGroups} starts with a cost-minimizing market outcome $(\mathbf{x},\mathbf{p})$ where each chore $j$ is assigned to an agent who has minimum cost for $j$. This ensures the allocation is fPO. The chore prices are set as follows. Each low-cost chore $j$ is assigned to an agent $i$ s.t. $c_{ij} = 1$. If an agent values all chores at $k$, then we can re-scale all values to $1$. Each low-cost chore is priced at 1, and each high-cost chore is priced at $k$. This pricing ensures that the mBB ratio of every agent is 1. The algorithm then eliminates pEF1-envy from the component of the big spender $b$ by identifying an agent $i$ in $C_b$ that is pEF1-envied by $b$, and transferring a single additional chore $j_\ell$ to $i$ from an agent $h_{\ell-1}$ who lies along a shortest alternating path from $b$ to $i$ (Lines 7 \& 8). Note that the identity of the big spender may change after transferring $j_\ell$ if $j_\ell$ belonged to $b$, so we must check who the big spender is after each transfer (Line 10). Once the component of the current big spender $b$ is pEF1, the same process is applied to the next big spender outside the previously made components. Repeated application of this process creates disjoint partial components $H_1, \ldots, H_R$ of agent sets $N_1,\dots,N_R$, where $R\le n$, all of which are pEF1. We refer to $N_1,\dots,N_R$ as agent \textit{groups}, and $H_1,\dots,H_R$ as initial (partial) components. Note also that the spending (up to the removal of the biggest chore) of the big spender $h_r$ of $H_r$ is weakly decreasing with $r$. We now record several properties of the output of Algorithm~\ref{alg:MakeInitGroups} .

\begin{restatable}{lemma}{initcompprop}\label{lem:initcompprop}
Algorithm~\ref{alg:MakeInitGroups} returns in $\poly{n,m}$-time a market outcome $(\mathbf{x},\mathbf{p})$ with agents partitioned into groups $N_1,\dots, N_R$, with the following properties:\normalfont
\begin{enumerate}
\item[(i)] For all low-cost chores $j\in M$, $p_j = 1$, and for all high-cost chores $j\in M$, $p_j = k$.
\item[(ii)] The mBB ratio $\alpha_i$ of every agent $i$ is $1$.
\item[(iii)] Let $H_r$ be the collection of agents $N_r$ and chores allocated to them in $(\mathbf{x},\mathbf{p})$. Then each $H_r$ is a \textit{partial component} of some agent. That is, for each $r\in [R]$, there is an agent $h_r \in H_r$ s.t. $H_r$ comprises of all agents and chores not in $\bigcup_{r'<r} H_{r'}$ reachable through alternating paths from $h_r$. Further, $h_r$ is the big spender among agents not in $\bigcup_{r'<r} H_{r'}$:
\[h_r \in \s{argmax}_{i\notin (\bigcup_{r'<r} H_{r'})} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)\]
\item[(iv)] The spending (up to removal of the largest chore) $f(r)$ of the big spender in $H_r$ weakly decreases with $r$. Here $f(r) = \max_{i\in H_r} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$.
\item[(v)] Each \textit{group is pEF1}, i.e., an agent does not pEF1-envy other agents in the same group.
\item[(vi)] For every agent $i\in H_r$ and chore $j\in H_{r'}$ with $r'<r$, $c_{ij} = k$.
\item[(vii)] All high-cost chores belong to $H_R$.
\end{enumerate}
\end{restatable}
\begin{proof}
Properties (i) and (ii) follow from the construction of the initial allocation in Line 1.

Property (iii) follows from the construction of the set $H_r$ in Line 11. The agent $h_r$ is the last agent $b$ chosen in Line 10. Property (iv) then follows from the last result of (iii).

To see why (v) holds, we examine the loop in Lines 6-10. This loop terminates only once the big spender $b$ in the component does not pEF1-envy any other agent in the component. Since every agent spends (up to the removal of one chore) less than the big spender, it must be that every agent does not pEF1-envy any other agent in the component. Thus, the component is pEF1.

Next, suppose for some agent $i\in H_r$ and some chore $j\in H_{r'}$ for $r'<r$, $c_{ij} = 1$. Then $j$ is a low-cost chore and must be priced at 1. Hence, $\alpha_{ij} = c_{ij}/p_j = 1 = \alpha_i$, implying that $j\in \textrm{mBB}_i$. However this means that $i$ would have been added to $H_{r'}$, since there is an alternating path from $h_{r'}$ to $i$ via $j\in H_{r'}$. This is a contradiction, thus showing (vi).

Next, we show (vii). Suppose a high-cost chore $j$ belongs to $H_r$ for $r<R$. We know $j$ is priced at $k$. Then for an agent $i\in H_R$, $\alpha_{ij} = c_{ij}/p_j = 1 = \alpha_i$, implying that $j\in \textrm{mBB}_i$. However this means $i$ belongs to $H_r$ since there is an alternating path from $h_r$ to $i$ via $j$, which is a contradiction.

Finally, we argue that in making a group starting with the a new big spender in $N'$ outside of previously established pEF1 groups, we do not disturb the previously established groups. Let $N_r$ be the current group being made, and let $N_{r'}$, where $r' < r$, be a previously established group. Let $b$ and $b'$ be the big spenders in $N_r$ and $N_{r'}$, respectively. We show that no agent in $N_{r'}$ gains or loses a chore. Note that there are no high-cost chores in $N_{r'}$, as high-cost chores are mBB for all agents so a group containing a high-cost chore must be the last group $N_R$. Since all chores are priced $1$ and $N_{r'}$ is pEF1, every agent in $N_{r'}$ has total spending either $\mathbf{p}(\mathbf{x}_{b'})$ or $\mathbf{p}(\mathbf{x}_{b'}) - 1$. We also have that $\mathbf{p}(\mathbf{x}_b) \leq \mathbf{p}(\mathbf{x}_{b'})$ by construction. Thus, it cannot be that $b$ pEF1-envies any agent in $N_{r'}$, so agents in $N_{r'}$ will not receive any chores. Agents in $N_{r'}$ also will not lose any chores, since they can only transfer chores to another agent in $N_{r'}$. However, we have already shown that agents in $N_{r'}$ cannot receive chores since they will not be pEF1-envied by $b$, so these transfers are impossible. Thus, all previous groups remain undisturbed while establishing a later group.
\end{proof}

Finally, we argue that:

\begin{restatable}{lemma}{inittermination}\label{lem:inittermination}
Algorithm~\ref{alg:MakeInitGroups} terminates in time $\poly{n,m}$.
\end{restatable}

\begin{algorithm}[ht]
\caption{Computing an EF1+fPO allocation}\label{alg:ef1po}
\textbf{Input:} Fair division instance $(N,M,C)$ with $c_{ij}\in \{1,k\}$\\
\textbf{Output:} An integral allocation $\mathbf{x}$
\begin{algorithmic}[1]
\State $(\mathbf{x},\mathbf{p}, \{N_r\}_{r\in [R]}) \gets \s{MakeInitGroups(N,M,V)}$
\State $U \gets [R]$ \Comment{Unraised groups}
\State $\mathbf{x}^0 \gets \mathbf{x}$ \Comment{Copy of initial allocation, used in Line 22}
\State $b \gets \s{argmax}_{i\in N} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$ \Comment{Big Spender}
\State $\ell\gets \s{argmin}_{i\in N} \mathbf{p}(\mathbf{x}_i)$ \Comment{Least Spender}
\While{$(\mathbf{x},\mathbf{p})$ is not pEF1 \textbf{and} $\ell \in U$}
\State $b \gets \s{argmax}_{i\in N} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$
\State $\ell\gets \s{argmin}_{i\in N} \mathbf{p}(\mathbf{x}_i)$
\State Let $(r,s)$ s.t. $b\in N_r$, $\ell \in N_s$ \Comment{$r < s$}
\If{$r \in U$}
\State Raise prices of chores owned by agents in $N_r$ by a factor of $k$
\State $U \gets U \setminus \{r\}$
\Else
\State Transfer a chore from $b$ to $\ell$ along an mBB edge
\EndIf
\EndWhile
\While{$(\mathbf{x},\mathbf{p})$ is not pEF1}
\State $b \gets \s{argmax}_{i\in N} \min_{j\in \mathbf{x}_i} \mathbf{p}(\mathbf{x}_i\setminus j)$
\State $\ell\gets \s{argmin}_{i\in N} \mathbf{p}(\mathbf{x}_i)$
\State Let $(r,s)$ s.t. $b\in N_r$, $\ell \in N_s$
\If{$s > r$}
\State Transfer a chore from $b$ to $\ell$ along an mBB edge
\ElsIf{$s < r$}
\State $\exists \, i \in N_{r'}$ s.t. $r' \in U$ and $\exists \, j \in \mathbf{x}_i$ s.t. $j \in \mathbf{x}^0_{\ell}$
\State Transfer $j$ from $i$ to $\ell$
\State Transfer a chore from $b$ to $i$
\EndIf
\EndWhile
\State \Return $(\mathbf{x},\mathbf{p})$
\end{algorithmic}
\end{algorithm}

\subsection{Overview of Algorithm~\ref{alg:ef1po}}\label{sec:overview}
Our main algorithm (Algorithm~\ref{alg:ef1po}) begins by calling Algorithm~\ref{alg:MakeInitGroups}, which returns a market outcome $(\mathbf{x},\mathbf{p})$ and a set of agent groups $\{N_r\}_{r\in[R]}$ (with associated partial components $\{H_r\}_{r\in [R]}$) satisfying properties in Lemma~\ref{lem:initcompprop}. In the subsequent discussion, we refer to $(\mathbf{x},\mathbf{p})$ as the \textit{initial allocation}. Also in the subsequent discussion, all mentions of an agent receiving or losing chores are relative to this initial allocation. The following is an important invariant of Algorithm~\ref{alg:ef1po} (after the initial allocation is constructed).
\begin{restatable}{lemma}{spendingofLS}\label{lem:spendingofLS}
The spending of the least spender does not decrease in the run of Algorithm~\ref{alg:ef1po}.
\end{restatable}

We say that a group $N_r$ is above (resp. below) group $N_s$ if $r < s$ (resp. $r > s$). Lemma~\ref{lem:initcompprop} shows that each group $N_r$ is initially pEF1. Hence if the initial allocation $(\mathbf{x},\mathbf{p})$ is not pEF1, then the big spender $b$ and the least spender $\ell$ must be in different components. Since $b\in H_1$, it must be the case that $\ell\in H_s$ for some $s>1$. Since we want to obtain an fPO allocation, we can only transfer along mBB edges. Hence we raise the prices of all chores in $H_1$. We show that doing so creates an mBB edge from all agents $i\notin H_1$ to all chores $j\in H_1$ (Lemma~\ref{lem:priortot} below). In particular, there is an mBB edge from $\ell$ to a chore assigned to $b$. Hence we transfer a chore \textit{directly} from $b$ to $\ell$, thus reducing the pEF1-envy of $b$. This may change the identity of the big and least spenders. If the allocation is not yet pEF1, we must continue this process.

At an arbitrary step in the run of the algorithm, let $b$ and $\ell$ be the big and least spenders. If the allocation is not pEF1, then $b$ pEF1-envies $\ell$ (Lemma~\ref{lem:BSenviesLS}). We consider cases based on the relative positions of $b$ and $\ell$. First we argue that $b$ and $\ell$ cannot lie in the same group, by showing that:

\begin{restatable}{lemma}{compsarepEFone}\label{lem:compsarepEF1}
Throughout the run of Algorithm~\ref{alg:ef1po}, each group $N_r$ remains pEF1.
\end{restatable}

Hence $b$ and $\ell$ must lie in different groups. Once again, since we want to transfer chores away from $b$ to reduce the pEF1-envy, and we want to obtain an fPO allocation, we only transfer chores along mBB edges. Doing so may require that we raise the prices of all chores belonging to certain agents in order to create new mBB edges to facilitate chore transfer. In our algorithm, \textit{all} agents in a group undergo price-rise together. We call a group $N_r$ a \textit{raised group} if its agents have undergone price-rise, else it is called an \textit{unraised group}. The set $U$ (Line 2) records the set of unraised components.

We will use the terms \textit{time-step} or \textit{iteration} interchangeably to denote either a chore transfer or a price-rise step. We say `at time-step $t$', to refer to the state of the algorithm \textit{just before} the event at $t$ happens. We denote by $(\mathbf{x}^{t},\mathbf{p}^t)$ the allocation and price vector at time-step $t$.

Let $T$ be the first time-step that the current LS enters a raised group. Note that such an event may or may not happen. Our algorithm performs instructions in Lines 6-14 before $T$, and Lines 15-24 after $T$, as we describe below.

\subsection{Algorithm prior to $T$ (Lines 6-14)}\label{sec:priortot}
We first record some properties of the algorithm prior to $T$. These observations follow directly from the algorithm.

\begin{restatable}{lemma}{algobs}\label{lem:algobs}
Prior to $T$, the following hold:
\begin{enumerate}
\item Any transfer of chores only takes place directly from the big spender $b$ to the least spender $\ell$. Thus, an agent receives a chore only if she is a least spender, and an agent loses a chore only if she is a big spender.
\item An agent ceases to be a least spender only if she receives a chore. An agent ceases to be a big spender only if she loses a chore.
\item A group undergoes price-rise at $t$ only if the group contains the big spender at $t$.
\end{enumerate}
\end{restatable}
We now show that:
\begin{restatable}{lemma}{BSincompofformerLS}\label{lem:BSincompofformerLS}
If at any point in the run of Algorithm~\ref{alg:ef1po} prior to $T$, the big spender lies in a group which contains a former least spender, then the allocation is pEF1.
\end{restatable}

This allows us to show that:
\begin{restatable}{lemma}{priortot}\label{lem:priortot}
Prior to $T$, the following hold:
\begin{enumerate}
\item[(i)] Let $r$ be the number of price-rise steps until time-step $t$, where $t<T$. Then the raised groups are exactly $N_1,\dots,N_r$. Furthermore they underwent price-rise exactly once and in that order.
\item[(ii)] For any chore $j$ allocated to an agent in a raised group $N_r$ and any agent $i$ in an unraised group $N_{r'}$, where $r'>r$, $j \in \textrm{mBB}_i$.
\item[(iii)] For each $r'\in[r]$, at the time of price-rise of $N_{r'}$, no agent in $N_{r'}$ has either received or lost a chore since the initial allocation.
\end{enumerate}
\end{restatable}

\begin{proof}
We prove (i), (ii) and (iii) by induction. For $r=0$, they are trivially true since there are no raised groups. Assume that at some time-step $t$, (i) groups $N_1,\dots,N_{r}$ have undergone price-rise, once and in that order, for some $r\ge 1$, and (ii) and (iii) hold.

Note that our algorithm only raises the prices of chores owned by a group if the group contains the big spender at the time (Lemma~\ref{lem:algobs}). If the current BS is in a raised group, then the induction hypothesis ensures that there is an mBB edge from the LS (who is in an unraised group prior to $T$) to chores owned by the BS. The algorithm therefore performs a direct chore transfers and no price-rise is necessary.

If eventually the BS enters an unraised group, then a price-rise step is potentially necessary. Suppose $b \in N_{r+1}$ is an agent who has received a chore prior to time-step $t$. If this happens then $b$ must have been a former LS by Lemma~\ref{lem:algobs}. Then Lemma~\ref{lem:BSincompofformerLS} shows that the allocation must already be pEF1.

Hence we assume $b$ has not received a new chore since the initial allocation in Line 1. Furthermore since $b$ pEF1-envies the LS $\ell$, it must be the case that $\ell\in N_s$ where $s\ge r+2$. Lemma~\ref{lem:initcompprop} shows that there is no mBB edge from $\ell$ to chores owned by $b$, hence a direct chore transfer is not possible and it is necessary for $N_{r+1}$ to undergo price-rise. This shows (i).

Now if an agent $i\in N_{r+1}$ had previously received a chore, then $i$ is a former LS at $t$. Then $b\in N_{r+1}$ is in a group containing a former LS $i$, hence Lemma~\ref{lem:BSincompofformerLS} shows that the allocation is pEF1. Similarly Lemma~\ref{lem:algobs} shows that no agent in $N_{r+1}$ can have lost a chore. This is because only BS agents lose chores. Prior to $t$, no agent of $N_{r+1}$ can be the BS. Hence no agent in $N_{r+1}$ has received or lost a chore since the initial allocation at the time $N_{r+1}$ undergoes price-rise, thus showing (iii).

The algorithm next raises the prices of all chores owned by $N_{r+1}$ by a factor of $k$, and $N_{r+1}$ becomes a raised group. Consider an agent $i\in N_{r'}$ for $r'\ge r+2$ and a chore allocated to an agent in $N_{r+1}$. Since the mBB ratio only changes upon a price-rise, the mBB ratio of $i$ is 1 since $N_{r'}$ does not undergo a price-rise before $N_{r+1}$.

Observe that since $i\notin N_{r+1}$, there is no alternating path from agents in $N_{r+1}$ to $i$. Hence $j\notin \textrm{mBB}_i$ before the price-rise. Thus $c_{ij}/p^t_j > 1$, showing $c_{ij} = k$ and $p^t_j = 1$. After the price-rise, we have that $p^{t+1}_j = k$, and $\alpha_i = c_{ij}/p^{t+1}_j$. Thus, $j\in \textrm{mBB}_i$ after the price-rise, which shows (ii).
\end{proof}

To summarize the behavior of the Algorithm prior to $T$, we have argued in the above proof that if the allocation is not pEF1, we can always (i) transfer a chore directly from $b$ to $\ell$, or (ii) perform a price-rise on the group of $b$ and then transfer a chore from $b$ to $\ell$. Further, we argue that the algorithm makes progress towards getting a pEF1 allocation.
\begin{lemma}\label{lem:priortoTtermination}
Algorithm~\ref{alg:ef1po} performs at most $\poly{n,m}$ steps prior to $T$.
\end{lemma}
\begin{proof}
Prior to $T$, the LS always remains in an unraised group. Chores are transferred away from agents who become big spenders in raised groups. Once an agent undergoes price-rise, she cannot gain any additional chores, since doing so would mean she is the LS in a raised group, which cannot happen prior to $T$. When the BS is in an unraised group, the group undergoes a price-rise. Thus, effectively, either agents in raised components only lose chores, or the BS `climbs-down' in the group list $N_1,\dots,N_R$, while the LS remains below the BS. Since there are $R\le n$ groups, and at most $m$ chores allocated to raised groups, after $\poly{n,m}$ steps either of two events happen: (i) the LS and BS both belong to the same group, or (ii) the LS enters a raised group. In the former case, the allocation is pEF1 due to Lemma~\ref{lem:compsarepEF1}, and the algorithm terminates in $\poly{n,m}$ steps. We discuss the latter case in the next section. Thus, there are at most $\poly{n,m}$ steps prior to $T$.
\end{proof}

\subsection{Algorithm after $T$ (Lines 15-24)}\label{sec:aftert}
We now describe the algorithm after $T$, i.e., once the LS enters a raised group (Lines 15-24). We show that subsequent to $T$, as long as the allocation is not pEF1, we can either (i) transfer a chore directly from $b$ to $\ell$, or (ii) transfer chores via an alternating path containing 3 agents. We do not perform any price-rises subsequent to $T$.

From Lemma~\ref{lem:priortot}, we know that at $T$, groups $N_1,\dots,N_r$ have undergone price-rise, for some $r\in[R]$. Let $N_{<r} = \bigcup_{r'< r} N_{r'}$, and $N_{>r} = \bigcup_{r'>r} N_{r'}$. The allocation at $T$ need not be pEF1, but we argue that it is already very close to being pEF1. Specifically, we show:

\begin{restatable}{lemma}{aboveHr}\label{lem:aboveHr}
At $T$, agents in $N_{<r}$ are pEF1 towards others.
\end{restatable}

\begin{restatable}{lemma}{belowHr}\label{lem:belowHr}
At $T$, agents in $N_{>r}$ are pEF1 towards others.
\end{restatable}

The above two lemmas imply that if the BS is not in $N_r$, then the allocation is pEF1. Let us assume that the allocation is not pEF1 at $T$. Let $b$, the BS at $T$ be in $N_r$, and $\ell$, the LS at $T$ be in $N_{<r}$, since the LS is in a raised group at $T$.

Suppose $\ell$ has never lost a chore. Let $\ell \in N_{r'}$, where $r'<r$, and $t'$ be the time when $N_{r'}$ underwent price-rise. Let $b'$ the BS at $t'$. Since the spending of the BS (up to removal of one chore) just after price-rises does not increase,
we have:
\[\mathbf{p}^T(\mathbf{x}^T_b\setminus j)\le \mathbf{p}^{t'}(\mathbf{x}^{t'}_{b'}\setminus j') \le \mathbf{p}^{t'}(\mathbf{x}^{t'}_\ell) = \mathbf{p}^T(\mathbf{x}^T_\ell), \]
for some chores $j\in \mathbf{x}^T_b, j'\in \mathbf{x}^{t'}_{b'}$. The intermediate transition follows from the property that $N_{r'}$ is pEF1. This shows that the allocation is pEF1.

On the other hand, suppose $\ell$ has lost at least one chore $j$ prior to $T$. At $T$, $j$ must be assigned to some unraised agent $i$ (Lemma~\ref{lem:priortot}). Further, there is a chore $j'\in \mathbf{x}^T_b$ s.t. $j'\in \textrm{mBB}_i$. Thus, $b \xrightarrow{\mathbf{x}} j' \xrightarrow{\text{mBB}} i \xrightarrow{\mathbf{x}} j \xrightarrow{\text{mBB}} \ell$ is an alternating path. The algorithm now transfers chores along this alternating path.

Note that as long as $\ell$ does not own a chore that she initially owned, such a path is available, and such a transfer is possible. If not, then it is as if $\ell$ has never lost a chore, and in that case the previous argument shows that the allocation must be pEF1.

Once again, doing such transfers may change the identities of the BS and LS, and we must continue the algorithm. We show that:
\begin{restatable}{lemma}{afterTinvariant}\label{lem:afterTinvariant}
After $T$, the following are invariant:
\begin{enumerate}
\item[(i)] Agents in $N_{<r}$ do not pEF1-envy any other agent.
\item[(ii)] Agents in $N_{>r}$ do not pEF1-envy any other agent.
\item[(iii)] Each group is pEF1.
\end{enumerate}
\end{restatable}

Just after $T$, the BS is in $N_r$ and the LS is in $N_{<r}$. After a chore transfer, the identity of the LS or BS can change. If the BS enters either $N_{<r}$ or $N_{>r}$, then using Lemma~\ref{lem:afterTinvariant} the allocation would be pEF1. While the BS is in $N_r$: (i) if the LS is in $N_r$, the allocation would be pEF1, (ii) if the LS is in $N_{>r}$, then we can transfer from BS to LS directly along an mBB edge (which exists due to Lemma~\ref{lem:priortot}), (iii) if the LS is in $N_{<r}$, then we can transfer from the BS to LS via an alternating path with three agents as described above.

Finally we argue termination in polynomial-time:

\begin{lemma}\label{lem:afterTtermination}
Algorithm~\ref{alg:ef1po} performs at most $\poly{n,m}$ steps after $T$ and terminates with a pEF1 allocation.
\end{lemma}
\begin{proof}
Call the difference between the spending (up to the removal of the biggest chore) of the big spender and the spending of the least spender as the \textit{spending gap}. If the allocation is not pEF1, the spending gap is positive. After $T$, there are no price-rises, hence the spending gap weakly decreases. As long as the allocation is not pEF1, the BS must be in $N_r$. Based on whether the LS is in $N_{<r}$ or $N_{>r}$ we can perform chore transfers which weakly decrease the spending gap. While the allocation is not pEF1, such a transfer is always possible. Further, each such transfer reduces the number of chores owned by agents in $N_r$, and such agents do not receive any chores again. Hence there can only be $\poly{n,m}$ steps after $T$ eventually terminating in a pEF1 allocation.
\end{proof}

\subsection{Summarizing our EF1+fPO algorithm}
We summarize Algorithm~\ref{alg:ef1po}.

\begin{enumerate}
\item Algorithm~\ref{alg:ef1po} first calls Algorithm~\ref{alg:MakeInitGroups} to partition agents into groups $N_1,\dots,N_R$ with properties as in Lemma~\ref{lem:initcompprop} to obtain an initial allocation. Lemma~\ref{lem:inittermination} shows this takes $\poly{n,m}$ steps.
\item When the current allocation $(\mathbf{x},\mathbf{p})$ is not pEF1, the BS $b$ pEF1-envies the LS $\ell$. While there is an mBB edge from $\ell$ to a chore owned by $b$, we transfer a chore directly from $b$ to $\ell$. If not, in order to transfer along mBB edges, we may have to raise the prices of chores belonging to the group of $b$, creating \textit{raised} groups.
\item Let $T$ be the first time-step when the LS enters a raised group. Prior to $T$, while the allocation is not pEF1, the algorithm either performs a direct chore transfer from the BS to the LS, or performs price-rise on the group of $b$. Lemma~\ref{lem:priortot} shows that the groups are raised exactly once and in order of $N_1,\dots,N_R$. Lemma~\ref{lem:priortoTtermination} shows the algorithm runs for $\poly{n,m}$ steps before $T$.
\item Once the LS enters a raised group at $T$, there are no more price-rise steps. The algorithm then performs chore transfers from the BS to LS via alternating paths with at most 3 agents. Lemma~\ref{lem:afterTinvariant} and Lemma~\ref{lem:afterTtermination} show that the algorithm performs at most $\poly{n,m}$ steps after $T$ and terminates with a pEF1 allocation.
\item Finally, we note that allocation is always fPO, since (i) Algorithm~\ref{alg:MakeInitGroups} returns a market outcome which is fPO, and (ii) any transfer of chores happens along mBB edges.
\end{enumerate}

\subsection{Examples}
We illustrate two examples of an execution of Algorithm~\ref{alg:ef1po} for a fair division instance, one in which the algorithm terminates before a time $T$ where the LS enters a raised component, and one in which the algorithm terminates after such a time $T$.

\subsubsection{Algorithm terminates before $\mathbf{T}$}
Consider the instance captured by the table of disutilities below.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{} & \multicolumn{13}{|c|}{Chores} \\
\cline{3-15}
 \multicolumn{2}{|c|}{} & $j_1$ & $j_2$ & $j_3$ & $j_4$ & $j_5$ & $j_6$ & $j_7$ & $j_8$ & $j_9$ & $j_{10}$ & $j_{11}$ & $j_{12}$ & $j_{13}$ \\
\hline
\multirow{6}{3em}{Agents} & $a_1$ & 1 & 1 & 1 & 1 & 1 & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ \\
\cline{2-15}
 & $a_2$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & 1 & 1 & 1 & $k$ & $k$ & $k$ & $k$ \\
\cline{2-15}
 & $a_3$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ & $k$ & $k$ \\
\cline{2-15}
 & $a_4$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ & $k$ \\
\cline{2-15}
 & $a_5$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ \\
\cline{2-15}
 & $a_6$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 \\
\hline
\end{tabular}
\end{center}
\hspace{1cm}
Algorithm~\ref{alg:ef1po} begins by calling Algorithm~\ref{alg:MakeInitGroups} which returns the following initial allocation $\mathbf{x}$.
\begin{multicols}{2}
\begin{itemize}
    \item $\mathbf{x}_{a_1} = \{j_1, j_2, j_3, j_4, j_5\}$
	\item $\mathbf{x}_{a_2} = \{j_6, j_7, j_8, j_9\}$
	\item $\mathbf{x}_{a_3} = \{j_{10}\}$
	\item $\mathbf{x}_{a_4} = \{j_{11}\}$
	\item $\mathbf{x}_{a_5} = \{j_{12}\}$
	\item $\mathbf{x}_{a_6} = \{j_{13}\}$
\end{itemize}
\end{multicols}

Suppose $k = 5$. Note that here each agent lies in its own group. Since $\mathbf{x}$ is not pEF1, Algorithm~\ref{alg:ef1po} proceeds to raises the prices of the chores of $a_1$ by a factor of $k$. Then, a chore is transferred from $a_1$ to each of $a_3$, $a_4$, $a_5$, and $a_6$. This gives us the following pEF1 (and thus EF1) allocation $\mathbf{x}'$.
\begin{multicols}{2}
\begin{itemize}
    \item $\mathbf{x}'_{a_1} = \{j_5\}$
	\item $\mathbf{x}'_{a_2} = \{j_6, j_7, j_8, j_9\}$
	\item $\mathbf{x}'_{a_3} = \{j_1, j_{10}\}$
	\item $\mathbf{x}'_{a_4} = \{j_2, j_{11}\}$
	\item $\mathbf{x}'_{a_5} = \{j_3, j_{12}\}$
	\item $\mathbf{x}'_{a_6} = \{j_4, j_{13}\}$
\end{itemize}
\end{multicols}

\subsubsection{Algorithm terminates after $\mathbf{T}$}
We now consider a slight alteration of the previous instance, with an additional agent $a_7$ and additional chore $j_{14}$. The table of disutilities is given below.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{} & \multicolumn{14}{|c|}{Chores} \\
\cline{3-16}
 \multicolumn{2}{|c|}{} & $j_1$ & $j_2$ & $j_3$ & $j_4$ & $j_5$ & $j_6$ & $j_7$ & $j_8$ & $j_9$ & $j_{10}$ & $j_{11}$ & $j_{12}$ & $j_{13}$ & $j_{14}$ \\
\hline
\multirow{7}{3em}{Agents} & $a_1$ & 1 & 1 & 1 & 1 & 1 & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ \\
\cline{2-16}
 & $a_2$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & 1 & 1 & 1 & $k$ & $k$ & $k$ & $k$ & $k$ \\
\cline{2-16}
 & $a_3$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ & $k$ & $k$ & $k$ \\
\cline{2-16}
 & $a_4$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ & $k$ & $k$ \\
\cline{2-16}
 & $a_5$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ & $k$ \\
\cline{2-16}
 & $a_6$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 & $k$ \\
\cline{2-16}
 & $a_7$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & $k$ & 1 \\
\hline
\end{tabular}
\end{center}
\hspace{1cm}

Again, Algorithm~\ref{alg:ef1po} first calls Algorithm~\ref{alg:MakeInitGroups} which returns the following initial allocation $\mathbf{y}$.

\begin{multicols}{2}
\begin{itemize}
    \item $\mathbf{y}_{a_1} = \{j_1, j_2, j_3, j_4, j_5\}$
	\item $\mathbf{y}_{a_2} = \{j_6, j_7, j_8, j_9\}$
	\item $\mathbf{y}_{a_3} = \{j_{10}\}$
	\item $\mathbf{y}_{a_4} = \{j_{11}\}$
	\item $\mathbf{y}_{a_5} = \{j_{12}\}$
	\item $\mathbf{y}_{a_6} = \{j_{13}\}$
	\item $\mathbf{y}_{a_7} = \{j_{14}\}$
	\item[~] ~
\end{itemize}
\end{multicols}

Again let $k=5$. As before, Algorithm~\ref{alg:ef1po} raises the prices of the chores of $a_1$ by a factor of $k$ and transfers a chore from $a_1$ to each of $a_3$, $a_4$, $a_5$, and $a_6$. Now, however, the allocation is not pEF1. The BS, $a_2$, still pEF1-envies the LS $a_7$. Thus, the prices of $a_2$'s chores are raised, and a chore is transferred from $a_2$ to $a_7$. We now have the following allocation $\mathbf{y}'$.

\begin{multicols}{2}
\begin{itemize}
    \item $\mathbf{y}'_{a_1} = \{j_5\}$
	\item $\mathbf{y}'_{a_2} = \{j_7, j_8, j_9\}$
	\item $\mathbf{y}'_{a_3} = \{j_1, j_{10}\}$
	\item $\mathbf{y}'_{a_4} = \{j_2, j_{11}\}$
	\item $\mathbf{y}'_{a_5} = \{j_3, j_{12}\}$
	\item $\mathbf{y}'_{a_6} = \{j_4, j_{13}\}$
	\item $\mathbf{y}'_{a_7} = \{j_6, j_{14}\}$
	\item[~] ~
\end{itemize}
\end{multicols}

We see that $\mathbf{y}'$ is not pEF1 as $a_2$ pEF1-envies $a_1$, and in fact $a_1$ is the LS. This marks the first time $T$ in which the LS has entered a raised group. Then, to achieve pEF1, $j_1$ is returned to $a_1$ from $a_3$, and $j_7$ is transferred from $a_2$ to $a_3$ as a replacement. This gives the pEF1 allocation $\mathbf{y}''$.
\begin{multicols}{2}
\begin{itemize}
    \item $\mathbf{y}''_{a_1} = \{j_1, j_5\}$
	\item $\mathbf{y}''_{a_2} = \{j_8, j_9\}$
	\item $\mathbf{y}''_{a_3} = \{j_7, j_{10}\}$
	\item $\mathbf{y}''_{a_4} = \{j_2, j_{11}\}$
	\item $\mathbf{y}''_{a_5} = \{j_3, j_{12}\}$
	\item $\mathbf{y}''_{a_6} = \{j_4, j_{13}\}$
	\item $\mathbf{y}''_{a_7} = \{j_6, j_{14}\}$
	\item[~] ~
\end{itemize}
\end{multicols}

\section{EF+PO allocation of divisible chores}\label{sec:divisible}
In this section, we prove our second result:
\begin{restatable}{theorem}{divisible}\label{thm:divisible}
Given a bivalued fair division instance $(N,M,V)$ of divisible chores with all $c_{ij} \in \{a,b\}$ for some $a,b\in \mathbb{R}^+$, an EF+fPO allocation can be computed in strongly polynomial-time.
\end{restatable}

We prove Theorem~\ref{thm:divisible} by showing that Algorithm~\ref{alg:efpo} computes an EF+fPO allocation in strongly polynomial-time. First note that we can scale the costs of the chores so that they are in $\{1, k\}$.

\subsection{Describing the Approach}\label{sec:divisible-approach}
Since we are interested in an EF+fPO allocation, we try to construct a (fractional) market outcome $(\mathbf{x},\mathbf{p})$ which is price-envy-free (pEF) as opposed to pEF1. A market outcome $(\mathbf{x},\mathbf{p})$ is said to be pEF if for all agents $i,h\in N$, $\mathbf{p}(\mathbf{x}_i)\ge \mathbf{p}(\mathbf{x}_h)$, i.e., all agents have equal spending. Similar to Lemma~\ref{lem:pEF1impliesEF1}, we can show that if $(\mathbf{x},\mathbf{p})$ is a pEF market outcome, then $\mathbf{x}$ is EF. Thus, our aim is to obtain a market outcome in which all agents have the same spending.

As in Algorithm~\ref{alg:ef1po}, we begin with an initial market outcome $(\mathbf{x},\mathbf{p})$ on mBB, with certain desirable properties. Specifically, we partition the agents into groups $N_1,\dots,N_R$ so that each group spends the same amount, each group is a partial component of some agent, and the \textit{per-agent spending} of the group $N_r$ decreases with $r$. Now, if the allocation is not pEF, it must be the case that any agent in the \textit{pool} of biggest spenders $B$ (here $B = \{b : b\in \s{argmax}_{i\in N} \mathbf{p}(\mathbf{x}_i)\}$) envies any agent in the pool of least spenders $L$ (here $L = \{ \ell : \ell\in \s{argmin}_{i\in N} \mathbf{p}(\mathbf{x}_i) \}$), i.e., $\mathbf{p}(\mathbf{x}_b) > \mathbf{p}(\mathbf{x}_\ell)$ for any $b\in B$ and $\ell \in L$. The natural idea following Algorithm~\ref{alg:ef1po} is to reduce the pEF-envy by \textit{draining} chores uniformly from $B$ to $L$ along mBB edges. Further, if the pool $B$ has chores which are not on mBB for $L$, then we raise the prices of certain chores in $B$ by a factor of $k$, which creates the required mBB edges following Lemma~\ref{lem:priortot}. Initially, $B$ equals $N_1$, and $L$ equals $N_R$. At a certain point in the run of the algorithm, $B$ equals $\bigcup_{i\le r} N_i$ and $L$ equals $\bigcup_{i\ge r'} N_{r'}$, where $r\le r'$. When eventually the pools of biggest and least spenders coincide, the algorithm terminates with a pEF allocation. This approach is similar to Algorithm~\ref{alg:ef1po} and terminates in polynomial time.

However, we observe a stronger property of this approach, which we use to design Algorithm~\ref{alg:efpo}. We claim that effectively, this approach is equivalent to raising the prices of all chores in the first $r^*$ groups, and then draining chores carefully, eventually resulting in a pEF allocation. Therefore, we can simply iterate over $r=1$ to $R-1 \le n$ as a guess for a right value of $r^*$. We now describe the parts of the algorithm and also prove the above argument.

\subsection{Obtaining Initial Groups}\label{sec:divisible-initcomps}
\begin{algorithm}[t]
\caption{$\s{MakeInitGroupsDiv}$}\label{alg:MakeInitGroupsDiv}
\textbf{Input:} Fair division instance $(N,M,C)$ with $c_{ij}\in \{1,k\}$\\
\textbf{Output:} Fractional alloc. $\mathbf{x}$, prices $\mathbf{p}$, agent groups $\{N_r\}_{r\in [R]}$
\begin{algorithmic}[1]
\State $(\mathbf{x},\mathbf{p}) \gets$ initial cost minimizing balanced flow fractional market allocation, where $p_j = c_{ij}$ for $j \in \mathbf{x}_i$.
\State $R\gets 1$, $N' \gets N$
\While{$N' \neq \emptyset$}
\State $b \gets \s{argmax}_{i \in N'} \mathbf{p}(\mathbf{x}_i)$ \Comment{Biggest Spender}
\State $C_b \gets$ Component of $b$ \Comment{See Definition~\ref{def:component}}
\State $H_R \gets C_b \cap (N' \cup \mathbf{x}_{N'})$ \Comment{Partial component}
\State $N_R \gets H_R \cap N$ \Comment{Agent group}
\State $N' \gets N' \setminus N_R$, $R\gets R+1$
\EndWhile
\State \Return $(\mathbf{x},\mathbf{p}, \{N_r\}_{r\in [R]})$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[t!]
\caption{Computing an EF+fPO allocation}\label{alg:efpo}
\textbf{Input:} Fair division instance $(N,M,C)$ with $c_{ij}\in \{1,k\}$\\
\textbf{Output:} A fractional allocation $\mathbf{x}$
\begin{algorithmic}[1]
\For {$r \in [R-1]$}
	\State $(\mathbf{x},\mathbf{p}, \{N_r\}_{r\in [R]}) \gets \s{MakeInitGroupsDiv(N,M,V)}$
	\State Raise prices of chores of agents in $\{N_i\}_{i \in [r]}$ by a factor of $k$
	\State $B \gets N_1$ \Comment{Pool of Biggest Spenders}
	\State $\beta \gets 1$ \Comment{Index of lowest group in $B$}
	\State $L \gets N_R$ \Comment{Pool of Least Spenders}
	\State $\lambda \gets R$ \Comment{Index of highest group of $L$}
	\While{$\beta \leq r$ \textbf{and} $\lambda \geq r + 1$}
		\State $d_B \gets |B| \cdot (s(B) - s(N_{\beta+1}))$ \State $d_L \gets |L| \cdot (s(N_{\lambda-1})) - s(L))$
		\For{agents $b \in B$}
			\If{$\beta = r$ \textbf{and} $\lambda = r + 1$}
				\State $q \gets \frac{|B| \cdot s(B) + |L| \cdot s(L)}{|N|}$
				\State $C \gets$ subset of $\mathbf{x}_{b}$ s.t. $\mathbf{p}(C) = s(B) - q$
			\ElsIf{$d_B \geq d_L$}
				\State $C \gets$ subset of $\mathbf{x}_{b}$ s.t. $\mathbf{p}(C) = \frac{d_L}{|B|}$
			\Else
				\State $C \gets$ subset of $\mathbf{x}_{b}$ s.t. $\mathbf{p}(C) = \frac{d_B}{|B|}$
			\EndIf
			\For{agents $\ell \in L$}
				\State $\mathbf{x}_{b} \gets \mathbf{x}_{b} \setminus \frac{1}{|L|}C$
				\State $\mathbf{x}_{\ell} \gets \mathbf{x}_{\ell} \cup \frac{1}{|L|}C$
			\EndFor
		\EndFor
		\If{$(\mathbf{x}, \mathbf{p})$ is pEF}
			\State \Return $(\mathbf{x}, \mathbf{p})$
		\ElsIf{$d_B \geq d_L$}
			\State $L \gets L \cup N_{\lambda-1}$
			\State $\lambda \gets \lambda - 1$
		\Else
			\State $B \gets B \cup N_{\beta+1}$
			\State $\beta \gets \beta + 1$

		\EndIf
	\EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:MakeInitGroupsDiv} obtains a partition of the set $N$ of agents into groups $N_1, \ldots, N_R$ similar to Algorithm~\ref{alg:MakeInitGroups}, with the strengthened condition that the partial components are price envy-free (pEF) rather than pEF1. The price vector $\mathbf{p}$ is set the same way as in Algorithm~\ref{alg:MakeInitGroups}. Then all low-cost chores are priced at $1$ and high-cost chores are priced at $k$. To allocate these chores, however, we use a balanced flow formulation~\cite{devanur2008mkteqb}. This gives us an allocation with the key property that if agent $i$ spends more than agent $j$, then there is no alternating path from $i$ to $j$. Then, each $b$ selected in Line 4 of Algorithm~\ref{alg:MakeInitGroupsDiv} is a biggest spender in its partial component, but also cannot spend more than any agent in its partial component. Thus, it must be that the partial component (i.e., group) is pEF. Algorithm~\ref{alg:MakeInitGroupsDiv} runs in polynomial time as the balanced flow allocation is achieved by at most $m$ max-flow computations (see~\cite{devanur2008mkteqb}) and the remaining structure is analogous to Algorithm~\ref{alg:MakeInitGroups}.

\subsection{Discussion on Algorithm~\ref{alg:efpo}}\label{sec:divisible-discussion}
Algorithm~\ref{alg:efpo} proceeds similarly to Algorithm~\ref{alg:ef1po} with two key differences:
\begin{enumerate}
	\item[(1)] Multiple groups are raised simultaneously rather than one at a time.
	\item[(2)] Transfer are made between a \textit{pool of biggest spenders} and a \textit{pool of least spenders}. That is, we transfer (fractions of) chores from \textit{all} biggest spenders to \textit{all} least spenders.
\end{enumerate}
We show that there always exists some $r^*$, $1 \leq r^* \leq R - 1$, such that simultaneously raising the first $r^*$ groups allows us to reach a pEF allocation by performing chore transfers along mBB edges from biggest spenders to least spenders. Recalling that the partial components associated with each group $N_i$ are pEF, let $s(N_i)$ denote the \textit{per agent spending} of $N_i$. By construction, we have that $s(N_i) \geq s(N_j)$ for $i \leq j$. Suppose we do an initial raise of the first $r$ groups. Let $\beta \in [n]$ be such that the pool of biggest spenders $B$ is the union of raised groups $\bigcup_{i=1}^\beta N_i$. Similarly, let $\lambda \in [n]$ be such that the pool of least spenders $L$ is the union of unraised groups $\bigcup_{i=\lambda}^R N_i$. Algorithm~\ref{alg:efpo} then proceeds to transfer chores out of agents in $B$ at a uniform rate $\rho_B$ and into agents in $L$ at a uniform rate $\rho_L$, such that $|B|\rho_B = |L|\rho_L$. Then, $s(B)$ will fall towards $s(N_{\beta+1})$ while $s(L)$ rises towards $s(N_{\lambda - 1})$. When we transfer enough chores so that $s(B)$ reaches $s(N_{\beta+1})$ or $s(L)$ reaches $s(N_{\lambda-1})$, whichever occurs first, we add the agents in that group to the respective pool. Note that in this process both $B$ and $L$ are only growing. Once an agent enters $B$ or $L$, she never leaves. In addition, we have that $s(B)$ is always decreasing while $s(L)$ is always increasing, i.e., the \textit{spending gap} $s(B) - s(L)$ is weakly decreasing. When the spending gap is zero, i.e. $s(B) = s(L)$, the allocation is pEF. However, to guarantee that transfers occur along mBB edges, we must have that all agents in $B$ are in raised groups, and all agents in $L$ are in unraised groups. Thus, we give the two conditions under which the algorithm \textit{cannot} obtain a pEF allocation after raising the first $r$ groups:
\begin{enumerate}
    \item[-] \textit{Condition 1.} Raised groups have \textit{too much} total spending. The spending of agents in $L$ rises to spending level of $N_{r}$ before the spending of agents in $B$ falls to the level of $N_{r}$. That is, a raised group enters $L$.
    \item[-] \textit{Condition 2.} Raised groups have \textit{too little} total spending. The spending of agents in $B$ falls to the level of $N_{r+1}$ before the spending of agents in $L$ rises to the level of $N_{r+1}$. That is, an unraised group enters $B$.
\end{enumerate}
If neither of these conditions hold, then $B$ always contains only raised groups, and $L$ always holds only unraised groups. It is clear then that we can perform transfers until the spending gap between $B$ and $L$ closes entirely and we have a pEF allocation. Specifically, this is possible when the algorithm reaches a point where $B$ contains all the raised groups and $L$ contains all the unraised groups (see Line 12). We show that is guaranteed for some $r^*$, $1 \leq r^* \leq R-1$.

Suppose we raise only the single group $N_1$. It cannot be that Condition 1 holds here, as $L$ rising to the level of $N_1$ implies that the allocation is pEF. It must be that we have Condition 2, or we would be done as the allocation will be pEF and the algorithm would halt.

Now suppose inductively that we have raised the first $r$ groups and found that the allocation is not pEF and Condition 1 is impossible for the first $r$ groups, i.e., Condition 2 holds. Then, it must also be that Condition 1 is impossible if we raise the first $r+1$ groups if the allocation is still not pEF. Let $\sigma = s(N_{r+1})$ be the per-agent spending of $N_{r+1}$ just before $N_{r+1}$ undergoes price-rise. Since raising $r$ groups results in Condition 2, we know that $s(B)$ falls to $\sigma$ \textit{before} $s(L)$ rises to $\sigma$. Surely then, in raising $r+1$ groups, $s(B)$ falls to $\sigma \cdot k$ before $s(L)$ rises to $\sigma \cdot k$, as $\sigma \cdot k > \sigma$. This shows Condition 1 cannot hold after raising the first $r+1$ groups, given that the allocation is not yet pEF.

Finally, suppose that we have raised the first $R-1$ groups, i.e., all but the last group, and the allocation is not pEF. Then, Condition 2 cannot hold, as $s(B)$ falling to the level of $s(N_R)$ implies that the allocation is pEF. Thus, if the allocation is not pEF, Condition 1 must hold, but this is impossible by our inductive argument. Hence it must be that for some $r^*$, $1 \leq r^* \leq R-1$, a pEF allocation was obtained.

Following this logic, Algorithm~\ref{alg:efpo} checks each possible $r$ until $r^*$ is found and a pEF allocation is obtained. Further, since all chore transfers are along mBB, the allocation remains fPO throughout. Thus the algorithm computes a pEF+fPO allocation.

For each $r \in [R]$, the algorithm performs at most $O(n^2)$ transfers before adding an agent group to either $B$ or $L$. A group cannot be added to both $B$ and $L$, nor can it leave $B$ or $L$ after being added. Thus, since $R \leq n$, the total number of transfers performed to check if some $r$ is correct is $O(n^3)$, so checking all possible $r$ takes $O(n^4)$ transfers. Hence, Algorithm~\ref{alg:efpo} terminates in strongly polynomial-time, proving Theorem~\ref{thm:divisible}.

\subsection{Pseudocode Description}
We describe the details of the pseudocode of Algorithm~\ref{alg:efpo}.

As described in Section~\ref{sec:divisible-approach}, Algorithm~\ref{alg:efpo} iteratively searches for a right value $r^*$ of the number of groups to raise. This corresponds to the for loop starting in Line 1. Line 2 calls Algorithm~\ref{alg:MakeInitGroupsDiv} to obtain initial groups as described in Section~\ref{sec:divisible-initcomps}.

Lines 4-5 initialize the pool of biggest spenders $B$ to $N_1$ and set the index of the lowest group in $B$, $\beta$, to 1. Lines 6-7 initialize the pool of least spenders $L$ to $N_R$ and set the index of the lowest group in $L$, $\lambda$, to $R$.

The loop starting in Line 8 is active while the pool of biggest spenders doesn't contain an unraised component ($\beta \le r$) and the pool of least spenders doesn't contain a raised component ($\lambda \ge r+1$). We then want to decide how much spending (chores) to \textit{drain} from $B$ to $L$. As described in Section~\ref{sec:divisible-discussion}, either the per-agent spending of $B$ can climb down to the per-agent spending of $N_{\beta+1}$, or the per-agent spending of $L$ can climb up to the per-agent spending of $N_{\lambda-1}$. Line 9 computes the total amount of spending $d_B$ to be transferred in the former case and Line 10 computes the total amount of spending $d_L$ to be transferred in the latter case.

The loop starting in Line 11 considers agents $b\in B$ one by one and computes an appropriately priced bundle of chores that should be taken away from them. If $B$ contains all the raised groups and $L$ contains all the unraised groups, i.e., if $\beta = r$ and $\lambda = r+1$ (Line 12), then we are a step away from obtaining a pEF allocation. We compute the average spending of all agents, $q$, in Line 13. This is the amount to which we want to bring every agent's spending. Hence, for each agent $b$ in consideration, we compute a subset $C\subseteq \mathbf{x}_b$ with value $s(B)-q$ (Line 14), and distribute it evenly to all agents in $L$ (Lines 20-21). Here, $\frac{1}{|L|}C$ denotes a (fractional) bundle of chores $C'$ where $C'_{ij} = \frac{1}{|L|}C_{ij}$ for agent $i$ and chore $j$ (revisit Section~\ref{sec:prelim} for the definition of a fractional allocation).

Otherwise, if $d_B \ge d_L$, then the per-agent spending of $L$ reaches the per-agent spending of $N_{\lambda-1}$ before the per-agent spending of $B$ reaches the per-agent spending of $N_{\beta+1}$. Hence each agent $\ell \in L$ must obtain an additional spending of $\frac{d_L}{|L|}$ from agents in $B$. We do this by computing a subset $C$ of $\mathbf{x}_b$ of value $\frac{d_L}{|B|}$ from every $b\in B$ (Line 16) and giving a $\frac{1}{|L|}$-sized fraction of $C$ to $\ell$ (Line 20-21). Thus, $\ell$ obtains a spending $\frac{1}{|L|}\cdot\frac{d_L}{|B|}$ from every agent in $B$, which totals to $\frac{d_L}{|L|}$, the required amount. Now, we update the pool of least spenders to include $N_{\lambda-1}$, and update $\lambda$ (Lines 25-26).

Analogously, when $d_B < d_L$, the per-agent spending of $B$ reaches the per-agent spending of $N_{\beta+1}$ before the per-agent spending of $L$ reaches the per-agent spending of $N_{\lambda-1}$. Hence, each agent $b\in B$ loses an amount equalling $\frac{d_B}{|B|}$. For each $b$, we compute a set $C$ with spending $\frac{d_B}{|B|}$ (Line 18), which is then transferred equally among all agents in $L$ (Line 20-21). We also update the pool of biggest spenders to include $N_{\beta+1}$, and update $\beta$ (Lines 28-29).

We terminate if the allocation is pEF (Lines 22-23). If not, then we continue our search for a right value $r^*$ by incrementing $r$ (Line 1). The arguments of Section~\ref{sec:divisible-discussion} show that for some $1\le r \le R-1$, Algorithm~\ref{alg:efpo} will terminate with a pEF+fPO allocation.

\section{Discussion}
In this paper, we presented a strongly polynomial-time algorithm for computing an EF1+fPO allocation of indivisible chores to agents with bivalued preferences, constituting the first non-trivial result for the EF1+PO problem for chores. Our algorithm is novel and relies on several involved arguments. Given that the general case is a challenging open problem, we believe extending our algorithm and its analysis to the class of $k$-ary chores is an interesting and natural next step. Another interesting question is whether we can compute an EFX allocation in this setting. We also presented a strongly polynomial-time for computing an EF+fPO allocation of divisible bivalued chores. Computing an EF+fPO allocation of divisible $k$-ary chores in polynomial-time is also a compelling direction for future work.

redpajama_set_name: RedPajamaArXiv


With only 10 days to go, let's learn a bit of history about the day....Why the 17th of March? This is widely believed to be the day that Patrick died. In its early years, the 17th of March was named the "Festival of St Patrick's Falling Asleep". It involved religious sermons about the life and work of Patrick, followed by celebratory activities, such as dancing, music, and perhaps even a little drinking.
Flanagan came home at four o'clock in the morning half drunk, and all his wages spent. His wife said, "How did you spend all your wages?"
He said, "I bought something for the house."
She said, "What could you buy for the house that cost so much?"
He said, "Eight rounds of drinks."
Applications for jobs on a government dam project had to take a written examination. The first question was: What does hydrodynamics meant?
Casey, who was an applicant, hesitated for a moment, then wrote, "It means that I don't get the job."


Best simple solution I can come up with is to get one of these flea-power Part 15 FM transmitters and something like the Grundig G-8 Traveler radio.
Avoid anything digital--you will have the same delay problem as with the Bluetooth devices. Again, you will need to create or find an adapter from the TRS headphone jack to XLR. Another consideration: what are you feeding into? If it is a mike level input, you will also need an audio pad to get the level down far enough that it doesn't overload your audio input.
Shure makes a combination 60 DB pad/adapter with a 1/4 plug on one end and an XLR female on the other. We use this to feed the output of a wireless mike receiver into our remote equipment. You can easily find adapters from 1/4 to 1/8th inch plugs.
Another approach is simply take the radio feed off-air---but I already know the answer why this probably won't work. Either you are streaming away games (and can't pick up the radio broadcast), or they use cell to feed the station, creating yet another digital delay.
TPT wrote: Best simple solution I can come up with is to get one of these flea-power Part 15 FM transmitters and something like the Grundig G-8 Traveler radio.
The only major problem I forsee with that approach is that, depending upon location, it may be difficult to find a way to mount the transmit antenna, as Part 15 FM transmitters must be used with the supplied antenna (See §15.203).
I have a 75 mhz. Comtek IFB, which is a Part 15 device. Using the included antenna--a simple whip that screws into the transmitter--I can cover a football field from the press box. I suspect the farthest distance that would need to be covered here is probably 100~150 feet across a field house. For example--from the play-by-play folks at court side to the TV equipment up near the top of the stands. So the built-in antenna supplied with these devices would surely put enough FM signal into a good portable radio to get the audio up to the TV equipment. Then it is just a matter of matching levels on transmit and receive from the respective equipment source and feed.
Long, long ago...in a galaxy far, far away. Oh, wait. Wrong story.
Quite a few years ago, we were faced with a similar situation - in our case, the video recording for the game was on the other side of the arena from the play-by-play. In this case, the recording was not for broadcast, it was to provide the video the league required of each game (at the time, it was the NPSL - indoor soccer). We used a simple wireless microphone. The lav mic on the transmitter was clipped to the headset boom for the play-by-play guy, the receiver connected to the camera. Nice, simple, and inexpensive as we had an extra wireless setup.


It is now possible for extensions to provide one or more PSR-4 definitions, in the ext_emconf.php file.
While it was possible to define a psr-4 section in a composer.json before already, now it is also possible to define an autoload/psr-4 section in the ext_emconf.php file as well, so that extension authors do not need to provide a composer.json just for that any more.
This is the new recommended way to register classes for TYPO3.
Without providing an autoload section, TYPO3 scans the complete extension directory for PHP class files and registers them all. This includes test classes or classes of third party libraries, which might lead to unexpected results.
Therefore it is recommended to provide such an autoload section in an extension. It will be ignored in older TYPO3 versions, so there will be no issue with backwards compatibility.


Smart Retail - empowering Retailers across the Globe.
Learn how we Empower Retailers daily.
Schedule your free demo. No Contracts. No Hassle.
with Smart Analytics and Insights.
Take advantage of our summer promo - starting at $39.99 / MO.
Download our latest Product Brochure PDF online.
Get SMART with your Retail Analytics.
Can Smart Retail transform your business?
Take a look at the Retailers we empower daily.
Gain valuable insights and trends from our blog.
Stay in sync with your shopper.
Smart Retail is a leading provider of loss prevention and security tools that will not only guard assets – but alert you to potential risks.
Smart Retail uses industry-leading video-analytics technology to allow retailers to optimize operations by responding quickly to customer needs and market trends.
To view a specific product – please select a tab to learn more or click below for all.
Through an interactive dashboard, merchants can harness real-time in-store analytics to create a personalized, omni-channel experience, capturing shopper interest at every touchpoint. Video data is enhanced by putting it in context with other data sources such as POS, inventory or RFID for the most complete picture for dynamic decision-making.
Monitor customer lines and cashier availability at registers through a simple notification interface, and dramatically reduce wait times. Additionally, leaders can gain powerful analytics on Average Wait Times, Average Queue Sizes, and Queue Flow Rate analysis.
Advertisement performance metrics and dwell time analysis focus on customer interactions with products and promotions.
With the precision of Smart Retail's face recognition – be alerted to known shoplifters or VIPs as they enter a retail location with Smart Alerts.
Customer Metrics captures what credit and membership card swipes miss; all the customers that did not purchase anything and more quantified, qualitative data on those that did.
Monitor secure areas of your back office or warehouse with unauthorized entry detection or loitering. Be alerted to any intruders or unauthorized parties in areas that are restricted or secure.
Manage your retail floor with in-depth analytics that monitor POS stations and other areas. This data can trigger alerts that notify internal teams of longer than usual wait times to allow better service of your customers and reduce unnecessary lines.
Store Conversion gives context to sales numbers. Smart Retail's store conversion product can accurately keep track of those who enter and purchase and those who do not.
Traffic Map clearly defines how consumers move about the premises. The system tracks where people are spending time and with which products or services they come in contact.
Get our latest Retailer Guide.
Meet the new Smart Retail.
Smart Retail names new Senior Director of Sales & Business Development.
Join Smart Retail at an upcoming event and test drive the most powerful platform available to Retailers.
Learn more about the strategic partners that stand behind Smart Retail.
Smart Retail is partnering with key value added resellers in the U.S. and International Markets.


Italian Creations--located at 16104 Hilliard Road in Lakewood--specializes in homemade gourmet Italian cuisine available for catering, carry-out, and delivery to your home or business. What a great idea to indulge in chicken marsala or perhaps fettuccini pesto accompanied with soup or salad and fresh focaccia bread delivered to you for lunch or dinner. You can even "Create Your Own Pizza & Pasta" with an array of sauces and toppings to choose from.
Make a statement at your next gathering with the popular Catering by Italian Creations. Holiday Parties, Weddings, Rehearsal Dinners, Showers, Lobster & Clam Bakes will be customized for you, or try the mouth-watering skewered beef tenderloin, seared scallops, or rack of lamb for an appetizer party with flare.
While specializing in off-premise catering, other services offered include tent rentals, china, silverware, bartenders, even valet.
Don't forget to call 216-226-2282 for that gourmet creation!
"Hosting a party can be a lot of work and stress. But the professional TEAM at Italian Creations makes hosting the party a breeze. They arrive early, they serve delicious hot food, and best of all, the clean every dish and glass before they leave. Whether at home or at work, when is the last time you actually had fun as the host of the party? If you haven't hired the professional TEAM Italian Creations, maybe now is the time to give them a try….and put the stress of hosting behind you. Colleen and I trust TEAM Italian Creations in our home and in our business."
© 2012 Italian Creations. All rights reserved. Website design and hosting by Website Solutions.


(JTA) — President Donald Trump took a swipe at the Jewish Democratic lawmaker challenging Nevada's sitting Republican senator.
Trump nicknamed Nevada Rep. Jacky Rosen "Wacky Jacky" on Saturday in a speech to the Nevada state GOP convention.
Rosen, a freshman congresswoman who served as president of her suburban Las Vegas Reform synagogue, is challenging Republican Sen. Dean Heller.
Trump also attacked Rosen for campaigning with Democratic Massachusetts Sen. Elizabeth Warren, who he referred to by the nickname "Pocahontas," over her claims of having some Native American ancestry.
"Wacky Jacky is campaigning with Pocahontas, you believe this? In your state!" he said.
Trump said he would be in Nevada "a lot" to campaign for Heller.
This story "Trump Nicknames Jewish Nevada Senate Candidate 'Wacky'" was written by JTA.


25 Fresh Palram Heavy Duty Greenhouse Shelf Kit. palram heavy duty greenhouse shelf kit costco, palram heavy duty greenhouse shelf kit supports up to 40 8 kg 90 lb galvanized steel brackets 3 plant hangers included. Tag : palram heavy duty greenhouse shelf kit, palram heavy duty shelf, palram heavy duty shelves, palram heavy duty shelf kit, palram heavy duty greenhouse shelf, palram heavy duty greenhouse shelf bundle 4 piece, 25 Fresh Palram Heavy Duty Greenhouse Shelf Kit.
Palram Greenhouse Heavy Duty Shelf Kit. Image for Palram Heavy Duty Greenhouse Shelf Kit Fantastic Palram Greenhouse Heavy Duty Shelf Kit.
So, if you want to acquire all of these fantastic pics about 25 Fresh Palram Heavy Duty Greenhouse Shelf Kit, press save icon to store the wallpapers for your pc. For many upgrades and latest information about 25 Fresh Palram Heavy Duty Greenhouse Shelf Kit images, please share to google plus or follow us on tweets, Instagram and path, or you mark this page on book mark area, We attempt to present you up-date regularly with fresh and new pics, enjoy your surfing, and find the perfect for you.


A BATTLE-OF-THE-BULGE is being fought across Cheshire as rival gooseberry growers defend their crops against a massed invasion of sun, heat and rain threatening the growing fruit, writes John Williams.
The sudden burst of sunshine gave a bumper harvest a ripening spurt some weeks too early for the annual gooseberry shows starting this weekend and continuing into next month in a string of villages, including Over Peover, Allostock, Goostrey and Holmes Chapel.
Russell Burns, patron of the Yellow Broom restaurant, Twemlow, is reportedly nurturing a "real whopper" of a berry on his bushes but it will be touch and go if it survives for the Swettenham show a week this Saturday.
"It is a really nice berry and I reckon if he is lucky and it doesn't burst it could win the Mid-Cheshire Association trophy for the heaviest this year," said Terry.
Association trophy for the heaviest this year," said Terry.


my name is Constantin. I am a student of computer science and economics at Vienna University of Technology.
This blog covers some of my interests such as coding, artificial intelligence, literature and personal development.
If you would like to provide some feedback, you can contact me here.
I hope you will enjoy reading!


At the direction of the School Board in response to the results of a community survey, district staff presented a smaller, less expensive list of facility work needed for the Board to consider as a bond package. The survey said that the community is supportive of a bond measure, but had concerns about what it would cost to pay for all the work.
During the Citizens Facilities Task Force process, the district's list of facility needs totaled about $766 million, and included improvements to address enrollment growth and crowding, expand Career-Technical/Vocational education programs, improve safety and security, including seismic safety, and more.
The narrowed list still addresses the needs, but includes fewer seismic and ADA projects, fewer classroom additions at middle schools, and includes refined cost estimates for all projects. The new total is about $619 million.
The estimated increase in the levy rate for a $619 million general obligation bond is $1.29 per thousand of assessed value. The community survey showed support for a bond measure in the $1.51 to $2.50 increase per thousand range.
After receiving the revised proposal, the Board asked staff for more information so they can deliberate further at their next meeting. Board members would like to see a list of items removed from the original $766 million package, more detail on the levy rate increase estimate, and how much more work could be added to the package at a levy rate of $1.51, the bottom of the range from the community survey.
The School Board will meet again on Tuesday, June 13, 2017, at 6:00 p.m. at Support Services Center, 2575 Commercial Street S.


We thinks what buyers think, the urgency of urgency to act during the interests of a purchaser position of theory, allowing for much better high-quality, reduced processing costs, charges are more reasonable, won the new and outdated consumers the support and affirmation for Original Factory Epever Ls0512eu 5a 12v Usb Output Manual Pwm Solar Charge Controller, We have constructed a reputable name among many purchasers. Quality&customer initially are normally our constant pursuit. We spare no endeavours to help make better items. Sit up for long-term cooperation and mutual advantages!
We thinks what buyers think, the urgency of urgency to act during the interests of a purchaser position of theory, allowing for much better high-quality, reduced processing costs, charges are more reasonable, won the new and outdated consumers the support and affirmation for Manual Pwm Solar Charge Controller, Manual Solar Charge Controller, Pwm Solar Charge Controller, We believe in quality and customer satisfaction achieved by a team of highly dedicated individuals. The team of our company with the use of cutting-edge technologies delivers impeccable quality merchandise supremely adored and appreciated by our customers worldwide.


text:
Darton ist der Name von:

 Darton (South Yorkshire), einer Ortschaft in England
 Nelson Horatio Darton (1865–1948), US-amerikanischer Geologe

redpajama_set_name: RedPajamaWikipedia


text:
Report: Gamers angry at DRM system from EA
PC gamers say the new digital rights management system is onerous and inconvenient, and makes them feel like the company is watching over their shoulders.
Daniel Terdiman
May 8, 2008 12:39 p.m. PT
Over on Techdirt Thursday morning, there's a report about some angry PC users of Electronic Arts games.
The gamers are upset, according to a post in the Mass Effect forums, because EA is apparently implementing a new Internet-based digital rights management system, known as SecuROM, that they find onerous, intrusive, and inconvenient.
Techdirt writes that a new version of SecuROM being employed by EA "is causing controversy due to an online verification system connected to its CD key. The system requires a connection to the Internet during installation to check (that) the CD key is valid, and then registers the key with the users' computer. After this the game will try to re-check the CD key every 5-10 days to ensure it hasn't since been found posted on a forum, or used in some form of piracy."
Then, it seems, if the key cannot be verified, SecuROM will attempt to do so for 10 more days. If, after that period, it still cannot be verified, Techdirt writes, the game will be locked down.
Further, SecuROM seems to limit the number of times a game can be installed to three.
Systems like this are never going to be winners for companies like EA. For every copy of one of its games that it successfully keeps from being illegally copied, it's going to lose a good customer who's beyond annoyed at the way the system works and the way they feel they're being treated.
To be sure, software companies feel they have to fight tooth and nail to avoid being robbed due to the ease with which many programs can be copied. But it seems they would do well to run their antipiracy/DRM systems by their PR departments--or, if they're doing that already, then some outside consultants--to make sure that the systems aren't going to alienate their user bases.
If they're already doing that, they might want to consider seeking additional guidance. Because as the Sony rootkit scandal and other DRM PR nightmares have shown, users do not want to be controlled in this way. And they vote with their wallets.
Discuss: Report: Gamers angry at DRM system from EA

redpajama_set_name: RedPajamaCommonCrawl