New Fairness Concepts for Allocating Indivisible Items

1 Introduction

Fair division is a popular research area, with origins in antiquity and important applications [Brams and Taylor, 1996; Moulin, 2004]. In a setting that has received much attention in the last fifteen years, a set of indivisible items is to be distributed fairly among agents. But what does "fairly" mean? There is no single answer here and different ways of interpreting "fairly" have been considered in the literature.

The first interpretation is comparative. To evaluate an allocation as fair, each agent compares the bundle of items allocated to her with bundles of the remaining items. The wellknown notion of envy-freeness [Foley, 1966] is a representative fairness concept defined this way, according to which an allocation is fair if each agent prefers the bundle allocated to her to the bundle allocated to any other agent. Typically, agents have valuation functions that allow them to evaluate or compare bundles of items.

The second interpretation is in absolute terms. In this category, each agent defines a threshold based on her view of the allocation instance and evaluates as fair those allocations in which she gets a bundle of value that exceeds this threshold. Proportionality [Dubins and Spanier, 1961; Steinhaus, 1948] is the representative fairness concept here. Each agent's threshold is simply her total value for all items divided by the number of agents. Then, an allocation is proportional if each agent gets a bundle of items for which her value exceeds her proportionality threshold.

Unfortunately, a seemingly attractive fairness concept may not be useful in the setting of indivisible items we consider. Even though it is undeniably hard to argue that an envy-free allocation is unfair, envy-freeness has at least two drawbacks. First, it may not be feasible to achieve. Consider the problem faced by a library where three computer science books (the items) are to be given to two CS students (the agents). Whichever student gets less than two books will be envious of the other. Second, finding an envy-free allocation may be a computationally challenging problem. It is not hard to see that deciding whether an envy-free allocation among two agents with identical valuations for the items exists is at least as hard as deciding the paradigmatic NP-hard PARTITION problem; e.g., see [Bouveret and Lemaˆıtre, 2016]. Proportionality suffers from the same infeasibility and high computational complexity drawbacks as well.

Several relaxations of envy-freeness proposed in the literature aim to circumvent this issue. The first one, envy-freeness up to some item (EF1), introduced by Budish [2011], requires that each agent prefers her own bundle to the bundle of any other agent, after removing some item from the latter. EF1 addresses the two above-mentioned issues in an ideal way. EF1 allocations always exist and can be computed efficiently [Lipton et al., 2004]. Unfortunately, it seems that EF1 has moved way too far and has lost the fairness properties of envy-freeness. For example, assume that the two students in our example have a high value for one of the three books. Then, the allocation that gives one low-value book to one of them is EF1. This student is indifferent to the bundle of the other student after removing the high-value book from it.

Intuitively, it is clear that a more fair allocation would give the two low-value books to one of the students and the high-value book to the other. This is what motivates the definition of envy-freeness up to any item (EFX), introduced by Caragiannis et al. [2019b]. An allocation is EFX if each agent prefers her own bundle to the bundle of any other agent, after removing any item from the latter. From the fairness point of view, EFX is almost as appealing as envy-freeness. However, despite significant efforts by researchers in the last five years [Plaut and Roughgarden, 2020; Caragiannis et al., 2019a; Chaudhury et al., 2020; Amanatidis et al., 2021; Chaudhury et al., 2021; Mahara, 2021; Berger et al., 2022], it is still unknown whether EFX is always feasible for instances with more than three agents. Furthermore, even for the case of three agents where the existence of EFX allocations is guaranteed, the computational complexity of the known methods is immense [Chaudhury et al., 2020; Mahara, 2021].

Among the relaxations of proportionality, the one that has received the lion's share of attention uses the so-called maximin fair share (MMS), i.e., the maximum value an agent can attain in any allocation where she is assigned her least preferred bundle, as threshold. Surprisingly, Kurokawa et al. [2016] proved that MMS allocations may not always exist. Since then, research has focused on computing allocations that approximate MMS; e.g., see [Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishnamurthy, 2020; Ghodsi et al., 2018; Garg and Taki, 2020; Feige et al., 2021]. These MMS-approximations are less appealing as fairness concepts. An excellent recent survey by Amanatidis et al. [2022] discusses the above fairness concepts and many more.

1.1 Our Conceptual and Technical Contribution

The discussion above suggests that the Holy Grail of research in fair division with indivisible items is to define a concept that is (1) intuitively, as close to fairness as envy-freeness and proportionality, (2) always feasible, and (3) efficiently computable. In this paper, we present two such concepts, inspired by EFX and MMS. Our first one, called epistemic envyfreeness up to any item (EEFX), is comparative and adapts the concepts of epistemic envy-freeness defined by Aziz et al.. An allocation is EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes "EFX-satisfied". An example follows.

This allocation is EEFX. Agents 1 and 2 are not envious of any other agent. For agent 3, by reshuffling the items a, ..., g in the bundles of agents 1 and 2, we can get the allocation ({a, b, c}, {d, e, f, g}, {h}), in which agent 3 is EFXsatisfied (note that the definition of EEFX requires that the reshuffling does not affect the bundle of agent 3). Her value of 24 for her bundle {h} is at least as high as her value for bundle {a, b, c} after removing her least-valued item b and for bundle {d, e, f, g} after removing her least-valued item g.

EEFX is particularly relevant in environments (with privacy restrictions or of very large scale) in which each agent knows the allocation instance (i.e., she is aware of all items and her valuations for them, as well as of the number of agents) but her knowledge of the allocation is limited to the contents of her bundle. Then, the agent is as optimistic as possible in the evaluation of her bundle; she compares it with each bundle in the allocation of the remaining items that would be best possible for her. In contrast to EEFX, the concepts of envy-freeness, EF1, and EFX are knowledgesensitive according to the definitions of Aziz et al. [2018].

Our second fairness concept interprets fairness in absolute terms by defining the minimum EFX share (MXS) as a threshold for each agent. The minimum EFX share of an agent is the minimum value she has among all allocations in which she is EFX-satisfied.

Example 2. We compute the minimum EFX share of agent 2 in Example 1 and show that it is equal to 25. Notice that the agent is EFX-satisfied in allocation ({a, g}, {f}, {b, c, d, e, h}). Indeed, her value is 25, which is also her value for bundle {a, g} after removing her leastvalued item a. Her value for the other bundle {b, c, d, e, h} after removing her least-valued item d is only 24. We can see that agent 2 is not EFX-satisfied in any allocation that gives her a value of 24. In this case, agent 2 gets her value of 24 by items b and c and at most two other items among a, d, e, and h. The items f and g should be in the first and third bundle, respectively. These bundles should also have at least two items among a, d, e, and h. Then, agent 2 will be envious of some of these two bundles after removing her least-valued item. Thus, the minimum EFX share of agent 2 is 25.

MXS allocations are similar in spirit to proportional and MMS allocations. An allocation is MXS if each agent gets a bundle of value at least her minimum EFX share. We define our two new fairness concepts formally in Section 2.

We present the following technical results about EEFX and MXS. First, in Section 3, we explore their relation to MMS as well as to proportionality up to any item (PROP1), another relaxation of proportionality [Conitzer et al., 2017]. We show that every MMS allocation is EEFX, every EEFX allocation is MXS, and every MXS allocation is PROP1. This chain of implications puts the new fairness concepts in the spectrum of existing fairness criteria and extends previous taxonomies by Bouveret and Lemaˆıtre [2016] and Aziz et al. [2018]. To the best of our knowledge, the fact that every MMS allocation is also PROP1 was not known before.

Our main result is a polynomial-time algorithm that computes an EEFX (and, hence, MXS) allocation in any fair division instance. Our analysis exploits several key ideas from the fair division literature, such as the concept of ordered instances, which are typically used in the design of approximation algorithms for MMS since the work of Bouveret and Lemaˆıtre [2016], the envy cycle elimination algorithm of Lipton et al. [2004], and the fact that applying this algorithm on ordered instances results in EFX allocations, observed independently by Plaut and Roughgarden [2020] and Barman and Krishnamurthy [2020]. Our algorithm is essentially identical to an algorithm used by Barman and Krishnamurthy [2020] to compute 2/3-MMS allocations. Due to our different fairness objective, our analysis is considerably different and rather simpler. In addition to EEFX, we get MXS and 2/3-MMS as bonus properties for the allocations computed by our algorithm. These results appear in Section 4.

Rather surprisingly, our last technical result states that computing the minimum EFX share is an NP-hard problem. This suggests that any efficient algorithm for computing MXS allocations cannot make explicit use of the minimum EFX share. This result appears in Section 5. All our results assume additive valuations. We conclude with a discussion on extensions of our new fairness concepts and many open problems in Section 6.

2 Definitions and Notation

Throughout the paper, we use [k] to denote the set {1, 2, ..., k} for a positive integer k.

A fair division instance I consists of the set of n agents and m (indivisible) items. We use positive integers to identify both the agents and the items and denote their sets as [n] and [m], respectively. Each agent i has a non-negative valuation vi(g) for each item g ∈ [m]. We use the term ordered instances to refer to instances in which the valuations of all agents for the items have a common ordering, i.e., they satisfy vi(g) ≥ vi(g′ ) whenever vi′ (g) > vi′ (g′ ) for every pair i, i′ of agents and every pair g, g′ of items. Valuations are additive; by slightly abusing notation, we define the valuation agent i has for the bundle S of items as vi(S) = ∑g∈S vi(g).

An allocation X = (X1,X2, . . . ,Xn) of the items to the agents is a partition of [m] into n bundles X1,X2, . . . ,Xn, with Xi being the bundle allocated to agent i. Formally, Xi ∩ Xj = ∅ for all i ̸= j and ∪ni=1Xi = [m]. We often use Γ to refer to the set of all allocations of a given instance.

Envy-freeness up to any item (EFX) is among the most compelling fairness concepts in the literature.

Definition 1 (Envy-freeness up to any item (EFX)). For a fair division instance, an allocation X = (X1, . . . ,Xn) is envy-free up to any item (EFX) if for any agent i ∈ [n], any bundle Xk ∈ X, and any item g ∈ Xk such that vi(g) > 0 it holds that vi(Xi) ≥ vi(Xk \ {g}).

We will say an agent i is EFX-satisfied with an allocation X if her envy against any other agent vanishes after removing any single item from that other agent's bundle. That is, an allocation X is EFX if every agent is EFX-satisfied with it. 1 We are ready to define our first new fairness concept.

Definition 2 (Epistemic EFX (EEFX) and EEFX certificates). For a fair division instance, an allocation X = (X1,X2, . . . ,Xn) is called epistemic EFX (EEFX) if for every agent i ∈ [n], there exists an allocation Y = (Y1, Y2, . . . , Yn) such that Yi = Xi and agent i is EFXsatisfied with Y . We will refer to such an allocation Y as an EEFX certificate of agent i for bundle Xi.

1 We refer the reader to Section 6 for a discussion on our choice of including the restriction vi(g) > 0 in Definition 1.

In other words, we can say that an allocation X is epistemic EFX if there exists an EEFX certificate for every agent with respect to her bundle in X. Note that, an EFX allocation trivially serves as an EEFX certificate for every agent, and, thus, an EFX allocation is EEFX as well.

Our second new fairness concept is similar in spirit to the well-known MMS fairness property.

Definition 3 (Maximin share (MMS)). For a fair division instance, we define the maximin share of an agent i ∈ [n], denoted as MMSi, as follows.

Moreover, we say that an allocation is MMS if every agent receives a bundle of value that is at least as high as her maximin share.

Analogously, we will define minimum EFX share (MXS) and MXS allocations. For a fair division instance, we use EFXi to denote the collection of all allocations where agent i is EFX-satisfied. Formally,

Note that when the above maximum is taken over an empty set, then it implies that agent i values every item in bundle Zj at 0, and hence the stated condition is trivially satisfied. We now define an agent's minimum EFX share as the least value she derives from any allocation where she is EFX-satisfied.

Definition 4 (Minimum EFX share, MXS allocations). For a fair division instance, we define the minimum EFX share of agent i as MXSi := minZ∈EFXi vi(Zi). Moreover, we say that Z = (Z1, . . . ,Zn) is an MXS allocation if vi(Zi) ≥ MXSi for every agent i ∈ [n].

One may wonder why we do not define a maximum EFX share fairness concept using the (similar to MMSi) threshold of maxZ∈EFXi minj∈[n] vi(Zj) for agent i. Interestingly, we can show that this gives just an alternative definition for MMS.

We conclude this section with the definition of proportionality up to some item (PROP1), a variation of the well-known concept of proportionality.

Definition 5 (Proportionality up to one item (PROP1)). For a fair division instance, we define the proportionality threshold for an agent i ∈ [n], denoted by PSi as PSi := vi([m])/n. An an allocation X = (X1, . . . ,Xn) is proportional up to one item (PROP1) if vi(Xi) ≥ PSi -maxg∈[m]\Xi vi(g) for every agent i ∈ [n].

It is well-known-e.g., see [Bouveret and Lemaˆıtre, 2016]-that in every fair division instance, we have MMSi ≤ PSi for every agent i ∈ [n].

3 Relations to Other Fairness Concepts

In this section, we establish interesting connections between our proposed fairness concepts of EEFX and MXS with previously well-studied notions of fairness in the literature, summarized in the following chain of implications:

The connection between EEFX and MXS allocations follows easily by the definitions.

Theorem 1 (EEFX ⇒ MXS). An EEFX allocation in a fair division instance is also MXS.

Proof. Let X = (X1, . . . ,Xn) denote an EEFX allocation in a fair division instance. Fixing an agent i ∈ [n], we will prove that vi(Xi) is at least as high as her minimum EFX share. By definition, since X is an EEFX allocation, there must exist an EEFX certificate Y = (Y1, . . . , Yn) for agent i such that Yi = Xi and Y ∈ EFXi. Therefore, we can write

Since, the bundles Xi and Yi are identical, we obtain vi(Xi) ≥ MXSi, thereby completing the proof.

The opposite implication, however, is not true as the following example shows.

Example 3 (MXS ⇏ EEFX). Consider the fair division instance with three agents having identical valuations v over six items g1, . . . , g6: items g1 and g2 have a value of 1, while each of the remaining items has a value of 2. Consider an allocation X = (X1,X2,X3), with X1 = {g1, g2},X2 = {g3, g4} and X3 = {g5, g6}, and notice that all agents are EFX-satisfied. Hence, we have MXSi ≤ 2 for each agent i.

Let us now consider the allocation X′ = (X′1 ,X′2 ,X′3 ), with X′1 = {g3},X′2 = {g1, g2, g4} and X′3 = {g5, g6}. This is an MXS allocation since every agent has a bundle of value greater or equal to 2. However, X′ is not EEFX. Indeed, consider an allocation Y in which agent 1 gets item g3. Clearly, agent 1 would not be EFX-satisfied if Y had the three items g4, g5, g6 in the same bundle. Furthermore, agent 1 would not be EFX-satisfied if one of g1 or g2 are in the same bundle with two items among g4, g5, g6. The only case left for Y is when there is a bundle containing one of the items g4, g5, g6 and both item g1 and g2; agent 1 would not be EFX-satisfied in this case either. Thus, for agent 1, there is no way to reallocate the remaining items and make her EFX-satisfied.

We now present a non-trivial connection where we prove that any maximin share allocation necessarily admits an EEFX-certificate for every agent.

Theorem 2 (MMS ⇒ EEFX). An MMS allocation in a fair division instance is also EEFX.

Proof. Consider a fair division instance. We begin with a definition. For an allocation Z = (Z1, . . . , Zn) and an agent i ∈ [n] in the fair division instance, denote by rZ,i the (n - 1)-entry vector with entries the values vi(Zj) for j ∈ [n] \ {i}, sorted in non-decreasing order, i.e., the vector rZ,i = ⟨rZ,i 1 , rZ,i 2 , . . . , rZ,i n-1 ⟩ satisfies rZ,i t ≤ rZ,i t+1 for t ∈ [n-2]. Let X = (X1, . . . ,Xn) be an MMS allocation in the fair division instance and i ∈ [n] any agent. Let Y = (Y1, . . . , Yn) be an allocation with Yi = Xi so that rY,i is lexicographically minimum. We will show that Y is an EEFX certificate for agent i and bundle Xi, proving that the allocation X is also EEFX.

Assume otherwise. Then, by definition, there exists j1 ∈ [n] \{i} so that for the item g ∈ Yj1 for which agent i has the minimum non-zero value among the items in Yj1 , it holds

Now, assume that vi(Yj) > vi(Xi) for every j ∈ [n] \ {i}. Then, for the allocation Z ′ = (Z ′1 , . . . ,Z ′n ) that is obtained from Y after removing item g from bundle Yj1 and adding it to bundle Yi, we obtain an allocation in which vi(Z ′j ) > vi(Xi) ≥ MMSi for every j ∈ [n]. This follows by our assumption for j ∈ [n] \ {i, j1}, since vi(g) > 0 for j = i, and by eq. (1) for j = j1 since vi(Z ′j1 ) = vi(Yj1 ) - vi(g) > vi(Xi). The existence of allocation Z ′ contradicts the fact that allocation X is MMS.

So, there must be j2 ∈ [n] \ {i, j1} so that vi(Yj2 ) ≤ vi(Xi). Now, consider the allocation Z ′′ = (Z ′′ 1 , . . . , Z ′′N ) obtained after removing item g from bundle Yj1 and adding it to bundle Yj2 . Notice that vi(Z ′′ j ) = vi(Yj) for j ∈ [n] \ {j1, j2}, vi(Z ′′ j1 ) = vi(Yj1 ) - vi(g) < vi(Yj1 ) and, vi(Z ′′ j2 ) = vi(Yj2 )+vi(g) ≤ vi(Xi)+vi(g) < vi(Yj1 ), using the definition of j2 and eq. (1). Hence, rZ′′ ,i is lexicographically smaller than rY,i and, furthermore, Z ′′ i = Xi, contradicting the assumption on Y . This completes the proof.

The implication of Theorem 2 is strict. As we show in the next section, EEFX allocations always exist. This is not the case for MMS, as Kurokawa et al. [2018] have proved. Then, any EEFX allocation in their counter-example instance cannot be MMS.

We conclude the section by establishing a connection between MXS and PROP1.

Theorem 3 (MXS ⇒ PROP1). An MXS allocation in a fair division instance is also PROP1.

Proof. Consider a fair division instance and let X = (X1, . . . ,Xn) be an MXS allocation. Clearly, the proportionality and, consequently, the PROP1 constraints are satisfied for every agent i with MXSi = PSi. Now, consider an agent i ∈ [n] with MXSi < PSi; we will show that X satisfies the PROP1 constraints for agent i as well.

Assume otherwise that

for every item g ∈ [m] \ Xi. Let Y = (Y1, . . . , Yn) be an allocation in EFXi such that vi(Yi) = MXSi < PSi. Since ∑j∈[n] vi(Yj) = n · PSi, there exists k ∈ [n] \ {i} such that vi(Yk) > PSi. By eq. (2), we have vi(Yk) > vi(Xi), meaning that there exists an item g∗ that belongs to Yk but not to Xi. By the definition of EFXi, we have

and, using eq. (2), we get

contradicting the fact that allocation X is MXS.

Again, the opposite implication is not true.

Algorithm 1 Computing EEFX allocations

Input: A fair division instance I

Output: An allocation X in I

• 1: I ′ ← Order(I);
• 2: X′ ← EnvyCycleElimination(I ′ );
• 3: L← PickingSequence(I ′ ,X′ );
• 4: X ← Pick(I,L);
• 5: return X

Example 4. Consider the fair division instance with four items and two agents with identical valuations of 1 for each of them. Then, each agent gets two items in each EFX allocation making the minimum EFX share equal to 2. So, the allocation in which agent 1 gets only one item is not MXS. It is PROP1 though.

4 Existence and Efficient Computation of EEFX Allocations

We now present our main result.

Theorem 4. In any fair division instance, an EEFX allocation exists and can be computed in polynomial time.

We will prove Theorem 4 using Algorithm 1. We remark that this is essentially identical to the algorithm proposed by Barman and Krishnamurthy [2020] to compute 2/3-MMS allocations. However, proving that the algorithm returns EEFX allocations requires additional arguments. Interestingly, our analysis is relatively simple.

Algorithm 1 takes as input a fair division instance I consisting of m items and n agents with valuations {vi}i∈[n] and works as follows:

• It first (Step 1) executes routine Order, which creates an ordered instance I ′ by modifying instance I. Instance I ′ has the same set of agents as I. The items of I are arbitrarily renamed as g1, g2, . . . , gm and the valuation v′i of agent i ∈ [n] is defined as follows: for j = 1, 2, . . . ,m, the valuation v′i (gj) of agent i for item gj is the j th highest value in the multiset {vi(g1), vi(g2), . . . , vi(gm)}.
• Next, in Step 2, the algorithm executes the envy cycle elimination algorithm of Lipton et al. [2004] on instance I ′ to get an intermediate allocationX′ = (X′1 , . . . ,X ′n ).
• Then, in Step 3, the routine PickingSequence takes as input instance I ′ and allocation X′ and computes the picking sequence L = [L1, . . . ,Lm] as follows. For j = 1, 2, . . . ,m, Lj is the agent who gets item gj in allocation X′ , i.e., gj ∈ X′Lj .
• Finally, in Step 4, the routine Pick is executed with input the instance I and the picking sequence L to compute the allocation X = (X1, . . . , Xn) as follows. Pick runs m rounds, one for each item. In round j, agent Lj picks the highest-valued item (breaking ties using a tiebreaking rule) that has not been allocated to any agent in rounds 1, 2, . . . , j - 1.

Algorithm 1 returns allocation X as output.

Algorithm 1 clearly runs in polynomial time. To complete the proof of Theorem 4, we will show (in Lemma 3) that allocation X is EEFX. To do so, we will exploit two crucial properties maintained by the algorithm. The first one follows by a result of Plaut and Roughgarden [2020] and Barman and Krishnamurthy [2020], who proved that the application of the envy cycle elimination algorithm on ordered fair division instances produces an EFX allocation.

Lemma 1 (Plaut and Roughgarden [2020]). The allocation X′ of instance I ′ is EFX.

The second crucial property is given by the next lemma.

Lemma 2. For every agent i ∈ [n], there exists a bijection πi : [m] → [m] such that the following are true:

• πi(g) ∈ Xi and vi(πi(g)) ≥ v′i (g) for every g ∈ X′ i .
• πi(g) ̸∈ Xi and vi(πi(g)) ≤ v′i (g) for every g ̸∈ X′ i .

Proof. Let i ∈ [n] be an agent. We will refer to the items using the renaming g1, g2, . . . , gm used by routine Order. Let σi : [m] → [m] be a permutation such that gσi(j) is agent i's j th most valuable item according to valuation function vi. Formally, for every j1, j2 ∈ [m] such that j1 < j2, we have vi(gσi(j1)) ≥ vi(gσi(j2)). Furthermore, when vi(gσi(j1)) = vi(gσi(j2)), the tie between items gσi(j1) and gσi(j2) is resolved in favour of gσi(j1) during the execution of routine Pick in Step 4 of Algorithm 1. By the definition of the ordered instance I ′ , it holds that vi(gσi(j)) = v′i (gj) for every j ∈ [m].

We define the function πi : [m] → [m] as follows. For every item gj ∈ X′ i , define πi(gj) to be the item picked in round j of the execution of Pick in Step 4 of Algorithm 1. For k = 1, . . . ,m-|X′ i |, consider the item g that is kth in the ordering g1, g2, . . . , gm, ignoring the items in X′ i . Set πi(g) to be the kth item in the ordering gσi(1), gσi(2), . . . , gσi(m), ignoring the items in Xi.

Clearly, πi is a bijection. Furthermore, by the definition of the picking sequence L, for every item gj ∈ X′ i , it is agent i who picks at round j of the execution of Pick at Step 4 of Algorithm 1 (i.e., Lj = i), and thus, πi(gj) ∈ Xi. The definition of πi(gj) for every gj ̸∈ X′ i ensures that πi(gj) ̸∈ Xi .

Now, notice that, for every gj ∈ X′ i , exactly j - 1 items have been picked before round j (of the execution of Pick in Step 4). So, some item in the set {gσi(1), . . . , gσi(j)}, which are the j highest-valued items for agent i, will be available and will be picked by agent i at round j. Thus, πi(gj) ∈ {gσi(1), . . . , gσi(j)} and vi(πi(gj)) ≥ vi(gσi(j)) = v′i (gj).

Finally, we prove that vi(πi(gj)) ≤ v′i (gj) for every item gj ̸∈ X′ i . Assume otherwise and let ℓ be the smallest integer in [m] such that gℓ ̸∈ X′ i and vi(πi(gℓ)) > v′i (gℓ) = vi(gσi(ℓ)), meaning that πi(gℓ) ∈ {gσi(1), . . . , gσi(ℓ-1)}. Also, for every t < ℓ such that gt ̸∈ X′ i , it must also be that πi(gt) ∈ {gσi(1), . . . , gσi(ℓ-1)} since, by the definition of πi, πi(gt) precedes πi(gℓ) in the ordering gσi(1), . . . , gσi(m). Finally, as we observed above, for every t < ℓ such that gt ∈ X′ i , πi(gt) ∈ {gσi(1), . . . , gσi(t)} ⊆ {gσi(1), . . . , gσi(ℓ-1)}. We conclude that {πi(g1), . . . , πi(gℓ)} ⊆ {gσi(1), . . . , gσi(ℓ-1)}, contradicting the fact that πi is a bijection.

We are now ready to complete the proof of Theorem 4 by proving the next lemma.

Lemma 3. Allocation X is EEFX.

Proof. Consider agent i ∈ [n] and let πi be the bijection defined in Lemma 2. Define the allocation Y with Yj = {πi(g) : g ∈ X′j } for j ∈ [n]. Since πi is a bijection, allocation Y is well-defined. Also, by Lemma 2, Yi = Xi. We will prove that Y is an EEFX certificate for agent i with bundle Xi.

Let j ∈ [n] \ {i} and g∗ be the item of bundle X′j such that πi(g∗ ) (which, by definition, belongs to bundle Yj) has minimum non-zero value according to vi. Thus, proving vi(Yi) ≥ vi(Yj \ {πi(g∗ )}) is enough to complete the proof.

Since g∗ ̸∈ X′ i and vi(πi(g∗ )) > 0, Lemma 2 implies that π(g∗ ) ̸∈ Xi and v′i (g∗ ) > 0. Then, the fact that X′ is EFX with respect to the valuations v′ (from Lemma 1) implies

Now, the properties of πi from Lemma 2 yield

and

By applying equations (4), (3), and (5), we get the desired inequality vi(Yi) ≥ vi(Yj \ {πi(g∗ )}).

We remark that the complexity of verifying if a given allocation is EEFX is currently an open problem. Fortunately, Lemma 3 implies that agents can trust that the allocation computed by Algorithm 1 is EEFX. Moreover, note that the proof of Lemma 3 shows that Algorithm 1 can be used to explicitly provide to each agent her EEFX certificate in polynomial time.

By Theorems 1 and 4, we obtain the next corollary. Paretooptimality follows since any Pareto-improvement of an MXS allocation is MXS as well.

Corollary 1. In any fair division instance, there exists a Pareto-optimal MXS allocation. Furthermore, an MXS allocation can be computed in polynomial time.

5 Computing the MinimumEFX Share

We now present a hardness result for computing the minimum EFX share, which may come as a surprise given the positive result in Corollary 1. Fortunately, Algorithm 1 computes MXS allocations without computing the minimum EFX share of any agent at any point of its execution.

Theorem 5. Computing the minimum EFX share of the agents in a fair division instance is NP-hard.

BALANCEDPARTITION

Input: A set N = {x1, . . . , x2t} of positive integer values such that ∑2t

h=1 xh = 2T for t, T ∈ N Problem: Does there exist a balanced partition of N, i.e., an equipartition (S, N \ S) of the elements in N (i.e., |S| = t) such that ∑h∈S xh = ∑h∈N\S xh?

Proof. We prove the theorem by developing a polynomialtime reduction from the NP-hard problem of BALANCEDPARTITION [Garey and Johnson, 1979].

Starting from an instance ϕ of BALANCEDPARTITION with a set N of elements and parameters t and T, we construct a fair division instance I(ϕ) as follows. For h = 1, ..., 2t, there is an element item corresponding to the element xh ∈ N; there is also an extra item 2t+1. There are two agents having identical valuations denoted by v; the value both agents have is 4T -xh for the element item h ∈ [2t] and 2T for the extra item 2t + 1. Our reduction is clearly polynomial-time.

For every allocation X = (X1,X2) in I(ϕ), define the induced partition (SX,N \ SX) as follows. Let i ∈ {1, 2} be such that 2t + 1 ∈ Xi. Then, SX = {xh ∈ N : h ∈ Xi}. The next two lemmas state structural properties of EFX allocations and their induced partitions.

Lemma 4. Let X = (X1,X2) be an EFX allocation of I(ϕ). Then, its induced partition (SX,N \ SX) is an equipartition of N.

Proof. Let t1 and t2 be the number of element items that bundles X1 and X2 have. Let i ∈ {1, 2} be such that the extra item 2t + 1 belongs to bundle Xi. Consequently, |SX| = ti and |N \ SX| = t3-i. Since X is EFX, bundle X3-i cannot be empty; let g be the least valued item in X3-i.

By the definition of valuations, we have

Since agent 3 - i is EFX-satisfied and ∑h∈SX xh ≤ 2T, equation (6) yields

i.e., ti - t3-i ≤ 1/2. Also, since agent i is EFX-satisfied, the facts ∑h̸∈SX xh ≤ 2T and v(g) < 4T , and equation (6)

i.e., ti - t3-i > -2. Since ti + t3-i = 2t the difference ti - t3-i must be an even integer, and ti = t3-i is the only case allowed by the inequalities -2 < ti - t3-i ≤ 1/2, implying that SX is an equipartition.

Lemma 5. Let X = (X1,X2) be an EFX allocation of I(ϕ) and i ∈ {1, 2} is such that 2t + 1 ∈ Xi. Then,

Proof. Notice that the rightmost inequality follows since agent 3 - i is EFX-satisfied. Now, by the definition of the valuations, the fact that the induced partition (SX,N \ SX) of allocation X is actually an equipartition (by Lemma 4), and since ∑h∈Sx xh ≤ 2T , we have

thus proving the leftmost inequality as well.

We are now ready to establish a connection between any EFX allocation and its induced equipartition.

Lemma 6. Let X = (X1,X2) be an EFX allocation of I(ϕ) that induces the partition (SX,N \ SX) of N. Then

Proof. Let i ∈ {1, 2} be such that 2t + 1 ∈ Xi. Since both bundles Xi and X3-i have t element items each (by Lemma 4), the inequality v(Xi) ≥ v(X3-i) from Lemma 5 implies that

and the inequality v(X3-i) ≥ v(Xi\{2t+1}) from Lemma 5 yields ∑h̸∈SX (4T - xh) ≥ ∑h∈SX (4T - xh) and, equivalently,

The lemma follows by equations (7) and (8).

Lemma 6 implies that there exists an EFX allocation X with min{v(X1), v(X2)} = (4t - 1)T (and, thus, the minimum EFX share of both agents is at most (4t - 1)T) if and only if its induced partition is balanced. To complete the proof of correctness for our reduction, we need to prove that every balanced partition is the induced partition of some EFX allocation; we do so in the following.

Consider the balanced partition (S,N \ S), i.e., ∑h∈S xh = ∑h̸∈S xh. Let us consider the allocation X = (X1,X2) where X1 = {h ∈ [2t] : xh ∈ S} ∪ {2t + 1} and X2 = {h ∈ [2t] : xh ∈ N \ S}. Note that it is straightforward to verify that the allocation X has the equipartition S as induced partition. To complete the proof, we will show that X is EFX.

For the sake of contradiction, assume otherwise that X is not EFX. Since S is an equipartition, it is trivial to see that v(X1) ≥ v(X2). Therefore, the only possibility is that agent 2 is not EFX-satisfied. Then, the item 2t + 1 is the least-valued item in bundle X1 and the fact that agent 2 is not EFX-satisfied yields

Thus, either t1 ̸= t2 and (S,N \ S) is not an equipartition or t1 = t2 but ∑h̸∈S xh < ∑h∈S xh, meaning that (S, N \ S) is an equipartition but not balanced. In any case, we obtain the desired contradiction.

6 Discussion

We have presented epistemic EFX and minimum EFX share, two new fairness concepts which are defined using the wellknown EFX fairness notion. We have adopted the original definition of EFX by Caragiannis et al. [2019b] here and used it in all our definitions. A simpler definition does not have the restriction vi(g) > 0 (see Definition 1) and yields a slightly stronger fairness notion, sometimes called EFX0 [Kyropoulou et al., 2020]. Using EFX0, we can define the variations EEFX0 and MXS0 in a similar way we defined EEFX and MXS. With the exception of Theorem 2, our results carry over to EEFX0 and MXS0. Interestingly, we can show that MMS does not imply EEFX0. So, we have used the standard EFX definition, which allows us to establish the seemingly novel implication MMS ⇒ PROP1 in Section 3.

Our work reveals many open problems. We have already mentioned that, in addition to being EEFX and MXS, the allocations computed by Algorithm 1 are 2/3-MMS as well [Barman and Krishnamurthy, 2020]. Are there EEFX allocations with better MMS guarantees possible? Can they be computed in polynomial time? Combining EEFX with other important fairness properties is also interesting. Are there EEFX allocations that are also EF1?

Furthermore, proving that EEFX and MXS are compatible with efficiency could nicely complement their fairness properties. For example, one question we have left open is whether Pareto-optimal EEFX allocations exist. Also, notice that the allocation we showed to be EEFX in Example 1 has maximum social welfare (i.e., maximum total value for the agents). It is tempting to conjecture that this is the case in general and EEFX has a low price of fairness [Caragiannis et al., 2012; Bertsimas et al., 2012]. This deserves investigation for both EEFX and MXS.

We remark that our main result (Theorem 4) holds for chores as well (where agents have costs, instead of values, for the items) with minor modifications in our arguments. Exploring the case of chores more systematically or even scenarios with mixed items, where an item can be good to some agents and a chore to others [Aziz et al., 2022], are possible directions for further work. Finally, it is certainly interesting to explore how/whether the results we present here generalize to non-additive valuations.

Acknowledgements

Ioannis Caragiannis was supported by the Independent Research Fund Denmark (DFF) under grant 2032-00185B. Jugal Garg and Eklavya Sharma were supported by NSF Grant CCF-1942321. Giovanna Varricchio was supported by DFG grant Ho 3831/5-1.