# Computing Pareto-Optimal and Almost Envy-Free
Allocations of Indivisible Goods††thanks: A preliminary version of the paper
appeared at AAAI 2021 [20]. Work supported by the NSF Grant CCF-1942321

Jugal Garg111University of Illinois at Urbana-Champaign, USA
<EMAIL_ADDRESS>Aniket Murhekar222University of Illinois at Urbana-
Champaign, USA
<EMAIL_ADDRESS>
###### Abstract

We study the problem of fair and efficient allocation of a set of indivisible
goods to agents with additive valuations using the popular fairness notions of
envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in
conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time
algorithm to compute an EF1+PO allocation, and a non-constructive proof of
existence of allocations that are both EF1 and fractionally Pareto-optimal
(fPO), which is a stronger notion than PO. We present a pseudo-polynomial time
algorithm to compute an EF1+fPO allocation, thereby improving the earlier
results. Our techniques also enable us to show that an EQ1+fPO allocation
always exists when the values are positive, and that it can be computed in
pseudo-polynomial time.

We also consider the class of $k$-ary instances where $k$ is a constant, i.e.,
each agent has at most $k$ different values for the goods. We show that for
such instances an EF1+fPO allocation can be computed in strongly polynomial
time. When all values are positive, we show that an EQ1+fPO allocation for
such instances can be computed in strongly polynomial time. Next, we consider
instances where the number of agents is constant, and show that an EF1+PO
(also EQ1+PO) allocation can be computed in polynomial time. These results
significantly extend the polynomial-time computability beyond the known cases
of binary or identical valuations.

Further, we show that the problem of computing an EF1+PO allocation
polynomial-time reduces to a problem in the complexity class PLS. We also
design a polynomial-time algorithm that computes a Nash welfare maximizing
allocation when there are constantly many agents with constant many different
values for the goods.

##  1 Introduction

The problem of fair division was formally introduced by Steinhaus [29], and
has since been extensively studied in various fields, including economics and
computer science [5, 25]. It concerns allocating resources to agents in a fair
and efficient manner, and has various practical applications such as rent
division, division of inheritance, course allocation and government auctions.
Much of the work has focused on divisible goods, which can be shared between
agents. In this setting, a prominent fairness notion is envy-freeness [14,
30], which requires that every agent prefer their own bundle of goods to that
of any other. On the other hand, when the goods are indivisible, envy-free
allocations need not even exist, e.g., in the simple case of one good and two
agents. Other classical notions of fairness, like equitability and
proportionality, may also be impossible to satisfy when goods are indivisible.
However, fair division of indivisible goods remains an important problem since
goods cannot always be shared, and also because it models several practical
scenarios such as a course allocation [27]. Since allocations satisfying
standard fairness criteria fail to exist in the case of indivisible goods,
several weaker fairness notions have been defined.

A relaxation of envy-freeness, called envy-freeness up to one good (EF1) was
defined by Budish [7]. An allocation is said to be EF1 if every agent prefers
their own bundle over the bundle of any other agent after removing at most one
good from the other agent’s bundle. When the valuations of the agents for the
goods are monotone, EF1 allocations exist and are polynomial time computable
[23].

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. A natural question to ask is whether
EF1 can be achieved in conjunction with PO under additive valuations. The
concept of Nash welfare provides a positive answer to this question. The Nash
welfare is the geometric mean of the agents’ utilities, and by maximizing it
we achieve a tradeoff between efficiency and fairness. Caragiannis et al. [8]
showed that any maximum Nash welfare (MNW) allocation is EF1 and PO. For
binary valuations, the MNW allocation can be computed in polynomial time [3].
However, in general, the problem of computing the MNW allocation is APX-hard
[22, 17].

Bypassing this barrier, Barman et al. [2] devised a pseudo-polynomial time
algorithm that computes an allocation that is both EF1 and PO. They also
showed that allocations that are both EF1 and fractionally Pareto-optimal
(fPO) always exist, where an allocation is said to be fPO if no fractional
allocation exists that makes an agent better off without making anyone else
worse off. They showed this result via a non-constructive convergence argument
used in real analysis, and did not provide an algorithm for computing such an
allocation. Clearly, fPO is a stronger notion of economic efficiency, and
hence the problem of computing EF1+fPO allocations is an important one.
Another reason to prefer fPO allocations over PO allocations in practice is
that the former property admits efficient verification; whereas checking if an
allocation is PO is known to be co-NP-complete [10]. This means that in
scenarios where a centralized entity is responsible for the allocation, all
participants can efficiently verify if an allocation is fPO (and thus PO).
However, in general, the same efficient verification is not possible for PO
allocations.

In this paper, we present a pseudo-polynomial time algorithm that computes an
allocation that is EF1+fPO. Not only does this improve the result of Barman et
al., but it also provides other interesting insights. We consider the class of
$k$-ary instances for a constant $k$, i.e., each agent has at most $k$
different values for the goods. Our analysis shows that for such instances, an
EF1+fPO allocation can be found in polynomial time. Our result becomes
especially interesting in light of the fact that computing the MNW allocation
remains NP-hard for such instances [22], and even for $k=3$ [1]. Further, this
is the first class apart from binary or identical valuations for which EF1+fPO
allocations are polynomial time computable.

While $k$-ary instances are interesting from a theoretical point of view to
understand the limits of tractability in computing fair and efficient
allocations, they are also relevant from a practical perspective. Eliciting
the values that agents have for goods is often a tricky task, as agents may
not be able to assert exactly what values they have for different goods. A
simple protocol that the entity in charge of the allocation can do is to ask
each agent to “rate” the goods using a few (constantly many) values. Based on
these responses, the valuations of the agents can be established.

Equitability up to one good (EQ1) is a generalization of the classical
fairness notion of equitability. An allocation is said to be EQ1 if the
utility an agent gets from her bundle is no less than the utility any other
agent gets after removing one specific good from their bundle. Using
techniques similar to those used by Barman et al. [2], a pseudo-polynomial
time algorithm to compute an EQ1+PO allocation was developed by Freeman et al.
[15], when all the values are positive. We show the stronger result that
EQ1+fPO allocations always exist for positive-valued instances, and can in
fact be computed in pseudo-polynomial time. Our techniques also show that for
$k$-ary instances with positive values where $k$ is a constant, an allocation
that is EQ1 and fPO can be computed in polynomial time.

In many practical applications, the number of agents $n$ is constant. We show
that for constant $n$, an EF1+PO allocation can be computed in time polynomial
in the number of goods for the case of general additive valuations. In
contrast, computing the MNW allocation remains NP-hard for $n=2$. Our
techniques also show that for constant $n$, an EQ1+PO allocation can also be
computed in polynomial time. Further, when we consider $k$-ary instances with
constant $n$ and $k$, we show that many fair division problems, including
computing the MNW allocation, have polynomial time complexity. This improves
the result of Bliem et al. [4] who show that the problem of computing an EF+PO
allocation is tractable in this case.

We also make progress on the complexity-front. We prove that the problem of
computing an EF1+PO allocation polynomial-time reduces to solving a problem in
the complexity class Polynomial Local Search (PLS). For this, we carefully
analyze Barman et al.’s [2] algorithm and show that it has the structure of
local-search problem. Finally, we remark that our techniques also improve the
results of Chakraborty et al. [9] and Freeman et al. [16] for the problems of
computing weighted-EF1+fPO allocations of goods and EQ1+fPO allocations of
_chores_ , respectively.

We summarize our results in the following table.

Instance type | EF1+fPO | EQ1+fPO∗
---|---|---
constant $n$ |  $\mathsf{poly}(m)$ (Theorem 9) |  $\mathsf{poly}(m)$ (Theorem 10)
$k$-ary with constant $k$ |  $\mathsf{poly}(n,m)$ (Theorem 3) |  $\mathsf{poly}(n,m)$ (Theorem 7)
general additive |  $\mathsf{poly}(n,m,v_{max})$ (Theorem 2) |  $\mathsf{poly}(n,m,v_{max})$ (Theorem 6)
Table 1: Best-known algorithm run-times for the EF1+fPO and EQ1+fPO problems
classified according to instance type. Here $n$ and $m$ denote the number of
agents and goods respectively, and $v_{max}$ denotes the maximum utility
value. Agents have additive valuations. Results for the EQ1+fPO problem apply
to positive instances.

###  1.1 Related Work.

Barman et al. [2] devised a pseudo-polynomial time algorithm that computes an
allocation that is both EF1 and PO. This algorithm runs in time
$\mathsf{poly}(n,m,v_{max})$, where $n$ is the number of agents, $m$ the
number of items, and $v_{max}$ the maximum utility value. Their algorithm
first perturbs the values to a desirable form, and then computes an EF1 and
fPO allocation for the perturbed instance. Their approach is via integral
market-equilibria, which guarantees fPO at every step. The spending of an
agent, which is the sum of prices of the goods she owns in the equilibrium,
works as a proxy for her utility. The returned allocation is approximately-EF1
and approximately-PO for the original instance, which for a fine-enough
approximation is EF1 and PO. Our algorithm proceeds in a similar manner to
their algorithm, with one main difference being that we do not need to
consider any approximate instance and can work directly with the given
valuations. Our algorithm returns an allocation that is not only PO, but is in
fact fPO. Another key difference is the run-time analysis: while their
analysis relies on bounding the number of steps using arguments about prices,
our analysis is more direct and works with the values. This allows us to prove
a general Theorem 1, of which polynomial run-time for $k$-ary instances with
constant $k$ is a consequence. Directly, such a conclusion cannot be drawn
from the analysis of Barman et al. Another technical difference is that we
raise the prices of multiple components of _least spenders_ simultaneously,
unlike in [2], and our analysis is arguably simpler than theirs. Barman et al.
also showed that there is a non-deterministic algorithm that computes an
EF1+fPO allocation, since checking if an allocation is fPO can be done
efficiently. In contrast, we present a deterministic algorithm computing an
EF1+fPO allocation, albeit with worst-case pseudopolynomial run time. Garg and
Murhekar [19] showed that allocations that are EFX (envy-free up to removal of
any good) and fPO exist and can be computed in polynomial time for a subclass
of 2-ary instances called bivalued instances. Recently, Garg et al. [21] and
Ebadian et al. [13], independently showed that EF1+fPO allocations can be
computed in polynomial-time for bivalued instances of chores.

We also show that finding an EF1+PO allocation reduces to a problem in PLS.
However this doesn’t place it in PLS, since the problem is not in the class
_Total Function NP_ $\supseteq$ PLS [2].

Freeman et al. [15] presented a pseudo-polynomial time algorithm for computing
an EQ1+PO allocation for instances with positive values. Since they consider
an approximate instance too, their algorithm does not achieve the guarantee of
fPO. They also show that the leximin solution, i.e., the allocation that
maximizes the minimum utility, and subject to this, maximizes the second
minimum utility, and so on; is EQX (a stronger requirement than EQ1) and PO
for positive utilities. However, as remarked by Plaut and Roughgarden [28],
computing a leximin solution is intractable. For positive bivalued instances,
Garg and Murhekar [19] showed that an EQX+fPO allocation can be computed in
polynomial time.

Knop et al. [6] presented a framework for fixed-parameter algorithms for many
fairness concepts, including EF1+PO, parameterized by $n+v_{max}$. Our results
improve their findings and show that the problem has polynomial time
complexity for the cases of (i) constant $n$, (ii) constant number of utility
values, (iii) $v_{max}$ bounded by $\mathsf{poly}(m,n)$.

##  2 Preliminaries

For $t\in\mathbb{N}$, let $[t]$ denote $\\{1,\dots,t\\}$.

#### Problem setting.

A fair division instance is a tuple $(N,M,V)$, where $N=[n]$ is a set of
$n\in\mathbb{N}$ agents, $M=[m]$ is the set of $m\in\mathbb{N}$ indivisible
items, and $V=\\{v_{1},\dots,v_{n}\\}$ is a set of utility functions, one for
each agent $i\in N$. Each utility function $v_{i}:M\rightarrow\mathbb{Z}_{\geq
0}$ is specified by $m$ numbers $v_{ij}\in\mathbb{Z}_{\geq 0}$, one for each
good $j\in M$, which denotes the value agent $i$ has for good $j$. We assume
that the valuation functions are additive, that is, for every agent $i\in N$,
and for $S\subseteq M$, $v_{i}(S)=\sum_{j\in S}v_{ij}$. Further, we assume
that for every good $j$, there is some agent $i$ such that $v_{ij}>0$. Note
that we can in general work with rational values, since they can be scaled to
make them integral.

We call a fair division instance $(N,M,V)$ a:

  1. 1.

Binary instance if for all $i\in N$ and $j\in M$, $v_{ij}\in\\{0,1\\}$.

  2. 2.

$k$-ary instance, if $\forall i\in N$, $|\\{v_{ij}:j\in M\\}|\leq k$.

  3. 3.

Positive-valued instance if $\forall i\in N$, $\forall j\in M$, $v_{ij}>0$.

Note that the class of $k$-ary instances generalizes the class of $k$-valued
instances as defined by [1], in which all values belong to a $k$-sized set,
whereas we allow each agent to have $k$ different values for the goods.

#### Allocation.

An allocation $\mathbf{x}$ of goods to agents is a $n$-partition of the goods
$\mathbf{x}_{1},\dots,\mathbf{x}_{n}$, where agent $i$ is allotted
$\mathbf{x}_{i}\subseteq M$, and gets a total value of
$v_{i}(\mathbf{x}_{i})$. A fractional allocation $\mathbf{x}\in[0,1]^{n\times
m}$ is a fractional assignment such that for each good $j\in M$, $\sum_{i\in
N}x_{ij}\leq 1$. Here, $x_{ij}\in[0,1]$ denotes the fraction of good $j$
allotted to agent $i$.

For an agent $i\in N$, let $U_{i}$ be the number of different utility values
$i$ can get in any allocation. Let $U=\max_{i\in N}U_{i}$.

#### Fairness notions.

An allocation $\mathbf{x}$ is said to be:

  1. 1.

Envy-free up to one good (EF1) if for all $i,h\in N$, there exists a good
$j\in\mathbf{x}_{h}$ s.t. $v_{i}(\mathbf{x}_{i})\geq
v_{i}(\mathbf{x}_{h}\setminus\\{j\\})$.

  2. 2.

Equitable up to one good (EQ1) if for all $i,h\in N$, there exists a good
$j\in\mathbf{x}_{h}$ s.t. $v_{i}(\mathbf{x}_{i})\geq
v_{h}(\mathbf{x}_{h}\setminus\\{j\\})$.

#### Pareto-optimality.

An allocation $\mathbf{y}$ dominates an allocation $\mathbf{x}$ if
$v_{i}(\mathbf{y}_{i})\geq v_{i}(\mathbf{x}_{i}),\forall i$ and there exists
$h$ s.t. $v_{h}(\mathbf{y}_{h})>v_{h}(\mathbf{x}_{h})$. An allocation is said
to be 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.

#### Maximum Nash Welfare.

The Nash welfare of an allocation $\mathbf{x}$ is given by
$\mathsf{NW}(\mathbf{x})=\big{(}\Pi_{i\in
N}v_{i}(\mathbf{x}_{i})\big{)}^{1/n}$. An allocation that maximizes the NW is
called a MNW allocation.

#### Fisher markets.

A Fisher market or a market instance is a tuple $(N,M,V,e)$, where the first
three terms are interpreted as before, and $e=\\{e_{1},\dots,e_{n}\\}$ is the
set of agents’ budgets, where $e_{i}\geq 0$, for each $i\in N$. In this model,
goods can be allocated fractionally. Given prices
$\mathbf{p}=(p_{1},\dots,p_{m})$ of goods, each agent aims to obtain the set
of goods that maximizes her total value subject to her budget constraint.

A market outcome is a (fractional) allocation $\mathbf{x}$ of the goods to the
agents and a set of prices $\mathbf{p}$ of the goods. The spending of an agent
$i$ under the market outcome $(\mathbf{x},\mathbf{p})$ is given by
$\mathbf{p}(\mathbf{x}_{i})=\sum_{j\in M}p_{j}x_{ij}$. For an agent $i$, we
define the bang-per-buck ratio $\alpha_{ij}$ of good $j$ as $v_{ij}/p_{j}$,
and the maximum bang-per-buck (MBB) ratio $\alpha_{i}=\max_{j}\alpha_{ij}$. We
define $mbb_{i}=\\{j\in M:v_{ij}/p_{j}=\alpha_{i}\\}$, called the MBB-set, to
be the set of goods that give MBB to agent $i$ at prices $\mathbf{p}$. A
market outcome $(\mathbf{x},\mathbf{p})$ is said to be ‘on MBB’ if for all
agents $i$ and goods $j$, $x_{ij}>0$ implies $j\in mbb_{i}$. For integral
$\mathbf{x}$, this means $\mathbf{x}_{i}\subseteq mbb_{i}$ for all $i\in N$.

A market outcome $(\mathbf{x},\mathbf{p})$ is said to be a market equilibrium
if (i) the market clears, i.e., all goods are fully allocated. Thus, for all
$j$, $\sum_{i\in N}x_{ij}=1$, (ii) budget of all agents is exhausted, for all
$i\in N$, $\sum_{j\in M}x_{ij}p_{j}=e_{i}$, and (iii) agents only spend money
on goods that give them maximum bang-per-buck, i.e., $(\mathbf{x},\mathbf{p})$
is on MBB. Given a market outcome $(\mathbf{x},\mathbf{p})$ with $\mathbf{x}$
integral, we say it is price envy-free up to one good (pEF1) if for all
$i,h\in N$ there is a good $j\in\mathbf{x}_{h}$ such that
$\mathbf{p}(\mathbf{x}_{i})\geq\mathbf{p}(\mathbf{x}_{h}\setminus\\{j\\})$.
For integral market outcomes on MBB, the pEF1 condition implies the EF1
condition.

######  Lemma 1.

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.

###### Proof.

We first show that $(\mathbf{x},\mathbf{p})$ forms a market equilibrium for
the Fisher market instance $(N,M,V,e)$, where for every $i\in N$,
$e_{i}=\mathbf{p}(\mathbf{x}_{i})$. It is easy to see that the market clears
and the budget of every agent is exhausted. Further $\mathbf{x}$ is on MBB as
per our assumption. Now the fact that $\mathbf{x}$ is fPO follows from the
First Welfare Theorem [24], 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 good $j\in\mathbf{x}_{h}$ s.t.
$\mathbf{p}(\mathbf{x}_{i})\geq\mathbf{p}(\mathbf{x}_{h}\setminus\\{j\\})$.
Since $(\mathbf{x},\mathbf{p})$ is on MBB, $\mathbf{x}_{i}\subseteq mbb_{i}$.
Let $\alpha_{i}$ be the MBB-ratio of $i$ at the prices $\mathbf{p}$. By
definition of MBB,
$v_{i}(\mathbf{x}_{i})=\alpha_{i}\mathbf{p}(\mathbf{x}_{i})$, and
$v_{h}(\mathbf{x}_{h}\setminus\\{j\\})\leq\alpha_{i}\mathbf{p}(\mathbf{x}_{h}\setminus\\{j\\})$.
Combining these, we get that $\mathbf{x}$ is EF1. ∎

Given a price vector $\mathbf{p}$, we define the MBB graph to be the bipartite
graph $G=(N,M,E)$ where for an agent $i$ and good $j$, $(i,j)\in E$ iff $j\in
mbb_{i}$. Such edges are called MBB. Given an accompanying allocation
$\mathbf{x}$, we supplement $G$ to include allocation edges, an edge between
$i$ and $j$ if $j\in\mathbf{x}_{i}$.

We call an agent $i$ with minimum $\mathbf{p}(\mathbf{x}_{i})$ a least spender
(LS), and denote by $L$ the set of least spenders. For agents
$i_{0},\dots,i_{\ell}$ and goods $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\leq\ell^{\prime}\leq\ell$,
$j_{\ell^{\prime}}\in\mathbf{x}_{i_{\ell^{\prime}-1}}\cap\textrm{mBB}_{i_{\ell^{\prime}}}$,
is called a special path. We define the 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 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 least spender agent.

######  Definition 1 (Component $C_{i}$ of a least spender $i$).

For a least spender $i$, define $C_{i}^{\ell}$ to be the set of all goods and
agents which lie on alternating paths of length $\ell$. Call
$C_{i}=\bigcup_{\ell}C_{i}^{\ell}$ the component of $i$, the set of all goods
and agents reachable from the least spender $i$ through alternating paths.

##  3 Finding EF1+fPO Allocations of Goods

We now present the main algorithm of our paper. Given a fair division instance
$(N,M,V)$, our algorithm returns an allocation $\mathbf{x}$ that is EF1 and
fPO. We show Algorithm 1 terminates in time $\mathsf{poly}(n,m,U)$ with an
EF1+fPO allocation.

Algorithm 1 starts with a welfare maximizing integral allocation
$(\mathbf{x},\mathbf{p})$, where $p_{j}=v_{ij}$ for $j\in\mathbf{x}_{i}$. The
algorithm then explores if there is an alternating path
$P=(i,j_{1},i_{1},\dots,j_{\ell},i_{\ell}=h)$, from some LS agent $i\in L$,
such that
$\mathbf{p}(\mathbf{x}_{h}\setminus\\{j_{\ell}\\})>\mathbf{p}(\mathbf{x}_{i})$,
i.e., an alternating path along which the pEF1 condition is violated for the
LS agent w.r.t the good $j_{\ell}$. When such a path is encountered, the
algorithm transfers $j_{\ell}$ from $h$ to $i_{\ell-1}$. When there is no such
path from $i$, the component $C_{i}$ of the LS agent $i$ is pEF1. We denote by
$C_{L}$ the union of all components of LS agents. Suppose the overall
allocation is not pEF1, then the algorithm raises the prices of all goods in
the $C_{L}$ until either (i) a new MBB edge gets added from an agent $h\in
C_{L}$ to a good $j\notin C_{L}$ (corresponding to a price rise of
$\gamma_{1}$), or (ii) the spending of an agent $h\notin C_{L}$ becomes equal
to the spending of the agents in $L$ (corresponding to a price rise of
$\gamma_{2}$). The algorithm then proceeds as before from Line 2.

Algorithm 1 Computing an EF1+fPO allocation of goods

Input: Fair division instance $(N,M,V)$
Output: An integral allocation $\mathbf{x}$

1:$(\mathbf{x},\mathbf{p})\leftarrow$ initial welfare maximizing integral
market allocation, where $p_{j}=v_{ij}$ for $j\in\mathbf{x}_{i}$.

2:$L\leftarrow\\{i\in N:i\in\mathsf{argmin}_{h\in
N}\mathbf{p}(\mathbf{x}_{h})\\}$ $\triangleright$ set of LS

3:if $\exists i\in L,\exists$ alternating path
$(i,j_{1},i_{1},\dots,j_{\ell},i_{\ell})$, s.t.
$\mathbf{p}(\mathbf{x}_{i_{\ell}}\setminus\\{j_{\ell}\\})>\mathbf{p}(\mathbf{x}_{i})$
then

4: Transfer $j_{\ell}$ from $i_{\ell}$ to $i_{\ell-1}$

5: Repeat from Line 2

6:if $(\mathbf{x},\mathbf{p})$ is pEF1 then return $\mathbf{x}$

7:else

8: $\gamma_{1}=\min_{h\in C_{L}\cap N,j\in M\setminus
C_{L}}\frac{\alpha_{h}}{v_{hj}/p_{j}}$ $\triangleright$ Factor by which prices
of goods in $C_{L}$ are raised until a new MBB edge appears from an agent in
$C_{L}$ to a good outside $C_{L}$

9: $\gamma_{2}=\min_{i\in L,h\in N\setminus
C_{L}}\frac{\mathbf{p}(\mathbf{x}_{h})}{\mathbf{p}(\mathbf{x}_{i})}$
$\triangleright$ Factor by which prices of goods in $C_{L}$ are raised until a
new agent outside $C_{L}$ becomes a new LS

10: $\beta=\min(\gamma_{1},\gamma_{2})$

11: for $j\in C_{L}\cap M$ do

12: $p_{j}\leftarrow\beta p_{j}$

13: Repeat from Line 2

We will use the terms time-step or iteration interchangeably to denote either
a transfer or a price rise step. We say ‘at time-step $t$’, to refer to the
state of the algorithm 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$. First we note that:

######  Lemma 2.

At any time-step $t$, $(\mathbf{x}^{t},\mathbf{p}^{t})$ is on MBB.

###### Proof.

We want to show that at every iteration of the algorithm, every agent owns
goods from their MBB-set. To see this, notice that this is the case in the
initial allocation in Line 1 of the algorithm. Suppose we assume inductively
that at iteration $t$, in the corresponding allocation $\mathbf{x}$, every
agent buys MBB goods. We ensure that the goods are transferred along MBB
edges, and thus no transfer step causes the MBB condition of any agent to be
violated. Consider a price-rise step, in which the prices of all goods in
$C_{L}$, the component of the least spenders $L$ are increased by a factor of
$\beta$. Since prices of these goods are raised, no agent $h\notin C_{L}$
prefers these goods over their own goods, and hence they continue to own goods
from their MBB set. For any agent $h\in C_{L}$ and a good $j\notin C_{L}$, the
bang-per-buck that $j$ gets from $h$ before the price rise is strictly less
than her MBB ratio, since $j$ is not in the MBB set of $h$. Further we never
raise these prices beyond the creation of a new MBB edge from any agent $h\in
C_{L}$ to some agent $j\in C_{L}$. Thus the MBB condition is not violated for
any agent $h\in C_{L}$.

In conclusion, the MBB condition is never violated for any agent throughout
the algorithm, and hence the allocation always on MBB. ∎

If Algorithm 1 terminates, then the final outcome $(\mathbf{x},\mathbf{p})$ is
pEF1. Since it is also on MBB, by Lemma 1, $\mathbf{x}$ is EF1+fPO. We now
proceed towards the run-time analysis of Algorithm 1. First we observe that
since prices are raised only until the spending of a new agent becomes equal
to the spending of the least spenders.

######  Lemma 3.

The spending of the least spender(s) does not decrease as the algorithm
progresses. Further at any price rise event $t$ with price-rise factor
$\beta$, the spending of the least spender(s) increases by a factor of
$\beta$.

Next, similar to Barman et al. [2], we observe that:

######  Lemma 4.

The number of iterations with the same set of least spenders is
$\mathsf{poly}(n,m)$.

###### Proof.

Let us fix a set $L$ of least spenders. We count the number of alternating
paths from some $i\in L$ to an agent $k$ who owns a good $j$ which is then
transferred to an agent $h$. The number of such paths is at most $n\cdot
n\cdot m\cdot n=n^{3}m$, thus there are at most $\mathsf{poly}(n,m)$ transfers
with the same set of LS in the absence of price-rise steps. Further, there can
be at most $n$ price-rise steps without any change in $L$. ∎

The next lemma is key. We argue that between the time-steps at which an agent
$i$ ceases to be a LS and subsequently becomes a LS again, her utility
strictly increases.

######  Lemma 5.

Let $t_{0}$ be a time-step where agent $i$ ceases to be a LS, and let
$t_{\ell}$ be the first subsequent time step just after which $i$ becomes the
LS again. Then:

$v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})>v_{i}(\mathbf{x}_{i}^{t_{0}})$

Note here that $v_{i}(\mathbf{x}_{i}^{t_{0}})$ is the utility of agent $i$
_just before_ time-step $t_{0}$, and $v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})$ her
utility _just after_ time-step $t_{\ell}$.

###### Proof.

From Lemma 3, since $i$ ceases to be a LS after time-step $t_{0}$, $i$ must
have received some good $j$ at time step $t_{0}$. Since $j\in mbb_{i}$ at
$t_{0}$, $v_{ij}>0$. Suppose $i$ does not lose any good in any subsequent
iterations until $t_{\ell}$, then
$\mathbf{x}^{t_{\ell}+1}_{i}\supseteq\mathbf{x}^{t_{0}}_{i}\cup\\{j\\}$, and
hence $v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})\geq
v_{i}(\mathbf{x}_{i}^{t_{0}}\cup\\{j\\})=v_{i}(\mathbf{x}_{i}^{t_{0}})+v_{ij}>v_{i}(\mathbf{x}_{i}^{t_{0}})$,
using additivity of valuations.

On the other hand suppose $i$ does lose some goods between $t_{0}$ and
$t_{\ell}$. Let $t_{k}\in(t_{0},t_{\ell}]$ be the last time-step when $i$
loses a good, say $j^{\prime}$. Let $t_{1},\dots,t_{k-1}$ be time-steps (in
order) between $t_{0}$ and $t_{k}$ when $i$ experiences price-rise, and
$t_{k+1},\dots,t_{\ell-1}$ be time-steps (in order) between $t_{k}$ and
$t_{\ell}$ when $i$ experiences price-rise, until finally after the event
$t_{\ell}$ agent $i$ becomes the LS again. Let us define $\beta_{t}$ to be the
price-rise factor at the time-step $t$. If $t$ is a price-rise step,
$\beta_{t}>1$, else we set $\beta_{t}=1$. Hence
$\beta_{t_{1}},\dots,\beta_{t_{k-1}},\beta_{t_{k+1}},\dots,\beta_{t_{\ell-1}}$
are price-rise factors at the corresponding events
$t_{1},\dots,t_{k-1},t_{k+1},\dots,t_{\ell-1}$ and are all greater than 1. If
$t_{\ell}$ is a price-rise event, let the price-rise factor be
$\beta_{t_{\ell}}>1$; and if not let $\beta_{t_{\ell}}=1$. Note that $t_{k}$
is not a price-rise event and hence $\beta_{t_{k}}=1$.

Using Lemma 3, together with the fact that $i$ does not lose any good after
$t_{k}$, we have:

$\mathbf{p}^{t_{\ell}+1}(\mathbf{x}_{i}^{t_{\ell}+1})\geq(\beta_{t_{\ell}}\beta_{t_{\ell-1}}\cdots\beta_{t_{k+1}})\mathbf{p}^{t_{k}}(\mathbf{x}^{t_{k}}_{i}\setminus\\{j^{\prime}\\}).$
(1)

The above may not be an equality because in addition to experiencing price-
rises during $t_{k+1},\dots,t_{\ell}$, agent $i$ may also gain some new good.
If $i_{k}$ is a LS at $t_{k}$, then for agent $i$ to lose the good
$j^{\prime}$ it must be the case that:

$\mathbf{p}^{t_{k}}(\mathbf{x}^{t_{k}}_{i}\setminus\\{j^{\prime}\\})>\mathbf{p}^{t_{k}}(\mathbf{x}^{t_{k}}_{i_{k}}).$
(2)

Let $i_{t}$ be a LS at time-step $t$. Then by repeatedly applying Lemma 3, we
get:

$\displaystyle\mathbf{p}^{t_{k}}(\mathbf{x}^{t_{k}}_{i_{k}})$
$\displaystyle\geq\beta_{t_{k}-1}p^{t_{k}-1}(\mathbf{x}^{t_{k}-1}_{i_{t_{k}-1}})$
(3)
$\displaystyle\geq\dots\geq(\beta_{t_{k}-1}\beta_{t_{k}-2}\cdots\beta_{1})\mathbf{p}^{t_{0}}(\mathbf{x}^{t_{0}}_{i_{t_{0}}})$
$\displaystyle\geq(\beta_{t_{k-1}}\beta_{t_{k-2}}\cdots\beta_{t_{1}})\mathbf{p}^{t_{0}}(\mathbf{x}^{t_{0}}_{i})\enspace,$

where the last transition follows from the facts that (i) each $\beta_{t}\geq
1$, (ii) $\\{t_{1},\dots,t_{k-1}\\}\subseteq\\{1,\dots,t_{k}-1\\}$, and (iii)
$i_{t_{0}}=i$, since $i$ is a least spender at $t_{0}$. Putting (1), (2) and
(3) together, we get:

$\mathbf{p}^{t_{\ell}+1}(\mathbf{x}_{i}^{t_{\ell}+1})>(\Pi_{r=1}^{\ell}\beta_{t_{r}})\mathbf{p}^{t_{0}}(\mathbf{x}^{t_{0}}_{i})\enspace.$
(4)

Let $\alpha^{t}_{i}$ denote the MBB-ratio of $i$ at the time step $t$. Observe
that in every price rise event with price rise factor $\beta$, the MBB ratio
of any agent experiencing the price rise decreases by a factor $\beta$.
Further, the MBB ratio of any agent does not change unless she experiences a
price-rise step. Thus:

$\alpha_{i}^{t_{\ell}+1}=\frac{\alpha_{i}^{t_{0}}}{(\beta_{t_{\ell}}\beta_{t_{\ell-1}}\cdots\beta_{t_{k+1}})(\beta_{t_{k-1}}\beta_{t_{k-2}}\cdots\beta_{t_{1}})}\enspace.$
(5)

Therefore using the fact that the allocation is on MBB edges, and with (4) and
(5), we have:

$\displaystyle v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})$
$\displaystyle=\alpha_{i}^{t_{\ell}+1}\mathbf{p}^{t_{\ell}+1}(\mathbf{x}^{t_{\ell}+1}_{i})$
($\mathbf{x}^{t_{\ell}+1}$ is on MBB)
$\displaystyle>\frac{\alpha_{i}^{t_{0}}}{(\Pi_{r=1}^{\ell}\beta_{t_{r}})}(\Pi_{r=1}^{\ell}\beta_{t_{r}})\mathbf{p}^{t_{0}}(\mathbf{x}^{t_{0}}_{i})$
(From (4) and (5))
$\displaystyle=\alpha^{t_{0}}_{i}\mathbf{p}^{t_{0}}(\mathbf{x}_{i}^{t_{0}})=v_{i}(\mathbf{x}_{i}^{t_{0}}),$
($\mathbf{x}^{t_{0}}$ is on MBB)

as claimed. ∎

Using the above lemmas, we show:

######  Lemma 6.

Algorithm 1 terminates in time $\mathsf{poly}(n,m,U)$.

###### Proof.

Consider any agent $i$. From Lemma 5, it is clear that every time $i$ becomes
the LS again her utility has strictly increased compared to her utility the
last time she was a LS. The number of utility values that $i$ can have is
$U_{i}$, and hence we conclude that the number of times she stops being an LS
and becomes LS again is at most $U_{i}$. Since there are $n$ agents, and each
agent $i$ can become the LS again at most $U_{i}$ times, we have that after
$\mathsf{poly}(n,\max_{i\in N}U_{i})$ changes in the set of least spenders,
there will be no changes further in the set of least spenders. After this, in
at most $n$ more price-rise steps, either the allocation becomes pEF1 or all
agents get added to $C_{L}$, since no new agent becomes a LS on raising
prices. Further, the number of transfers with the same set of least spenders
is at most $\mathsf{poly}(n,m)$ (Lemma 4). This shows that Algorithm 1
terminates in time $\mathsf{poly}(n,m,U)$. ∎

Putting it all together, we conclude:

######  Theorem 1.

Let $I=(N,M,V)$ be a fair division instance. Then an allocation that is both
EF1 and fPO can be computed in time $\mathsf{poly}(n,m,U)$.

Observe that in any allocation and for any agent, the minimum utility is 0,
and the maximum utility is $mv_{max}$, where $v_{max}=\max_{i,j}v_{ij}$. Since
the utility values are integral, we have $U\leq mv_{max}+1$. Thus, Algorithm 1
computes an EF1+fPO allocation in pseudo-polynomial time.

######  Theorem 2.

Given a fair division instance $I=(N,M,V)$, an allocation that is both EF1 and
fPO can be computed in time $\mathsf{poly}(n,m,v_{max})$, where
$v_{max}=\max_{i,j}v_{ij}$. In particular, when
$v_{max}\leq\mathsf{poly}(n,m)$, an EF1+fPO allocation can be computed in
$\mathsf{poly}(n,m)$ time.

The guarantee of EF1+fPO offered by our algorithm is stronger than the
guarantee of EF1+PO provided by the algorithm of Barman et al. [2]. We next
turn our attention to $k$-ary instances where $k$ is a constant. First we
observe that for such instances, the maximum number of different utility
values any agent can get is at most $\mathsf{poly}(m)$.

######  Lemma 7.

In a $k$-ary fair division instance $(N,M,V)$ with constant $k$,
$U\leq\mathsf{poly}(m)$.

###### Proof.

For any agent $i$, let $\\{v_{i}^{\ell}\\}_{\ell\in[k]}$ be the different
utility values $i$ has for the goods. In an allocation $\mathbf{x}$, let
$m_{i}^{\ell}\in\mathbb{Z}_{\geq 0}$ be the number of goods in
$\mathbf{x}_{i}$ with value $v_{i}^{\ell}$. Then agent $i$’s utility is
simply: $v_{i}(\mathbf{x}_{i})=m_{i}^{1}v_{i}^{1}+\dots+m_{i}^{k}v_{i}^{k}$.
Since each $0\leq m_{i}^{\ell}\leq m$, the number of possible utility values
that $i$ can get in any allocation is at most $(m+1)^{k}$, which is
$\mathsf{poly}(m)$ since $k$ is constant. Thus $U\leq\mathsf{poly}(m)$. ∎

Therefore, using Lemma 7, Theorem 1 gives:

######  Theorem 3.

Given a $k$-ary fair division instance $I=(N,M,V)$ where $k$ is a constant, an
allocation that is both EF1 and fPO can be computed in time
$\mathsf{poly}(n,m)$.

######  Remark 4.

We note that our techniques can also be used to show that an allocation that
is weighted-EF1 (wEF1) and fPO exists and can be computed in pseudo-polynomial
time.

##  4 Finding EQ1+fPO Allocations of Goods

We now show that Algorithm 2 finds an EQ1+fPO allocation given a fair division
instance with positive values. We require the values to be positive because
instances with zero values might not even admit an allocation that is EQ1+PO
[15]. Algorithm 2 is similar to Algorithm 1, except that it works with values
instead of spendings of agents since EQ1 allocations are desired as opposed to
EF1.

Algorithm 2 starts with a welfare maximizing integral allocation
$(\mathbf{x},\mathbf{p})$, where $p_{j}=v_{ij}$ for $j\in\mathbf{x}_{i}$. We
refer to the agent(s) with the least utility as the LU agent(s), and let $L$
be the set of LU agents. The algorithm first explores if there is an
alternating path $P=(i=i_{0},j_{1},i_{1},\dots,j_{\ell},i_{\ell}=h)$, from
some LU agent $i\in L$, such that
$v_{h}(\mathbf{x}_{h}\setminus\\{j_{\ell}\\})>v_{i}(\mathbf{x}_{i})$, i.e., an
alternating path along which the EQ1 condition is violated for the LU agent.
When such a path is encountered, the algorithm transfers $j_{\ell}$ from $h$
to $i_{\ell-1}$. When there is no such path from $i$, the component $C_{i}$ of
the LS agent $i$ is EQ1. Let $C_{L}$ be the union of components of the LU
agents. Suppose the overall allocation is not EQ1, then the algorithm raises
the prices of all goods in the $C_{L}$ until a new MBB edge gets added from an
agent $h\in C_{L}$ to a good $j\notin C_{L}$. The algorithm then proceeds as
before from Line 2.

Algorithm 2 Computing an EQ1+fPO allocation of goods

Input: Positive-valued fair division instance $(N,M,V)$
Output: An integral allocation ${\mathbf{x}}$

1:$(\mathbf{x},\mathbf{p})\leftarrow$ initial welfare maximizing integral
market allocation, where $p_{j}=v_{ij}$ for $j\in\mathbf{x}_{i}$.

2:$L\leftarrow\\{i\in N:i\in\mathsf{argmin}_{h\in N}v_{h}(\mathbf{x}_{h})\\}$
$\triangleright$ set of LU

3:if $\exists i\in L$, $\exists$ alt. path
$(i,j_{1},i_{1},\dots,j_{\ell},i_{\ell})$, s.t.
$v_{i_{\ell}}(\mathbf{x}_{i_{\ell}}\setminus\\{j_{\ell}\\})>v_{i}(\mathbf{x}_{i})$
then

4: Transfer $j_{\ell}$ from $i_{\ell}$ to $i_{\ell-1}$

5: Repeat from Line 2

6:if $\mathbf{x}$ is EQ1 then return $\mathbf{x}$

7:else

8: $\beta=\min_{h\in C_{L}\cap N,j\in M\setminus
C_{L}}\frac{\alpha_{h}}{v_{hj}/p_{j}}$ $\triangleright$ Factor by which prices
of goods in $C_{L}$ are raised until a new MBB edge appears from an agent in
$C_{L}$ to a good outside $C_{L}$

9: for $j\in C_{L}\cap M$ do

10: $p_{j}\leftarrow\beta p_{j}$

11: Repeat from Line 2

By arguments similar to Lemma 2, we can show that the allocation (together
with associated prices) is always on MBB, and hence is fPO. Further the
algorithm only terminates if the allocation is EQ1 (Line 7). Similar to Lemma
5, we can show the following:

######  Lemma 8.

Let $t_{0}$ be a time-step where agent $i$ ceases to be an LU agent, and let
$t_{\ell}$ be the first subsequent time step just after which $i$ becomes the
LU agent again. Then:

$v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})>v_{i}(\mathbf{x}_{i}^{t_{0}}).$

###### Proof.

From Lemma 3, $i$ must have received some good $j$ at time step $t_{0}$. Since
$j\in mbb_{i}$ at $t_{0}$, $v_{ij}>0$. Suppose $i$ does not lose any good in
any subsequent iterations, then
$\mathbf{x}^{t_{\ell}+1}_{i}\supseteq\mathbf{x}^{t_{0}}_{i}\cup\\{j\\}$, and
hence $v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})>v_{i}(\mathbf{x}_{i}^{t_{0}})$. On
the other hand suppose $i$ does lose some goods. Let
$t_{k}\in(t_{0},t_{\ell}]$ be a subsequent time step where $i$ loses a good
$j^{\prime}$ for the last time. Since $i$ does not lose any good after
$t_{k}$, we have:

$v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})\geq
v_{i}(\mathbf{x}^{t_{k}}_{i}\setminus\\{j^{\prime}\\}).$ (6)

If $i_{k}$ is a LU at $t_{k}$, then for $i$ to lose $j^{\prime}$ it must be
that:

$v_{i}(\mathbf{x}^{t_{k}}_{i}\setminus\\{j^{\prime}\\})>v_{i_{t_{k}}}(\mathbf{x}^{t_{k}}_{i_{k}}).$
(7)

Finally since the utility of LU agent does not decrease:

$v_{i_{t_{k}}}(\mathbf{x}^{t_{k}}_{i_{k}})\geq
v_{i}({\mathbf{x}^{t_{0}}_{i}}).$ (8)

Putting (6), (7) and (8) together, we get:

$v_{i}(\mathbf{x}_{i}^{t_{\ell}+1})>v_{i}(\mathbf{x}_{i}^{t_{0}})$

as required. ∎

Using the above, as argued in Lemma 6, we can show:

######  Lemma 9.

Algorithm 2 terminates in time $\mathsf{poly}(n,m,U)$.

###### Proof.

Consider any agent $i$. From Lemma 8, it is clear that every time an agent $i$
becomes a LU agent again her utility has strictly increased compared to her
utility the last time she was a LU agent. The number of utility values that
$i$ can have is $U_{i}$, and hence we conclude that the number of times she
stops being an LU agent and becomes LU agent again is at most $U_{i}$. Since
there are $n$ agents, and each agent $i$ can become the LU agent again at most
$U_{i}$ times, we have that after $\mathsf{poly}(n,\max_{i\in N}U_{i})$
changes in the set of LU agents, there will be no changes further in the set
of LU agents. Further we know from an analysis similar to Lemma 4, that the
number of transfers with the same set of LU agents is at most
$\mathsf{poly}(n,m)$. This shows that Algorithm 1 terminates in time
$\mathsf{poly}(n,m,U)$. ∎

We conclude:

######  Theorem 5.

Let $I=(N,M,V)$ be a positive-valued fair division instance. Then an
allocation that is both EQ1 and fPO can be computed in time
$\mathsf{poly}(n,m,U)$.

As argued before, we have $U\leq mv_{max}+1$. This gives:

######  Theorem 6.

Given a fair division instance $I=(N,M,V)$, an allocation that is EQ1 and fPO
can be computed in time $\mathsf{poly}(n,m,v_{max})$, where
$v_{max}=\max_{i,j}v_{ij}$. In particular, when
$v_{max}\leq\mathsf{poly}(n,m)$, an EQ1+fPO allocation can be computed in
$\mathsf{poly}(n,m)$ time.

Finally using Lemma 7, Theorem 5 becomes:

######  Theorem 7.

Given a $k$-ary fair division instance $I=(N,M,V)$ where $k$ is a constant, an
allocation that is EQ1 and fPO can be computed in time $\mathsf{poly}(n,m)$.

######  Remark 8.

We remark that our techniques can be used to show that EQ1+fPO allocations of
chores can be computed in pseudo-polynomial time, and in polynomial-time for
$k$-ary instances with constant $k$.

##  5 Finding EF1+PO Allocations for Constant $n$

Our algorithm relies on the fact that there exists an integral allocation that
is EF1+fPO, even when the values are rational numbers and not integers, since
valuations are scale-free.

We call an instance non-degenerate if there are no multiplicative
relationships between the $v_{ij}$’s. For such an instance, the MBB graph of
market equilibrium is acyclic [26, 12]. In particular, this means that in any
fractional allocation respecting the MBB graph, at most $n-1$ goods are shared
between agents, and remaining goods are allocated integrally. Since each
shared good is shared between at most $n$ agents, there are at most
$(n-1)^{n}=O(1)$ many integral allocations, obtained by rounding all possible
fractional allocations that respect a given MBB graph. Note that an MBB graph
is uniquely defined by the prices of the goods.

Thus, for a non-degenerate instance, our algorithm first enumerates all
possible price vectors that correspond to market equilibria. It is possible to
enumerate all possible equilibrium price vectors via cell-enumeration in time
$\mathsf{poly}(m)$ when $n$ is constant; see e.g., [11, 18]. Then, for each
such price vector, since we know the MBB graph is acyclic, we can enumerate
all possible integral equilibria corresponding to it. Finally, we check if the
allocation is EF1 in $\mathsf{poly}(m)$ time. Since we know that there exists
some EF1+fPO allocation, and since we enumerate all possible price vectors
corresponding to fPO allocations, and then compute all possible integral
allocations at those prices, our algorithm is guaranteed to find one such
allocation.

We now show how to adapt our algorithm for all instances, not just non-
degenerate ones. Given a fair division instance $I=(N,M,V)$, we construct a
non-degenerate instance $I^{\prime}=(N,M,V^{\prime})$, where $V^{\prime}$ is
defined as follows:

$v^{\prime}_{ij}=\begin{cases}v_{ij}+\delta_{ij}\text{, if }v_{ij}>0\\\
0\text{, if }v_{ij}=0\end{cases}\enspace,$

where for all $i,j$, $\delta_{ij}$ is a small rational perturbation that
ensures that the instance $I^{\prime}$ is non-degenerate. For instance, [26]
set $\delta_{ij}=\epsilon^{in}+\epsilon^{j}$, where $\epsilon$ is arbitrarily
close to 0. Let $\delta=\max_{i,j}\delta_{ij}$. We can ensure that
$\delta<\frac{1}{2mv_{max}}$.

We now run our algorithm on the non-degenerate instance $I^{\prime}$ and we
are guaranteed to find a market equilibrium $(\mathbf{x},\mathbf{p})$ that is
EF1 and fPO. Since the prices can be scaled, we can ensure for all $j\in M$,
$1\leq p_{j}\leq p_{max}$, where $p_{max}=\frac{1}{2mv_{max}\delta}$. We can
then show using the following two lemmas that the allocation $\mathbf{x}$
which is EF1+fPO for $I^{\prime}$, is EF1+PO for $I$.

######  Lemma 10.

If $\mathbf{x}$ is EF1 for $I^{\prime}$, then $\mathbf{x}$ is EF1 for $I$.

###### Proof.

Consider any agent $i\in N$ and two sets $S,T\subseteq M$ such that
$v_{i}(S)>v_{i}(T)$. Then we have:

$\displaystyle v^{\prime}_{i}(S)-v^{\prime}_{i}(T)$ $\displaystyle=\sum_{j\in
S}v^{\prime}_{ij}-\sum_{j\in T}v^{\prime}_{ij}$ $\displaystyle=\sum_{j\in
S}v_{ij}-\sum_{j\in T}v_{ij}+\sum_{j\in S}\delta_{ij}-\sum_{j\in
T}\delta_{ij}$ $\displaystyle\geq v_{i}(S)-v_{i}(T)-m\delta$ $\displaystyle>0$

where first we used additivity of valuations, and then the fact that $|T|\leq
m$ and $\delta_{ij}\leq\delta$. For the final transition, we noted that since
the valuations are integral, $v_{i}(S)-v_{i}(T)\geq 1$, and by our choice of
$\delta$, $m\delta<1$.

Now suppose that $\mathbf{x}$ is EF1 for the instance $I^{\prime}$ and not EF1
for the instance $I$. Then there are two agents $i,h$ s.t. for all
$j\in\mathbf{x}_{h}$:
$v_{i}(\mathbf{x}_{h}\setminus\\{j\\})>v_{i}(\mathbf{x}_{i})$. Then it must be
the case that
$v^{\prime}_{i}(\mathbf{x}_{h}\setminus\\{j\\})>v^{\prime}_{i}(\mathbf{x}_{i})$,
for every $j\in\mathbf{x}_{h}$, which contradicts our assumption that
$\mathbf{x}$ is EF1 for $I^{\prime}$. ∎

######  Lemma 11.

If $\mathbf{x}$ is fPO for $I^{\prime}$, then $\mathbf{x}$ is PO for $I$.

###### Proof.

Since $\mathbf{x}$ is fPO for $I^{\prime}$, by the Second Welfare Theorem,
there exist a set of prices $\mathbf{p}$ s.t. $(\mathbf{x},\mathbf{p})$ is a
market equilibrium for an associated Fisher market instance. In particular,
$(\mathbf{x},\mathbf{p})$ is on MBB. For an agent $i$, let
$\alpha^{\prime}_{i}=\max_{j\in M}v^{\prime}_{ij}/p_{j}$, and let
$\alpha_{i}=\max_{j\in M}v_{ij}/p_{j}$.

For any agent $i$ and good $j$, by the definition of $v^{\prime}_{ij}$ and
noting that $\delta_{ij}\leq\delta$, together with the fact that for any non-
zero $v_{ij}$, $v_{ij}\geq 1$, we have:

$v_{ij}\leq v^{\prime}_{ij}\leq v_{ij}(1+\delta)$

This means that $\alpha^{\prime}_{i}\geq\alpha_{i}$ for every $i\in N$.
Further, since $(\mathbf{x},\mathbf{p})$ is on MBB for $I^{\prime}$, for any
$i\in N$:

$\mathbf{p}(\mathbf{x}_{i})=\frac{v^{\prime}_{i}(\mathbf{x}_{i})}{\alpha^{\prime}_{i}}\leq\frac{(1+\delta)v_{i}(\mathbf{x}_{i})}{\alpha_{i}}$

which gives:

$\sum_{i\in N}\frac{v_{i}(\mathbf{x}_{i})}{\alpha_{i}}\geq\sum_{i\in
N}\frac{\mathbf{p}(\mathbf{x}_{i})}{1+\delta}\geq\frac{\mathbf{p}(M)}{1+\delta}$
(9)

Now suppose $\mathbf{x}$ is not PO for the instance $I$. Then there is some
allocation $\mathbf{y}$ that Pareto-dominates $\mathbf{x}$, i.e., for every
$i\in N$, $v_{i}(\mathbf{y}_{i})\geq v_{i}(\mathbf{x}_{i})$, and for some
$h\in N$, $v_{h}(\mathbf{y}_{h})\geq v_{h}(\mathbf{x}_{h})+1$, since the
valuations $v_{ij}$ are integral. Further since $\alpha_{i}$ is the maximum
bang-per-buck ratio for an agent $i$ at prices $\mathbf{p}$, we have for every
$i\neq h$:
$\mathbf{p}(\mathbf{y}_{i})\geq\frac{v_{i}(\mathbf{y}_{i})}{\alpha_{i}}\geq\frac{v_{i}(\mathbf{x}_{i})}{\alpha_{i}}$
and
$\mathbf{p}(\mathbf{y}_{h})\geq\frac{v_{h}(\mathbf{y}_{h})}{\alpha_{h}}\geq\frac{v_{h}(\mathbf{x}_{h})+1}{\alpha_{h}}$.
This gives:

$\displaystyle\sum_{i\in N}\frac{v_{i}(\mathbf{x}_{i})}{\alpha_{i}}$
$\displaystyle=\sum_{i\in
N\setminus\\{h\\}}\frac{v_{i}(\mathbf{x}_{i})}{\alpha_{i}}+\frac{v_{h}(\mathbf{x}_{h})}{\alpha_{h}}$
(10) $\displaystyle\leq\sum_{i\in
N\setminus\\{h\\}}\mathbf{p}(\mathbf{x}_{i})+\mathbf{p}(\mathbf{x}_{h})-\frac{1}{\alpha_{h}}$
$\displaystyle=\mathbf{p}(M)-1/\alpha_{h}$

Putting (9) and (10) together, we get:

$\mathbf{p}(M)-1/\alpha_{h}\geq\frac{\mathbf{p}(M)}{1+\delta}$

which simplifies to:

$\delta\alpha_{h}\mathbf{p}(M)\geq 1+\delta$

Notice however that $\alpha_{h}\leq v_{max}$, and $\mathbf{p}(M)\leq
mp_{max}$, and hence:

$\delta\alpha_{h}\mathbf{p}(M)\leq\delta v_{max}mp_{max}=\delta
v_{max}m\frac{1}{2mv_{max}\delta}<1$

which leads to a contradiction. Hence $\mathbf{x}$ must be PO. ∎

Thus we have shown:

######  Theorem 9.

Given a fair division instance $I=(N,M,V)$, where $n$ is constant, an EF1+PO
allocation can be computed in $\mathsf{poly}(m)$ time.

Finally, we note that the techniques in Lemma 10 also extend easily to EQ1.
Since we showed that an EQ1+fPO allocation is guaranteed to exist for positive
instances:

######  Theorem 10.

Given a positive fair division instance $I=(N,M,V)$, where $n$ is constant, an
EQ1+PO allocation can be computed in $\mathsf{poly}(m)$ time.

##  6 $k$-ary Instances with Constant $n$ and $k$

We now consider $k$-ary fair division instances $(N,M,V)$ where both $k$ and
$n$, the number of agents is constant.

Let $\mathcal{X}$ be the set of all allocations for the instance $I$. For each
agent $i\in N$, let
$T_{i}=\\{v_{i}(\mathbf{x}_{i}):\mathbf{x}\in\mathcal{X}\\}$, the set of
different utility values $i$ can get from any allocation. Let $U=\max_{i\in
N}|T_{i}|$. From Lemma 7, we know $U$ is at most $\mathsf{poly}(m)$. Define
$T=T_{1}\times\cdots\times T_{n}$. We note that
$|T|\leq(\mathsf{poly}(m))^{n}=\mathsf{poly}(m)$, since $n$ is constant, and
can be computed in $\mathsf{poly}(m)$-time.

To solve certain fair division problems for such instances, we enumerate over
each entry $(u_{1},\dots,u_{n})$ of $T$, and check if there is a feasible
allocation $\mathbf{x}$ in which each agent $i$ gets utility exactly $u_{i}$.
The next lemma shows that the latter can be done efficiently.

######  Lemma 12.

Given a vector $(u_{1},\dots,u_{n})\in T$, it can be checked in
$\mathsf{poly}(m)$-time whether there is a feasible allocation $\mathbf{x}$
s.t. for all agents $i$, $v_{i}(\mathbf{x}_{i})=u_{i}$.

###### Proof.

For each agent $i\in N$, let $S_{i}=\\{v_{ij}:j\in M\\}$ be the set of values
$i$ has for the goods. For each good $j\in M$, define $\mathsf{label}(j)$ to
be the position of the vector $(v_{1j},\dots,v_{nj})$ when the elements of
$S_{1}\times\cdots\times S_{n}$ are ordered lexicographically. Let $L$ be the
set of labels. Clearly $|L|\leq|S_{1}|\cdots|S_{n}|=O(1)$ since each
$|S_{i}|\leq k$, and $k$ and $n$ are constants. Essentially, this means that
there are $|L|=O(1)$ different types of goods. For a label $1\leq\ell\leq|L|$,
and for any agent $i$, let $v_{i\ell}$ equal $v_{ij}$ for any good $j$ with
$\mathsf{label}(j)=\ell$. Further let $m_{\ell}$ be the number of goods with
label $\ell$. All goods can be labeled in $\mathsf{poly}(m)$ time.

Let $\mathcal{X}$ be the set of all allocations for the instance $I$. For each
agent $i\in N$, let
$T_{i}=\\{v_{i}(\mathbf{x}_{i}):\mathbf{x}\in\mathcal{X}\\}$, the set of
different utility values $i$ can get from any allocation. Let $U=\max_{i\in
N}|T_{i}|$. From Lemma 7, we know $U$ is at most $\mathsf{poly}(m)$. Define
$T=T_{1}\times\cdots\times T_{n}$. We note that
$|T|\leq(\mathsf{poly}(m))^{n}=\mathsf{poly}(m)$, since $n$ is constant.

To solve certain fair division problems for such instances, we simply
enumerate over each entry $(u_{1},\dots,u_{n})$ of the set $T$, and check if
there is a feasible allocation $\mathbf{x}$ in which each agent $i$ gets
utility exactly $u_{i}$.

For the latter, we define integer variables $m_{i\ell}$ for each $i\in N$ and
$1\leq\ell\leq|L|$, which represents the number of goods with label $\ell$
assigned to agent $i$. Now consider the following linear system:

$\displaystyle\forall i\in N:$
$\displaystyle\quad\sum_{\ell=1}^{|L|}m_{i\ell}v_{i\ell}=u_{i}$
$\displaystyle\forall\ell\in[|L|]:$ $\displaystyle\quad\sum_{i\in
N}m_{i\ell}=m_{\ell}$ $\displaystyle\forall i\in N,\,\forall\ell\in[|L|]:$
$\displaystyle\quad 0\leq m_{i\ell}\leq m_{\ell}$

This system has $n|L|$ variables, and each variable $m_{i\ell}$ can take at
most $m+1$ values. Therefore this system has constant dimension and each
variable is in a bounded range. Thus, by simple enumeration we can check in
$\mathsf{poly}(m)$ time whether this system has a solution or not. If it does,
then there exists an allocation $\mathbf{x}$ which gives every agent $i$ a
utility of $u_{i}$.

Therefore, given a vector $(u_{1},\dots,u_{n})\in T$, checking if there is a
feasible allocation $\mathbf{x}$ in which each agent $i$ gets utility exactly
$u_{i}$ can be done in $\mathsf{poly}(m)$-time. ∎

By iterating through $T$ we can in $\mathsf{poly}(m)$-time prepare a list of
feasible utility vectors (and corresponding allocations) that satisfy our
fairness and efficiency criteria.

######  Theorem 11.

For $k$-ary instance $I=(N,M,V)$ where both $k$ and the number of agents $n$
are constants, we can compute in $\mathsf{poly}(m)$ time (i) an MNW
allocation, (ii) a leximin optimal allocation, (iii) a $\mathcal{F}$+fPO
allocation (when it exists) where $\mathcal{F}$ is any polynomial-time
checkable property.

##  7 PLS and Finding an EF1+PO Allocation

In this section we show that the problem of computing an EF1 and PO allocation
for a fair division instance $(N,M,V)$ reduces to a problem in the complexity
class PLS.

We closely follow the algorithm $\mathcal{A}$ of [2] that finds an EF1+PO
allocation in time $\mathsf{poly}(n,m,v_{max})$, where
$v_{max}=\max_{i,j}v_{ij}$, and show that it has the structure of a local
search problem. We first define some terms relevant to $\mathcal{A}$. For a
small perturbation $\epsilon>0$, a market outcome $(\mathbf{x},\mathbf{p})$ is
said to be $\epsilon$-price envy-free up to one good ($\epsilon$-pEF1) if for
all agents $i,h$ there is a good $j\in\mathbf{x}_{h}$ such that
$(1+\epsilon)\mathbf{p}(\mathbf{x}_{i})\geq\mathbf{p}(\mathbf{x}_{h}\setminus\\{j\\})$.

We can show like in Lemma 1, that if $(\mathbf{x},\mathbf{p})$ is
$\epsilon$-pEF1, then $\mathbf{x}$ is $\epsilon$-EF1. Further, for
sufficiently small $\epsilon$, if $\mathbf{x}$ is $\epsilon$-EF1, then
$\mathbf{x}$ is also EF1 by using that $v_{ij}$’s are integers. The algorithm
$\mathcal{A}$ first perturbs all valuations to powers of $1+\epsilon$, and
then proceeds similarly to Algorithm 1, except that it transfers goods along
alternating paths when the $\epsilon$-pEF1 condition is violated. Further,
prices are always maintained as powers of $1+\epsilon$, bounded by $p_{max}$
and a single agent is chosen as the LS, with ties broken lexicographically.
The algorithm and its analysis is further described in Appendix A.

By the above arguments, computing an EF1+PO allocation is equivalent to
computing an $\epsilon$-pEF1+fPO market outcome $(\mathbf{x},\mathbf{p})$ for
the corresponding $\epsilon$-perturbed instance, for small enough $\epsilon$.
We now reduce the EF1+PO problem to a PLS problem. First we describe its
solution space, cost function, and the neighborhood structure.

Solution space. For an allocation $\mathbf{x}$ and a vector of prices
$\mathbf{p}=(p_{1},\dots,p_{m})$, call a configuration
$(\mathbf{x},\mathbf{p})$ valid if (i) $\mathbf{x}$ is integral (ii)
$(\mathbf{x},\mathbf{p})$ is on MBB (iii) all prices $p_{j}$ are of the form
$(1+\epsilon)^{q_{j}}$, where $q_{j}\in\mathbb{Z}$ is between 0 and
$\log_{1+\epsilon}p_{max}$. Let the solution space be given by
$S=\\{(\mathbf{x},\mathbf{p})|(\mathbf{x},\mathbf{p})\text{ is valid}\\}$.
Since allocations are integral and prices are bounded integral powers of
$(1+\epsilon)$, $S$ is bounded.

Cost function. Let $\delta(\mathbf{x},\mathbf{p})=1$ if a valid allocation
$(\mathbf{x},\mathbf{p})$ is $\epsilon$-pEF1, else 0. The cost function is a
lexicographic function given by
$\mathsf{cost}(\mathbf{x},\mathbf{p})=(\delta(\mathbf{x},\mathbf{p}),\min_{i\in
N}\mathbf{p}(\mathbf{x}_{i}))$ if $(\mathbf{x},\mathbf{p})\in S$, and equal to
$(-1,-1)$ if $(\mathbf{x},\mathbf{p})\notin S$.

Neighborhood structure (Algorithm D). The structure is described by a
polynomial time algorithm $D$. Each configuration $(\mathbf{x},\mathbf{p})$
has a single neighbor. If $(\mathbf{x},\mathbf{p})\notin S$, then its neighbor
$D(\mathbf{x},\mathbf{p})$ is $(\mathbf{x}_{0},\mathbf{p}_{0})$. If
$(\mathbf{x},\mathbf{p})\in S$, then
$D(\mathbf{x},\mathbf{p})=(\mathbf{x}^{\prime},\mathbf{p}^{\prime})$, which is
the allocation obtained by running $\mathcal{A}$ starting with the allocation
$(\mathbf{x},\mathbf{p})$ until the spending of the least spender strictly
increases. We argue in Appendix A that:

######  Lemma 13.

Algorithm $D$ terminates in polynomial time.

Membership in PLS. We need to show the existence of three polynomial time
algorithms:

  * A

: which outputs a solution $(\mathbf{x}_{0},\mathbf{p}_{0})$

  * B

: which on input $(\mathbf{x},\mathbf{p})$ computes the
$\mathsf{cost}(\mathbf{x},\mathbf{p})$

  * C

: which on input $(\mathbf{x},\mathbf{p})$ computes a neighbor which has a
strictly larger cost.

Algorithms A and B are trivial and in polynomial time. Observe that each
solution $(\mathbf{x},\mathbf{p})$ has only one neighbor
$(\mathbf{x}^{\prime},\mathbf{p}^{\prime})$, and that it has a strictly larger
cost since spending of the least spender at
$(\mathbf{x}^{\prime},\mathbf{p}^{\prime})$ is strictly more than the spending
of the least spender at $(\mathbf{x},\mathbf{p})$, or the latter is EF1. Thus
algorithm $D$ itself is algorithm $C$. Finally note that any local maxima of
$(S,\mathsf{cost},D)$ is an integral market allocation
$(\mathbf{x},\mathbf{p})$ where $\delta(\mathbf{x},\mathbf{p})=1$, i.e., it is
$\epsilon$-pEF1, and thus EF1, even for the original valuations. Similarly, as
is argued for the analysis of $\mathcal{A}$, the allocation is also PO for the
original valuations. Therefore, computing an EF1+PO allocation for integral,
additive valuations polynomial-time reduces to a PLS problem. However since it
is not in TFNP $\supseteq$ PLS, this does not show membership in PLS.

##  8 Discussion

In this paper, we showed that an EF1+fPO allocation can be computed in pseudo-
polynomial time, thus improving upon the result of Barman et al. [2]. Our work
also implies polynomial time algorithms for two special cases: (i) computing
EF1+fPO allocation for $k$-ary instances where $k$ is a constant, (ii)
computing EF1+PO allocation when $n$ (number of agents) is constant. Settling
the complexity of the problem for general $k$ and $n$ remains a challenging
open problem. Our results extend to the fairness notions of EQ1 and weighted-
EF1 as well. We showed that computing an EF1+PO allocation reduces to a
problem in the complexity class PLS. Showing the membership of the problem of
computing an EF1+fPO allocation in PLS is another open question. Finally,
showing the existence of EF1+PO allocations for general additive instances of
chores is another interesting research direction.

## References

  * [1] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris.  Maximum Nash welfare and other stories about EFX.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI), pages 24–30, 2020.
  * [2] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018.
  * [3] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Greedy algorithms for maximizing Nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 7–13, 2018.
  * [4] Bernhard Bliem, Robert Bredereck, and Rolf Niedermeier.  Complexity of efficient and envy-free resource allocation: Few agents, resources, or utility levels.  In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), page 102–108, 2016.
  * [5] S.J. Brams and A.D. Taylor.  Fair Division: From Cake-Cutting to Dispute Resolution.  Cambridge University Press, 1996.
  * [6] Robert Bredereck, Andrzej Kaczmarczyk, Dušan Knop, and Rolf Niedermeier.  High-multiplicity fair allocation: Lenstra empowered by n-fold integer programming.  In Proceedings of the 2019 ACM Conference on Economics and Computation, page 505–523, 2019.
  * [7] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061 – 1103, 2011.
  * [8] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum Nash welfare.  In Proceedings of the 17th ACM Conference on Economics and Computation (EC), page 305–322, 2016.
  * [9] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick.  Weighted envy-freeness in indivisible item allocation.  In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 231–239, 2020.
  * [10] Bart de Keijzer, Sylvain Bouveret, Tomas Klos, and Yingqian Zhang.  On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences.  In Francesca Rossi and Alexis Tsoukias, editors, Algorithmic Decision Theory, pages 98–110, 2009.
  * [11] N. R. Devanur and R. Kannan.  Market equilibria in polynomial time for fixed number of goods or agents.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 45–53, 2008.
  * [12] Ran Duan, Jugal Garg, and Kurt Mehlhorn.  An improved combinatorial polynomial algorithm for the linear arrow-debreu market.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 90–106, 2016.
  * [13] Soroush Ebadian, Dominik Peters, and Nisarg Shah.  How to fairly allocate easy and difficult chores.  In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2022.
  * [14] D.K. Foley.  Resource allocation and the public sector.  Yale Economic Essays, 7(1):45–98, 1967.
  * [15] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia.  Equitable allocations of indivisible goods.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 280–286, 2019.
  * [16] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia.  Equitable allocations of indivisible chores.  In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’20, page 384–392, 2020.
  * [17] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Satiation in Fisher markets and approximation of Nash social welfare.  CoRR, abs/1707.04428, 2017.
  * [18] Jugal Garg and Peter McGlaughlin.  Computing competitive equilibria with mixed manna.  In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 420–428, 2020.
  * [19] Jugal Garg and Aniket Murhekar.  Computing fair and efficient allocations with few utility values.  In In Proc. 14th Symp. Algorithmic Game Theory (SAGT), 2021.
  * [20] Jugal Garg and Aniket Murhekar.  On fair and efficient allocations of indivisible goods.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021.
  * [21] Jugal Garg, Aniket Murhekar, and John Qin.  Fair and efficient allocations of chores under bivalued preferences.  In Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2022.
  * [22] Euiwoong Lee.  APX-hardness of maximizing Nash social welfare with indivisible items.  Information Processing Letters, 122, 07 2015.
  * [23] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004.
  * [24] A. Mas-Colell, M.D. Whinston, and J.R. Green.  Microeconomic Theory.  Oxford University Press, 1995.
  * [25] H. Moulin.  Fair Division and Collective Welfare.  Mit Press. MIT Press, 2004.
  * [26] James B. Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC), page 291–300, 2010.
  * [27] Abraham Othman, Tuomas Sandholm, and Eric Budish.  Finding approximate competitive equilibria: Efficient and fair course allocation.  In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), page 873–880, 2010.
  * [28] Benjamin Plaut and Tim Roughgarden.  Almost envy-freeness with general valuations.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 2584–2603, 2018.
  * [29] H. Steinhaus.  Sur la division pragmatique.  Econometrica, 17(1):315–319, 1949.
  * [30] Hal R Varian.  Equity, envy, and efficiency.  Journal of Economic Theory, 9(1):63 – 91, 1974.

##  Appendix A Appendix to Section 7

_Description of Algorithm $\mathcal{A}$ of Barman et al. [2] and run-time
analysis._

We describe $\mathcal{A}$ at a high level. The algorithm always maintains an
integral equilibrium and follows these steps:

  1. 1.

Let $\epsilon=\frac{1}{12m^{3}v_{max}^{4}}$. Round the values $v_{ij}$ as

$v^{\prime}_{ij}=\begin{cases}(1+\epsilon)^{\lfloor\log_{1+\epsilon}v_{ij}\rfloor},\text{
if }v_{ij}>0\\\ 0\text{ otherwise. }\end{cases}$

  2. 2.

Compute an initial integral market equilibrium
$(\mathbf{x}_{0},\mathbf{p}_{0})$, where the price of good $j$ is the value
$v^{\prime}_{ij}$ if $\mathbf{x}_{ij}=1$

  3. 3.

Consider alternating paths $P=(i,\dots,h^{\prime},j,h)$ from the LS $i$,
starting from shortest to longest. If for some path
$\mathbf{p}(\mathbf{x}_{h}\setminus\\{j\\})>(1+\epsilon)\mathbf{p}(\mathbf{x}_{i})$
then transfer $j$ from $h$ to $h^{\prime}$.

  4. 4.

Compute the least spender again and repeat step 3.

  5. 5.

If $(\mathbf{x},\mathbf{p})$ is $\epsilon$-pEF1, return
$(\mathbf{x},\mathbf{p})$

  6. 6.

If not, and $i$ does not $\epsilon$-EF1-envy any agent in $C_{i}$, then raise
prices of goods in $C_{i}$ by powers of $(1+\epsilon)$ until:

     * (a)

A new MBB edge gets added from an agent in $C_{i}$ to a good outside $C_{i}$.

     * (b)

$i$ does not price-EF1-envy any other agent.

     * (c)

An agent not in $C_{i}$ becomes the new least spender.

  7. 7.

If event $(b)$ occurs first then return $(\mathbf{x},\mathbf{p})$, else repeat
from step 2.

The following are arguments made in the run-time analysis of $\mathcal{A}$,
which we will use to show PLS-membership of this problem.

  1. 1.

The spending of the least spender does not decrease.

  2. 2.

Except possibly in the last step, the price of every good is an integral power
of $(1+\epsilon$). Further the price of every good always lies between $1$ and
$p_{max}=\mathsf{poly}(m,v_{max})$.

  3. 3.

An agent can be a least spender for $\mathsf{poly}(m,n)$ steps until the least
spender changes or a price rise step occurs.

  4. 4.

In the absence of price rise steps, if $i$ ceases to be a least spender, then
when $i$ becomes least spender again she would have strictly gained a new good
or her spending would have increased by a factor of $1+\epsilon$.

###### Proof of Lemma 13.

Let $i$ be the least spender at $(\mathbf{x},\mathbf{p})$. Suppose a price-
rise step does not take place in subsequent iterations. Then observe that
after at most $\mathsf{poly}(n,m)$ iterations, the least spender gets a good.
Either the spending of the least spender has increased, or the least spender
has changed but has the same spending. In the former case $D$ halts. In the
latter case, notice that after $n+1$ identity changes of the least spender
(without a price rise step) and without a spending increase, some agent
$i^{\prime}$ must have become the least spender twice. Between these two
events, either she gains a good (thus increasing the spending), or her
spending increases by a factor of $(1+\epsilon)$.

Now suppose a price-rise step takes place. Then either $i$ is still the least
spender or a new agent $i^{\prime}$ outside $C_{i}$ is the new least spender
with a larger spending. In either case $D$ halts. Suppose $i^{\prime}$ has the
same spending as $i$ before the price-rise. Then either the spending of the
least spender will strictly increase in polynomially many steps as argued
before, or only price-rise steps keep happening with the same spending of the
least spender. But observe that in each such step, the number of least
spenders strictly decreases. Thus, in at most $n$ such consecutive price rise
steps the spending of the least spender will increase.

The above arguments show that the spending of the least spender strictly
increases after polynomially many steps, implying that $D$ is a polynomial
time algorithm. ∎