Fair Division of Indivisible Goods: A Survey

1 Introduction

Fair division is concerned with the fundamental task of fairly partitioning or allocating a set of resources to a set of people with diverse and heterogeneous preferences over these resources. The associated theory originated in the works of Steinhaus [1949], Banach, and Knaster (see [Dubins and Spanier, 1961]), and has been in the focus of economics, mathematics and computer science for the better part of the last century. Most of the classic work on the problem has been devoted to the fair division of infinitely divisible resources, where "fair" here may have different interpretations, with two predominant ones being proportionality [Steinhaus, 1949] and envy-freeness [Gamow and Stern, 1958; Varian, 1974].

Compared to the divisible setting, the fair division of indivisible resources, which we refer to as discrete fair division, turns out to be inherently more challenging. Indeed, it is clear that no reasonable fair solution can be guaranteed in some cases, e.g., when there is a single valuable item. A typical remedy to this situation is to employ randomization, and aim for fairness (e.g., envy-freeness) in expectation.

A fundamentally different approach to discrete fair division came via the introduction of appropriate relaxations of envyfreeness and proportionality, originating in the works of Lipton et al. [2004], Budish [2011], Caragiannis et al. [2019b], Gourv`es et al. [2014], which are geared to escape adverse examples. The main notions that were introduced in this literature were envy-freeness up to one good (EF1), envy-freeness up to any good (EFX) and maximin share fairness (MMS).

Since then, work on the topic has flourished, centered around fundamental questions about the existence and the efficient computation of allocations satisfying these or other related fairness criteria.

More generally, over the past decade, discrete fair division had been in the epicenter of computational fair division, for several different fairness notions and a variety of different settings. In this survey, we highlight the main contributions of this literature, the most significant variants of the main setting, as well as some of the major open problems in the area.

1.1 The setting

For the general discrete fair division problem we consider here, there is a set N of n agents and a set M of m goods which cannot be divided or shared. Each agent i is equipped with a valuation function vi : 2M → R≥0, which assigns a non-negative real number to each possible subset of items and is normalized, i.e., vi(∅) = 0. In this survey we focus on the case where the valuation function of each agent i is also assumed to be additive, so that vi(S) = ∑g∈S vi(g) for any subset of items S ⊆ M; vi(g) is used as a shortcut for vi({g}). Other types of valuation functions have also been studied and are briefly discussed but, unless otherwise specified, in what follows we refer to the additive case. An allocation is a tuple of subsets of M, A = (A1, . . . , An), such that each agent i ∈ N receives the bundle Ai ⊆ M, Ai ∩Aj = ∅ for every pair of agents i, j ∈ N, and ⋃i∈N Ai = M. The objective is to compute a fair allocation, i.e., an allocation that satisfies a desired fairness criterion.

As already mentioned, since the early fair division literature there are two predominant fairness notions, namely envyfreeness and proportionality. An allocation is said to be envyfree if no agent believes that another agent was given a better bundle, i.e., envy-freeness depends on pairwise comparisons.

Definition 1 (Envy-freeness). An allocation A is envy-free if

vi(Ai) ≥ vi(Aj) for every pair of agents i, j ∈ N.

On the other hand, an allocation is said to be proportional if each agent is guaranteed her proportional share in terms of total value, independently of what others get.

Definition 2 (Proportionality). An allocation A is proportional if vi(Ai) ≥ vi(M)/n or every agent i ∈ N.

Is not hard to see that in the additive case if an allocation is envy-free, then it is also proportional, but the converse is not necessarily true. Envy-free or proportional allocations do not always exist in our setting as indicated by the simple example with two agents and a single good that is positively valued by both. Since only one of the agents receives the good, the other agent gets zero value and, thus, she envies the agent with the item and also does not achieve her proportional share.

Despite this impossibility, one could still be interested in finding envy-free or proportional allocations when they exist. Unfortunately, it turns out that the problem of even deciding whether an instance admits an envy-free (or proportional) allocation is NP-complete, which can be shown via a simple reduction from PARTITION [Lipton et al., 2004]. These straightforward impossibility results have led to the definition of multiple relaxations of these two notions, tailored for discrete fair division.

2 Envy-Freeness up to One Good (EF1)

The first such relaxation of envy-freeness is envy-freeness up to one good (EF1), implicitly introduced by Lipton et al. [2004], but formally defined by Budish [2011]. According to EF1 it is acceptable for an agent i to envy another agent j, as long as there exists a good in j's bundle the hypothetical removal of which would eliminate i's envy towards j.

Definition 3 (EF1). An allocation A is envy-free up to one good (EF1) if, for every pair of agents i, j ∈ N, it holds that vi(Ai) ≥ vi(Aj \ {g}) for some g ∈ Aj .

This instance does not admit any envy-free or proportional allocations. To see this, observe that in any proportional allocation, agent a3 must get at least {g1} or {g2, g3, g4, g5}. In the latter case at least one of a1 and a2 will get no goods, whereas in the former case a1 must get at least three of the remaining four goods and a2 must get at least two, which is not possible. On the other hand, note that the allocation A1 = {g3, g4}, A2 = {g2, g5}, A3 = {g1} is EF1: a2 and a3 are not envious, and the envy of a1 towards a2 and a3 can be eliminated by the hypothetical removals of g5 from A2 and g1 fromA3 respectively.

There are simple, polynomial-time algorithms for computing EF1 allocations. The first such algorithm is known as Envy-Cycle Elimination, and was developed by Lipton et al. [2004] several years before EF1 was formally defined.

Algorithm 1 (Envy-Cycle elimination). Envy-Cycle Elimination operates in phases. In each phase, it first allocates one of the available goods to some agent that no other agent envies. Then, it looks for cycles in the current envy-graph (a graph that contains a node for each agent and a directed edge from agent i to agent j if and only if i envies j), and eliminates them by appropriately reallocating the bundles of the involved agents. This guarantees that there is always an agent no one envies at the beginning of the next phase.

While Envy-Cycle Elimination works for any monotone valuations, for the additive case EF1 allocations can be computed using a much simpler draft algorithm, known as RoundRobin [Caragiannis et al., 2019b].

Algorithm 2 (Round-Robin). Round-Robin fixes an ordering of the agents and, according to this ordering, it lets one agent at a time choose their favorite available good until all goods have been allocated.

To see why Round-Robin achieves EF1 allocations, consider two agents i and j, such that i comes before j in the ordering. As i has the chance to pick a good before j in every single round of the algorithm, i cannot envy j. Of course, agent j may envy agent i. Let g be the first good chosen by i. From that point on, we can see the execution of the algorithm on the remaining goods as a fresh run where now j has the chance to pick a good before i in every round. So j does not envy i's bundle after the removal of good g from it.

While EF1 allocations are rather easy to achieve, as demonstrated above, Caragiannis et al. [2019b] identified an interesting inherent connection between EF1 and the notion of maximum Nash welfare (MNW).

Definition 4 (MNW allocation). An allocation A is said to be a maximum Nash welfare (MNW) allocation if (a) it maximizes the product of agent values ∏i vi(Ai), and (b) in case the Nash welfare of all allocations is 0, it then maximizes the product for the agents with positive value.

In particular, Caragiannis et al. [2019b] showed that MNW allocations are always EF1 and also Pareto optimal (PO). This result shows that there exist allocations that combine fairness with other desired properties, in particular with PO. However, it is known that MNW allocations are generally hard to compute in polynomial time (in fact, it is hard to even approximate them [Hoefer et al., 2021]). Hence, the question of whether it is possible to efficiently compute EF1 and PO allocations was left open. Barman et al. [2018b] recently made progress by computing such allocations in pseudopolynomial time. This brings us to our first open problem.

Open Problem 1. Can an EF1 and PO allocation be computed in polynomial time?

3 Envy-Freeness up to Any Good (EFX)

While EF1 is easy to achieve, in many cases it is a fairly weak fairness notion; an EF1 allocation is considered to be fair for an agent even when a very highly-valued good is hypothetically removed from another agent's bundle (e.g., a house or an expensive car). For example, consider agent a1's perspective of the allocation in Example 1, where the proposed EF1 solution requires the removal of rather valuable goods for the agent. A very natural refinement of the notion is the stricter relaxation of envy-freeness up to any good (EFX) that was introduced in 2016 by Caragiannis et al. [2019b] in the conference version of their work but also somewhat earlier by Gourv`es et al. [2014] under the name near envy-freeness. An allocation is said to be EFX if the envy of an agent i towards another agent j can be eliminated by the hypothetical removal of any good in j's bundle.

Definition 5 (EFX). An allocation A is envy-free up to any good (EFX) if, for every pair of agents i, j ∈ N, it holds that vi(Ai) ≥ vi(Aj \ {g}) for any g ∈ Aj such that vi(g) > 0.

Example 2. Consider again the instance of Example 1. The allocation A1 = {g3, g4}, A2 = {g2, g5}, A3 = {g1} is not EFX, since the envy of a1 towards a2 cannot be eliminated by removing g2 (a1's least favorite good in A2) from A2. Nevertheless, it is easy to modify this allocation to get B1 = {g4, g5}, B2 = {g2, g3}, B3 = {g1} which is EFX. Indeed, the envy of a1 towards a3 can be eliminated by removing g1 from B3, whereas the envy of a2 towards a1 can be eliminated by removing g4 from B1; in both cases the hypothetical removal involves the envious agent's least valued good in the other agent's bundle.

In contrast to EF1, where the existence is guaranteed via simple polynomial-time algorithms, the existence of EFX allocations is a challenging open problem. Procaccia [2020] in fact referred to this as "fair division's most enigmatic question". In the past few years, a sequence of works have positively answered this question for important special cases, centered mainly around two axes: a small number of agents or restricted agents' valuations.

EFX for two and three agents: Plaut and Roughgarden [2020] showed that an EFX allocation always exists and can be efficiently computed when there are only two agents. In a breakthrough paper, Chaudhury et al. [2020] showed that EFX allocations always exist for instances with three agents and described a procedure that computes such an allocation in pseudo-polynomial time; computing EFX allocations for three agents in polynomial time is still an open problem.

EFX for restricted valuations: In [Plaut and Roughgarden, 2020], it was also shown that EFX allocations exist and can be computed in polynomial time when all agents agree on the ordering of the goods with respect to their values. For instances where there are only two distinct possible values that an agent may have for each good, Amanatidis et al. [2021a] showed that EFX allocations exist and can be efficiently computed for any number of agents; later, Garg and Murhekar [2021] showed that this is possible even in conjunction with PO. In fact, Amanatidis et al. [2021a] also demonstrated an interesting connection between EFX and MNW allocations for bi-valued instances, by showing that MNW implies EFX. A similar result was later shown by Babaioff et al. [2021b] for general valuations with binary (i.e., 0 or 1) marginals.

Here, it is instructive to mention that in the related literature, the requirement that the inequality must hold only for positively-valued goods in the definition of Caragiannis et al. [2019b] stated above is often dropped. This stronger version of EFX is usually called EFX0 [Kyropoulou et al., 2020]. In the case of binary valuations, a special case of bi-valued instances, the distinction makes a difference but in more general settings, the existence and computation of EFX0 allocations can be reduced to the existence and computation of EFX allocations; see [Amanatidis et al., 2021a] for a related discussion. It is easy to see that envy-freeness implies EFX0, which implies EFX, which in turn implies EF1.

While the aformentioned results are positive first steps towards showing the existence of EFX allocations, a general positive (or negative) result still remains elusive. This brings us to our second open problem, which is one of the most important open problems in fair division.

Open Problem 2. Does an EFX allocation exist for instances with n ≥ 4 agents and unrestricted additive valuations?

3.1 Relaxations of EFX

Instead of focusing on exact EFX allocations, a growing line of work has taken a different approach by aiming to compute allocations that are approximately EFX, for different notions of approximation. The first such notion is in terms of multiplicative approximations to the values obtained by the agents.

Definition 6 (α-EFX). Let α ∈ (0, 1]. An allocation A is αEFX if, for every pair of agent i, j ∈ N, it holds that vi(Ai) ≥ α · vi(Aj \ {g}) for any g ∈ Aj such that vi(g) > 0.

Plaut and Roughgarden [2020] were the first to pursue this, showing that 1/2-EFX allocations always exist, even for subadditive valuation functions, and later Chan et al. [2019] showed that computing such allocations can be done in polynomial time. The approximation ratio for the additive case was further improved by Amanatidis et al. [2020] to φ-1 ≈ 0.618 by combining Round-Robin and Envy-Cycle Elimination with some appropriate pre-processing. To this end, we have the following open question:

Open Problem 3. What is the best possible α for which αEFX allocations exist?

A positive answer to Open Problem 2 would establish that α = 1 in Open Problem 3, but a negative answer would make the latter open problem very meaningful in its own right. Additionally, as is the case for all of these notions, the next natural question is whether existence can be paired with polynomial-time algorithms for finding such allocations, or whether some kind of computational hardness can be proven.

Another recent approach is that of relaxing the requirement to allocate all available goods. Clearly, if done without any constraints, this makes the problem trivial: simply leaving all goods unallocated, results in an envy-free allocation. However, the objective here is to only leave "a few" goods unallocated (e.g., donate them to charity instead), or remove some goods without affecting the maximum possible Nash social welfare by "too much". On this front, Caragiannis et al. [2019a] showed that it is possible to compute an EFX allocation of a subset of the goods, the Nash welfare of which is at least half of the maximum Nash welfare on the original set. Chaudhury et al. [2020] presented an algorithm that computes a partial EFX allocation, but the number of unallocated goods is at most n - 1, and no agent prefers the set of these goods to her own bundle. The latter result was recently improved by Berger et al. [2021] who showed that the unallocated goods can be decreased to n - 2 in general, and to just one for the case of 4 agents. Finally, Chaudhury et al. [2021] showed that a (1-ε)-EFX allocation with at most a sublinear number of unallocated goods and high Nash welfare can be computed in polynomial time. This motivates the next open problem.

Open Problem 4. Is it possible to achieve an exact EFX allocation by donating a sublinear number of goods?

4 Maximin Share Fairness (MMS)

Besides the two additive relaxations of envy-freeness discussed so far, an extensively studied fairness notion in discrete fair division is maximin share fairness, also introduced by Budish [2011]. The notion can be seen as a generalization of the rationale of the well-known cut-and-choose protocol, which is known to guarantee an envy-free partition of a divisible resource. Here the goal is to give to each agent i goods of value at least as much as her maximin share µni (M), which is the maximum value this agent could guarantee for herself by partitioning the goods into n disjoint bundles and keeping the worst of them. As such, it is a relaxation of proportionality.

Definition 7 (MMS). Let An(M) be the collection of possible allocations of the goods in M to n agents. An allocation A is said to be maximin share fair (MMS) if for each agent i ∈ N, it holds that vi(Ai) ≥ µni (M) = max B∈An(M) min S∈B vi(S).

Example 3. Returning to the instance of Example 1, we can see that µ31 (M) = 6, since it is not possible to partition the items into three sets with strictly more value, but 6 is guaranteed by the partition {g1}, {g2, g3, g4}, {g5}. Similarly, µ32 (M) = 7 and µ33 (M) = 6. Therefore, B1 = {g4, g5}, B2 = {g2, g3}, B3 = {g1}, from Example 2, is an MMS allocation, but A1 = {g3, g4}, A2 = {g2, g5}, A3 = {g1}, from Example 1, is only a 2/3-MMS allocation as agent a1 gets a bundle of value 4 = 2/3·µ31 (M) (see also below).

While it is easy to see that computing MMS allocations or even computing the maximin share of an agent is an NP-hard problem using a reduction from PARTITION, there is a PTAS for the latter task [Woeginger, 1997]. The first breakthrough about MMS was that allocations that guarantee it do not always exist when there are more than two agents [Kurokawa et al., 2018; Kurokawa et al., 2016], yet it is possible to compute approximate MMS allocations. We say that an allocation is α-MMS, for α ∈ (0, 1], if each agent i is guaranteed to get value at least αµni (M). To this end, Kurokawa et al. [2018] showed how to find 2/3-MMS allocations, albeit not in polynomial time. Amanatidis et al. [2017b] matched this guarantee in polynomial time, as did Barman and Krishnamurthy [2020] with a much simpler algorithm. The barrier of 2/3 was broken by Ghodsi et al. [2021] who designed an elaborate (3/4 - ε)-approximation algorithm. A simpler algorithm with a slightly improved approximation guarantee of 3/4 + 1/(12n) was proposed by Garg and Taki [2021]. On the negative side, Feige et al. [2021] recently showed that it is impossible to achieve an approximation bound better than 39/40. Barman and Krishnamurthy [2020] and Ghodsi et al. [2022] designed algorithms for computing approximate MMS allocations for richer classes of valuations (such as submodular, XOS, and subadditive).

Open Problem 5. Is it possible to improve upon the bound of 3/4 + 1/(12n) for additive valuations? Is there a stronger inapproximability bound than 39/40?

As expected, by restricting the number of agents or the space of the valuation functions, one can get stronger results.

MMS for four or fewer agents: When there are only two agents a simple cut-and-choose protocol always produces an MMS allocation. Specifically, the first agent partitions the set of goods as equally as possible (thus the worst set has value equal to her maximin share) and the second agent chooses who gets each of these sets. As suggested above, the first step is computationally hard but producing a (1 - ε)-MMS allocation in polynomial time is still possible. Even though in the general case, the algorithm of Kurokawa et al. [2018] guaranteed a 2/3-approximation, for three or four agents it guarantees an improved 3/4-approximation. The approximation factor for the case of three agents was then improved to 7/8 [Amanatidis et al., 2017b] and later to 8/9 [Gourv`es and Monnot, 2019], whereas for the case of four agents the factor was improved to 4/5 [Ghodsi et al., 2021].

MMS for restricted valuations: It follows by Definition 7 that MMS allocations exist for instances where all agents have identical valuation functions. Bouveret and Lemaˆıtre [2016] showed that, unlike with EFX, the hardest instances for MMS (among all possible instances) are the ones where all agents agree on the ordering of the goods. They also suggested a simple construction of exact MMS allocations when the valuation functions are binary.

This result can be generalized, as MMS allocations always exist and can be computed efficiently for ternary valuation functions [Amanatidis et al., 2017b] and for bi-valued valuation functions [Feige, 2022]. Ebadian et al. [2021] showed that this is also the case when there are at most two values per agent (possibly not common across all agents) and for general instances where the value of each good is at least as much as the value of all lesser goods combined.

Open Problem 6. Are there other classes of structured valuations for which MMS is guaranteed to exist, such as when there are only a few (but more than two) possible values?

5 Further Notable Fairness Notions

EFL and EFR: The EFX notion was defined as a more realistic counterpart to EF1, however, as we discussed in Section 3, it is still unknown if it can always be guaranteed. This has led to the definition of notions that lie "in-between" EF1 and EFX. Barman et al. [2018a] defined the notion of envyfreeness up to one less-preferred good (EFL) according to which an agent i may envy another agent j if either Aj contains at most one good that i values positively, or the envy of i can be eliminated by the hypothetical removal of a good g ∈ Aj such that vi(Ai) ≥ vi(g). They showed that EFL allocations always exist and can be computed using a variant of Envy-Cycle Elimination. Farhadi et al. [2021] defined the notion of envy-freeness up to a random good (EFR) according to which the envy of an agent i towards another agent j can be eliminated in expectation after the hypothetical removal of a randomly chosen good from Aj. They showed that a 0.73EFR allocation can be computed in polynomial time.

Open Problem 7. Does an EFR allocation always exist?

PMMS and GMMS: Several variations of MMS have also been considered. Caragiannis et al. [2019b] defined the notion of pairwise maximin share fairness (PMMS) according to which, for every pair of agents i and j, i's value for Ai must be at least as much as the maximum she could obtain by redistributing the set of goods in Ai ∪ Aj into two bundles and picking the worst of them. In other words, instead of requiring the maximin share guarantee to be achieved for the set of all agents, PMMS requires that it is achieved for any pair of agents. Despite the apparent similarities in the definitions of PMMS and MMS, Caragiannis et al. [2019b] showed that their exact versions are actually incomparable. The main open problem here is the following.

Open Problem 8. Does a PMMS allocation always exist?

Interestingly, showing the existence of PMMS allocations is at least as hard as showing the existence of EFX allocations (Open Problem 2), as PMMS implies EFX. For approximate PMMS, the best known result is 0.781 by Kurokawa [2017].

An even stronger notion, which implies both MMS and PMMS, is that of groupwise maximin share fairness (GMMS) defined by Barman et al. [2018a], and which requires that the maximin share guarantee is simultaneously achieved for any possible subset of agents. Barman et al. [2018a] showed that GMMS allocations exist for some restricted settings, such as when the agents have binary or identical values. They also showed that any EFL allocation is 1/2-GMMS, and thus such an allocation can be computed efficiently. The currently best known approximation of GMMS is 4/7 [Amanatidis et al., 2020; Chaudhury et al., 2020]. The implication relations between all the aforementioned notions has been used many times to show that particular algorithms have guarantees that hold for multiple notions at once. We refer the reader to the paper of Amanatidis et al. [2018] for a discussion of the relations between (approximate versions of) these notions.

Open Problem 9. What is the best possible α for which αGMMS allocations exist?

Prop1, PropX and PropM: A line of work has also focused on relaxations of proportionality that are similar in essence to EF1 and EFX. Conitzer et al. [2017] defined the notion of proportionality up to one good (Prop1) according to which each agent could obtain her proportional share if given one extra good. An allocation that is Prop1 and PO always exists [Conitzer et al., 2017] and can be computed in polynomial time [Barman and Krishnamurthy, 2019]. Aziz et al. [2020] defined PropX which demands that each agent can obtain her proportional share when given the least positivelyvalued good among those allocated to other agents. PropX is rather demanding and it cannot be always guaranteed, even in simple scenarios. Recently, Baklanov et al. [2021a; 2021b] introduced the notion of proportionality up to the maximin good (PropM) and showed that such allocations always exist and can be computed in polynomial time.

6 Other Topics

Here we consider other interesting directions like the relation between fairness and efficiency, or the possibility to achieve fairness when the agents are strategic. Finally, we briefly discuss further meaningful discrete fair division settings.

6.1 Fairness and Efficiency

There is a significant line of work that considers the question of whether it is possible to simultaneously achieve fairness and efficiency. A common type of efficiency is that of Pareto optimality, which, as we already discussed, can be guaranteed in conjunction with some fairness notions, like EF1 and Prop1. Another natural goal is to (approximately) maximize some objective function of the values of the agents, such as the social welfare, i.e., the total value of the agents for the goods they receive. To this end, Bertsimas et al. [2011] and Caragiannis et al. [2012] defined the Price of Fairness, a measure which, similarly to the approximation ratio for algorithms, measures the deterioration of the objective due to the fairness requirement (which may refer to any fairness notion).

The Price of Fairness for EF1 and EFX allocations (only for instances with two agents) was considered by Bei et al. [2021]. Barman et al. [2020] managed to close a gap on the price of EF1 that was left open in the work of Bei et al. [2021], and also showed tight bounds for other fairness notions, in particular, 1/2-MMS and Prop1. Halpern and Shah [2021] showed tight bounds on the Price of EF1 and of approximate MMS under the constraint of having only ordinal information about the agent values, a typical assumption made in the context of distortion in social choice [Anshelevich et al., 2021].

6.2 Fair Division with Strategic Agents

Most of the papers mentioned so far, studied the problem from an algorithmic perspective under the assumption that the agents are non-strategic. In the strategic version of the problem, an agent may intentionally misreport how she values the goods in order to end up with a better bundle. This introduces an additional layer of difficulty, as the goal is to produce fair allocations according to the true values of the agents, while their declarations might be far from truth. This version of the problem has been considered mostly from a mechanism design without monetary transfers perspective, in which the utility of an agent is defined as her (true) value for her bundle.

A first direction was the design of truthful mechanisms (i.e., mechanisms where no agent has an incentive to lie) that are also fair. Caragiannis et al. [2009], showed that no truthful mechanism for two agents and two goods can always output allocations of minimum envy. Amanatidis et al. [2016] revisited the problem for the case of two agents and any number of goods, and showed that no truthful mechanism can always output α-MMS allocations, for α > 2/m. A characterization of truthful mechanisms for two agents, showing that truthfulness and fairness are incompatible (in the sense that there is no truthful mechanism with bounded fairness guarantees under any meaningful fairness notion) was provided by Amanatidis et al. [2017a]. This impossibility, however, does not apply to restricted cases. Halpern et al. [2020] showed that for binary valuations, there is a polynomial-time truthful mechanism that produces EF1 and PO allocations, and Babaioff et al. [2021a] showed an analogous result with respect to MMS. In fact, Babaioff et al. [2021a] also showed that for the submodular analog of binary valuations, there is a truthful mechanism that always outputs EFX allocations.

More recently, the aforementioned impossibility results led to a different direction, where the focus was shifted to the stable states of non-truthful mechanisms. In particular, Amanatidis et al. [2021b] studied mechanisms that always have pure Nash equilibria, and showed that every allocation that corresponds to an equilibrium of Round Robin is EF1 with respect to the (unknown) true values of the agents.

Open Problem 10. Are there mechanisms that always have pure Nash equilibrium allocations with stronger guarantees than EF1?

6.3 Notable Variants of the Setting

We conclude by giving a brief overview of other interesting settings in discrete fair division and their main results.

Arbitrary Entitlements. So far, it is always assumed that agents have equal entitlements over the goods. However, there are settings where the fairness of an allocation must be considered with respect to asymmetric entitlements, e.g., in many inheritance scenarios, closer relatives have higher entitlements often determined by law. In order to capture fairness in the presence of arbitrary entitlements, one may generalize existing notions to their weighted counterparts, like weighted MMS [Farhadi et al., 2019] and weighted EF1 [Chakraborty et al., 2021], or tweek their definitions approprietly, like in the MMS-inspired ℓ-out-of-d share of Babaioff et al. [2021c]. In a recent work, Babaioff et al. [2021b] introduce the notion of AnyPrice share (APS) as the maximum value an agent can guarantee to herself if she has a budget equal to her entitlement and the goods are adversarially priced with prices that sum up to 1, and show how to efficiently compute an allocation where everyone gets value no less than 3/5 of her APS.

Group Fairness. In the model we discussed in the main part of the survey, each agent is assumed to be unrelated to other agents. However, there are applications where it makes more sense for agents to be grouped together (e.g., each group might correspond to a family). Several models capturing scenarios along these lines have been considered in the literature. Suksompong [2018] focused on a setting where each agent derives full value from all the goods allocated to the group she belongs to, and showed bounds on the best possible approximation of MMS. Kyropoulou et al. [2020] considered EF1 and EFX allocations in the same setting, as well as in settings with dynamic group formation; some of these results were later improved by Manurangsi and Suksompong [2021] using ideas from discrepancy theory. Segal-Halevi and Suksompong [2019] focused on the case of democratic fairness, where the goal is to compute allocations that are considered fair (e.g., satisfying EF1) by a high fraction of the agents in each group. A different model was studied by Conitzer et al. [2019], where goods given to a group are then distributed among its members, and thus the agents derive value only from the goods allocated personally to them.

Online Fair Division. Our model here is static, as all items, agents, and their valuation functions do not change over time. Online fair division considers settings where the agents or the goods arrive in an online manner. In the most common model there is a fixed set of agents, items arrive one by one, and they need to be allocated to the agents immediately and irrevocably [Aleksandrov et al., 2015; Aleksandrov and Walsh, 2020]. Usually, in order to bypass strong negative results and show that it is possible for envy to vanish over time or the allocations to always remain EF1, the values of the goods are assumed to be bounded [Benade et al., 2018; Zeng and Psomas, 2020] or a limited number of reallocations is allowed [He et al., 2019]. The alternative model which considers a fixed set of resources and agents who arrive or depart over time has not been considered for indivisible resources, partially because it is very challenging to achieve positive results [Kash et al., 2014].

Randomness in Fair Division. Until very recently there were barely any works on randomized algorithms for discrete fair division. This is partially due to the strong general preference for deterministic algorithms / mechanisms within the Computational Social Choice community (which is welljustified in many settings, yet such a discussion is beyond the scope of this survey), but also due to the nature of the problem itself. On one hand, randomness cannot help with achieving ex-post fairness, i.e., fairness in each resulting allocation, for any of the deterministic notions mentioned herein. On the other hand, achieving ex-ante envy-freeness, i.e., envy freeness with respect to the expected utilities, is trivial; just allocate all the goods to a single agent uniformly at random. Freeman et al. [2020] proposed an algorithm that achieves ex-ante envy-freeness but is also ex-post EF1, i.e., all the possible allocations it outputs are deterministically EF1. Aziz [2020] gave a simpler algorithm with the same fairness guarantees that also satisfies a weak efficiency property. Finally, in a somewhat different direction, Caragiannis et al. [2021] studied interim envy-freeness, a notion which lies between exante and ex-post envy-freeness.

Subsidies. As we saw in Section 6.2, even in a gametheoretic setting no monetary transfers are allowed in fair division problems. Indeed, arbitrary payments would significantly alter the flavor of these problems and often go against their motivation. A recent line of work, however, considers the question of whether it is possible to pay the agents just a small amount of money (subsidy) on top of a given allocation in order to make it envy-free (when the subsidies are also taken into consideration). Allocations for which this can be done are called envy-freeable. Halpern and Shah [2019], who introduced the problem, showed that the total subsidy needed to turn an envy-freeable allocation into an envy-free one is at most (n - 1)mv∗ , where v∗ is the maximum value of any agent for any good. This upper bound was later improved to (n - 1)v∗ by [Brustle et al., 2020]. More recently, Caragiannis and Ioannidis [2021] provided approximation guarantees and hardness results for computing an envy-freeable allocation that minimizes the total amount of subsidies.

Fair Division under Constraints. Depending on the application, some allocations may not be feasible due to restrictions such as connectivity, cardinality, separation, or budget constraints. Such models have recently attracted the attention of the community. Rather than referring to specific works, we point the reader to the survey of Suksompong [2021] which discusses this part of the literature in detail.

Chores and Mixed Manna. Beyond discrete fair division of goods that we focus on in this survey, there is a significant line of work that considers similar questions when items can be seen as chores (which are negatively valued by the agents), or mixed manna (a mixture of both goods and chores). As such settings are out of the scope of our survey, we refer the reader to the works of Aziz et al. [2022], Li et al. [2021], Aziz et al. [2017], Sun et al. [2021] and references therein.

Acknowledgments

This work was supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets", the MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets", and the NWO Veni project No. VI.Veni.192.153.