#  Algorithmic Fair Allocation of Indivisible Items: A Survey and New
Questions

Haris Aziz1 Bo Li2 Hervé Moulin3&Xiaowei Wu4
1UNSW Sydney and Data61 CSIRO, Sydney, Australia
2Department of Computing, The Hong Kong Polytechnic University, Hong Kong,
China
3University of Glasgow, Glasgow, UK and Higher School of Economics, St.
Petersburg, Russia
4IOTSC, University of Macau, Macau, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The theory of algorithmic fair allocation is within the center of multi-agent
systems and economics in the last decade due to its industrial and social
importance. At a high level, the problem is to assign a set of items that are
either goods or chores to a set of agents so that every agent is happy with
what she obtains. Particularly, in this survey, we focus on indivisible items,
for which absolute fairness such as envy-freeness and proportionality cannot
be guaranteed. One main theme in the recent research agenda is about designing
algorithms that approximately achieve the fairness criteria. We aim at
presenting a comprehensive survey of recent progresses through the prism of
algorithms, highlighting the ways to relax fairness notions and common
techniques to design algorithms, as well as the most interesting questions for
future research.

##  1 Introduction

While fair allocation is an age-old problem and the widely known Divide-and-
Choose algorithm can trace back to the Bible, modern research on fair
allocation is regarded to be initiated by Steinhaus at a meeting of the
Econometric Society in Washington D.C. in 1947 Steinhaus (1948). Since then, a
large body of works in economics and mathematics have been directed towards
understanding the theory of allocating resources among agents in a fair manner
Moulin (2003). The recent focus on indivisible items is motivated, in part, by
the applications that inherently entail allocation of items that cannot be
fractionally allocated, such as assigning computational resources in a cloud
computing environment and courses to teachers in a school. In the last decade,
computer science offered a fresh and practical angle to the research agenda –
algorithmic fair allocation. Besides designing algorithms, computer science
has brought many more ideas, such as computational and communication
complexity, and informational assumptions, which do not align with the main
theme of the current survey. Interested readers can refer to the surveys by
Walsh (2020) and Aziz (2020a) for detailed discussion. Fair allocation
algorithms have been implemented in the real world; for instance, Course Match
is employed for course allocation at the Wharton School in the University of
Pennsylvania, and the websites Spliddit (spliddit.org) and Fair Outcomes
(fairoutcomes.com) provide online access to fair allocation algorithms.

Although this survey mainly focuses on indivisible items, the study of fair
allocation was classically centered around allocating a divisible resource,
which is also known as the cake-cutting problem Brams and Taylor (1996);
Robertson and Webb (1998). Fairness is mostly captured by envy-freeness and
proportionality in the literature. An envy-free allocation (which is also
proportional) of a divisible cake always exists and can be found in bounded
steps Aziz and Mackenzie (2016). Moreover, a competitive equilibrium from
equal incomes guarantees envy-freeness and Pareto optimality simultaneously
Varian (1973). A recent line of research extends the study to chores, such as
the computation of envy-free allocations Dehghani et al. (2018) and
competitive equilibria Boodaghians et al. (2021); Chaudhury et al. (2021a).
Unlike divisible items, when items are indivisible, absolutely fair
allocations rarely exist. For example, when allocating a single item to two
agents, every allocation is not envy-free or proportional. Accordingly, an
extensively studied subject is to investigate the extent to which these
fairness notions or their relaxations can be approximately satisfied.

There are several surveys highlighting different perspectives of fair
allocation theory. Moulin (2018) reviewed the theory through the prism of
economics. Aleksandrov and Walsh (2020) and Suksompong (2021) respectively
focused on the online and constrained settings. Lang and Rothe (2016), Walsh
(2020) and Aziz (2020a) reviewed the problem in the perspective of broad
computer science. Instead, the angle of the current survey is algorithmic and
the focus is particularly on the introduction of common techniques to design
(approximation) algorithms. Moreover, we will discuss more sophisticated
settings that were introduced in the last couple of years which uncovered new
challenges and open problems in the field of fair allocation.

#### Roadmap

In the remaining of the survey, we define the model of fair allocation in
Section 2 and introduce the widely adopted solution concepts in Sections 3 and
4. In Section 5, we review the commonly used techniques to design fair
allocation algorithms. In Section 6, we introduce the more sophisticated
settings that are proposed recently. Finally, we discuss two more properties,
efficiency and truthfulness that are desired to be satisfied together with
fairness, in Section 7.

##  2 Model

In a fair allocation instance, we allocate a set of $m$ indivisible items
$M=\\{1,\ldots,m\\}$ to a group of $n$ agents $N=\\{1,\ldots,n\\}$. An
allocation is represented by an $n$-partition
$\mathbf{X}=(X_{1},\ldots,X_{n})$ of $M$, where $X_{i}\subseteq M$ is the
bundle allocated to agent $i$. It is required that each item is allocated to
exactly one agent, i.e., $X_{i}\cap X_{j}=\emptyset$ for all $i\neq j$ and
$\cup_{i\in N}X_{i}=M$. If $\cup_{i\in N}X_{i}\neq M$, $\mathbf{X}$ is a
partial allocation. We sometimes consider fractional allocations, denoted by
$\mathbf{x}=(x_{ie})_{i\in N,e\in M}$, where $0\leq x_{ie}\leq 1$ denotes the
fraction of item $e$ allocated to agent $i$, and $\sum_{i\in N}x_{ie}=1$ for
all $e\in M$. Each agent $i$ has a valuation function
$v_{i}:2^{M}\rightarrow\mathbb{R}$ that assigns a value to each bundle of
items. When $v_{i}(S)\geq 0$ for all $i\in N$ and $S\subseteq M$, the items
are _goods_ ; when $v_{i}(S)\leq 0$ for all $i$ and $S$, the items are
_chores_. For ease of exposition, we mainly discuss the case when the
valuations are additive and leave the discussion on more general valuations to
Section 6. That is, for any $i\in N$ and $S\subseteq M$, we have
$v_{i}(S)=\sum_{e\in S}v_{i}(\\{e\\})$. When there is no confusion, we use
$v_{i}(e)$ to denote $v_{i}(\\{e\\})$. Further, for any $S\subseteq M$ and
$e\in M$, we use $S+e$ and $S-e$ to denote $S\cup\\{e\\}$ and
$S\setminus\\{e\\}$, respectively. Let $\mathcal{I}=(N,M,\mathbf{v})$ be a
fair allocation instance where $\mathbf{v}=(v_{1},\ldots,v_{n})$. When all
agents agree on the same ordering of all items in values (e.g.,
$v_{i}(1)\geq\cdots\geq v_{i}(m)$ for all $i$), the instance is called
identical ordering (IDO).

Before the extensive study of fairness, efficiency was at the centre of the
theory of resource allocation. The _utilitarian welfare_ of an allocation
$\mathbf{X}$ is $\sum_{i\in N}v_{i}(X_{i})$, by maximizing which the total
happiness of the agents is maximized. The _egalitarian welfare_ is $\min_{i\in
N}\\{v_{i}(X_{i})\\}$, by maximizing which the smallest happiness is
maximized. A compromise between utilitarian and egalitarian welfare is _Nash
welfare_ , i.e., $\Pi_{i\in N}v_{i}(X_{i})$. We say an allocation $\mathbf{X}$
_Pareto dominates_ another allocation $\mathbf{X}^{\prime}$ if
$v_{i}(X_{i})\geq v_{i}(X^{\prime}_{i})$ for all $i\in N$ and
$v_{i}(X_{i})>v_{i}(X^{\prime}_{i})$ for some $i$. An allocation is _Pareto
optimal_ (PO) if it is not Pareto dominated by any other allocation.

Naturally, the fairness of an allocation can be evaluated by its egalitarian
welfare, such Santa Claus problem Bansal and Sviridenko (2006) and load
balancing problem Lenstra et al. (1990). However, in practice, since agents
may have heterogeneous valuations, the max-min objective is not enough to
satisfy all of them. Thus, various notions were proposed to characterize the
fairness of allocations, including envy-freeness (EF) Foley (1966),
proportionality (PROP) Steinhaus (1948) and equitability (EQ) Dubins and
Spanier (1961). The relationships among these notions are discussed by
Amanatidis et al. (2018),Sun et al. (2021) and Chakraborty et al. (2021). Due
to space limit, this survey only focuses on two of the most widely studied,
namely EF and PROP.

##  3 Envy-freeness

We first consider envy-freeness, whose study dates back to Foley (1966) and
Tinbergen (1930), and its relaxations.

######  Definition 3.1 (EF)

For the allocation of items (goods or chores), an allocation $\mathbf{X}$ is
envy-free (EF) if for any two agents $i,j\in N$, we have $v_{i}(X_{i})\geq
v_{i}(X_{j})$.

The problem of checking whether a given instance admits an EF allocation is
NP-complete even for $\\{0,1\\}$\- or $\\{0,-1\\}$-valued instances Aziz et
al. (2015); Bhaskar et al. (2021). Moreover, the example of allocating a
single item between two agents defies any bounded multiplicative approximation
of EF, and thus researchers turn their attention to additive approximations.
Two of the most popular ones are envy-free up to one item (EF1) and envy-free
up to any item (EFX).

#### EF1

The notion of EF1 was first studied for the allocation of goods by Lipton et
al. (2004), which allows an agent to envy another agent but requires that the
envy can be eliminated by removing an item from the envied agent’s bundle.
This notion naturally extends to chores by removing an item from the envious
agent’s bundle. For both goods and chores, EF1 allocations always exist and
can be efficiently computed by the Round Robin algorithm; see Section 5.

######  Definition 3.2 ($\alpha$-EF1)

For any $\alpha\geq 0$, an allocation $\mathbf{X}$ is $\alpha$-approximate
envy-free up to one item ($\alpha$-EF1) if for any $i,j\in N$, there exists
$e\in X_{i}\cup X_{j}$ such that $v_{i}(X_{i}-e)\geq\alpha\cdot
v_{i}(X_{j}-e)$. When $\alpha=1$, the allocation is EF1.

#### EFX

Same as EF1, the EFX relaxation was proposed for the allocation of goods, by
Caragiannis et al. (2019b). Informally speaking, the notion of EFX strengthens
the fairness by requiring that the envy between two agents can be eliminated
by removing _any_ item owned by these two agents.

######  Definition 3.3 ($\alpha$-EFX)

For any $\alpha\geq 0$, an allocation $\mathbf{X}$ for goods (resp. chores) is
$\alpha$-approximate envy-free up to any item ($\alpha$-EFX) if for any
$i,j\in N$ and any $e\in X_{j}$ (resp. $e\in X_{i}$),
$v_{i}(X_{i})\geq\alpha\cdot v_{i}(X_{j}-e)$ (resp.
$v_{i}(X_{i}-e)\geq\alpha\cdot v_{i}(X_{j})$). When $\alpha=1$, the allocation
is EFX.

Unlike the case of EF1 allocations, the existence of EFX allocations remains
unknown. For the case of goods, it was shown by Plaut and Roughgarden (2020)
that EFX allocations exist in some special cases: (1) identical
(combinatorial) valuations, (2) IDO additive valuations, and (3) $n=2$.
Chaudhury et al. (2020) and Amanatidis et al. (2021a) further extended the
existence of EFX allocations to the cases when (4) $n=3$, and (5) bi-valued
valuations. While the existence of EFX allocations remains unknown for the
general cases, there are fruitful results regarding EFX partial allocations
(where unallocated items are assumed to be donated to a _charity_) and
approximation of EFX allocations. Since allocating nothing to the agents is
trivially EFX, researchers are interested in finding EFX partial allocations
with high efficiency. Caragiannis et al. (2019a) showed that there exists an
EFX partial allocation achieving half of the maximum Nash welfare. Chaudhury
et al. (2021d) proposed a pseudo-polynomial time algorithm that computes an
EFX partial allocation with at most $n-1$ unallocated items under which no
agent envies the charity. This result was improved by Berger et al. (2021),
who showed that there is an EFX allocation with at most a single unallocated
item for $n=4$, and $n-2$ unallocated items for $n\geq 5$. There are also
results that aim at computing approximately EFX allocations. Plaut and
Roughgarden (2020) showed that every instance (even with subadditive
valuations) admits a $0.5$-EFX allocation. The approximation ratio was
improved to $0.618$ under additive valuations by a polynomial time algorithm
proposed by Amanatidis et al. (2020). Chaudhury et al. (2021b) proposed a
polynomial time algorithm that computes a $(1-\epsilon)$-EFX allocation with
$o(n)$ unallocated items and high Nash welfare. In contrast to the case of
goods, the chores counterpart is much less well studied. EFX allocations are
known to exist only for a few special cases, e.g., IDO instances Li et al.
(2022) and leveled preference instances Gafni et al. (2021). For general
instances, only $O(n^{2})$ approximation of EFX is known to exist Zhou and Wu
(2021). The existence of EFX allocations remains unknown even for $n=3$ agents
or bi-valued instance.

##  4 Proportionality and Maximin Share

Proportionality (PROP) was proposed by Steinhaus (1948), which is the most
widely studied threshold-based solution concept. PROP is weaker than EF under
additive valuations.

######  Definition 4.1 (PROP)

An allocation $\mathbf{X}$ is proportional (PROP) if for every agent $i\in N$,
we have $v_{i}(X_{i})\geq\mathsf{PROP}_{i}$, where
$\mathsf{PROP}_{i}=(1/n)\cdot v_{i}(M)$.

For divisible goods and normalized valuations, the items can be allocated such
that every agent has value at least $1/n$, which is not true for indivisible
items. Hill (1987) studied the worst case guarantee that an agent can have as
a function of $n$ and $\max_{i\in N,e\in M}\\{v_{i}(e)\\}$. With two agents,
the chores version is equivalent to the goods one; but with three or more
agents, the equivalence is far from clear, and may not hold. One drawback of
this guarantee is that the value of the function decreases quickly and goes to
0 as $\max_{i,e}\\{v_{i}(e)\\}$ becomes large.

#### Maximin Share Fairness

Besides the worst case guarantee studied by Hill (1987), one popular
relaxation of PROP is the maximin share fairness, motivated by the following
imaginary experiment. If agent $i$ is the mediator and divides all items into
$n$ bundles, the best way to approximate PROP for $i$ is to maximize the
smallest bundle according to her own valuation. Formally, define the maximin
share (MMS) of $i$ as

$\mathsf{MMS}_{i}(M,n)=\max_{\mathbf{X}\in\Pi_{n}(M)}\min_{j}\\{v_{i}(X_{j})\\},$

where $\Pi_{n}(M)$ denotes the set of all $n$-partitions of $M$. When $M$ and
$n$ are clear from the context, we write $\mathsf{MMS}_{i}$ for short. Note
that $\mathsf{MMS}_{i}\leq\mathsf{PROP}_{i}$, and the computation of
$\mathsf{MMS}_{i}$ is NP-complete.

######  Definition 4.2 ($\alpha$-MMS)

For any $\alpha\geq 0$, an allocation $\mathbf{X}$ is $\alpha$-approximate
maximin share fair ($\alpha$-MMS) if for any $i\in N$,
$v_{i}(X_{i})\geq\alpha\cdot\mathsf{MMS}_{i}$. When $\alpha=1$, the allocation
is MMS.

Note that the approximation ratio $\alpha\leq 1$ for goods and $\alpha\geq 1$
for chores. The definition of MMS fairness was first introduced by Budish
(2011), based on the concept of Moulin (1990). Unfortunately, it is shown that
there exist instances for which no allocation can ensure $\mathsf{MMS}_{i}$
value for every agent for the case of goods Kurokawa et al. (2018) and chores
Aziz et al. (2017b). The best known approximation results are
$(3/4+1/(12n))$-MMS for goods Garg and Taki (2021) and $11/9$-MMS for chores
Huang and Lu (2021). The best known negative results are that $\alpha\leq
39/40$ for goods and for $\alpha\geq 44/43$ for chores Feige et al. (2021).

#### More Solution Concepts

Motivated by the definition of MMS, Caragiannis et al. (2019b) proposed
pairwise MMS (PMMS) and Barman et al. (2018a) proposed groupwise MMS (GMMS).
Informally, PMMS is similar to MMS, but instead requires that the allocation
is MMS for the instance induced by any two agents. GMMS generalizes both MMS
and PMMS and requires that the allocation is MMS for the instance induced by
any subset of agents. We refer the readers to, e.g., Caragiannis et al.
(2019b); Barman et al. (2018a); Amanatidis et al. (2020), for more detailed
discussions.

Finally, similar to EF1 and EFX, we can relax PROP to PROP1 and PROPX. It is
known that a PROP1 allocation always exists and can be found in polynomial
time when the items are goods Conitzer et al. (2017); Barman and Krishnamurthy
(2019), chores Brânzei and Sandomirskiy (2019) or mixture of goods and chores
Aziz et al. (2020b). Regarding PROPX, when items are goods, PROPX allocations
may not exist Moulin (2018); Aziz et al. (2020b). However, when items are
chores, PROPX allocations exist and can be found efficiently Moulin (2018); Li
et al. (2022).

##  5 Algorithms and Common Techniques

In this section, we introduce the techniques to design fair allocation
algorithms. Unfortunately, due to space limit, we were not able to include all
of them. Instead, we choose some of the most commonly used and powerful ones
that are also the basis of more complicated algorithms.

#### Divide-and-Choose

Divide-and-Choose is one of the most classic allocation algorithms. The
algorithm is very useful and intuitive when there are only two agents. The
idea is to let the first agent partition the items into two bundles and the
other agent choose her preferred bundle. The remaining bundle is allocated to
the first agent, and thus her best strategy is to maximize the value of the
smaller bundle, i.e.,

$(X_{1},X_{2})\in\arg\max\limits_{(S_{1},S_{2})\in\Pi_{2}(M)}\min\\{v_{1}(S_{1}),v_{1}(S_{2})\\}.$

Plaut and Roughgarden (2020) proved that $(X_{1},X_{2})$ is always MMS and EFX
to the first agent if we break tie by maximizing the size of the smaller
bundle in $(X_{1},X_{2})$, i.e., leximin++ allocation. Actually, this result
holds for any number of agents which implies the existence of EFX allocations
for the case of identical valuations. Since the second agent obtains her
preferred bundle in $(X_{1},X_{2})$, the allocation is EF to her. Therefore,
with two agents, Divide-and-Choose algorithm returns an allocation that is MMS
and EFX.

#### Adjusted-Winner

Adjusted-Winner is another widely used algorithm for the two-agent case Brams
and Taylor (1996). The idea is to sort the items according to the ratios
between the utilities that they yield for the two agents, i.e.,

$\frac{v_{1}(1)}{v_{2}(1)}\geq\frac{v_{1}(2)}{v_{2}(2)}\geq\cdots\geq\frac{v_{1}(m)}{v_{2}(m)},$

and let agent 1 choose a minimal set of consecutive items for which she is EF1
starting from left (the remainings are given to agent 2). The advantage is
that it ensures high social welfare between two agents Bei et al. (2021c).
This allocation is EF1 but not necessarily MMS or EFX.

#### Sequential Allocation and Round-Robin

A general class of algorithms that is also suitable for a distributed
implementation is that of sequential-picking allocation Brams and Taylor
(2000), which was formally studied in a general and systematic way by Bouveret
and Lang (2011). Under these methods, agents have a sequence of turns to pick
their most preferred item that is still available. A popular sequence protocol
is the Round-Robin, where the picking sequence repeats the pattern
$1,\ldots,n$. The Round-Robin algorithm produces allocations that are EF1 (but
not necessarily EFX) for both goods and chores111When items are only goods or
only chores, there is a larger class of protocols ensuring EF1. This class of
protocols uses a recursively balanced sequence in which at any point, the
difference between the number of turns of any of two agents is at most 1., but
not for mixture of them. For this, Aziz et al. (2020b) proposed the double
Round-Robin method that computes EF1 allocations for mixture of goods and
chores. Amanatidis et al. (2016) and Aziz et al. (2020a) designed more
involved picking sequences to approximate MMS fairness, for goods and chores
respectively.

#### Envy-cycle Elimination

The Envy-cycle Elimination algorithm is inherently a greedy algorithm that in
each round a new item is assigned to the agent who is in a disadvantage for
goods or advantage for chores Lipton et al. (2004). The main technique of the
algorithm is to ensure the existence of an agent that is not envied (for
goods) or not envious (for chores) by trading items among agents. We use goods
as an illustration. The algorithm is based on an envy graph, where the nodes
correspond to agents and there is an edge from agent $i$ to agent $j$ if $i$
is envious of $j$’s bundle. The algorithm works by assigning, at each step, an
unassigned item to an agent who is not envied by any other agents, i.e., a
node with in-degree $0$ in the envy graph. If no such agent exists, the graph
must contain a directed cycle. Then the cycle can be resolved by exchanging
the bundles of items along the cycle, i.e., an agent in the cycle gets the
bundle of the agent she points to. The algorithm terminates when all items are
allocated and outputs an EF1 allocation for arbitrary monotone combinatorial
valuation functions Lipton et al. (2004).

The algorithm and its adaptations are very widely studied, combining with
which stronger fairness notions can also be satisfied. For example, the
algorithm itself ensures EFX Plaut and Roughgarden (2020) and $2/3$-MMS Barman
and Krishnamurthy (2020) for IDO instances. With more involved preprocessing
procedures, it can ensure 0.618-EFX, 0.553-GMMS, 0.667-PMMS and EF1
simultaneously Amanatidis et al. (2020). For chores, it is shown in Barman and
Krishnamurthy (2020) that the returned allocation is $4/3$-MMS. However, noted
by Bhaskar et al. (2021), this allocation may not be EF1 if the cycle is
resolved arbitrarily. Instead, they used the top-trading technique (in which
each agent only points to the agent she envies the most) to preserve EF1.
Later, Li et al. (2022) further showed that with this technique, the returned
allocation is PROPX. We can also observe the shadow of the algorithm in more
complicated techniques, such as the (group) champion graphs and rainbow cycle
number Chaudhury et al. (2020, 2021b) which enable stronger existence and
approximation results of EFX.

#### Bag-filling Algorithms

Bag-filling Algorithms are particularly helpful for the threshold-based
fairness like MMS. The idea is to maintain a bag and keep adding items to it
until some agent thinks the bag is good enough (for goods) or about to be too
bad to all agents (for chores). Then the bag is taken away by some satisfied
agent and the algorithm repeats the procedure with the remaining items. The
difficulty is to select a proper threshold for the bag so that the
approximation for the agent who takes away a bag is good and there remains
sufficiently many (or few) items for the remaining agents. With a more careful
design and analysis, the approximation ratio can be improved to $2/3$ Garg et
al. (2019) and further better than $3/4$ Garg and Taki (2021) for goods, For
chores the approximation ratio can be improved to $11/9$ Huang and Lu (2021).
There are several nice properties regarding MMS fairness Amanatidis et al.
(2017b); Garg et al. (2019), e.g., the scale invariant and the reduction to
IDO instances. Interestingly, the second property shows that any algorithm for
approximating MMS allocations for IDO instances applies to general instances
with the same approximation ratio preserved. Making use of these properties
the design of algorithms can be significantly simplified.

#### Rounding Fractional Solutions

Although competitive equilibria may not exist for indivisible items, we can
first compute a market equilibrium by assuming the items being divisible and
then carefully round the fractional allocation to an integral one Barman and
Krishnamurthy (2019); Brânzei and Sandomirskiy (2019); Garg et al. (2021a).
This approach is especially helpful when efficiency is desired along with
fairness, e.g., for the computation of EF1+PO or PROP1+PO allocations for
goods Barman et al. (2018b); Barman and Krishnamurthy (2019), EF1+PO
allocations for bi-valued chores Garg et al. (2021b); Ebadian et al. (2021),
PROP1+PO Aziz et al. (2020b) and approximately MMS+PO allocations for mixture
of goods and chores Kulkarni et al. (2021).

#### Eating Algorithms

The Probabilistic-Serial (PS) algorithm of Bogomolnaia and Moulin (2001) is a
randomized algorithm for allocating indivisible items in an ex-ante EF manner.
Agents eat their most preferred items at a uniform rate and move on to the
next item when the previous one is consumed. The probability share of an agent
for an item is the fraction of the item eaten by the agent. In recent works
Freeman et al. (2020); Aziz (2020b), researchers have sought allocation
algorithms that simultaneously satisfy ex-ante EF and ex-post EF1 for the
allocation of indivisible items that are goods or chores. In particular, the
PS-lottery method was proposed that provides an explicit lottery over a set of
EF1 allocations. Aziz and Brandl (2020) presented an eating algorithm that is
suitable for any type of feasibility constraint and allocation problem with
ordinal preferences.

##  6 More Sophisticated Settings

The past several years have witnessed the emergence of more sophisticated
settings that brought new challenges to the design of fair allocation
algorithms, including mixture of goods and chores, weighted agents, partial
information and general valuations. In the following, we review their models,
as well as the corresponding results and open problems.

#### Mixture of Goods and Chores

The general case when items are mixture of goods and chores has recently been
studied in Bogomolnaia et al. (2017, 2019); Aziz et al. (2020b, 2022). This
model is particularly interesting because it includes the typical setting when
the valuations are not monotone. Aziz et al. (2022) proved that a double Round
Robin algorithm is able to compute an EF1 allocation for any number of agents,
and a generalized adjusted winner algorithm can find an EF1 and PO allocation
for two agents. A natural open question is whether PO and EF1 allocations
exist for arbitrary number of agents. Recently, Aziz et al. (2020b) and
Kulkarni et al. (2021) designed algorithms that compute PROP1+PO or
approximately MMS+PO allocations, respectively. More generally, it is an
intriguing future research direction to study the fair allocation problem
under arbitrary non-monotonic valuations.

#### Asymmetric Agents

For most of the aforementioned research works, the agents are assumed to be
symmetric in the sense of taking the same share in the system. Motivated by
the real-world scenarios where people at leadership positions take more
responsibilities, some recent works took the asymmetry into consideration and
studied the fair treatment of non-equals. The definitions of envy-freeness and
maximin share fairness have been adapted to the weighted settings by Farhadi
et al. (2019), Aziz et al. (2019a) and Chakraborty et al. (2020). Regarding
goods, it is shown by Farhadi et al. (2019) that the best approximation ratio
for weighted MMS is $\Theta(n)$ and by Chakraborty et al. (2020) that weighted
EF1 allocations exist. Regarding chores, although weighted MMS was studied in
Aziz et al. (2019a), the best approximation ratio and the existence of
weighted EF1 allocations are still unknown. Novel fairness notions, such as
AnyPrice share and $l$-out-of-$d$ maximin share, were proposed and studied in
Babaioff et al. (2021a, b) which highlight different perspectives of the
weighted setting.

#### With Monetary Transfers

Since fairness notion like envy-freeness cannot be satisfied exactly, there
are works studying how to use payments or subsidies to compensate agents and
achieve fairness accordingly Halpern and Shah (2019); Brustle et al. (2020).
The problem has been extensively considered in the economics literature under
the context of rent division problem Edward Su (1999). Halpern and Shah (2019)
aimed at bounding the amount of external subsidies when the marginal value of
each item is at most one for every agent, and Brustle et al. (2020) proved
that at most one unit of subsidies per agent is sufficient to guarantee the
existence of an envy-free allocation Brustle et al. (2020). Caragiannis and
Ioannidis (2021) studied the optimization problem of computing allocations
that are envy-freeable using minimum amount of subsidies, and designed a fully
polynomial time approximation scheme for instances with a constant number of
agents. A more general problem is the fair allocation of mixture of divisible
and indivisible items, where the divisible item can be viewed as heterogeneous
subsidies Bei et al. (2021a, b).

#### Partial Information

Researchers also care about fair allocation with partial information, and
particularly the ordinal preference setting, where the algorithm only knows
each agent’s ranking over all items without the cardinal values. For goods,
the best possible approximation ratio of MMS allocations using only ordinal
preferences is $\Omega(\log n)$ by Amanatidis et al. (2016) and Halpern and
Shah (2021); for chores, constant upper and lower bounds are proved by Aziz et
al. (2020a). Recently, Hosseini et al. (2021a) proposed the ordinal MMS
fairness, which is more robust to cardinal values. Another interesting
question is to investigate the query complexity of unknown valuations. In this
model the algorithms can access the valuations by making queries to an oracle.
Oh et al. (2021) proved that $\Theta(\log m)$ queries suffices to define an
algorithm that returns EF1 allocations. In general, it is an important
research direction to explore how much knowledge is sufficient to design a
fair allocation algorithm.

#### General Valuations

Besides additive valuations, we may have more complex and combinatorial
preferences that involve substitutabilities and complementarities in the
items, including submodular, XOS, and subadditive valuations. Formal
definitions and discussions of these valuations can be found in Nisan (2000).
Some of the results we have discussed in previous sections also apply to
general valuations. For example, the envy-cycle elimination algorithm returns
an EF1 allocation for monotone combinatorial valuations Lipton et al. (2004).
Plaut and Roughgarden (2020) proved the existence of $0.5$-EFX allocations for
subadditive valuations. Regarding MMS, Barman and Krishnamurthy (2020) and
Ghodsi et al. (2018) designed polynomial time algorithms to compute constant-
approximate allocations for submodular and XOS valuations, and $O(\log
n)$-approximate for subadditive valuations. Chaudhury et al. (2021c) further
designed algorithms to compute allocations that are approximately EFX and
simultaneously achieve $O(n)$-approximation to the maximum Nash welfare for
subadditive valuations.

Besides the above settings, there are more in the literature, such as
constrained resources Suksompong (2021), public resources Conitzer et al.
(2017); Fain et al. (2018), group fairness Suksompong (2018); Conitzer et al.
(2019), and dynamic settings Aleksandrov and Walsh (2020). Due to space limit,
we were not able to discuss all of them in details.

##  7 Beyond Fairness: Efficiency and Incentives

Beyond achieving fairness alone, more and more attention is paid to
investigating the extent to which we can design algorithms to compute
allocations that are fair and simultaneously satisfy other properties, such as
efficiency and truthfulness.

###  7.1 Computing Fair and Efficient Allocations

Although finding an allocation that maximizes the utilitarian welfare is
straightforward (by allocating each item to the agent who has highest value),
finding such an allocation within fair allocations is NP-hard Barman et al.
(2019). One interesting research question here is to bound the utilitarian
welfare loss by enforcing the allocations to be fair, i.e., the price of
fairness Bei et al. (2021c); Barman et al. (2020). Besides utilitarian
welfare, a large body of works studied the compatibility between fairness
notions and the weaker efficiency notion of PO. For the case of goods,
Caragiannis et al. (2019b) proved that the allocation that maximizes Nash
welfare is EF1 and PO. Later, Barman et al. (2018b) designed a
pseudopolynomial time algorithm for computing EF1+PO allocations. Truly
polynomial time algorithms for the problem remain unknown. Barman and
Krishnamurthy (2019) designed a polynomial time algorithm for computing
PROP1+PO allocations. Regarding the stronger fairness notion of EFX,
Amanatidis et al. (2021a) proved that for bi-valued valuations, the allocation
that maximizes Nash welfare is EFX+PO, and Garg and Murhekar (2021) improved
this result by giving a polynomial time algorithm. Further, Garg and Murhekar
(2021) proved that if the valuations have three different values, EFX+PO
allocations may not exist. In contrast, Hosseini et al. (2021b) proved that if
the valuations are lexicographic, EFX+PO allocations exist and can be found in
polynomial time.

For chores, most of the problems are still open. The good news is that
PROP1+PO allocations can be computed in polynomial time, even if the items are
mixture of goods and chores Aziz et al. (2020b). However, for EF1 and PROPX,
their compatibility with PO are still unknown. Ebadian et al. (2021) and Garg
et al. (2021b) proved that for bi-valued instances, EF1+PO allocations always
exist and can be found efficiently, which are the only exceptions so far.

###  7.2 Being Fair for Strategic Agents

Fair allocation problems are often faced by strategic agents in real-life
scenarios, where an agent may intentionally misreport her values for the items
to manipulate the outcome of the algorithm and obtain a bundle of higher
value. The goal is to design truthful algorithms in which agents maximize
their utilities by reporting true preferences. For two agents, Amanatidis et
al. (2017a) gave a complete characterization of truthful algorithms, using
which we have the tight approximation bounds for solution concepts such as EF1
and MMS. For an arbitrary number of agents, Amanatidis et al. (2016) and Aziz
et al. (2019b) designed truthful approximation algorithms but the tight bounds
are still unknown. The aforementioned works consider the social environment
where monetary transfers are not allowed. With monetary transfers, polynomial
time truthful mechanisms were designed in Barman et al. (2019) for single-
parameter valuations, which maximize the social welfare and approximately
satisfy fairness notions such as MMS and EF1.

Another game-theoretic research agenda is to investigate the agents’ strategic
behaviours in the algorithms that may not be truthful. For example, Amanatidis
et al. (2021b) proved that in the Round-Robin algorithm, the allocations
induced by pure Nash equilibria are always EF1 (regarding the true values).
Bouveret and Lang (2014) and Aziz et al. (2017a) studied the strategic setting
in general sequential allocation algorithms. It is interesting to study the
agents’ behaviours in other algorithms and with other fairness notions.

## References

  * Aleksandrov and Walsh [2020] Martin Aleksandrov and Toby Walsh.  Online fair division: A survey.  In AAAI, 2020.
  * Amanatidis et al. [2016] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis.  On truthful mechanisms for maximin share allocations.  In IJCAI, pages 31–37, 2016.
  * Amanatidis et al. [2017a] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis.  Truthful allocation mechanisms without payments: Characterization and implications on fairness.  In EC, pages 545–562, 2017.
  * Amanatidis et al. [2017b] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  ACM Trans. Algorithms, 13(4):52:1–52:28, 2017.
  * Amanatidis et al. [2018] Georgios Amanatidis, Georgios Birmpas, and Vangelis Markakis.  Comparing approximate relaxations of envy-freeness.  In IJCAI, pages 42–48, 2018.
  * Amanatidis et al. [2020] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  Theor. Comput. Sci., 841:94–109, 2020.
  * Amanatidis et al. [2021a] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris.  Maximum nash welfare and other stories about EFX.  Theor. Comput. Sci., 863:69–85, 2021.
  * Amanatidis et al. [2021b] Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Allocating indivisible goods to strategic agents: Pure nash equilibria and fairness.  In WINE, volume 13112, pages 149–166, 2021.
  * Aziz and Brandl [2020] Haris Aziz and Florian Brandl.  The vigilant eating rule: A general approach for probabilistic economic design with constraints.  CoRR, abs/2008.08991, 2020.
  * Aziz and Mackenzie [2016] Haris Aziz and Simon Mackenzie.  A discrete and bounded envy-free cake cutting protocol for any number of agents.  In FOCS, pages 416–427, 2016.
  * Aziz et al. [2015] Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh.  Fair assignment of indivisible objects under ordinal preferences.  Artif. Intell., 227:71–92, 2015.
  * Aziz et al. [2017a] Haris Aziz, Sylvain Bouveret, Jérôme Lang, and Simon Mackenzie.  Complexity of manipulating sequential allocation.  In AAAI, pages 328–334, 2017.
  * Aziz et al. [2017b] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In AAAI, pages 335–341, 2017.
  * Aziz et al. [2019a] Haris Aziz, Hau Chan, and Bo Li.  Weighted maxmin fair share allocation of indivisible chores.  In IJCAI, pages 46–52, 2019.
  * Aziz et al. [2019b] Haris Aziz, Bo Li, and Xiaowei Wu.  Strategyproof and approximately maxmin fair share allocation of chores.  In IJCAI, pages 60–66, 2019.
  * Aziz et al. [2020a] Haris Aziz, Bo Li, and Xiaowei Wu.  Approximate and strategyproof maximin share allocation of chores with ordinal preferences.  CoRR, abs/2012.13884, 2020.
  * Aziz et al. [2020b] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy.  A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation.  Oper. Res. Lett., 48(5):573–578, 2020.
  * Aziz et al. [2022] Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh.  Fair allocation of indivisible goods and chores.  Auton. Agents Multi Agent Syst., 36(1):3, 2022.
  * Aziz [2020a] Haris Aziz.  Developments in multi-agent fair allocation.  In AAAI, pages 13563–13568, 2020.
  * Aziz [2020b] Haris Aziz.  Simultaneously achieving ex-ante and ex-post fairness.  In WINE, volume 12495, pages 341–355, 2020.
  * Babaioff et al. [2021a] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Fair-share allocations for agents with arbitrary entitlements.  In EC, page 127, 2021.
  * Babaioff et al. [2021b] Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen.  Competitive equilibrium with indivisible goods and generic budgets.  Math. Oper. Res., 46(1):382–403, 2021.
  * Bansal and Sviridenko [2006] Nikhil Bansal and Maxim Sviridenko.  The santa claus problem.  In STOC, pages 31–40, 2006.
  * Barman and Krishnamurthy [2019] Siddharth Barman and Sanath Kumar Krishnamurthy.  On the proximity of markets with integral equilibria.  In AAAI, pages 1748–1755, 2019.
  * Barman and Krishnamurthy [2020] Siddharth Barman and Sanath Kumar Krishnamurthy.  Approximation algorithms for maximin fair division.  ACM Trans. Economics and Comput., 8(1):5:1–5:28, 2020.
  * Barman et al. [2018a] Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, and Yadati Narahari.  Groupwise maximin fair allocation of indivisible goods.  In AAAI, 2018.
  * Barman et al. [2018b] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In EC, pages 557–574. ACM, 2018.
  * Barman et al. [2019] Siddharth Barman, Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang.  Fair division of indivisible goods among strategic agents.  In AAMAS, 2019.
  * Barman et al. [2020] Siddharth Barman, Umang Bhaskar, and Nisarg Shah.  Optimal bounds on the price of fairness for indivisible goods.  In WINE, pages 356–369, 2020.
  * Bei et al. [2021a] Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu.  Fair division of mixed divisible and indivisible goods.  Artif. Intell., 293:103436, 2021.
  * Bei et al. [2021b] Xiaohui Bei, Shengxin Liu, Xinhang Lu, and Hongao Wang.  Maximin fairness with mixed divisible and indivisible goods.  Auton. Agents Multi Agent Syst., 35(2):34, 2021.
  * Bei et al. [2021c] Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong.  The price of fairness for indivisible goods.  Theory Comput. Syst., 65(7):1069–1093, 2021.
  * Berger et al. [2021] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat.  (almost full) EFX exists for four agents (and beyond).  CoRR, abs/2102.10654, 2021.
  * Bhaskar et al. [2021] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish.  On approximate envy-freeness for indivisible chores and mixed resources.  In APPROX-RANDOM, 2021.
  * Bogomolnaia and Moulin [2001] Anna Bogomolnaia and Hervé Moulin.  A new solution to the random assignment problem.  J. Econ. Theory, 100(2):295–328, 2001.
  * Bogomolnaia et al. [2017] Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaya.  Competitive Division of a Mixed Manna.  Econometrica, 85(6):1847–1871, 2017.
  * Bogomolnaia et al. [2019] Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaya.  Dividing goods and bads under additive utilities.  Soc Choice Welf, 52:395–417, 2019.
  * Boodaghians et al. [2021] Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta.  Polynomial time algorithms to find an approximate competitive equilibrium for chores.  CoRR, abs/2107.06649, 2021.
  * Bouveret and Lang [2011] Sylvain Bouveret and Jérôme Lang.  A general elicitation-free protocol for allocating indivisible goods.  In IJCAI, pages 73–78, 2011.
  * Bouveret and Lang [2014] Sylvain Bouveret and Jérôme Lang.  Manipulating picking sequences.  In ECAI, pages 141–146, 2014.
  * Brams and Taylor [1996] Steven J. Brams and Alan D. Taylor.  Fair division - from cake-cutting to dispute resolution.  1996\.
  * Brams and Taylor [2000] Steven J. Brams and Alan D. Taylor.  The win-win solution - guaranteeing fair shares to everybody.  2000\.
  * Brânzei and Sandomirskiy [2019] Simina Brânzei and Fedor Sandomirskiy.  Algorithms for competitive division of chores.  CoRR, abs/1907.01766, 2019.
  * Brustle et al. [2020] Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, and Adrian Vetta.  One dollar each eliminates envy.  In EC, pages 23–39, 2020.
  * Budish [2011] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * Caragiannis and Ioannidis [2021] Ioannis Caragiannis and Stavros Ioannidis.  Computing envy-freeable allocations with limited subsidies.  In WINE, volume 13112, pages 522–539, 2021.
  * Caragiannis et al. [2019a] Ioannis Caragiannis, Nick Gravin, and Xin Huang.  Envy-freeness up to any item with high nash welfare: The virtue of donating items.  In EC, pages 527–545, 2019.
  * Caragiannis et al. [2019b] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  ACM Trans. Economics and Comput., 7(3):12:1–12:32, 2019.
  * Chakraborty et al. [2020] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick.  Weighted envy-freeness in indivisible item allocation.  In AAMAS, pages 231–239, 2020.
  * Chakraborty et al. [2021] Mithun Chakraborty, Erel Segal-Halevi, and Warut Suksompong.  Weighted fairness notions for indivisible items revisited.  CoRR, abs/2112.04166, 2021.
  * Chaudhury et al. [2020] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  EFX exists for three agents.  In EC, 2020.
  * Chaudhury et al. [2021a] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  Competitive allocation of a mixed manna.  In SODA, pages 1405–1424, 2021.
  * Chaudhury et al. [2021b] Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra.  Improving EFX guarantees through rainbow cycle number.  In EC, 2021.
  * Chaudhury et al. [2021c] Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta.  Fair and efficient allocations under subadditive valuations.  In AAAI, pages 5269–5276, 2021.
  * Chaudhury et al. [2021d] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  SIAM J. Comput., 2021.
  * Conitzer et al. [2017] Vincent Conitzer, Rupert Freeman, and Nisarg Shah.  Fair public decision making.  In EC, 2017.
  * Conitzer et al. [2019] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan.  Group fairness for the allocation of indivisible goods.  In AAAI, pages 1853–1860, 2019.
  * Dehghani et al. [2018] Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, and Hadi Yami.  Envy-free chore division for an arbitrary number of agents.  In SODA, 2018.
  * Dubins and Spanier [1961] Lester E Dubins and Edwin H Spanier.  How to cut a cake fairly.  The American Mathematical Monthly, 68(1P1):1–17, 1961.
  * Ebadian et al. [2021] Soroush Ebadian, Dominik Peters, and Nisarg Shah.  How to fairly allocate easy and difficult chores.  CoRR, abs/2110.11285, 2021.
  * Edward Su [1999] Francis Edward Su.  Rental harmony: Sperner’s lemma in fair division.  The American mathematical monthly, 106(10):930–942, 1999.
  * Fain et al. [2018] Brandon Fain, Kamesh Munagala, and Nisarg Shah.  Fair allocation of indivisible public goods.  In EC, 2018.
  * Farhadi et al. [2019] Alireza Farhadi, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Sébastien Lahaie, David M. Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods to asymmetric agents.  J. Artif. Intell. Res., 64:1–20, 2019.
  * Feige et al. [2021] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  In WINE, pages 355–372, 2021.
  * Foley [1966] Duncan Karl Foley.  Resource allocation and the public sector.  Yale University, 1966.
  * Freeman et al. [2020] Rupert Freeman, Nisarg Shah, and Rohit Vaish.  Best of both worlds: Ex-ante and ex-post fairness in resource allocation.  In EC, pages 21–22, 2020.
  * Gafni et al. [2021] Yotam Gafni, Xin Huang, Ron Lavi, and Inbal Talgam-Cohen.  Unified fair allocation of goods and chores via copies.  CoRR, abs/2109.08671, 2021.
  * Garg and Murhekar [2021] Jugal Garg and Aniket Murhekar.  Computing fair and efficient allocations with few utility values.  In SAGT, volume 12885 of Lecture Notes in Computer Science, pages 345–359. Springer, 2021.
  * Garg and Taki [2021] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  Artif. Intell., 300:103547, 2021.
  * Garg et al. [2019] Jugal Garg, Peter McGlaughlin, and Setareh Taki.  Approximating maximin share allocations.  In SOSA, volume 69, pages 20:1–20:11, 2019.
  * Garg et al. [2021a] Jugal Garg, Martin Hoefer, Peter McGlaughlin, and Marco Schmalhofer.  When dividing mixed manna is easier than dividing goods: Competitive equilibria with a constant number of chores.  In SAGT, volume 12885, pages 329–344, 2021.
  * Garg et al. [2021b] Jugal Garg, Aniket Murhekar, and John Qin.  Fair and efficient allocations of chores under bivalued preferences.  CoRR, abs/2110.09601, 2021.
  * Ghodsi et al. [2018] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In EC, pages 539–556, 2018.
  * Halpern and Shah [2019] Daniel Halpern and Nisarg Shah.  Fair division with subsidy.  In SAGT, pages 374–389, 2019.
  * Halpern and Shah [2021] Daniel Halpern and Nisarg Shah.  Fair and efficient resource allocation with partial information.  In IJCAI, pages 224–230, 2021.
  * Hill [1987] Theodore P Hill.  Partitioning general probability measures.  The Annals of Probability, pages 804–813, 1987.
  * Hosseini et al. [2021a] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia.  Fair and efficient allocations under lexicographic preferences.  In AAAI, pages 5472–5480, 2021.
  * Hosseini et al. [2021b] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia.  Fair and efficient allocations under lexicographic preferences.  In AAAI, pages 5472–5480, 2021.
  * Huang and Lu [2021] Xin Huang and Pinyan Lu.  An algorithmic framework for approximating maximin share allocation of chores.  In EC, pages 630–631, 2021.
  * Kulkarni et al. [2021] Rucha Kulkarni, Ruta Mehta, and Setareh Taki.  Indivisible mixed manna: On the computability of MMS+PO allocations.  In EC, pages 683–684, 2021.
  * Kurokawa et al. [2018] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  J. ACM, 65(2):8:1–8:27, 2018.
  * Lang and Rothe [2016] Jérôme Lang and Jörg Rothe.  Fair division of indivisible goods.  In Economics and Computation, pages 493–550. 2016.
  * Lenstra et al. [1990] Jan Karel Lenstra, David B. Shmoys, and Éva Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  Math. Program., 46:259–271, 1990.
  * Li et al. [2022] Bo Li, Yingkai Li, and Xiaowei Wu.  Almost proportional allocations for indivisible chores.  TheWebConf, 2022.
  * Lipton et al. [2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In EC, pages 125–131, 2004.
  * Moulin [1990] Hervé Moulin.  Uniform externalities: Two axioms for fair allocation.  J. Public Econ., 43(3):305–326, 1990.
  * Moulin [2003] Hervé Moulin.  Fair division and collective welfare.  MIT Press, 2003.
  * Moulin [2018] Hervé Moulin.  Fair division in the age of internet.  Annu. Rev. Econ., 2018.
  * Nisan [2000] Noam Nisan.  Bidding and allocation in combinatorial auctions.  In EC, pages 1–12, 2000.
  * Oh et al. [2021] Hoon Oh, Ariel D. Procaccia, and Warut Suksompong.  Fairly allocating many goods with few queries.  SIAM J. Discret. Math., 35(2):788–813, 2021.
  * Plaut and Roughgarden [2020] Benjamin Plaut and Tim Roughgarden.  Almost envy-freeness with general valuations.  SIAM J. Discret. Math., 34(2):1039–1068, 2020.
  * Robertson and Webb [1998] Jack M. Robertson and William A. Webb.  Cake-cutting algorithms - be fair if you can.  1998\.
  * Steinhaus [1948] Hugo Steinhaus.  The problem of fair division.  Econometrica, 16:101–104, 1948.
  * Suksompong [2018] Warut Suksompong.  Approximate maximin shares for groups of agents.  Math. Soc. Sci., 92:40–47, 2018.
  * Suksompong [2021] Warut Suksompong.  Constraints in fair division.  ACM SIGecom Exchanges, 19(2):46–61, 2021.
  * Sun et al. [2021] Ankang Sun, Bo Chen, and Xuan Vinh Doan.  Connections between fairness criteria and efficiency for allocating indivisible chores.  In AAMAS, pages 1281–1289, 2021.
  * Tinbergen [1930] Jan Tinbergen.  Mathematiese psychologie.  Mens en Maatschappij, 6(4):342–352, 1930.
  * Varian [1973] Hal R Varian.  Equity, envy, and efficiency.  1973\.
  * Walsh [2020] Toby Walsh.  Fair division: The computer scientist’s perspective.  In IJCAI, pages 4966–4972, 2020.
  * Zhou and Wu [2021] Shengwei Zhou and Xiaowei Wu.  Approximately EFX allocations for indivisible chores.  CoRR, abs/2109.07313, 2021.