# Fair Allocation of goods and chores – Tutorial and Survey of Recent Results

Shaily Mishra, Manisha Padala, Sujit Gujar
Machine Learning Lab
International Institute of Information Technology (IIIT), Hyderabad
{shaily.mishra<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
(July 2023)

###### Abstract

Fair resource allocation is an important problem in many real-world scenarios,
where resources such as goods and chores must be allocated among agents. In
this survey, we delve into the intricacies of fair allocation, focusing
specifically on the challenges associated with indivisible resources. We
define fairness and efficiency within this context and thoroughly survey
existential results, algorithms, and approximations that satisfy various
fairness criteria, including envyfreeness, proportionality, MMS, and their
relaxations. Additionally, we discuss algorithms that achieve fairness and
efficiency, such as Pareto Optimality and Utilitarian Welfare. We also study
the computational complexity of these algorithms, the likelihood of finding
fair allocations, and the price of fairness for each fairness notion. We also
cover mixed instances of indivisible and divisible items and investigate
different valuation and allocation settings. By summarizing the state-of-the-
art research, this survey provides valuable insights into fair resource
allocation of indivisible goods and chores, highlighting computational
complexities, fairness guarantees, and trade-offs between fairness and
efficiency. It serves as a foundation for future advancements in this vital
field.

_K_ eywords Resource Allocation $\cdot$ Fairness $\cdot$ Survey

##  1 Introduction

Fair division of resources is a well-studied problem in the division of
inheritance, divorce settlement, treaty negotiations, and resolving disputes.
Polish mathematicians Steinhaus, Banach, and Knaster [95] are credited with
being the first to study this problem formally. Since then, the topic has
piqued interest both in social sciences and game theory, garnering various
academic books written on this topic like [42], [84], [96]. Most of the
existing literature focuses on resources that can be divided, such as land or
money. In these cases, the concept of fair distribution is often explored
through the lens of cake cutting, with the classic “divide and choose”
algorithm as the cornerstone. Many intriguing notions of fairness and
corresponding algorithms have been proposed within this framework. However,
when resources are indivisible, it introduces even more captivating challenges
to the field.

In the real world, numerous examples of fair division have emerged to address
allocation challenges across various domains. Notable instances include Course
Match (coursematch.io), Spliddit (spliddit.org), and Fair Outcomes
(fairoutcomes.com) offer practical applications of fair allocation algorithms
for diverse scenarios. These algorithms cater to allocation dilemmas such as
course allocation, equitable rent distribution among roommates, sharing taxi
fares, and assigning goods among a group of individuals. Moreover, allocating
chores is equally important, especially for gig economies. For example, food
delivery platforms worry about distributing delivery orders among the
available drivers, and other platforms like Uber worry about distributing
rides. The gig economies have the responsibility of maintaining and ensuring
the customers are happy by reducing delivery/travel times while making sure
the employees are not over or underworked. Hence both efficiency and fairness
matter. More importantly, with the advent of the internet, large tech
companies have pushed towards distributed computing. Allocating multiple
resources to multiple available tasks to distribute the task load and
facilitate maximum utilisation of available resources. Due to the rapid
advancement in technology, such as Artificial Intelligence (AI) and the
Internet of Things (IoT), many autonomous agents encounter the challenge of
task or resource allocation. Fairness in resource allocation is essential for
AI’s sustainable and responsible growth and for minimizing biases and
discrimination.

Given the limited availability of resources, addressing fairness and
efficiency concerns during the allocation process is crucial. While fairness
ensures that each individual receives their fair share based on relevant
criteria, efficiency aims to optimize the allocation to maximize the benefit
of the limited resources. Therefore, achieving fairness and efficiency is of
utmost importance when allocating limited resources among diverse groups of
individuals. In this setting, we explore several questions. Firstly, we define
what constitutes a fair allocation and whether such allocations exist. If they
do, how can we compute them? Alternatively, if fair allocations do not exist,
can we relax our fairness criteria? Once we have achieved a fair allocation,
can we obtain an allocation that maximizes efficiency among the set of fair
allocations? How can we achieve both fairness and efficiency in our
allocations? This survey addresses fundamental questions concerning attaining
fair and efficient allocations.

Extensive research has been undertaken in the realm of fair and efficient
allocation of goods and chores. In this survey, we aim to provide a
comprehensive tutorial-like approach, delving into intricate details
concerning allocating goods, chores, and their combined scenarios, along with
various valuations and discussing the latest findings and algorithms about
these allocation domains.

Numerous surveys have delved into this subject, offering valuable insights.
For instance, [4] examines the recent advancements in dividing indivisible
goods, presenting results and algorithms, [17] provides a short survey on the
algorithmic aspects of fairness notions of indivisible items, exploring open
questions in the field. These surveys serve as illuminating resources for
understanding the current state and future directions of fair allocation, [10]
provides a survey of fair division in multi-agents, [3] focuses on fair
division in online settings. For other results, there are several surveys
shedding light on fair allocations [85, 99, 39]. However, our survey is recent
with a broader scope. Most surveys focus solely on goods or chores; we have
diligently combined both aspects, providing a comprehensive analysis. In
addition, we review results for a combination of goods and chores and delve
into situations where there is a mixture of divisible and indivisible
resources. In summary, our survey focuses on facilitating comprehension and
comparison of the surveyed results; we present a comprehensive summary in
Table 1. This table is valuable for researchers and practitioners, providing a
concise overview of the surveyed findings, algorithms, and critical insights.
Additionally, the survey also aims to provide a tutorial on fair division –
explaining the various fairness and efficiency notions with examples. It lets
readers quickly understand the state-of-the-art advancements in fair and
efficient allocation without any prior knowledge in the domain. In addition to
focusing on indivisible goods and chores, we briefly survey the fair division
literature concerning divisible and indivisible items. By exploring both
domains, we aim to provide a more holistic understanding of fair allocation
mechanisms across a broader range of resource types. Again, we summarize the
key findings and approaches in Table 2, offering a convenient reference for
readers interested in the fair division of divisible and indivisible items.
Overall, our survey goes beyond a mere compilation of existing research. It
provides a tutorial-like exposition, offering detailed insights, algorithmic
approaches, and open questions regarding fair and efficient allocation. The
summarized tables enhance the accessibility of the surveyed information,
facilitating further research and advancements in this vital domain.

Organization of this survey In Section 2, first, we explain the need for fair
division through a few examples. In Section 3, we explain important
definitions related to fairness and efficiency. Building upon this foundation,
we then delve into the topic of fair and efficient allocation in the context
of indivisible goods in Section 4. Subsequently, we explore the intricacies of
fair and efficient allocation in the domain of indivisible chores in Section
5. To further enhance our understanding, we investigate the combined setting
of indivisible goods and chores in Section 6. This section explores the
challenges and considerations when allocating resources that encompass goods
and chores. In Section 7, we focus on the mixed setting of indivisible and
divisible items. Here, we examine the implications and approaches of fair
allocation when resources include both items. Continuing our exploration,
Section 8 analyzes various results related to the likelihood of fair
allocation, the price of fairness, and different fairness settings. This
section highlights the probability of achieving fair allocations, the price of
fairness, and the different perspectives on defining fairness. Finally, we
conclude our survey in Section LABEL:sec:sum, summarizing the key insights and
open questions that emerged from examining fair and efficient resource
allocation in the context of indivisible goods and chores.

##  2 Motivation and the Problem

We will illustrate the problem of fair allocation, starting with a simple
example.

######  Example 2.1.

Two intelligent friends, Agastya and Noorie, won a contest and received an
uncut veggie pizza as a reward. These friends need to divide this pizza
fairly.

Suppose both of them like veggie pizza equally; hence the fairest way to
divide it is to cut it equally. Let’s say that the pizza has various toppings,
such as pineapple, mushroom, olives, and corn. If both like all the toppings,
they can cut the pizza equally for each topping. However, what if they have
their preferences? Imagine Agastya dislikes pineapple toppings, and Noorie is
allergic to mushrooms. Can they cut the pizza according to their preferences?

Noorie suggests splitting the pizza in two, and Agastya could choose first
what he likes while she takes the remaining piece. Would this be fair? Let’s
analyze this approach. Noorie cuts the pizza so that both the partitions are
equal to her. As a result, she is happy with any piece she gets. Agastya picks
the pizza part he likes the most. This division is famously known as the Cut-
and-Choose algorithm, ‘I cut, you choose’.

The above pizza was uncut, and the agents were free to cut the pizza in any
way they liked. These types of items are called divisible items.

######  Example 2.2.

Let us, however, consider a modification where Agastya and Noorie receive
eight pieces of pizza and cannot cut the pieces any further. Either they take
the whole piece, or they don’t. They both like every piece equally. This
setting is called as indivisible items. Each person can take four pieces, so
the allocations are fair. Consider, however, if they only received seven
pieces. Is it possible to distribute the pieces fairly among them in such a
case?

Before we can answer this, let’s look at the following situation.

######  Example 2.3.

Agastya and Noorie need to clean their house. This includes tasks such as
cleaning the living room, clearing the kitchen mess, dusting the furniture,
etc. Having fewer chores is what everyone wants. What is the best way to
divide the tasks such that everyone gets their fair share?

Comparing Example 2.1 to Example 2.3, in the first one, everyone would like to
obtain a bigger share, while in the second, everyone is more interested in
obtaining a smaller share. It is commonly known (in the literature) that items
(resources/tasks) with such positive value are called goods, and those with
negative value are called chores. The approach to solving fair division for
goods and chores is quite different, even though it may seem like just a
matter of negation. We will examine this in more detail later.

Suppose there are multiple friends – agents in the system. How should we
generalize this notion of fairness? The idea that agents should be happy with
their allocations (allocated bundles) is envy-freeness [60]. Envy-freeness
means agents/players value their bundle more than others, i.e., no agent
envies others. We can always divide divisible items without envy. Allocating
indivisible items without inciting envy is, however, a challenging task. For
example, if there is only one good, and Noorie receives it, Agastya will envy
her. It is widely known that EF is not guaranteed to exist for indivisible
items.

With the negative results concerning the existence of envy-freeness for
indivisible items, the question naturally arises, can we ensure envy-freeness
approximately, i.e., to relax the fairness notion? For Example 2.2, giving
three of the seven pieces to one person and the remaining four to another is
arguably the fairest way to allocate them. Assuming Agastya receives three
pieces and Noorie receives four, he envies Noorie by at most one piece. Budish
introduced such a relaxation of envy-freeness, called Envy-freeness up to 1
item (EF1) [45]. We will formally define all the fairness notions in detail
later on, but in essence, EF1 implies that if envy exists in the system, an
agent can only envy the other agent by at most one item.

Finding a fair allocation in a simple example involving two friends was
challenging. Here, we present a highly complex example to illustrate the
problem’s difficulty. Imagine that the Government wishes to invest in
improving national security, economy, agriculture, and healthcare. It picks
four re-owned scientists in these individuals’ domains and asks them to set up
a Research Lab for the nation’s improvement. It provides them with a wide
variety of resources such as professors, laboratory assistants, engineers,
vehicles, books, subscriptions, journals, drones, microscopes, biometrics
systems, computer servers, land, water facility, electricity facility,
supercomputers, etc. This intricate scenario involves distributing many
divisible and indivisible goods and responsibilities to the four scientists
forming Research Centers. The Government wants to ensure that all four centers
feel equal so that each one gives its best to develop this project. In
addition, it wants to ensure that the resources are allocated to the Lab,
which will put them to best use; for example, microscopes will benefit the
pathology department in the Healthcare Center rather than the Economic Center.
There are divisible items such as Land, Electric facilities, Water facilities,
etc., and indivisible items such as Computer Systems, Servers, Books, etc. An
item may be beneficial to one person but a chore to another. Microscopes, for
example, may be valued positively by the Healthcare Center but negatively by
the Economic Center since they are of no use to them. We should also strive to
ensure efficiency among fair allocations; since, otherwise, not distributing
any item to an agent is fair. We are looking for a fair and efficient
allocation.

Fairness depends heavily on the context; what may be fair in one setting may
not be fair in another. Suppose Agastya and Noorie are supposed to purchase a
new refrigerator. Agastya likes Samsung, and Noorie likes LG. Regardless of
what kind of refrigerator they buy, the concept of envy is no longer
applicable. We choose fairness criteria depending on the context. Later, we
will discuss various kinds of fairness notions in detail. In essence, we will
aim to formulate broadly acceptable fairness criteria. In doing so, we seek to
determine whether it always exists. If it does, can we find it in a reasonable
amount of time? In essence, we will aim to formulate broadly acceptable
fairness criteria. In doing so, we seek to determine whether it always exists.
If it does, can we find it in a reasonable amount of time? Is it possible to
relax the fairness criteria to apply to the setting if one does not exist?

It is an NP-complete problem to determine whether there is an envy-free
allocation when there are indivisible items, even when the valuation is binary
[14, 69]. Even if it exists, finding it is NP-hard [38]. It is natural to look
for fairness relaxations that exist as well as polynomial-time algorithms.
Researchers are interested in studying relaxed fairness notions in light of
the impossibility of fairness for indivisible items. Relaxations can be
categorized into two: additive relaxations and multiplicative relaxations.
Ideally, if we cannot find a fair distribution, we would prefer an allocation
that approximates the fairness guarantees in some multiplicative way. Suppose,
for example, that we cannot find a fair share allocation; we’re aiming to find
an allocation that approximates the fair share in some multiplicative way for
each agent. However, fairness is difficult to achieve even with a
multiplicative approximation. Therefore, we turn to additive approximation,
which exhibits possibilities and impossibilities.

##  3 Preliminaries

First, we define all essential concepts pertaining to fairness and introduce
all needed notation.

###  3.1 Fair Resource Allocation: Basic Model and Notations

We consider the problem $\langle N,M,V\rangle$ of allocating $M$ indivisible
resources/items among $N$ interested agents with valuation profile $v\in V$,
where $M=[m]$, i.e., $M=\\{1,2,\ldots,m\\}$, $N=[n]$ and $m,n\in\mathbb{N}$.
We define allocation $A\in\Pi_{n}(M)$ as the partition of $M$ indivisible
items into $n$ bundles, i.e., $A=(A_{1},A_{2},\ldots,A_{n})$, where $A_{i}$ is
the bundle allocated to agent $i$. We only allow complete allocation, and no
two agents can receive the same item. That is, $A=(A_{1},A_{2},\ldots,A_{n})$,
s.t., $\forall i,j\in N$, $i\neq j;A_{i}\cap A_{j}=\emptyset$ and
$\bigcup_{i}A_{i}=M$. We denote the allocation for all the agents except $i$
as $A_{-i}$. An allocation is called partial if $\bigcup_{i}A_{i}\subset M$.

#### Goods vs Chores

Each agent $i\in N$ has a valuation function
$v_{i}:2^{M}\rightarrow\mathbb{R}$, and $v_{i}(S)$ represents its valuation
for the subset $S\subseteq M$. We represent the valuation profile as
$v=(v_{1},v_{2},\ldots,v_{n})$. For all agents, the valuations are normalized,
i.e., $v_{i}(\emptyset)=0$. We denote the valuation of an item $k\in M$ for
any agent $i\in N$ as $v_{i}(\\{k\\})$ or $v_{ik}$. For an agent $i$, an item
$k\in M$ is a _good_ if, $v_{ik}\geq 0$, and a _chore_ if, $v_{ik}<0$. Goods
are desirable/positively valued and chores are undesirable/negatively valued
items. There could be three settings - pure goods, pure chores, and a
combination of goods and chores. In combination, $\forall k\in M$ it is
possible that, for some agent $i\in N$, $v_{ik}>0$ and for another agent $j\in
N$, $v_{jk}<0$. I.e., an item may be good for one agent and a chore for
another. Note that we use the terms – valuation and utility interchangeably in
this chapter.

#### Different Types of Valuation Functions

In most of the literature, we assume that the valuation functions of agents
are _monotonic_ for goods and _anti-monotonic_ for chores. If we increase
goods in an agent’s bundle, the utility increases, and if we increase chores,
the utility decreases. Formally, we define it as follows,

######  Definition 3.1 (Monotonicity).

A valuation function $v_{i}$ is monotonic if, $\forall S\subseteq T\subseteq
M,v_{i}(S)\leq v_{i}(T)$.

######  Definition 3.2 (Anti-monotonicity).

A valuation function $v_{i}$ is anti-monotonic if, $\forall S\subseteq
T\subseteq M,v_{i}(S)\geq v_{i}(T)$.

We say that agents have _additive valuations_ when, for each agent, the
valuation of a non-empty bundle equals the sum of the valuations of the
individual items. However, it is also possible that agents value an allocation
more or less than the sum of the values of the individual items, i.e., super-
additive or sub-additive. Furthermore, agents may have marginal decreases or
increases in their valuation with every additional item, i.e., sub-modular,
super-modular valuations.

In the most general setting, the agents may have arbitrary valuations for
every subset i.e., the _general valuation_ setting. General valuations are
rich and complex functions. Consider dividing 30 items among several agents.
To provide a complete valuation of items, each agent should provide their
value for every bundle of the items, i.e., they would have to report the value
of more than 1 billion bundles. Hence in literature additive valuations are
widely studied.

######  Definition 3.3 (Additive Valuations).

Agents have additive valuations if, an agent $i$, $\forall i\in N$ values any
non-empty bundle $A_{i}$ as $v_{i}(A_{i})=\sum_{k\in A_{i}}v_{ik}$.

A valuation instance is said to be _identical_ when all agents have the same
valuation for all subsets of items, formally,

######  Definition 3.4 (Identical Valuations).

The valuations are identical if, $\forall i,j\in N,\forall S\subseteq
M,v_{i}(S)=v_{j}(S)$.

Often, agents do not have identical valuations, but they order the items
likewise, i.e., agents have the same rank for the items. We call such
valuations _Identical Ordering (IDO)_.

######  Definition 3.5 (Identical Ordering (IDO)).

Valuations are IDO when when all agents agree on the same ranking of the
items, i.e., for $\forall i\in N$, $v_{i1}\geq v_{i2}\ldots\geq v_{im}$.

The cardinal cost functions of agents in an IDO instance may still differ. In
approval-based settings, agents have binary valuations, where they either
approve or disapprove an item.

######  Definition 3.6 (Binary Valuations).

The valuations are binary, if $\forall i\in N$, $\forall k\subseteq M$,
$v_{ik}\in\\{1,0\\}$.

We next define fairness and efficiency properties considered in this paper.

###  3.2 Important Definitions.

#### Fairness Related Definitions

The concept of envy-freeness (EF) introduced by [60] is a well-established
notion of fairness. It ensures that no agent envies the bundle of any other
agent. Unfortunately, an EF allocation of indivisible items may not exist; for
example, when there is a single good and two agents, the agent who doesn’t get
the good feels envious of the agent that does. The researchers were interested
in relaxing the concept of EF in order to limit the envy of every agent. They
introduced the idea of $\epsilon$-EF, which ensures that if envy exists, it is
at most $\epsilon$. However, $\epsilon$-EF allocations also need not exist.
The non-existence of EF and $\epsilon$-EF has prompted researchers to propose
additive relaxed notions of EF, such as EF1 and EFX.

For goods, an allocation is EF1 when all agents value their bundle at least as
much as they value another agent’s bundle with their most valued item removed.
EFX is stronger than EF1 and requires that all agents value their bundle no
less than the other agents’ bundle with their least valued item removed. For
chores, a similar definition applies, but unlike in goods, a chore is removed
from the agent’s bundle and then compared with the other agents’. In the case
of a combination of goods and chores, EF1 implies that if an agent envies
another agent, we can eliminate the envy either by virtually removing the most
valued good from the other agent’s bundle or removing the least favorite chore
from the agent’s own bundle. A standard definition is as follows,

######  Definition 3.7 (Envy-free (EF) and relaxations [13, 45, 48, 60, 101]).

For the items (goods or chores), an allocation $A$ that satisfies $\forall
i,j\in N$,

$\displaystyle v_{i}(A_{i})\geq v_{i}(A_{j})\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}EF}} }$
$\displaystyle\begin{rcases}v_{ik}<0,v_{i}(A_{i}\setminus\\{k\\})\geq
v_{i}(A_{j});\forall k\in A_{i}\\\ v_{ik}>0,v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus\\{k\\});\forall k\in A_{j}\ \end{rcases}\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}EFX}}}$
$\displaystyle v_{i}(A_{i}\setminus\\{k\\})\geq
v_{i}(A_{j}\setminus\\{k\\});\exists k\in\\{A_{i}\cup A_{j}\\}\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}EF1}}}$
$\displaystyle v_{i}(A_{i})+\epsilon\geq v_{i}(A_{j})\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}$\epsilon$-EF}}}$
$\displaystyle v_{i}(A_{i})\geq\alpha\cdot v_{i}(A_{j})\;\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}$\alpha$-EF}}}$

In addition to EF and its relaxations, proportional allocations are also well
studied in the context of fairness. As introduced by [95], Proportionality
requires that each agent gets at least 1/n of their share of the total value.
Furthermore, even proportional allocations may not always exist; for this
reason, researchers have considered relaxations. Researchers then looked into
$\alpha$-prop, which requires that every agent receives an $\alpha$ fraction
of its proportional share. But unfortunately, that solution does not exist as
well. Similar to EF, we adapted additive relaxation for proportionality as
well. Proportionality up to one item, PROP1 requires that every agent is
guaranteed to receive their proportionality guarantee if they lose their least
valued chore or receive their most valuable good from any other agent’s
bundle. Proportionality up to any item, PROPX requires that every agent is
guaranteed to receive their proportionality guarantee if they lose their most
valued chore or receive their least valued good allocated to another agent.

######  Definition 3.8 (Proportionality (PROP) [20, 23, 53, 95]).

For the items (chores or goods), an allocation $A$ that satisfies $\forall
i\in N$,

$\displaystyle v_{i}(A_{i})\geq 1/n\cdot v_{i}(M)\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}PROP}}}$
$\displaystyle\begin{rcases}v_{ik}>0,v_{i}(A_{i}\cup\\{k\\})\geq 1/n\cdot
v_{i}(M);\forall\ k\in\\{M\setminus A_{i}\\}\\\
v_{ik}<0,v_{i}(A_{i}\setminus\\{k\\})\geq 1/n\cdot v_{i}(M);\forall\ k\in
A_{i}\end{rcases}\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}PROPX}}}$
$\displaystyle\begin{rcases}v_{i}(A_{i}\cup\\{k\\})\geq 1/n\cdot
v_{i}(M);\exists\ k\in\\{M\setminus A_{i}\\}\mbox{ or,}\\\
v_{i}(A_{i}\setminus\\{k\\})\geq 1/n\cdot v_{i}(M);\exists\ k\in
A_{i}\end{rcases}\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}PROP1}}
}$ $\displaystyle v_{i}(A_{i}\cup\\{k\\})\geq 1/n\cdot
v_{i}(M);k\in\max_{j\neq i}\min_{k\in A_{j}}v_{i}(A_{jk})\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}PROPm
(only for goods)}}}$ $\displaystyle v_{i}(A_{i})\geq\alpha\cdot 1/n\cdot
v_{i}(M)\mbox{ is
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}$\alpha$-PROP}}}$

Relationship between EF and PROP.

When agents have sub-additive valuations, Envy-freeness is a stronger notion
than proportionality, i.e., EF implies PROP. Similarly, when agents have
additive valuations, EF1 implies PROP1. It may seem counter-intuitive at first
glance that EFX implies PROPX when agents have additive valuations. Note that
EF $\implies$ EFX $\implies$ EF1. PROP $\implies$ PROPX $\implies$ PROPm
$\implies$ PROP1.

Following, we explore Maximin share (MMS) introduced by [45], extending the
concept of Cut and Choose to indivisible goods. Imagine telling an agent to
divide the items into $n$ bundles and pick the one they value the least. The
agent would divide the items into $n$ partitions so that they maximize the
value of the least valued bundle. We call this value their Maximin Share. An
allocation satisfies MMS guarantees if every agent receives at least their MMS
value.

######  Definition 3.9 (Maxmin Share MMS [45]).

An allocation $A$ is said to be MMS if $\forall i\in
N,v_{i}(A_{i})\geq\mu_{i}$, where

$\mu_{i}=\max_{(A_{1},A_{2},\ldots,A_{n})\in\prod_{n}(M)}\min_{j\in
N}v_{i}(A_{j})$

Introduced by [90] [90], an allocation $A$ is said to be $\alpha$-MMS if it
guarantees $v_{i}(A_{i})\geq\alpha\cdot\mu_{i}$ when $\mu_{i}\geq 0$ and
$v_{i}(A_{i})\geq\frac{1}{\alpha}\cdot\mu_{i}$ when $\mu_{i}<0$, where
$\alpha\in(0,1]$.

#### Efficiency Related Definitions

In the previous subsection, we discussed some popular fairness notions. Note
that refusing to assign any item to any agent is also Envy-free. However, we
also desire efficiency, so fairness is considered in connection with
efficiency criteria as well. One of the most frequently studied efficiency
criteria in fairness literature is Pareto-Optimality. A Pareto optimal (PO)
allocation ensures that there is no other allocation which Pareto dominates,
i.e., better for all agents and strictly better for at least one. It is
interesting to consider PO and fair allocations.

######  Definition 3.10 (Pareto-Optimal (PO)).

An allocation $A^{\prime}$ is said to Pareto dominate allocation $A$, if
$\forall i\in N$, $v_{i}(A^{\prime}_{i})\geq v_{i}(A_{i})$ and $\exists i\in
N$, $v_{i}(A^{\prime}_{i})>v_{i}(A_{i})$. When there is no allocation that
Pareto dominates allocation $A$, it is said to be Pareto-optimal.

We then consider utilitarian welfare, the sum of agents’ utilities. On the
other hand, Nash welfare corresponds to the product of agents’ utilities, and
egalitarian welfare, to the minimum of individual agents’ utility.

######  Definition 3.11.

Given an instance $(N,M,\mathcal{V})$, an allocation $A^{*}$ satisfies,

Maximum $\displaystyle\mbox{
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Utilitarian
Welfare}}, MUW}(v),\ \mbox{if}$ $\displaystyle
A^{*}\in\max_{A}\sum_{i=1}^{n}v_{i}(A_{i})$ (1) Maximum $\displaystyle\mbox{
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Nash
Welfare}}, MNW}(v)\ \mbox{if}$ $\displaystyle
A^{*}\in\max_{A}\prod_{i=1}^{n}v_{i}(A_{i})$ (2) Maximum $\displaystyle\mbox{
{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Egalitarian
Welfare}}, MEW}(v)\ \mbox{if}$ $\displaystyle
A^{*}=\max_{A}\min_{i}v_{i}(A_{i})$ (3)

We proceed to the next section, summarizing the existential and computational
results pertaining to various fairness notions. We discuss various results for
goods in Section 4 and further categorize them in subsections 4.1 and 4.2,
which deal with the results of determining the fair allocation and fair and
efficient allocations, respectively. Our discussion of chores is similarly
addressed in Section 5, and the combination of goods and chores is described
in Section 6.

##  4 Indivisible Goods

###  4.1 Fair Allocation

#### Envy-Freeness (EF):

As defined in Definition 3.7, EF is a popular and strong notion of fairness.
However, EF allocation may not exist for $n\geq 2$, for instance, imagine that
we have to distribute a single good among $n$ agents. Even when agents have
binary additive valuations for goods, the problem of checking whether EF
allocation exists or not is NP-complete [14, 69]. Hence, next, we study a
prominent relaxation of EF, i.e., EF1 - Envy-free up to one item. The notion
of EF1 was introduced by [45] formally and implicitly it appeared in [80].

#### Envy-Freeness up to one item (EF1):

As given in Definition 3.7, in the case of goods, Envy-free up to one item
(EF1) implies that for any pair of agents $i$ and $j$, if agent $i$ envies
agent $j$, the envy can be eliminated by virtually taking out agent $i$’s most
valuable item from $j$’s bundle, i.e., $v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus\\{g\\}),\;\exists g\in A_{j}$. EF1 allocation always
exists and can be obtained in polynomial time.

######  Theorem 4.1 ([45, 48, 80]).

EF1 allocation always exist and can be found in polynomial time.

When agents have additive valuations, round-robin algorithm gives EF1 for
goods in polynomial time, i.e., $\mathcal{O}(mn\log{}m)$ [48]. We formally
describe the steps in Algorithm 5. To allocate items in a round-robin fashion,
we select an arbitrary sequence of agents. Each agent selects their favorite
items when their turn comes. For any $i,j\in N$, if agent $i$ picks before
agent $j$, they will never envy agent $j$. If agent $i$ picks after agent $j$,
they may envy agent $j$’s first selected item. Let’s assume that we remove
agent $j$’s first pick, which was the item it most preferred. Because we
removed agent $j$’s first selected item, hypothetical agent $i$ picks first.
We know that the agent who comes earlier in the sequence has no envy for the
agent who comes after them. Thus, agent $i$ does not envy agent $j$ if we
remove agent $j$’s first selected item, i.e., the envy is bounded up to one
item.

Algorithm 1 Round Robin 1:Set $\forall i,A_{i}=\emptyset$ 2:Every agent sort
the items in decreasing order  3:Arrange agents in an arbitrary sequence
w.l.o.g $\\{1,\ldots,n\\}$ 4:while $M\neq\emptyset$ do 5: for $i\leftarrow
1\textit{ to }n$ do 6: ${A_{i}\leftarrow A_{i}\cup\mbox{arg}\max_{k\in
M}v_{ik}}$ 7: $M\leftarrow M\setminus\\{k\\}$ 8: end for 9:end whilereturn
Allocation $A$

When agents have general monotone valuations, [80] proposed an envy-cycle
elimination algorithm that gives EF1 allocation for goods in polynomial time
$\mathcal{O}(mn^{3})$. This algorithm bounds the envy of any agent by the
maximum marginal value of any good; it corresponds to the notion of EF1 for
goods. We define the envy graph first. An envy graph of allocation $A$
consists of nodes for each agent and directed edges from agent $i$ to agent
$j$ if $i$ envies $j$, i.e., $v_{i}(A_{i})<v_{i}(A_{j})$. The algorithm
selects an unenvied agent in each iteration, i.e., an agent with no edges
directed towards them, and assigns an arbitrary good. If there are no such
agents, there must be cycles of envy, and the agents can exchange bundles
until no more cycles remain. Upon receiving the good, other agents may envy
this agent; we can eliminate this envy by removing the good they just received
since they were previously unenvied. Thus, if agent $i$ envy agent $j$, the
envy is bounded up to one good, i.e., by the recently added good in agent
$j$’s bundle. After each round of partial allocation, this algorithm ensures
that EF1 is satisfied. In contrast, [34] showed that the envy-cycle
elimination algorithm fails to find an EF1 allocation when agents have general
non-monotone valuations. However, whether or not EF1 allocation exists for
general non-monotone valuations is still an open question.

Algorithm 2 Envy-Cycle Elimination 1:Set $\forall i,A_{i}=\emptyset$ 2:for
$k\leftarrow 1\textit{ to }m$ do 3: Find an unenvied agent $i$ 4:
$A_{i}\leftarrow A_{i}\cup k$ 5: if Envy-Cycle exists then 6: Swap bundles to
resolve  7: end if 8:end forreturn Allocation $A$

Apart from EF1, weighted EF1 allocation always exists for goods [49], i.e., in
presence of asymmetric agents. Now in order to eliminate envy, EF1 removes the
most valuable item. However, the exciting results of EF1 may probably not
apply to the real world; i.e., EF1 can be relatively unfair, but the instance
may still admit a fairer allocation.

######  Example 4.1.

Assume Agastya and Noorie have one Toberlone and 99 Eclairs to divide among
themselves. Both prefer Toberlone over Eclairs. The round-robin allocation
gives 49 Eclairs, one Toberlone to Noorie, and 50 Eclairs to Agastya. Even
though the allocation is EF1, it is unfair to Agastya.

Therefore, it is desirable to strengthen fairness in many cases. [48] proposed
the concept of EFX, i.e., Envy-free up to any item as defined in Definition
3.7. Since then, a lot of work has been focused on EFX allocation’s existence,
but the question is yet to be resolved beyond the case of two agents. The
existence of EFX is an open question for $n>3$ for additive valuations and
$n>2$ for general valuations. Researchers consider EFX to be the best fairness
notion for indivisible items. In contrast to the weaker notion of EF1, the
study of EFX existence remains limited and elusive.

#### Envy-Freeness up to any item (EFX):

As defined in Definition 3.7, in the case of goods, EFX implies that for any
pair of agents $i$ and $j$, if $i$ envies $j$, the envy can be eliminated by
hypothetically removing any good from $j$’s bundle, i.e., by removing the
least valued item for $i$ from $j$’s bundle, i.e., $v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus\\{g\\}),\;\forall g\in A_{j}$. Note that EFX implies EF1.

######  Theorem 4.2 ([89]).

When agents have general but identical valuations, a modified Leximin
algorithm, i.e., Leximin++, ensures EFX.

[89] showed that when agents have general but identical valuations, a
modification of the Leximin, i.e, leximin++ solution is EFX. As mentioned in
Preliminaries 3, in the case of identical valuations, for any pair of agents
$i$ and $j$, $\forall S\subseteq M,\;v_{i}(S)=v_{j}(S)$. Leximin selects the
allocation that maximizes the minimum individual utility; further, if multiple
allocations achieve it, it chooses the allocation that maximizes the second
minimum individual utility, and so forth. It is well-known that finding the
Leximin solution can take exponential time. Plaut modified the Leximin
algorithm as follows; Leximin++ selects the allocation that maximizes the
minimum individual utility; further, if multiple allocations achieve it, it
chooses the allocation that maximizes the size of the minimum utility agent’s
bundle. Further, if multiple allocations achieve it, it chooses the allocation
that maximizes the second minimum individual utility, followed by the
cardinality maximum of the second minimum agent’s bundle, and so forth.

Algorithm 3 Leximin++ Algorithm 1:Set $\forall i,A_{i}=\emptyset$
2:$A\leftarrow\max_{A^{\prime}\in\prod_{n}(M)}\min_{i\in
N}v_{i}(A^{\prime}_{i})$ 3:while $|A|>1$ do 4: $i\leftarrow\min_{j\in
N}v_{j}(A_{j})$ 5: $A\leftarrow\max_{A}|A_{i}|$ 6:
$A\leftarrow\max_{A^{\prime}\in A}\min_{i\in N}v_{i}(A^{\prime}_{i})$ 7:end
whilereturn Allocation $A$

######  Remark 4.1.

However, Leximin++ may not ensure EFX allocation when agents have distinct
valuations

######  Theorem 4.3 ([89]).

An EFX allocation exists for two agents with general monotone valuations.

Using Leximin++ combined with Cut-and-Choose, [89] demonstrated that there
exists EFX allocation for two agents. As described in algorithm 4, the first
agent applies Leximin++ to partition the goods into two bundles (i.e., they
compute Leximin++ with two copies of themselves). The second agent picks their
favorite bundle. As can be seen, the second agent never envies the first
agent. Indeed, according to agent 1, the allocation is EFX regardless of what
they receive because the partition was created using Leximin++.

Algorithm 4 Leximin++ Combined with Cut-and-Choose 1:Run Algorithm 3 with two
copies of first agent  2:$A_{2}\leftarrow\max{v_{2}(A_{1}),v_{2}(A_{2})}$
3:$A_{1}\leftarrow M\setminus A_{2}$ return Allocation $A$

Even when two agents have identical submodular valuations, [89] showed that
finding EFX takes exponential time. On the other hand, the algorithm of [80]
finds an EF1 allocation in polynomial time for any number of agents with
monotone valuations. Thus, EFX is indeed significantly stronger than EF1. In
addition, [89] proposed an algorithm for EFX allocation in polynomial time,
i.e., $\mathcal{O}(mn^{3})$ when agents have additive valuations with
identical ranking, which relies on envy-cycle elimination [80]. [89] showed
that this algorithm combined with Cut-and-Choose results in a polynomial-time
EFX allocation for two agents with additive valuations. The first agent runs
the algorithm with two copies of themselves, and the second agent picks first,
just like algorithm 4. [67] also presented a polynomial time algorithm for EFX
(called as Near Envy-freeness) when for two agents with additive valuations.

A recent study by [50] showed that EFX allocation always exists for instances
with three agents with additive valuations. Their rigorous, constructive proof
required an extensive and cumbersome case analysis to prove the existence of
EFX that involves pseudo-polynomial time complexity. Despite the ongoing
efforts, the question of EFX’s existence remains unanswered for any valuation
system that involves more than three agents.

######  Theorem 4.4 ([50]).

EFX always exists in the case of three agents with additive valuations.

EFX is arguably the most compelling fairness notion for indivisible items.
However, its existence has not been settled and remains one of the major open
questions in the fair division. In an attempt to resolve this problem, a range
of impressive solutions has been explored, such as considering approximately
EFX or EFX with charity, i.e., we leave some low-value items unallocated or
solve the cases when agents have special valuation functions. The authors in
[1, 6, 22] studied EFX allocations when agents have restricted valuation
functions. [22] presented a polynomial-time algorithm for finding EFX
allocations for submodular dichotomous valuations. [6] proposed a polynomial-
time algorithm called ”MATCH & FREEZE” for allocating EFX allocations (they
refer to it as EFX0) for 2-value instances, i.e., $\forall i\in N,k\in
M,v_{ik}\in I$ and $|I|=2$. In addition, they presented a modified round-
robin, in which they reverse the order of agents in the last round, giving EFX
when agents have a valuation in an interval, i.e., $\forall i\in N,k\in
M,v_{ik}\in[x_{i},2x_{i}]$, where $x_{i}>0$.

##### EFX with charity

We search for partial EFX allocations, which do not require all items to be
allocated and satisfy EFX. A trivial allocation involves no items assigned to
any agent. Therefore, the goal is to determine allocations with some bound on
the set of unallocated items. Authors in [46, 35, 52] showed that an EFX
allocation always exists if we do not allocate at most $n-1$ goods. This
result was improved by [35] to $n-2$ goods. They also proved that for four
agents, EFX could be ensured by leaving at most one good. For general
valuations, [50] showed that an EFX allocation always exists with a pool of
unallocated items $C$ such that no one envies the pool and $C$ has less than
$n$ goods. [46] demonstrated that for goods with additive valuations, there
exists a partial EFX allocation where all agents get at least half of their
MNW allocation value, thus indicating that unallocated goods are low-valued.
In [46], the authors conjectured that, ”In particular, we suspect that adding
an item to an allocation problem (that provably has an EFX allocation) yields
another problem that also has an EFX allocation with at least as high Nash
welfare as the initial one.” Nevertheless, [50] disproved the conjecture by
displaying an example of a partial EFX allocation with a higher Nash welfare
than a complete EFX allocation. In parallel to this line of research, many
impressive results show the existence of approximate EFX allocations.

##### Approximately EFX

[89] proposed approximate EFX, which implies that for any pair of agents $i$
and $j$, $v_{i}(A_{i})\geq\alpha\cdot v_{i}(A_{j}\setminus\\{g\\}),\;\forall
g\in A_{j}$, where $\alpha>0$. Note that $\alpha$-EFX and EF1 are not
comparable, meaning none of the properties implies the other. [89] showed that
1/2-EFX allocations always exist when players have sub-additive valuations
using a modified envy-cycle elimination method. [9] proved the existence of
$0.618$-EFX allocations for additive valuations. For $\epsilon\in(0,1/2]$,
[51] showed that there is always an $(1-\epsilon)$-EFX allocation with a sub-
linear number of unallocated goods and a high Nash welfare. [6] also proposed
$\alpha$-EFX-value notion.

The envy-freeness concept doesn’t always make sense, for instance, in the
context of Public Decision Making. As explained in the Introduction, Agastya
and Noorie are supposed to purchase a new refrigerator; Agastya likes Samsung,
and Noorie likes LG. Regardless of what kind of refrigerator they buy, the
concept of envy is no longer applicable. In the next section, we discuss the
results related to proportionality for indivisible goods. We now move to
another intuitive fairness notion introduced by [95], proportionality.

Figure 1: Summary of Envy-freeness fairness notion for indivisible goods. The
Violet box (number 1) represents the polynomial-time algorithm. The blue box
(number 2) represents exponential time. The red box (number 3) represents
Pseudo-polynomial time. The green box (number 4) represents an open question.
The grey box (number 5) represents such an allocation does not exist.

#### Proportionality (PROP):

To attain proportionality, each agent would have to receive at least $1/n$ of
their value for all items, as stated in Definition 3.8. However, it is known
that it is not always possible to assign indivisible items proportionality.
The allocation of a single good among agents cannot ever be proportional. Note
that EF allocation is always PROP with sub-additive valuation. For $\alpha>0$,
$\alpha$-proportional allocation may not always exist; for example, in the
distribution of single good among two agents, one receives a utility of zero.
Naturally, researchers explored the additive approximations of PROP, i.e.,
PROP1, PROPm, and PROPX. In any situation, we look for the fairest allocation
possible, and if it is not possible, we relax our criteria in a way that
maintains fairness.

#### Proportionality up to one item (PROP1):

[53] introduced the notion of PROP1 in the setting of Public Decision Making,
which is more generic than indivisible item allocations. Along the lines of
EF1, PROP1 requires each agent to receive a utility at least their
proportional share if we add the largest good allocated to another agent to
their bundle, as stated in Definition 3.8. Each agent receives its
proportional share after hypothetically including one extra good from another
agent’s allocation into its bundle.

Under additive valuation, an EF1 allocation is also a PROP1 allocation;
therefore, every algorithm that gives EF1 also gives PROP1. In the setting of
Public Decision Making, [53] shows that a PROP1 allocation always exists in
polynomial time. In addition to fairness, [13] demonstrated that one could
achieve another requirement besides fairness: connectivity. They modeled the
situation in which items are placed on a path, and each agent wants a
connected bundle of the path. In many scenarios, finding a connected set of
items is essential. For example, the items could be a set of rooms along a
corridor, and the agents could be research groups seeking adjacent rooms. The
authors showed that contiguous proportional allocations of goods exist for
additive utilities and that they can be computed in polynomial time. In the
later sections, we will discuss how the combination of efficiency and fairness
becomes more intriguing in these contexts.

######  Theorem 4.5 ([13]).

Connected PROP1 exists in polynomial time for indivisible goods.

#### Proportionality up to any item (PROPX):

PROPX requires each agent to receive a utility at least their proportional
share if we add the small good allocated among the remaining agents to their
bundle, as stated in Definition 3.8. Each agent receives its proportional
share after hypothetically including one extra smallest good from the
remaining agents’ allocations into its bundle. The PROPX notion is stronger
than PROP1. It is also important to note that EFX is weaker than PROPX. While
EFX exists for three agents with additive valuations [50], [20] presented the
following counter-example where PROPX doesn’t exist with three agents having
identical valuations over five goods, i.e., they all value each good 3,3,3,3,
and 1 respectively.

In contrast to PROP1, which is easy to satisfy and much weaker, PROPX is much
more demanding and is not known to exist even for small instances. Therefore
this led researchers to explore alternate ways to relax proportionality.

#### Proportionality up to the maximin item (PROPm):

The problem is that PROP1 is too weak, and PROPX may not exist; there has to
be a fairness concept that is stricter than PROP1 but weaker than PROPX; [23]
introduced the notion of PROPm. PROPX requires each agent to receive a utility
worth at least their proportional share if we add the largest good among the
set of smallest goods allotted to the remaining agents to their bundle, as
stated in Definition 1. In other words, PROPm considers the least valued item
(from i’s perspective) in each of the other agent’s bundles and then takes the
highest value among them. Note that PROPX implies PROPm implies PROP1.

[23] presented that PROPm exists at least for up to five agents with additive
valuations, though the algorithm is exponential in terms of the number of
items. There is a limit of five agents, not because of the rigid limitations
of the constructive proof of their algorithm, but because as agents increases,
the complexity of analyzing all cases increases. As a result, they conjectured
that PROPm will always exist for any number of agents or items. Additionally,
[23] explored various relaxations of PROP, such as allowing the value to be
added to be equal to a median, mode, or minimax value of the agent. However,
their results showed that this fails to exist for as little as three agents.
They presented a counter-example with three agents having identical additive
valuation over seven items, i.e., all value the items
$1-6\epsilon,\epsilon,\epsilon,\epsilon,\epsilon,\epsilon$ and $\epsilon$,
respectively. It is easy to verify that there always exists an agent with
utility at most 3. Hence, it violates approximate proportionality with the
mean ($<0.25$), the median ($\epsilon$), the mode ($\epsilon$), and the
minimax item value ($\epsilon$). Later on, [24] demonstrated that PROPm
allocations exist in polynomial time.

######  Theorem 4.6 ([24]).

PROPm exists, and we can find it in polynomial time in terms of the number of
agents and goods.

The heart of the algorithm lies in breaking the allocation problem into
subparts and finding PROPm in each of them, i.e., it recursively solves PROPm
by splitting into agent- and item-disjoint sub-problems. This allocation is
also PROPm for the original instance. The algorithm starts by selecting an
arbitrary divider agent $i$, and this agent sorts the items in non-decreasing
order and partitions $m$ items into $n$ bundles, $(S_{1},S_{2},\ldots,S_{n})$,
such that $\forall j\in[n],v_{i}(S_{j})=1/(n-j+1)\cdot
v_{i}(M\setminus(\cup_{i=1}^{j-1}S_{i}))$. The algorithm then evaluates how
other agents value these bundles, splits the problem into two, and assigns a
bundle to this divider agent. Initially, this is one problem; hence, the
proportional Decomposition set $D$ is empty. We set $N_{d}$ as an empty set
representing the agents interested in $D$, i.e., their valuation of the items
in $D$ is proportional. We set $N_{r}$ as $N^{-i}$ representing the remaining
agents. The algorithm iterates for $n$ rounds; in any round $t$, it computes
$c$ as the number of agents in $N_{r}$ who value the first $t$ bundles $>t/n$.
If $c$ is $0$ and $|N_{d}|$ is less than $t$, it assigns $S_{t}$ to the
divider agent. It further decomposes the agents-items into two sub-problems
involving $N_{d}$ agents composed of $t-1$ agents with $D$ items consisting of
the first $t-1$ bundles and $N_{r}$ agents composed of $n-t$ agents with the
last $n-t$ bundles. If $c>0$, there is an over-demand of the initial set of
bundles, so the algorithm calls a subroutine UpdateDecomposition. The
subroutine uses graph analysis (novel graph representation) to update $D$ by
either reducing $c$ by one or increasing the agents in $N_{d}$ by one.

Figure 2: Summary of Proportionality fairness notion for indivisible goods.
The Violet box (number 1) represents the polynomial-time algorithm. The grey
box (number 2) represents such an allocation does not exist.

Additionally, an alternate relaxation that has received considerable attention
is [45]’s maximin share (MMS). We study MMS allocation in detail in the
following section.

#### Maximin Share (MMS):

In essence, MMS is an extension of the well-known “Cut-and-Choose” algorithm
used in solving the cake-cutting problem. Let’s say we ask an agent to divide
$m$ items into $n$ bundles and take the bundle that they’re least interested
in. This risk-averse agent would divide the bundles to maximize the minimum
utility, which is the MMS share of the agent. An MMS allocation guarantees
every agent their MMS share. Note that MMS is a weaker fairness property than
proportionality; a proportional allocation is always MMS. Even though MMS is
weaker, MMS is still too demanding in the case of indivisible items.

Despite its appealing formulation, MMS does have a computational disadvantage.
For one, even the computation of the maximin share for an agent with additive
valuations is an NP-Complete problem [41]. And computing an MMS allocation is
strongly NP-Hard. The problem is weakly NP-hard even for two agents [21, 41].
However, a PTAS for computing MMS exists [103]. Originally, [103] gave PTAS to
compute a maximum partition for a particular agent within the context of job
scheduling. However, the problem is identical to computing a maximin partition
for the given agent.

[41] addressed the question of whether MMS allocation exists for indivisible
items. While they answered the question for special cases, they left the
question of MMS allocation for additive valuations open. Their results show
that when agents have additive valuations, MMS allocations exist in the
following cases: (i) Binary valuations, (ii) For two agents, and (iii) $m\leq
n+3$. When agents have binary valuations, [41] showed that an MMS allocation
exists in polynomial time and can be found by employing a round-robin
algorithm with an alternating sequence, whereby each agent iteratively selects
their most favorite item from the remaining ones. By using polynomial-time
case analysis, [41] demonstrated that there exists MMS allocation for
instances having $n$ agents and $n+3$ goods. An MMS allocation exists in
instances with two agents with additive valuations using the “Cut-and-Choose”
protocol. [41] showed that it is challenging to find an MMS allocation when
agents have similar preferences, i.e., the more conflict, the more difficult
it is to find an MMS allocation. The authors proved that if one can find an
MMS allocation for an identical preference instance, every permutation derived
from that preference instance can also be allocated as an MMS allocation.

[41] showed that an MMS allocation need not exist when agents have general
valuations, even in the case of two agents, and left the existence of MMS
allocation for additive valuations as an open question. In the case of
additive valuations, despite the experimental results of [41], which had MMS
allocations consistently, [90] presented an intricate example in which every
allocation fails to achieve MMS guarantees. Thus, MMS is not guaranteed to
exist in instances with more than two agents with additive valuations. The
authors of [59, 76, 90] provided counter-examples to demonstrate that the MMS
allocation for goods may not always exist, even with additive valuations. [76]
provided an example involving $m$ that is linear in $n$, while [90] provided
an example involving $m$ that is exponential in $n$.

######  Theorem 4.7.

Given a resource allocation problem $(N,M,\mathcal{V})$, there exists $M$ and
(additive) valuations such that no allocation is MMS for any $n\geq 3$,

Because MMS need not exist, naturally, we seek relaxation in the allocation.
The goal is to construct an efficient algorithm to provide approximate MMS
guarantees. Fortunately, a multiplicative approximation of MMS always exists.
We discuss $\alpha$-MMS in the following section.

####  $\alpha$-Maximin Share (MMS):

[90] introduced a new concept of approximate maximin share ($\alpha$-MMS) to
solve this problem. An $\alpha$-MMS allocation guarantees every agent at least
the $\alpha$ fraction of the MMS share. Note that all the results mentioned
below are in the presence of additive valuations for MMS allocation.

The papers [8, 28, 90] showed that 2/3-MMS for goods always exists. Paper [62,
64] showed that 3/4-MMS for goods always exists. Authors in [62] provide an
algorithm that guarantees $3/4+1/12n$-MMS for goods.

[90] proved that the 2/3-MMS allocation for goods always exists and devised an
exponential-time algorithm. The algorithm enables one of the agents to divide
the items as its maximum partition and creates a bipartite graph (between
agents and bundles so that edges exist if a bundle is acceptable to the
agent). Using Hall’s Theorem, they showed that such a graph has a perfect
matching, and the algorithm runs recursively on the remaining agents and
items. If $n$ is constant, the (PTAS) algorithm runs in polynomial time. They
also showed that in the case of three and four agents, 3/4-MMS allocation
always exists using the same algorithm.

[8] presented a PTAS algorithm that computes $2/3-\epsilon$-MMS allocation,
polynomial for any number of agents and goods. They redesigned the algorithm
presented in [90] by manipulating matchings of the bipartite graph. Further,
they proved that in the case of three agents, there always exists 7/8-MMS
allocation and $7/8-\epsilon$ in polynomial time using the PTAS algorithm.
Lastly, when the valuation of every agent for each item, i.e., $\forall
i,k,v_{ik}\in\\{0,1,2\\}$, there always exists MMS allocation and presented a
polynomial-time algorithm, a variant of a round-robin algorithm. They also
provided a much simpler and faster algorithm that computes at least 1/2-MMS,
based on a round-robin algorithm with a slight modification of allocating the
most valuable goods first. [28] developed an algorithm that achieves the same
level of approximation guarantee as these results. [62] presented a simple
polynomial-time algorithm for 2/3-MMS allocation with straightforward
analysis.

Later, [64] proved that 3/4-MMS always exists and gave a PTAS algorithm for
allocating $3/4-\epsilon$-MMS in polynomial time. This result is exciting
because [90] proved that a 2/3-MMS allocation was tight, which means using
their algorithm would not guarantee better performance. Furthermore, [64]
demonstrated that the 4/5-MMS allocation always exists if there are four
agents as well as $4/5-\epsilon$ in polynomial time using the PTAS algorithm.
Then [63] presented a polynomial-time algorithm for finding the 3/4-MMS
allocation of goods. The most recent results of [63]’s work indicates that
$3/4+1/12n$ MMS always exists.

Figure 3: Summary of MMS fairness notion for indivisible goods. The Violet box
(number 1) represents the polynomial-time algorithm. The blue box (number 2)
represents exponential time. The grey box (number 3) represents such an
allocation does not exist.

We describe the latest algorithm in detail, i.e., the polynomial-time
algorithm for 3/4-MMS allocation. Except for that, we simply skim over other
algorithms briefly. We now talk about two sub-routines.

Normalized Valuations $\alpha$-MMS is scale invariant, i.e., if $A$ is
$\alpha$-MMS allocation for the valuation profile $\mathcal{V}$, and if we
consider a scaled valuation profile $\mathcal{V}^{\prime}$, i.e., $\forall
i\in N,k\in M,v^{\prime}_{ik}=c\cdot v_{ik}$, $A$ is $\alpha$-MMS for
$\mathcal{V}^{\prime}$. For simplicity, we scale the valuations such that
$\forall i,\mu_{i}\leq 1$, i.e., $v_{i}(M)=|N|$.

Bag Filling. [64] introduced bag filling to allocate low-value goods as an
extension of the Moving Knife Procedure (allocates divisible goods
proportionally). The algorithm begins by filling an empty bag with arbitrary
goods until it satisfies some agent, that is until the agent calls for the
bag; after that, the algorithm assigns the bundle to the agent and starts
refilling an empty bag again, and repeats the process with the remaining
agents. When agents value each item less than $\delta\mu_{i}$, i.e.,
$v_{ik}\leq\delta\mu_{i}$, the bag filling algorithm gives
$(1-\delta)\mu_{i}$-MMS allocation. The intention is that after an agent
receives a bundle, enough goods are left for the rest of the agents to meet
their $(1-\delta)\mu_{i}$-MMS allocations. When assigning a bundle to an
agent, the other agents value it less than $(1-\delta)\mu_{i}$ (since they
didn’t call for the bundle), so the valuation of the rest of the agents for
remaining goods is at least $\frac{n-1}{n}\cdot v_{i}(M)$, which is
proportionally more than before assigning the bundle. We can say that the
agents who pick bundles early leave more goods than they take. For normalized
valuations (i.e. $\forall i\in N$, $v_{i}(M)=n$), if $\forall i$ and $\forall
k$, $v_{ik}\leq\delta$, the bag filling guarantees $(1-\delta)$-MMS
allocation, where $0\leq\delta\leq 1/2$.

Algorithm 5 Bag Filling Algorithm 1:Normalize valuations  2:Set $\forall
i,A_{i}=\emptyset$, $B=\emptyset$ 3:for $k\leftarrow 1\textit{ to }m$ do 4: if
$\exists i\in N,v_{i}(B\cup k)>(1-\delta)$ then 5: $A_{i}\leftarrow B$ 6:
$B\leftarrow\emptyset$ 7: end if 8: $B\leftarrow B\cup k$ 9:end forreturn
Allocation $A$

Valid Reduction. If we remove an agent $i$ and an item $k$ from an instance
$\mathcal{I}=\langle M,N,\mathcal{V}\rangle$, it doesn’t reduce MMS guarantees
for the remaining agents. We mean to say that in $\mathcal{I}^{\prime}=\langle
M\setminus\\{i\\},N\setminus\\{k\\},\mathcal{V}\rangle$,
$\mu^{\prime}_{i}\geq\mu_{i}$, i.e., the MMS value in the new reduced instance
is at least the MMS value in the original instance. For high valued items,
i.e., $\exists i,k,v_{ik}\leq\alpha\mu_{i}$, we assign item $k$ to agent $i$.
After assigning this high-valued item, we still have enough goods, i.e., the
MMS value of each agent in the reduced instance is at least the MMS value in
the original instance. Our goal is to assign alpha-MMS, i.e., the idea is to
assign the high-value items firstly, i.e., giving an agent an item if they
value more than alpha mu. We reach the stage where the instance is
irreducible, i.e., none of the remaining agents have any remaining high-value
items. We say an instance is $\alpha$-irreducible, if there $\not\exists i\in
N$, $k\not\exists M$, such that $v_{ik}\geq\alpha\mu_{i}$.

The core concept lies in using these two algorithms to ensure $\alpha$-MMS,
i.e., firstly assign high-valued items using valid reduction and further
assign low-valued and medium-valued items using a modified bag filling.

A polynomial-time 1/2-MMS We start by normalizing the valuations for all the
agents. We assign an item to an agent if they value it more than 1/2. We break
ties arbitrarily. Note that when we assign an item to an agent, in the reduced
instance, the new MMS value of all the remaining agents is at least as much as
in the original instance. Once the instance becomes 1/2-irreducible, i.e., if
there are remaining agents, they all value the remaining items less than 1/2,
we assign the rest of the goods using the bag filling algorithm.

Ordered Instances Further, there’s another core concept used by these
algorithms, which was first noticed by [41]. They showed that it is
challenging to find an MMS allocation when agents have similar preferences,
i.e., the more conflict, the more difficult it is to find an MMS allocation.
The authors proved that if one can find an MMS allocation for an identical
preference instance, i.e., an ordered instance, every permutation derived from
that preference instance can also be allocated as an MMS allocation. Formally,
we say an instance is an ordered instance _iff_ there exists a total ordering
over the set of goods, i.e., $\forall i\in N,v_{i1}\geq v_{i2}\geq\ldots\geq
v_{im}$. Further, [41, 28] provided a reduction from any arbitrary instance
$I=(N,M,\mathcal{V})$ to an ordered instance $I^{\prime}$, and showed that if
$A^{\prime}$ satisfies $\alpha$-MMS guarantees for $I^{\prime}$, we can find
allocation $A$ for $I$ in polynomial time derived from $A^{\prime}$ in
polynomial-time.

Given an instance $I=(N,M,\mathcal{V})$, we construct an ordered instance
$I^{\prime}=(N,M,\mathcal{V}^{\prime})$ as follows,

Algorithm 6 Converting into Ordered Instance 1:for $k\leftarrow 1\textit{ to
}m$ do 2: for $i\leftarrow 1\textit{ to }n$ do 3:
$k^{*}\leftarrow\textit{agent }i\textit{'s }\textit{$k^{th}$ most valuable
good}$ 4: $v^{\prime}_{ik}\leftarrow v_{ik^{*}}$ 5: end for 6:end forreturn
Valuation $\mathcal{V}^{\prime}$

Now given an allocation $A^{\prime}$ which satisfies $\alpha$-MMS for
$I^{\prime}$, we construct $A$ which satisfies the same for $I$ as follows,

Algorithm 7 $\alpha$-MMS for Original Instance $I$
1:$A=(\emptyset,\emptyset,\ldots,\emptyset)$, and $R\leftarrow M$ 2:for
$k\leftarrow 1\textit{ to }m$ do 3: Pick the agent $i$ who has item $k$ in
$A^{\prime}$ 4: $g\leftarrow\textit{argmax}_{k\in R}v_{ik}$ 5:
$A_{i}\leftarrow A_{i}\cup\\{g\\}$ and $R\leftarrow R\setminus\\{g\\}$ 6:end
forreturn Valuation $\mathcal{V}^{\prime}$

It is easy to verify that this whole procedure is a polynomial-time algorithm.
From now, we only need to address the setting of ordered instances, i.e.,
identical preferences, and using a polynomial time algorithm, we can compute
$\alpha$-MMS for any arbitrary additive instances. Observe that the MMS values
of an agent in $I$ and $I^{\prime}$ are the same because it neither depends on
the order of the items nor on other agents’ valuations.

3/4 MMS when we know the $\mu$ values

We now discuss the algorithm for computing 3/4-MMS allocation. We pre-process
our instances such that they are normalized and ordered. We assume that we
know the MMS value of each agent, and we scale the valuation such that the MMS
value becomes 1 for all. Note that this is a crucial assumption; later, for
the strongly polynomial time algorithm for exact 3/4, we will change the way
we normalize the valuations.

For ease of exposition, we abuse notation and use $M$ and $N$ to denote the
set of unallocated items and the set of agents who have not yet received any
bundle. The basic structure of the algorithm closely resembles that of valid
reduction and bag filling.

The algorithm first assigns high-valued items. In the algorithms, they make it
a simple process of greedy assignment by leveraging the pigeonhole principle
to make valid reductions. They define bundles $S_{1}:=\\{1\\}$,
$S_{2}:=\\{n,n+1\\}(\emptyset,\textit{if}m\leq n)$,
$S_{3}:=\\{2n-1,2n,2n+1\\}(\emptyset,\textit{if}m\leq 2n)$, and
$S_{4}:=\\{1,2n+1\\}$. $S_{1}$ has the highest valued item in $M$, $S_{2}$ has
the $n^{th}$ and $(n+1)^{th}$ highest valued items in $M$, and so on. If any
of these bundles value $3/4$ to an agent, then it is a valid reduction. We
assign the lowest index bundle in $\\{S_{1},S_{2},S_{3},S_{4}\\}$ to agent $i$
such that it is valued at least 3/4. Note that after each valid reduction, we
update $M$ and $N$, and these bundles will change accordingly.

Once the instance becomes $\alpha$-irreducible, i.e., for the remaining agents
$i\in N$, $S\in\\{S_{1},S_{2},S_{3},S_{4}\\}$, and $\forall i,S,v_{i}(S)<3/4$,
we proceed to the modified bag filling algorithm for the rest of the agents.
Let $J_{1}:=\\{1,2,\ldots,n\\}$ and $J_{2}:=\\{n+1,\ldots,2n\\}$. Next, we
initialize $n$ bags as follows: $B=\\{B_{1},B_{2},\ldots,B_{n}\\}$; where
$B_{k}=\\{k,2n-k+1\\},\forall k$. Each bag contains one item from $J_{1}$ and
one item from $J_{2}$ such that from $B_{1}$ to $B_{n}$ value of items from
$J_{1}$ decreases and the value of items from $J_{2}$ increases. Now in each
round $k$, it starts a new bundle $T$ with $T\leftarrow B_{k}$. If there is an
agent who values $T$ to be at least 3/4, then assign $T$ to such an agent.
Otherwise, keep adding goods from $M\setminus\\{J_{1}\cup J_{2}\\}$ to $T$ one
by one until an agent with no bundle assigned to her values $T$ at least 3/4.
The algorithm allocates $T$ to that agent, and if there are multiple such
agents, it chooses one arbitrarily. The complete details are given in the
Algorithm 8.

However, note that this algorithm requires a detail of the exact MMS value of
all the agents, which is NP-Hard to compute. The authors further modified the
algorithm in such a that it is strongly polynomial in time and computes exact
3/4-MMS allocation with the same underlying concepts. The key modification is
the way we normalize valuation, allocation of $S_{4}$ bundle, and use the
average as an upper bound for the MMS value.

Algorithm 8 Exact 3/4-MMS Algorithm 1:Assume MMS values are known, alpha,
2:Normalize the Valuations such that $\forall i,\mu_{i}=1$ 3:Using Modified
Valid Reduction now  4:$S_{1}\leftarrow\\{1\\}$,
$S_{2}\leftarrow\\{n,n+1\\},S_{3}\leftarrow\\{2n-1,2n,2n+1\\},S_{4}\leftarrow\\{1,2n+1\\}$
5:$\forall S\subseteq M$, we define $\tau(S):=\\{i\in N:v_{i}(S)\geq\alpha\\}$
6:while
$(\tau(S_{1})\cup\tau(S_{2})\cup\tau(S_{3})\cup\tau(S_{4})))\neq\emptyset$ do
7: $S\leftarrow$ lowest index in $\\{S_{1},S_{2},S_{3},S_{4}\\}$ which
satisfies $\alpha$ 8: agent $i$ in $\tau(S)$ 9: $A_{i}\leftarrow S$ 10:
$M\leftarrow M\setminus S$; $N\leftarrow N\setminus\\{i\\}$ 11:end while
12:Initialize bags $B$, where $B_{k}=\\{k,2n-k+1\\},\forall k$ 13:$R\leftarrow
M\setminus J$ 14:for $k\leftarrow 1\textit{ to }n$ do 15: $T\leftarrow B_{k}$
16: while $v_{i}(T)<\alpha$ do 17: $g\in R$ 18: $T\leftarrow
T\cup\\{j\\};R\leftarrow R\setminus\\{j\\}$ 19: end while 20: $\exists i$,
$v_{i}(T)\geq\alpha$, $A_{i}\leftarrow T$, $N\leftarrow N\setminus i$ 21:end
forreturn Valuation $\mathcal{V}^{\prime}$

[63] proved that existence of $\frac{3}{4}+\frac{1}{12n}$ using Algorithm 8.
They showed that this bound is tight. They showed that extending this approach
for improved $\alpha$ would be challenging.

Apart from additive valuations for indivisible goods, MMS allocations have
been studied extensively in various other settings. [58] studied MMS
allocation for asymmetric agents. [93] explored MMS allocation in the presence
of externalities. [5, 7, 18, 27] studied MMS allocation for strategic agents.
[28, 64, 79, 66, 37] studied MMS allocation beyond additive valuations.

Next, we discuss fair and efficient algorithms for indivisible goods.

###  4.2 Fair and Efficient Allocation

For various reasons, we strive to seek fair, effective allocations. We want to
ensure fairness, but we also want to ensure the items go to the most
deserving; however, we encounter various difficulties when doing so. Within
the PROP1 allocation set, finding an allocation that is utilitarian-maximum is
NP-hard [16]. The problem of making Pareto improvements to PROP1 allocation is
computationally challenging [12, 74]. It is possible that a Pareto improvement
over a PROP1 allocation will not even satisfy PROP1. In this section, we
summarize the literature on efficient fair allocation for indivisible goods.

#### Efficient EF1 allocations

Our aim in this section is to discuss the results regarding efficient
allocation of EF1.

##### EF1 + PO

Recall that an allocation is said to be Pareto optimal (PO) if it is not
Pareto dominated by any other allocation, i.e., there is no other allocation
in which every agent is better off and at least one agent is strictly better
off. Under additive valuations, [48] [48] has shown that EF1 and PO
allocations always exist. As shown in their study, the MNW allocation (i.e.,
an allocation that maximizes Nash social welfare) satisfies both EF1 and PO.
This is challenging because the complexity of computing an allocation like
this is high, i.e., even though finding EF1 is polynomial time, even for
additive valuations, polynomial-time algorithms are not available to find EF1
and PO. Computing MNW allocation is APX-hard [77]. In addition,[30] [30]
proposed a pseudo-polynomial time algorithm for determining PO and EF1
allocations.

##### EF1 + USW

Among a set of utilitarian maximal allocations, [15] [15] proved that it is
strongly NP-hard to find an allocation that is PROP1. Furthermore, they showed
that maximizing the utilitarian welfare among a set of fair allocations when
the number of agents is variable is strongly NP-Hard, while it is NP-Hard when
the number of agents is fixed and greater than two. There is a polynomial-time
algorithm that determines whether an EF1 allocation exists or not among the
utilitarian maximal allocations when there are two agents. Further, they
designed pseudo-polynomial time algorithms for both problems with a fixed
number of agents.

In light of these open questions in finding efficient EF1 allocations,
researchers have explored efficient PROP1 allocations and obtained positive
results.

#### Efficient PROP1 allocations

##### PROP1 + PO

EF1 and PO are satisfied by MNW allocation, which implies that when agents
have additive valuations, an allocation that meets PROP1 and PO exists. [53].
In public decision settings (a setting that is more general than indivisible
goods allocation), [53][53] proved that there is always a PROP1 and PO
allocation. They left the complexity of computing such an allocation as an
open question. For goods with additive valuations, [29][29] proposed a
strongly polynomial-time algorithm for calculating PROP1 and fPO (stronger
than PO) by leveraging pure market equilibrium. In contrast to PO, fPO
requires that an allocation is not dominated by fractional (or integral)
allocations; fPO is, therefore, a stronger solution concept. Because finding
Pareto improvements while maintaining PROP1 is challenging, they deal with
fractional allocations that are improving and convert them into integral
allocations. They do so by leveraging fisher markets, i.e., such markets
consist of a set of divisible goods, a set of agents with budgets and
valuations over these goods. Fisher markets clear when goods are assigned
prices; each agent spends its entire budget on only those most valuable goods
per unit spent, and the market is in equilibrium. From the resource allocation
perspective, market equilibrium is applicable since the first welfare theorem
states that these equilibria are always Pareto efficient [82]. In Fisher
markets with additive valuations, Eisenberg and Gale’s convex program provides
an efficient way to determine equilibrium allocations and prices: the primal
and dual solutions of the convex program correspond to the equilibrium
allocations and prices [56, 91]. Strongly polynomial-time algorithms exist for
the same [87, 100]. The equilibrium allocation is fractionally Pareto
efficient (fPO). However, equilibrium allocations are not necessarily
integral, i.e., the allocation we get may not be applicable in the context of
indivisible goods. Note that (in contrast to computing an arbitrary
equilibrium) finding an integral equilibrium is computationally hard, i.e.,
determining whether a given Fisher market is pure is an NP-hard problem [29].
In general, agents are assigned fractional shares of goods in a market
equilibrium. In other words, we cannot directly incorporate indivisible goods
into the market framework.

The authors developed an efficient algorithm that first computes an
equilibrium ($A$, $p$) of the market $B$ and, then, round (fractional)
allocation $A$ to an integral allocation $A^{\prime}$ such that it is an
integral equilibrium of the market $B^{\prime}$. The algorithm doesn’t change
the price of the goods. It defines the new budgets (a bounded change in
agents’ budgets) to explicitly satisfy budget exhaustion with respect to the
computed allocations and the unchanged prices at the end. Since $A^{\prime}$
is an equilibrium of the Fisher market $B^{\prime}$, via the first welfare
theorem, $A^{\prime}$ is fPO and PROP1. This conversion to $A^{\prime}$ is in
strongly polynomial time. Briefly speaking, given a market and its equilibrium
$(A,p)$, the spending graph $G(A,p)$ is a forest. The algorithm starts by
identifying the root of each tree at some agent in this forest. Then assign
child goods to root agent $i$ (with no parents) until adding more child goods
to $i$ violates the budget constraint. The remaining child goods are then
appropriately assigned to grandchildren agents. After each distribution,
delete this parent agent $i$ and all its allocated child goods. Iteratively
assign remaining goods to agents until all the goods are allocated. Note that
if a good is completely assigned to an agent, i.e., it is integrally assigned,
then it will continue to be assigned to the same agent after conversion. This
algorithm gives weighted-PROP1, which was later mentioned in [44]. This
algorithm satisfies EF$1^{1}$, weighted-PROP1, and fPO.

##### PROP1 + USW

Among a set of utilitarian maximal allocations, [15] [15] proved that it is
strongly NP-hard to find an allocation that is PROP1. Furthermore, they showed
that maximizing the utilitarian welfare among a set of fair allocations when
the number of agents is variable is strongly NP-Hard, while it is NP-Hard when
the number of agents is fixed and greater than two. There is a polynomial-time
algorithm that determines whether a PROP1 allocation exists or not among the
utilitarian maximal allocations when there are two agents. Further, they
designed pseudo-polynomial time algorithms for both problems with a fixed
number of agents.

##### PROPm + PO/USW

Towards finding efficient PROPm allocations, this area of study remains
unexplored, leaving the scope for future research.

#### Efficient EFX allocations

##### EFX + PO

In the presence of zero marginal valuations, [89] [89] showed that there are
additive valuations in which no EFX allocation is also PO. In the presence of
zero marginal valuations, [89] [89] showed that there are general and
identical valuations in which no EFX allocation is also PO. In the presence of
nonzero marginal valuations, for any number of agents with general but
identical valuations, and for two agents with (possibly distinct) additive
valuations, the leximin++ solution is EFX and PO. They also argued that the
assumption of nonzero marginal utility is quite reasonable with two agents
having additive valuations as one agent is indifferent to some good; we can
assign the good to the other agent and exclude it from the division process
completely.

Towards finding efficient, fair allocations, especially for general
valuations, this area of study remains unexplored, leaving the scope for
future research. Moreover, it would be interesting to explore efficient
allocation when a fair allocation, i.e., if MMS allocation exists, what are
the efficiency guarantees we can achieve? We summarize our results about the
efficient, fair allocation of goods in Figure 4. Next, we move on to the
discussion of chores.

Figure 4: Summary of efficient fairness allocation for indivisible goods. The
Violet box (number 1) represents the polynomial-time algorithm. The blue box
(number 2) represents exponential time. The grey box (number 5) represents
such an allocation does not exist. The red box (number 3) represents pseudo-
polynomial time. The green box (number 4) represents open questions.

##  5 Indivisible Chores

###  5.1 Fair Allocation

#### Envy-Freeness:

Similar to indivisible goods, determining the existence of an envy-free
allocation is NP-complete, even in the simple case when agents have binary
additive valuations for chores [36].

#### Envy-Freeness up to one item (EF1):

Similarly to goods, a simple round robin gives an EF1 for chores in polynomial
time – O($mn\log m$). The chore division problem might appear to be the
‘opposite’ of the goods problem, and therefore intuitively, one might expect
the natural adaptation of algorithms designed to compute an EF1 allocation for
goods, to also work for chores. This, however, is not the case. The envy-cycle
elimination algorithm [80] doesn’t give EF1 allocation in the case of chores.
[36] [36] presented Top-trading envy-cycle elimination algorithm, a modified
Envy-cycle algorithm for chores that gives EF1 for indivisible chores with
anti-monotonic valuations. For indivisible goods, resolving arbitrary envy
cycles (until the envy graph becomes acyclic) is known to preserve EF1.
However, for indivisible chores, the choice of which envy cycle is resolved
matters. EF1 for chores entails that any pairwise envy can be addressed by
removing some chores from the envious agent’s bundle. The algorithm works by
assigning, at each step, an unassigned item with the largest cost to an agent
who does not envy anyone else (i.e., a non-envious agent who is a “sink” node
in the top-trading envy graph). If the top-trading envy graph does not have a
sink, then it must have a cycle. Then resolving the top-trading envy cycles
guarantees the existence of a sink agent in the top-trading envy graph.

Now we briefly describe the algorithm for EF1 for chores as follows. In the
above algorithm, given a partial allocation $A$, we consider a subgraph of the
envy-graph $G_{A}$ that we call the top-trading envy graph $T_{A}$ whose
vertices denote the agents, and an edge $(i,k)$ denotes that agent $i$’s
(weakly) most preferred bundle is $A_{k}$. If the envy graph does not have a
sink, then the top-trading envy graph $T_{A}$ has a cycle. Therefore,
resolving top-trading envy cycles guarantees the existence of a sink agent in
the envy graph, and it also preserves EF1. This is because every agent
involved in the top-trading exchange receives their most preferred bundle
after the swap, which means they do not envy anyone else in the next round.

#### Envy-Freeness up to any item (EFX):

An EFX allocation also exists for IDO instances for chores [78]. As described
in [36], the Top Trading Envy Cycle algorithm allocates items in any order,
and it meets the EF1 requirement. Modifying this algorithm to allocate the
largest chores (minimum valued items) to sink agents guarantees EFX allocation
for IDO instances. We can ensure that EFX allocation is made for IDO instances
if we select the item with the highest cost at each step. This returns an EFX
allocation in polynomial time for additive valuations for any IDO instance.
For two agents or any agents with IDO valuation functions, EFX allocations
always exist.

##### Approximate EFX allocations

While good results have been obtained for the (approximation of) EFX
allocations for goods, little is known about how EFX is allocated
(approximately). It is not known even if constant approximations of EFX
allocations exist for three agents with general additive valuations, let alone
whether EFX allocations exist at all. For indivisible chores, the authors
propose algorithms to compute approximate EFX allocations in polynomial time
in [104]. When there are three agents, the algorithm produces 5-EFX, and when
there are four or more agents, it produces $3n^{2}$, i.e.,$\mathcal{O}(n^{2})$
as the approximation ratio. The authors observed that in doing so, i.e., the
algorithm in order to allocate approximate EFX often would increase the cost
of other agents instead of decreasing the cost of an envied agent, which can
lead to inefficient allocation. Another interesting open question in
approximate-EFX is, can we get a constant approximate ratio for any number of
agents? Apart from approximate-EFX, in the case of goods, EFX with charity is
well explored as described in Section; however, it is unknown whether similar
results hold for the allocation of chores.

#### Proportionality (PROP):

Similar to indivisible goods, there may not be a proportional allocation for
indivisible chores. Determining if a proportional allocation is possible, even
for just two agents, is a problem that is NP-Complete [41].

Algorithm 9 EF1 for Chores with General Valuations 1:Initialize
$A\leftarrow(\emptyset,\emptyset,\ldots,\emptyset)$ 2:for $k\leftarrow
1\textit{ to }m$ do 3: if there is no sink agent in envy graph $G_{A}$ then 4:
$C\leftarrow$ any cycle in $T_{A}$ 5: $A\leftarrow A^{C}$ 6: end if 7: Chose a
sink $j$ in the envy graph $G_{A}$ 8: $A_{j}\leftarrow A_{j}\cup k$ 9:end
forreturn Allocation $A$

Figure 5: Summary of EF fairness notion for indivisible chores. The Violet box
(number 1) represents the polynomial-time algorithm. The blue box (number 2)
represents exponential time. The grey box (number 4) represents such an
allocation does not exist. The green box (number 3) represents an open
question.

#### Proportionality up to one item (PROP1):

When valuations are additive, EF1 and PROP1 are equivalent. This means that
any algorithm that results in EF1 allocations also satisfies PROP1. According
to a study by Aziz et al. ([13]), using the PROP1 concept allows for not only
fairness but also connectivity in the allocation of mixed goods (including
chores) in a contiguous and proportional manner and can be computed
efficiently.

#### Proportionality up to any item (PROPX):

It is widely acknowledged that EFX (Envyfreeness up to any item) is stronger
to PROPX (Proportionality up to any item) when it comes to the allocation of
chores. This stands in contrast to the allocation of goods, where PROPX has
been found to be more stronger. In their study, [78] examined the concept of
weighted proportionality up to any item and established that a weighted PROPX
allocation exists and can be calculated in a computationally efficient manner.
Therefore, while PROPX may not be applicable to indivisible goods, it can be
calculated efficiently for indivisible chores. The “Bid-and-Take” algorithm, a
variation of the ”Top trading envy cycle algorithm” [36], is presented by
[78]. In this algorithm, they choose the largest tasks (items with the lowest
value) and assign them to the active agent who has the lowest current social
cost for the item. Initially, all agents are active. When an agent’s
cumulative cost exceeds their proportional share, they are deactivated. It is
important to note that in [36], items were allocated in any order and were
EF1. However, this modification guarantees that the allocation is EFX (and
therefore PROPX) for IDO instances.

The authors proposed using a similar approach to algorithms for approximate
MMS, where they reduce the instance to IDO to find the $\alpha$-MMS and then
reconvert it back to the original instance, while still maintaining its
$\alpha$-MMS status. They state that if a polynomial time algorithm exists
that can compute an $\alpha$-WPROPX allocation for any IDO instance, then
there also exists a polynomial time algorithm that can compute an
$\alpha$-WPROPX allocation for any additive instance. This modified envy-cycle
elimination algorithm ensures both weighted PROPX and 4/3 approximate MMS
simultaneously. Additionally, the authors have also found that an EFX and a
weighted EF1 allocation for indivisible chores exist if all agents have the
same ordinal preference. It should be noted that while all PROPX allocations
are PROP1, the reverse is not necessarily true. As demonstrated for
indivisible chores, wPROPX allocations can be computed in a polynomial time,
the emphasis is placed on wPROPX allocations, and any findings apply to PROP1.

Figure 6: Summary of PROP fairness notion for indivisible chores. The Violet
box (number 1) represents the polynomial-time algorithm. The grey box (number
2) represents such an allocation does not exist.

#### Maximin Share Allocation (MMS):

The problem of allocating MMS allocation to chores is closely related to bin
packing problem/job scheduling problem.

[21] [21] presented an example based on [90] with three agents with additive
valuations where every allocation results in some agents having a lower MMS
value than they should. There is no guarantee that an MMS allocation for
chores exists, even with additive valuations, as demonstrated in [21, 59].
While it has been shown that MMS allocations are not guaranteed to exist for
indivisible chores [21], there are many works that study its approximations
[21, 28, 71]. The state-of-the-art approximation ratio for MMS allocation for
indivisible chores is 11/9 [71]

######  Theorem 5.1.

[21] Given a chore allocation problem $(N,M,\mathcal{V})$, for any $n\geq 3$,
there exists $M$ and (additive) valuations that do not admit an MMS
allocation.

#### Approximately MMS Allocation ($\alpha$-MMS):

Researchers have been working on finding efficient algorithms for
approximating the maximum minimum share (MMS) allocation, particularly for
situations where MMS does not always exist, such as in the case of chores. One
such algorithm for 2-MMS has been demonstrated to be polynomial time by
[21][21]. This result has been improved upon by [28], who presented a
polynomial time algorithm for 4/3-MMS. In the latest development, [71] showed
that an 11/9-MMS allocation could be achieved by converting the instances to
identical ordinal instances (IDO) and then solving for approximate maximin
allocation. The authors proposed a mechanism similar to the First Fit
Decreasing (FFD) algorithm for bin packing problems to allocate chores. This
involves starting with high-valued chores and adding them to the bundle in
decreasing order until an agent’s threshold is met, and then allocating that
bundle to that agent. The algorithm repeats this process for all agents until
all chores are allocated. The authors also provided a polynomial time
approximation scheme (PTAS) and a polynomial time algorithm for 5/4-MMS
allocation.

To compute the 11/9-MMS allocation, the algorithm first converts the instance
to an IDO instance and orders the chores in decreasing order. Then, starting
with high-valued chores, the algorithm adds chores to the bundle until an
agent’s threshold is met and allocates the bundle to that agent. This process
is repeated for all agents until all chores are allocated. The authors proved
that if the threshold value is set to 11/9, then the algorithm terminates with
an 11/9-MMS allocation, with all chores being allocated. However, the best
approximation achievable using this method is an open question.

In summary, researchers have been exploring ways to approximate the MMS
allocation for situations where it does not always exist, such as in the case
of chores. The latest development is an algorithm that can achieve an 11/9-MMS
allocation by converting instances to IDO instances and using a mechanism
similar to the FFD algorithm for allocating chores. This algorithm has been
shown to be polynomial time, and the authors also provided a PTAS and a
polynomial time algorithm for 5/4-MMS allocation. However, the best
approximation achievable using this method is still unknown.

Algorithm 10 Algorithm for $11/9$-MMS 1:Assume IDO instance and threshold
values of each agent $(\alpha_{1},\alpha_{2},\ldots,\alpha_{3})$ 2:Assume
$\forall i,\mu_{i}=1$ 3:for $i\leftarrow 1\textit{ to }n$ do 4:
$K\leftarrow\emptyset$ 5: for $k\leftarrow 1\textit{ to }m$ do 6: if $j\exists
N,\;v_{j}(A_{j}\cup M_{k})\leq\alpha_{j}$ then 7: $K\leftarrow K\cup M_{k}$ 8:
end if 9: end for 10: $M\leftarrow M\setminus K$ 11: Let $j$ be the agent who
is allocated K, i.e., $v_{j}(K)\leq\alpha_{j}$ 12: $A_{j}\leftarrow K$ and
$N\leftarrow N\setminus j$ 13:end forreturn Allocation $A$

Figure 7: Summary of MMS fairness notion for indivisible chores. The Violet
box (number 1) represents the polynomial-time algorithm. The blue box (number
2) represents the exponential-time algorithm. The green box (number 3)
represents an open question. The grey box (number 4) represents such an
allocation does not exist.

###  5.2 Fair and Efficient Allocation

#### Efficient EF1 allocations

When valuations are negative, the existence and complexity of an allocation
that satisfies EF1 (envy-freeness up to one item) and PO (proportional)
properties is still an open problem. However, alternative fairness criteria,
such as EF${}^{1}_{1}$ (envy-freeness up to one item and one penny) introduced
in [44], do exist and can be efficiently computed along with fPO (fractional
proportional) allocation. Additionally, the problem of maximizing utilitarian
welfare while ensuring EF1 allocation is not fully explored in chore
allocation.

In summary, despite the challenge posed by negative valuations, there exist
fair allocation criteria that can be efficiently computed, and there is still
room for further research in maximizing welfare while satisfying fairness
constraints in the context of chore allocation.

#### Efficient PROP1 allocations

In a recent study, Branzei et al. [44] demonstrated the existence of a
strongly polynomial-time algorithm for solving the chores problem. This
algorithm guarantees a weighted PROP1 and PO allocation, provided the number
of agents or items is fixed. The underlying algorithm used in their study is
similar to the pure market equilibria approach proposed by Barman et al. [29].

The researchers also established that for any chore division problem, there
exists an indivisible allocation $A$ that is Pareto optimal in the divisible
problem and satisfies weighted-EF$1^{1}$ and weighted-Prop1. Furthermore, they
computed a competitive allocation $A^{\prime}$ and demonstrated that an
integral competitive allocation $A$ with a budget satisfying could be
constructed from $A^{\prime}$. This allocation is Pareto optimal by the first
welfare theorem.

In summary, Branzei et al. proposed an efficient algorithm for solving the
chores problem and provided theoretical guarantees for the Pareto optimality
and efficiency of their proposed allocation. Their findings provide valuable
insights into the design of allocation algorithms for resource allocation
problems. It is important to note that the existence of PROPX and PO
allocation for chore allocation problems remains an open question.

Figure 8: Summary of efficient fairness notion for indivisible chores. The
Violet box (number 1) represents the polynomial-time algorithm. The blue box
(number 2) represents exponential time. The green box (number 3) represents an
open question.

We summarize the results discussed in this section in the following Table 1.
The red line represents impossibilities. And brown line represents open
questions in the literature. Even though there is a rich literature, there are
still a lot of open problems that need to be resolved.

Table 1: Summary of Fair Division for Indivisible Goods or/and Chores

Fairness | Efficiency | Agents | Items | Valuations | Existence | Computation | Algorithm | Paper
---|---|---|---|---|---|---|---|---
EF | any | any | any | any | no | NP-Hard | - | -
EF1 | - | any | goods | additive | yes | polynomial | round robin |  [48] [48]
chores |  [13] [13]
comb |  | doubly round
---
robin elimination
EF1 | - | any | goods | general | yes | polynomial |  | envy cycle
---
elimination
[80] [80]
chores |  modified envy cycle elimination | [36] [36]
comb
EF1 | - | any | any | arbitrary | ? | ? | ? | ?
EF1 | PO | any | any | general | ? | ? | ? | ?
|  |  | goods |  | yes |  | pseudo
---
polynomial
market equilibria |  | [30]
---
[30]
|  |  | chores |  |  |  |  |
EF1 | PO | any | comb | additive | ? | ? | ? | ?
EF1 | USW | any | any | any | yes | NP-Hard | ? | ?
EF1 | USW | any | good | additive | yes | exponential | dynamic programming |  [15] [15]
EFX | any | any |  | goods/
---
chores
general | ? | ? | ? | ?
EFX | any | any |  | goods/
---
chores
additive | ? | ? | ? | ?
EFX | - | any | comb |  | lexicographic sub
---
domain of additive
no |  |  |  [70] [70]
|  |  | goods |  | yes | exponential | leximin++ |  [89] [89]
|  |  | chores |  |  |  |  |
EFX | - | any | comb | IDO general | ? | ? | ? | ?
|  |  | goods |  |  |  | envy cycle |  [89] [89]
|  |  | chores |  | yes | polynomial | envy cycle |  [78] [78]
EFX | - | any | comb | IDO additive | ? | ? | ? | ?
EFX | - | any | goods | 2-value instances | yes | polynomial | match&freeze |  [6] [6]
EFX |  |  | goods |  | interval valuation
---
$[v_{i}-2v_{i}]$
yes | polynomial | modified RR |  [6] [6]
EFX | - | $n=3$ | goods | additive | yes |  | pseudo
---
polynomial
|  [50] [50]
| - |  | goods |  |  |  |  | cut-choose,
---
leximin++
[89] [89]
| - |  | chores |  |  |  | cut-choose |  Implied [104] [104]
EFX | - | $n=2$ | comb | general | yes | exponential | cut-choose | Implied
EFX | - | $n=2$ | goods | additive |  | polynomial | envy cycle |  [89] [89]
1/2 EFX | - | any | goods | subadditive | yes | polynomial | envy cycle |  [89] [89]
0.618 EFX | - | any | goods | additive | yes | polynomial |  |  [9] [9]
| EFX with
---
charity
- | any | goods | additive | yes | polynomial |  |  [46] [46]
| approx EFX
---
with charity
- | any | goods | additive | yes | polynomial |  |  [51] [51]
approx EFX | any | any |  | chores/
---
comb
any | ? | ? | ? | ?
| EFX with
---
charity
any | any |  | chores/
---
comb
any | ? | ? | ? | ?
Continued on next page |  |  |  |  |

Fairness | Efficiency | Agents | Items | Valuations | Existence | Computation | Algorithm | Paper
---|---|---|---|---|---|---|---|---
EFX | PO | $n=2$ | goods |  | general nonzero
---
marginal utility
| exponential |  | cut-choose,
---
leximin++
[89] [89]
EFX | PO | any | goods |  | identical general
---
non zero marginal
| exponential | leximin++ |  [89] [89]
EFX | PO | any | goods | 2-value instances |  | exponential | MNW |  [6] [6]
| EFX, PROPX,
---
4/3 MMS
|  | chores | IDO additive |  | polynomial | envy cycle |  [78] [78]
PROP | any | any | any | any | no | NP-Hard | ? | ?
PROP1 | - | any | goods | additive | yes | polynomial |  EF1 implies PROP1 for additive |  |  [48] [48]
---
[13] [13]
chores
comb
| connected
---
PROP1
- | any | any | additive | yes | polynomial |  |  [13] [13]
wPROP1 | fPO | any | any | additive | yes | polynomial | market equilibria |  [20] [20]
PROP1 | USW | any | goods | additive | yes | exponential |  | dynamic
---
programming
[15] [15]
any | ? | ? | ?
| PROPX
---
wPROPX
- | any | goods | additive | no | - | - |  [13] [13]
|  |  | comb |  |  |  |  | Implied
|  |  | chores |  |  | polynomial | envy cycle, bid and take |  [78] [78]
PROPX | PO | any | chores | additive | ? | ? | ? | ?
PROPX | USW | any | chores | additive | yes | NP-Hard | ? | ?
PROPm | - | any | goods | additive | yes | polynomial |  | divide and conquer
---
plus graph reassigning
[24] [24]
PROPm |  |  | comb | additive | ? | ? | ? | ?
PROPm | PO | any | any | additive | ? | ? | ? | ?
PROP | USW | any | any | additive | yes | NP-Hard | ? | ?
MMS | - | any | any | additive | no | NP-Hard | - |  [90] [90] [21] [21]
MMS | - | any | any | IDO | yes | NP-Hard |  |  [41] [41]
MMS | - | any | goods | 0,1 | yes | polynomial | RR with modification |  [41] [41]
MMS | - | any | goods | 0,1,2 | yes | polynomial | RR with modification |  [8] [8]
MMS | - | $m\leq n+3$ | goods | additive | yes |  |  |  [41] [41]
MMS | - | $n=2$ | goods | additive | yes | exponential | cut and choose |  [41] [41]
3/4 MMS | - | any | goods | additive | yes | polynomial |  valid reduction, clustering, bag filling |  [63] [63]
3/4+1/12n | - | any | goods | additive | yes | exponential |  [63] [63]
11/9 MMS | - | any | chores | additive | yes | exponential |  modified bag filling with threshold |  [71] [71]
5/4 MMS | - | any | chores | additive | yes | polynomial |  [71] [71]
$\alpha$-MMS | any | any | comb | additive | no | - | - |  [75] [75]
$\alpha$-MMS | PO | any | any | additive | ? | ? | ? | ?
$\alpha$-MMS | USW | any | any | any | yes | ? | ? | ?

##  6 Combination of Indivisible Goods and Chores

###  6.1 Fair Allocation

#### Envy-freeness up to one item (EF1):

[13] proposed a double round-robin algorithm for the combination of goods and
chores when agents have additive valuations for computing EF1 allocation in
polynomial time. The algorithm involves two phases and applies the round-robin
method twice, once in a clockwise direction and once in an anticlockwise
direction. During the first phase, the algorithm allocates chores to agents
based on their non-positive utility using the round-robin algorithm. In the
second phase, the algorithm allocates the remaining goods to agents using the
reversed round-robin algorithm, starting with the agent who chose the last in
the first phase.

For more general valuations, [36] presented a modified version of the envy
cycle elimination, which allocates goods and chores to agents in a doubly
monotone instance where the items are indivisible. The algorithm runs in two
phases. In the first phase, the algorithm allocates items that are goods for
at least one agent using the envy-cycle elimination algorithm [80]. However,
this is done only for the subgraph of agents who consider the item a good. In
the second phase, the algorithm allocates items that are chores to the
remaining agents using the top-trading envy cycle elimination algorithm. The
paper’s authors have proven that the modified algorithm returns an EF1 (envy-
free up to one item) allocation. Additionally, they maintain the invariant
that the partial allocation remains EF1 at every algorithm step. Moreover, the
algorithm terminates in polynomial time.

#### Envy-freeness up to any item (EFX):

[69] investigated the problem of finding EFX allocation in the presence of
lexicographic valuations, a subclass of additive valuations, where items can
be goods or chores. The authors demonstrated that an envy-free allocation
existence is computationally hard for instances where only chores are
considered under lexicographic preferences, in contrast to the polynomial-time
solvability of the goods-only case. They also showed that even in the case of
combinations of goods and chores, an EFX allocation may not exist. Despite
these challenges, the authors identified a domain restriction where EFX
allocations are guaranteed to exist and can be computed efficiently.
Furthermore, they showed that a different notion of fairness, maximin share
(MMS), always exists and can be computed efficiently for any mixed instance
with lexicographic preferences.

#### Proportionality up to one item (PROP1):

In the case of additive valuations, the EF1 allocation implies the PROP1
allocation. Consequently, any algorithm that gives EF1 allocations also
guarantees PROP1. [13] [13] proved that a contiguous PROP1 allocation of a
combination of goods and chores could be computed in polynomial time for
additive utilities. This exciting result paves the way for practical
algorithms that can achieve fairness and connectivity in allocating
indivisible goods and chores.

Algorithm 11 EF1 for Combination of Goods and Chores with General Valuations
1:Initialize $A\leftarrow(\emptyset,\emptyset,\ldots,\emptyset)$ 2:// For each
good  3:for $k\leftarrow 1\textit{ to }m$ do 4:
$V^{g}\leftarrow{i\in[n];g\in[m];|v_{ig}\geq 0}$ // Agents who value the good
positively  5: Choose a source agent $j$ from the envy graph $G^{g}_{A}$ 6:
$A_{j}\leftarrow A_{j}\cup{k}$ 7: while $G_{A}$ has a directed cycle $C$ do 8:
$A\leftarrow A^{C}$ // Remove the cycle from the allocation  9: end while
10:end for 11:// For each chore  12:for $k\leftarrow 1\textit{ to }m$ do 13:
if there is no sink agent in envy graph $G_{A}$ then 14: $C\leftarrow$ any
cycle in $T_{A}$ 15: $A\leftarrow A^{C}$ // Remove the cycle from the
allocation  16: end if 17: Choose a sink agent $j$ from the envy graph $G_{A}$
18: $A_{j}\leftarrow A_{j}\cup{k}$ 19:end forreturn Allocation $A$

#### Proportionality up to any item (PROPX):

PROPX requires that each agent receives a utility that is at least
proportional to their share, even after we add a small good allocated among
the remaining agents to their bundle or remove the smallest chore (least
negative) from the agent’s bundle as mentioned in Definition 3.8. However,
PROPX may not exist even for three agents when items are only goods [20].
Therefore, it can be concluded that PROPX may not exist in the case of a
combination of goods and chores. However, this is a much less explored domain.
Although we know that PROPm exists in polynomial time for goods and PROPX
exists in polynomial time for chores, we have yet to explore a stronger notion
than PROP1 but weaker for proportionality in the case of goods and chores.

#### Maximin Share (MMS):

When allocating indivisible goods or chores among a group of agents, MMS
allocation is often used to ensure fairness. However, the MMS allocation may
not exist when goods or chores are indivisible. Hence, in the case of the
combination of goods and chores, MMS allocation may not exist.

To address this issue, researchers have explored the concept of approximate
MMS ($\alpha$-MMS) allocation, which aims to allocate goods or chores to
approximate the ideal MMS allocation. The best-known approximate solution for
$\alpha$-MMS in goods is $3/4+1/12n$, where $n$ is the number of agents.

In a recent study, [75] introduced the problem of finding the (near) best
$\alpha\in(0,1]$ for which an $\alpha$-MMS allocation exists. They showed that
an $\alpha$-MMS allocation may not always exist for any given $\alpha>0$,
making it challenging to solve the problem for a fixed $\alpha$. To tackle
this challenge, the authors developed an efficient algorithm to find an
$\alpha$-MMS and Pareto Optimal (PO) allocation for the maximum
$\alpha\in(0,1]$ for which it exists. This approach can provide a fair
allocation of indivisible goods or chores, even when an exact MMS solution is
not possible.

###  6.2 Fair and Efficient Allocation

#### Efficient EF1 allocations

The concept of allocating goods and chores fairly and efficiently has been
studied recently. In Section 5, it was noted that when valuations are
negative, it is still an unsolved issue to find an allocation that meets both
EF1 (envy-freeness up to one item) and PO (proportional) properties. While
there is a pseudo-polynomial time algorithm for determining PO and EF1
allocation in the case of goods, the existence and complexity of such an
allocation for a combination of goods and chores remain unclear. However, [2]
has explored a weaker form of EF1 and PO for mixed sets of goods and chores.

Another area of interest is maximizing utilitarian welfare while ensuring EF1
allocation in mixed good and chore allocation. Unfortunately, this problem has
not been fully explored yet.

#### Efficient PROP1 allocations

The paper by [20] [20] presents a strongly polynomial time algorithm for
computing allocations that are Pareto optimal and PROP1 for both goods and
chores. They demonstrate that an fPO and PROP1 allocation always exists, even
for mixed utilities and any number of agents. To achieve this, they first
compute a proportional fPO allocation with divisible items and then round it
to preserve the fPO property and ensure PROP1. The paper by [44] and [29] use
the same methodology but rely heavily on the concept of competitive
equilibrium with equal incomes (CEEI), which does not apply to economies with
a mixture of goods and chores. Therefore, the authors of [20] construct a
rounding procedure that does not rely on equilibrium prices and applies to any
fPO proportional allocation of divisible items with an acyclic consumption
graph. This is achieved by starting with an equal division and then finding a
Pareto-dominating allocation through sequential cyclic trades, ensuring the
consumption graph remains acyclic. The algorithm picks an agent who shares
some items with other agents and rounds all their fractions to their
advantage, breaking all other partial shares in the corresponding sub-tree.
The acyclicity of the tree ensures that the algorithm terminates and returns a
PROP1 allocation.

In conclusion, despite the challenges posed by the combination of goods and
chores, there are fair allocation criteria that can be computed efficiently.
However, there is still much room for further research, particularly in
maximizing welfare while ensuring fairness constraints. We summarize the
results of goods and chores in the following image.

Figure 9: Summary of fairness and efficient notion for indivisible goods and
chores. The Violet box (number 1) represents the polynomial-time algorithm.
The blue box (number 2) represents exponential time. The red box (number 3)
represents Pseudo-polynomial time. The green box (number 4) represents an open
question. The grey box (number 5) represents such an allocation does not
exist.

##  7 Mixed Indivisible and Divisible Goods and Chores

The world of fair division literature has long been fixated on the concept of
items being either divisible or indivisible. But what happens when reality
throws us a curveball, and we’re suddenly faced with the challenge of
allocating a mixed bag of divisible and indivisible items? As it turns out,
this is a very real predicament many of us encounter daily, as evidenced by
the classic example of room sharing and rent division. This scenario poses the
intriguing possibility of some items being allocated fractionally while others
must be claimed in their entirety. To break it down even further, let $D={k\in
M\mid k\mbox{ is divisible item }}$ and $I={k\in M\mid k\mbox{ is indivisible
item }}$, with $D\cap I=\emptyset\mbox{ and }D\cup I=M$. So the question
becomes: how do we navigate this complex terrain of mixed divisible and
indivisible items to achieve a fair and equitable division for all involved?

The study of fair division with mixed types of resources was initiated by [32]
in their research, in which they explored envy-freeness for mixed goods,
including both indivisible and divisible items. Further, [36] delved into
envy-freeness for mixed goods/chores, encompassing both indivisible
goods/chores and divisible chores. While they also attempted to investigate
envy-freeness for indivisible chores and divisible goods, their research
yielded limited positive results, leaving room for further exploration.

Since envy-freeness cannot be achieved for indivisible items, relaxation
techniques must be considered. However, EF1 (envy-freeness up to one item) can
be too weak when only divisible resources are present. This raises the
question of whether we can combine a relaxation notion that captures EF and
EF1. For instance, imagine Agastya and Noorie are tasked with cleaning their
house (a divisible chore) and dividing a bicycle between them (an indivisible
good). What would be a fair allocation in this situation? If we use EF1 for
indivisible items and EF for divisible items, both would clean the house
equally, and Agastya would get the bicycle. However, is this allocation truly
fair? A fairer allocation would be for Agastya to clean the house and receive
the bicycle. This highlights the need to reconsider our notions of fairness
and efficiency in such settings.

[32] proposed a new concept called EFM (envy-freeness for mixed goods), which
applies to both indivisible and divisible goods. This notion was then extended
by [36] to include indivisible goods/chores and divisible goods/chores. In
essence, EFM means that any agent who owns divisible goods should not be
envied, any agent who owns divisible chores should not envy anyone else, and,
subject to these conditions, any pairwise envy should be EF1. In summary, EFM
provides a more comprehensive and nuanced approach to achieving fairness in
allocating mixed types of resources. Next, we define EFM for various
scenarios.

##### Divisible Good, Indivisible Good ($D,I$ both consists of goods)[32]

In the case of divisible and indivisible goods, an allocation is considered
EFM if an agent’s allocation contains a divisible good, then other agents
compare their allocation to that agent using the EF criterion. However, if the
allocation contains only indivisible goods, then the other agents compare
their allocation to that agent’s bundle using EF1. More formally, $\forall
i,j\in N$,

$\displaystyle\begin{rcases}v_{i}(A_{i})\geq v_{i}(A_{j})&;\mbox{ $\exists
k\in A_{j}$ s.t. $k$ is divisible good}\\\ v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus k)&;\mbox{ $\exists k\in A_{j};A_{j}\subseteq
I$}\end{rcases}\mbox{{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
is EFM}}}$

##### Divisible Good, Indivisible Chore($D$ consists of goods, $I$ consists of
chores)[36]

In the case of divisible goods and indivisible chores, an allocation is EFM if
an agent’s allocation contains a divisible good, then other agents compare
their allocation to that agent using the EF criterion. However, if the
allocation contains any indivisible chore, the agent compares their allocation
to other agents’ allocation using EF1. More formally, $\forall i,j\in N$,

$\displaystyle\begin{rcases}v_{i}(A_{i})\geq v_{i}(A_{j})&;\mbox{ $\exists
k\in A_{j}$ s.t. $k$ is divisible good}\\\ v_{i}(A_{i}\setminus k)\geq
v_{i}(A_{j})&;\mbox{ $\exists k\in
A_{i};v_{ik}<0$}\end{rcases}\mbox{{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
is EFM}}}$

##### Divisible Chore, Indivisible Good($D$ consists of goods, $I$ consists of
chores)[36]

In the case of divisible chores and indivisible goods, an allocation is EFM if
an agent’s allocation contains a divisible chore, then the agent compares
their allocation to other agents’ allocation using the EF criterion. However,
if the allocation contains an indivisible good, the other agents compare their
allocation to that agent using EF1 More formally, $\forall i,j\in N$,

$\displaystyle\begin{rcases}v_{i}(A_{i})\geq v_{i}(A_{j})&;\mbox{ $\exists
k\in A_{i}$ s.t. $k$ is divisible chore}\;\mbox{or}\\\ v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus k)&;\mbox{ $\exists k\in
A_{j};v_{ik}>0$}\end{rcases}\mbox{{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
is EFM}}}$

##### Divisible Chore, Indivisible Chore ($D$ consists of chores, $I$ consists
of chores) [36]

Lastly, in the case of divisible and indivisible chores, an allocation is EFM
if an agent’s allocation contains a divisible chore, then other agents compare
their allocation to that agent using the EF criterion. However, if the
allocation contains an indivisible chore, the agent compares their allocation
to other agents’ allocation using EF1. More formally, $\forall i,j\in N$,

$\displaystyle\begin{rcases}v_{i}(A_{i})\geq v_{i}(A_{j})&;\mbox{ $\exists
k\in A_{i}$ s.t. $k$ is divisible chore}\;\mbox{or}\\\ v_{i}(A_{i}\setminus
k)\geq v_{i}(A_{j})&;\mbox{ $\exists k\in A_{i};A_{i}\subseteq
I$}\end{rcases}\mbox{{\em{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
is EFM}}}$

The paper by [32][32] examines the problem of fairly dividing a set of
heterogeneous divisible goods and a collection of indivisible goods. The
authors prove that an allocation that satisfies envy-freeness for mixed
resources (EFM) for mixed goods with additive valuations for divisible goods
and general monotone indivisible goods always exists. The algorithm used to
achieve this requires an oracle for computing a perfect allocation in cake
cutting but can compute an EFM allocation in a polynomial number of steps. The
algorithm starts by obtaining an arbitrary EF1 allocation (using the Envy-
cycle elimination algorithm) of the indivisible goods, and then allocates the
divisible goods to obtain an EFM allocation. While the paper’s algorithm is
only proven for additive valuation for indivisible goods, [36] shows that it
also works for general monotone valuation.

Additionally, the authors present two algorithms for computing an EFM
allocation for special cases without using the perfect allocation oracle. The
first algorithm is for two agents with general additive valuations in the
Robertson-Webb model, and the second is for any number of agents with piece-
wise linear valuation functions.

In the Robertson-Webb model, the authors present an algorithm that computes an
$\epsilon$-EFM allocation with a polynomial running time complexity that is
dependent on the number of agents, the number of indivisible goods, and
$1/\epsilon$. The authors note that it is unclear whether an EFM allocation
can be computed in a finite number of steps in the Robertson-Webb model in
general. The algorithm does not require a perfect allocation oracle, which is
an appealing result due to its polynomial running time complexity. In
contrast, a bounded exact EFM protocol, if it exists, is likely to require a
large number of queries and cuts. For instance, in the special case when all
resources are divisible, EFM reduces to EF in cake cutting, and the best-known
protocol [19] for this problem has a very high query complexity (a tower of
exponents of $n$).

[36][36] investigates a mixed model consisting of indivisible items
(goods/chores) and a divisible heterogeneous chore. The authors extend the
definition of EFM to this model and prove that an EFM allocation always
exists. They use a similar algorithmic approach to that in [32], starting with
an arbitrary EF1 allocation of the indivisible item and then allocating the
cake to obtain an EFM allocation.

Finally, the authors of [36] also study a mixed model with indivisible chores
and divisible goods, which proves to be more challenging. Unlike previous
cases, it is not possible to start with an arbitrary EF1 allocation of the
indivisible items and allocate the cake to obtain an EFM allocation. However,
the authors show that an EFM allocation exists for two special cases in this
model: when each agent has the same ranking over the chores, and when the
number of chores is at most one more than the number of agents. In particular,
for two agents, an EFM allocation always exists in this setting, and with $n$
agents, $m$ additive indivisible chores, and cake, where $m\leq n+1$, an EFM
allocation exists.

We have summarized the results for a mixed setting of divisible and
indivisible item instances in Table 2. From the table, it can be observed that
this domain has been relatively less explored but is highly relevant and has
the potential to yield exciting findings.

Table 2: Summary of Fair Division for Mixed Model

Fairness | Agents |  | Divisible
---
Item
| Divisible
---
Valuation
| Indivisible
---
Item
| Indivisible
---
Valuation
Paper | Computation | Details
EFM | any | good | additive | good | general |  [32] [32] | polynomial | With perfect allocation oracle
EFM | any | good | additive | chores | general | ? | ? |
EFM | any | chores | additive | good | general | [36] [36] | polynomial | With perfect allocation orcale
chores
combination
|  | good |  | good | general |  [32] [32] | polynomial |
|  | good |  |  |  |  |  |
EFM | $n=2$ | chore | general | combination | general | ? | ? | With perfect allocation orcale
|  |  |  | good |  |  | polynomial |
|  | good |  |  |  | ? | ? |
EFM | any | chore | piece wise linear | combination | general | ? | ? | With perfect allocation orcale
| $n=2$ | good | additive |  |  |  |  |
| any | good | additive identical for n-1 |  |  |  |  |
EFM | $m\leq n+1$ | good | additive | chore | general | [36] [36] | polynomial | With perfect allocation orcale
|  |  |  | good |  |  [32] [32] | polynomial |
|  | good |  |  |  |  |  |
$\epsilon$-EFM | any | chores | additive | combination | general | ? | ? | Without perfect allocation orcale

##  8 Summary of Complexity Results for Fair Division

The problems of computing allocations that maximize the egalitarian welfare
(utility of the worst-off agent) or Nash welfare (geometric mean of the
utilities of agents) have been shown to be NP-hard, as demonstrated in prior
research by [86]. Moreover, even computing an exact maximin share for an agent
with additive valuations has been proven to be an NP-complete problem, as
shown through a reduction from the NP-hard problem of Partition. Additionally,
in the case of agents with binary additive valuations for goods, checking for
the existence of an envy-free (EF) allocation has also been shown to be NP-
complete, as demonstrated in studies by [14, 69]. Furthermore, the problem of
making efficiency improvements in fair allocation has been identified as NP-
hard in research by [16], further highlighting the computational complexity of
these allocation problems.

In addition to the computational complexity, it is important to consider the
likelihood of finding a fair allocation in real-world scenarios. Research has
explored the conditions under which a fair allocation is likely to exist or
not, shedding light on the practical feasibility of achieving fairness in
allocation mechanisms.

##  9 Other Important Results

In this section, we will provide a brief overview of other important aspects
in the field of fair division, including the likelihood of finding a fair
allocation, and the price of fairness.

###  9.1 Likelihood of Finding a Fair Allocation

[55] was the first to address this question, under the assumption that
utilities are additive and each agent’s utilities for individual items are
drawn from probability distributions. They established that an envy-free
allocation is likely to exist with high probability when the number of items
$m$ is at least $\Omega(nlogn)$, but not when $m=n+o(n)$. [98] investigated
the asymptotic existence of proportional allocations - which are weaker than
envy-free allocations under the additivity assumption - and showed that such
allocations occur with high probability provided that either $m$ is a multiple
of $n$ or $m=w(n)$.

[81] showed that EFX allocations, which satisfy envy-freeness up to any item,
exist with high probability for any number of agents and items under the
assumption that the valuations of the agents are drawn at random from a
probability distribution. When agents’ valuations for individual items are
randomly drawn from a probability distribution, they show that the classical
round-robin algorithm is likely to result in an envy-free allocation,
particularly when the number of items $m$, satisfies the condition
$m=\Omega(n\log n/\log\log n)$. Furthermore, they demonstrated that a
proportional allocation is likely to exist with high probability as long as
the number of items, $m$, is greater than or equal to the number of agents,
$n$. Additionally, an allocation that satisfies envy-freeness up to any item
(EFX) is likely to be present for any relationship between $m$ and $n$. They
also demonstrated the challenge of showing the existence of EFX allocations,
as in instances with two agents there can be as few as two EFX allocations,
while the number of EF1 allocations is always exponential in the number of
items.

[8] undertook a probabilistic analysis and proved that in randomly generated
instances, maximin share allocations exist with high probability, motivated by
the apparent difficulty in establishing lower bounds in calculating
$\alpha$-MMS. Furthermore, [90] showed that the non-existence of MMW (maximin
share with weights) allocation requires a number of items that is exponential
in the number of players. In contrast, if the number of items is only slightly
larger than the number of players, an MMS allocation is guaranteed to exist
[41]. This raises the question of what is the largest number of items for
which an MMS allocation is guaranteed to exist.

In conclusion, the likelihood of finding a fair allocation depends on various
factors such as the specific fairness notion, the type of valuations, and the
number of agents and items involved. Probabilistic analyses have been
conducted to understand the conditions under which fair allocations are likely
to exist, shedding light on the practical feasibility of achieving fairness in
real-world scenarios.

###  9.2 Price of fairness

The concept of the price of fairness quantitatively measures the tradeoff
between fairness and social welfare. It represents the ratio of the maximum
welfare of any allocation to the maximum welfare of any allocation that
satisfies the desired fairness notion, and it provides insights into the
efficiency loss incurred in achieving fairness.

The authors, [47], investigated the effect of fairness on the efficiency of
resource allocations. They examined three fairness criteria, namely
proportionality, envy-freeness, and equitability, for allocations of divisible
and indivisible goods and chores. They presented a set of findings on the
price of fairness under each of these criteria that quantify the loss in
efficiency in fair allocations compared to optimal ones.

For indivisible goods, the authors derived an exact bound of $n+1/n$ on the
price of proportionality, while they demonstrated that the price of envy-
freeness is $\theta(n)$. In contrast, for indivisible chores, they established
an exact bound of $n$ on the price of proportionality, but both the price of
envy-freeness and equitability are infinite. These results indicate that, in
the case of indivisible chores, envy-freeness and equitability are typically
incompatible with efficiency.

Their work provides insights into the trade-off between efficiency and
fairness in resource allocation, considering both divisible and indivisible
goods. However, a limitation of their study is that fairness notions may not
always be satisfied for indivisible goods, which they addressed by ignoring
such instances in their analysis of the price of fairness. This omission may
not capture certain scenarios that can arise in practice. Furthermore, the
assumption that envy-free allocations are always proportional may not
necessarily hold true, as there are instances where proportional allocations
exist but envy-free allocations do not.

In the study by [33], the focus shifts from classical fairness notions, such
as envy-freeness, proportionality, and equitability, which may not always be
achievable for indivisible goods, to notions with guaranteed existence,
including envy-freeness up to one good (EF1), balancedness, maximum Nash
welfare (MNW), and leximin. They also introduce the concept of the strong
price of fairness, which captures the efficiency loss in the worst fair
allocation. They provide tight or asymptotically tight bounds on the worst-
case efficiency loss for allocations satisfying these notions, for both the
price of fairness and the strong price of fairness.

Specifically, the study shows that for the price of EF1, a lower bound of
$\Omega(\sqrt{n})$ and an upper bound of $O(n)$ are provided. Additionally, it
is shown that two common methods for obtaining an EF1 allocation, namely the
round-robin algorithm and MNW, have a price of fairness of linear order (with
the exact price being n for round-robin), indicating that these methods cannot
improve the upper bound for EF1. For MNW, MEW, and leximin, an asymptotically
tight bound of $\theta(n)$ on the price of fairness is proven. The results
suggest that round-robin is a promising allocation method, as it produces an
EF1 allocation with high welfare, is simple and intuitive, and always produces
a balanced allocation.

The authors of [26] address the impact of fairness guarantees on social
welfare in the allocation of indivisible goods by resolving the price of two
well-known fairness notions: envy-freeness up to one good (EF1) and
approximate maximin share (MMS). They show that the price of fairness is
$O(\sqrt{n})$ for both EF1 and 1/2-MMS, using different techniques. The
$\Omega(\sqrt{n})$ lower bound due to [33] is matched by their upper bound,
which holds for the more general class of subadditive valuations, as opposed
to additive valuations. Their work therefore resolves this open question for
all valuation classes between additive and subadditive and also settles the
price of proportionality up to one good (Prop1) as $\theta(\sqrt{n})$ for
additive valuations.

For the 1/2-MMS fairness notion and additive valuations, the authors also show
that the price of fairness is $\theta(\sqrt{n})$ using a different algorithm.
They prove that for a fixed $\epsilon>0$, a $(1/2-\epsilon)$-MMS allocation
with welfare within $O(\sqrt{n})$ factor of the optimal can be computed in
polynomial time. Overall, their main contribution is comprehensively settling