--- title: "Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio" authors: - "Bo Li" - "Zihao Li" - "Shengxin Liu" - "Zekai Wu" doi: "10.24963/ijcai.2024/318" url: "https://ijcai.org/proceedings/2024/318" pdf: "https://ijcai.org/proceedings/2024/0318.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "2868-2876" track: "Main Track" keywords: - "Game Theory and Economic Paradigms: GTEP: Fair division" --- # Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio Bo Li, Zihao Li, Shengxin Liu, Zekai Wu *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 2868-2876. DOI: [10.24963/ijcai.2024/318](https://doi.org/10.24963/ijcai.2024/318) ## Abstract We consider the problem of fairly allocating a combination of divisible and indivisible goods. While fairness criteria like envy-freeness (EF) and proportionality (PROP) can always be achieved for divisible goods, only their relaxed versions, such as the “up to one” relaxations EF1 and PROP1, can be satisfied when the goods are indivisible. The “up to one” relaxations require the fairness conditions to be satisfied provided that one good can be completely eliminated or added in the comparison. In this work, we bridge the gap between the two extremes and propose “up to a fraction” relaxations for the allocation of mixed divisible and indivisible goods. The fraction is determined based on the proportion of indivisible goods, which we call the indivisibility ratio. The new concepts also introduce asymmetric conditions that are customized for individuals with varying indivisibility ratios. We provide both upper and lower bounds on the fractions of the modified item in order to satisfy the fairness criterion. Our results are tight up to a constant for EF and asymptotically tight for PROP. ## Full text ## 1 Introduction Fair division of a mixture of divisible and indivisible goods has been well motivated since Bei et al. [2021a]. This scenario is exemplified in the context of dividing inheritances, where the assets include both money and land (divisible goods) as well as houses and cars (indivisible goods). In contrast to the division of purely divisible goods, one of the key challenges lies in defining and characterizing the notions of fairness that are both ideal and practical. This aspect continues to be a subject of ongoing discussion and exploration in the literature [Kawase et al., 2023; Liu et al., 2024], and our work contributes to this ongoing debate. When the goods are all divisible, envy-freeness (EF) [Foley, 1967; Varian, 1974] and proportionality (PROP) [Steinhaus, 1949] are the prominent fairness notions. Informally, an allocation is EF if every agent does not envy any other agent's bundle, and is PROP if every agent's utility over her bundle is no less than 1/n, where n is the number of agents and each agent's total utility is normalized to 1. When the goods are all indivisible, due to the fact that EF and PROP allocations barely exist, the "up to one" relaxation is one of the most widely accepted notions, such as envy-freeness up to one good (EF1) which ensures that the envy between two agents can be resolved by removing a single good [Lipton et al., 2004; Budish, 2011], and proportionality up to one good (PROP1) which requires every agent's utility to be no less than 1/n after grabbing an additional good from some other agent's bundle [Conitzer et al., 2017]. EF1 and PROP1 have some nice properties, such as guaranteed existence, simple computation, and being compatible with Pareto optimality (PO) [Caragiannis et al., 2019]. ∗ Shengxin Liu is the corresponding author. When the goods are mixed, EF1 and PROP1 can be directly applied and guaranteed to be satisfiable, by treating the divisible goods as hypothetical infinitesimally indivisible units. However, these "up to one" relaxations are rather weak fairness criteria, as the presence of divisible goods can help alleviate the burden of unfairness. In light of this, Bei et al. [2021a] introduced envy-freeness for mixed goods (EFM), whose existence is also guaranteed: for any two agents i and j, agent i does not EFM-envy agent j if (1) agent i does not envy agent j, or (2) agent j's bundle only contains indivisible goods and agent i does not EF1-envy agent j. EFM serves as a stronger notion than EF1 as condition (2) forces j's bundle to only contain indivisible goods if agents i envies j. Apart from EFM, a more straightforward approach to enhance EF1 and quantify the help of divisible goods in achieving fairness is to directly strengthen the "up to one" relaxation to the "up to a fraction", and the specific fraction depends on the portion of indivisible goods in relation to all goods. Intuitively, an agent may desire fairer allocations when her portion of divisible goods is more valuable. One possible way to quantify the portion of (in)divisible goods for each agent i is through her indivisibility ratio αi, where αi represents the portion of utility derived from indivisible goods. Then, an allocation is envy-free up to α-fraction of one good (EFα) to agent i if any envy she has towards another agent j can be resolved by obtaining an αi fraction of some indivisible item from agent j's bundle. Similarly, an allocation is proportional up to α-fraction of one good (PROPα) to agent i if her utility remains at least 1/n after acquiring an αi fraction of some indivisible item from another agent's bundle. It is important to note that the "up to α" relaxation allows for varying indivisibility ratios among the agents, thereby tailoring the evaluation of fairness based on each agent's specific perspective. In this work, we focus on EFα and PROPα. Example. To illustrate the difference between EFM and EFα, we consider the following example, where two indivisible goods M = {o1, o2} and one cake C are allocated to three identical agents. The utility function u(·) is shown in Table 1. Allocation A = (A1, A2, A3) with A1 = A2 = 12 C and A3 = {o1, o2} is EFM, but it is not EFα since removing 0.5 fraction from item o1, the remaining utility of A3 is 0.25 × 0.5 + 0.25 = 0.375 which is still greater than 0.25. From this example, we observe that when the indivisibility ratio is small, EFα can ensure a fairer or more balanced allocation which can be closer to EF. In contrast, EFM may return an allocation that appears somewhat unfair due to its adherence to the EF1 criteria for bundles comprising solely indivisible goods. Furthermore, unlike EFM, when agents are non-identical, EFα guarantees customized fairness based on various personalized indivisibility ratios. Table 1: An Example on EFM v.s. EFα | o1 | o2 | C | α | |-----------|------|-----|-----| | u(·) 0.25 | 0.25 | 0.5 | 0.5 | ## 1.1 Main Results In this paper, we propose to study the "up to a fraction" relaxation of EF and PROP, when a mixture of divisible and indivisible goods are allocated. We show that an EFα allocation may not exist and a PROPα allocation always exists. Thus we would like to understand to what extent EFα needs to be relaxed and PROPα can be strengthened, namely EFf (α) and PROPf(α), so that a fair "up to a fraction" allocation exists. In Section 3, we study the "up to a fraction" relaxation of EF, i.e., EFα and EFf(α). We first prove that f(α) = Θ(n)α is necessary and sufficient to satisfy EF by removing f(α) fraction of a good. We find that any EFM allocation is EFnα, and thus an EFnα allocation always exists (by [Bei et al., 2021a]). The guarantee of EFM cannot be improved even when agents have identical valuations. On the other hand, we prove that at least n2 4(n-1) α fraction of the good has to be removed in order to satisfy EF, and thus our results are tight up to a constant. Besides, when agents have identical valuations, we show that a simple greedy algorithm ensures an EF n2 4(n-1) α allocation, which exactly characterizes the extent to which EFf(α) can be guaranteed in this restricted case. We then focus on the "up to a fraction" relaxation of PROP, namely, PROPα and PROPf(α), in Section 4. In contrast to EFα, EFM implies PROPα whose existence is thus guaranteed. Additionally, we design a simple polynomial-time algorithm to compute such an allocation. On the negative side, we find that a PROP( n-1 n -ε)α allocation does not always exist for any ε > 0 so that our bound is asymptotically the best possible. On top of the existence result, in Section 5, we prove that PROPα and an economic efficiency criterion of Pareto optimality (PO) can be ensured simultaneously. Throughout our analysis, we draw upon the ideas in [Caragiannis et al., 2019] and show that any maximum Nash welfare allocation satisfies PROPα and PO in the context of mixed goods. We stress that our analysis significantly differs from and is much more intricate than the analysis in [Caragiannis et al., 2019]. This is because we need to evaluate the allocation as a whole, compelled by the PROP requirement and the definition of the indivisibility ratio, rather than relying on a simple pairwise exchange analysis. To tackle this issue, we utilize a monotone property to derive a decent tight condition on one agent's utility. We also point out that previous results on the compatibility of PROP and PO were directly deduced from the compatibility of EF and PO. However, as an EFα allocation may not exist, we directly study PROPα in this paper. The relations between the "up to a fraction" fairness notions and other well-known notions in the mixed goods setting are discussed in Section 6. ## 1.2 RelatedWork The study of fair allocation is extensive (see, e.g., Brams and Taylor; Robertson and Webb; Moulin; Suksompong; Amanatidis et al. [1995; 1998; 2019; 2021; 2023] for a survey). To capture fairness, various notions have been proposed for divisible and indivisible goods, including EF [Foley, 1967; Varian, 1974] and PROP [Steinhaus, 1949] for divisible goods; EF1 [Lipton et al., 2004; Budish, 2011] and PROP1 [Conitzer et al., 2017] for indivisible goods. There are also some notable fairness notions, e.g., envy-freeness up to any good (EFX) [Lipton et al., 2004; Gourv`es et al., 2014] and maximin share (MMS) [Budish, 2011], etc. Recently, a stream of literature has focused on the fair allocation problem with a mixture of divisible and indivisible goods (mixed goods) [Bei et al., 2021a; Bei et al., 2021b; Bhaskar et al., 2021; Nishimura and Sumita, 2023; Bei et al., 2023]. In particular, Bei et al. [2021a] initiated the fair division problem with mixed goods and proposed the fairness notion envy-freeness for mixed goods (EFM). Further, Bei et al. [2021b] and Kawase et al. [2023] considered the fairness notions of MMS and envy-freeness up to one good for mixed goods (EF1M) in the mixed goods setting, respectively. Note that, the ratio of approximate MMS allocation obtained in [Bei et al., 2021b] is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values. On the other hand, our proposed indivisible ratio is determined by how an agent values the divisible goods relative to her value of all goods. Furthermore, Li et al. [2023] and Li et al. [2024] examined EFM in conjunction with the issues of truthfulness and price of fairness, respectively. See a recent survey on the mixed fair division for more details [Liu et al., 2024]. In addition, several studies considered the interplay between fairness and efficiency for fair allocation [Barman et al., 2018; Barman and Krishnamurthy, 2019; Freeman et al., 2019; Murhekar and Garg, 2021; Aziz et al., 2020; Wu et al., 2021]. Specifically, EF, EF1, and EF1M are compatible with Pareto optimality (PO) (i.e., a criterion of efficiency) via the maximum Nash welfare allocation in the divisible, indivisible, and mixed goods settings, respectively [Segal-Halevi and Sziklai, 2019; Caragiannis et al., 2019]. It is worth noting that EFM is incompatible with PO while whether a weak version of EFM can be combined with PO is an open question in the mixed goods setting [Bei et al., 2021a]. ## 2 Preliminaries Let [k] denote the set {1, 2, . . . , k} for any positive integer k. We consider the mixed goods setting. Denote by N = {1, 2, . . . , n} the set of n agents, M = {o1, o2, . . . , om} the set of m indivisible goods, and C = [0, 1] the set of heterogeneous divisible goods or a single cake. 1 Define A = M∪C to be the set of mixed goods. An allocation of the mixed goods is defined as A = (A1, A2, . . . , An) where Ai = Mi ∪ Ci is the bundle allocated to agent i subject to: 1) Ci is a union of countably many intervals; 2) for any i, j ∈ [n], Mi ∩Mj = ∅ and Ci ∩ Cj = ∅; 3) ⋃i∈[n] Ai = A. Each agent i has a nonnegative utility function ui(·). Assume that each ui is additive over A and integrable over C, that is, for any M ′ ⊆ M and C ′ ⊆ C, ui(M ′ ∪ C ′ ) = ∑o∈M′ ui(o) + ∫C′ ui(x)dx. We also assume without loss of generality that agents' utilities are normalized to 1, i.e., ui(M ∪ C) = 1 for each i ∈ N. We first show the classic fairness notions in the literature. ## Definition 2.1 (EF & PROP). An allocation A is called - envy-freeness (EF) if for any agents i, j ∈ N, ui(Ai) ≥ ui(Aj ); - proportionality (PROP) if for any agent i ∈ N, ui(Ai) ≥ 1/n. As mentioned before, for indivisible goods, relaxations of EF/PROP are commonly studied in the previous works. Definition 2.2 (EF1 & PROP1). An allocation A is called - envy-freeness up to one good (EF1) if for any agents i, j ∈ N, there exists an indivisible good o ∈ Mj such that ui(Ai) ≥ ui(Aj \ {o}); - proportionality up to one good (PROP1) if for any agent i ∈ N, there exists an indivisible good o ∈ M\Mi such that ui(Ai) + ui(o) ≥ 1/n. However, as illustrated in the introduction, EF1 and PROP1 are rather weak in the mixed goods setting. In this paper, we introduce new "up to a fraction" fairness notions with the help of indivisibility ratio. Definition 2.3 (Indivisibility Ratio). For each agent i, the indivisibility ratio αi is defined as αi := ui(M) ui(M)+ui(C) . For each agent i, αi is the ratio between the utility for all indivisible goods and the utility for all goods. We point out that each agent has a personalized indivisibility ratio, allowing us to define the fairness with respect to each agent's perspective. Specifically, we introduce the following new fairness notions. Definition 2.4 (EFα & PROPα). An allocation A is called 1 When there are more than one heterogeneous divisible goods, say C = {c1, c2, . . . , cℓ}, each cake can be represented by an interval [ j-1 ℓ , jℓ ), and thus the entire set of divisible goods can be regarded as a single cake C = [0, 1). Later we assume agents' utility functions over C are non-atomic, and hence the cake [0, 1) is equivalent to [0, 1]. - envy-freeness up to α-fraction of one good (EFα) if for any agents i, j ∈ N, there exists an indivisible good o ∈ Mj such that ui(Ai) ≥ ui(Aj) - αi · ui(o). - proportionality up to α-fraction of one good (PROPα) if for any agent i ∈ N, there exists an indivisible good o ∈ M\Mi such that ui(Ai) + αi · ui(o) ≥ 1/n. It is easy to observe that when an agent has a higher utility for the cake, her indivisible ratio becomes smaller. This, in turn, implies that she is more likely to receive an allocation closer to EF/PROP under the EFα/PROPα criteria. One can easily check that when good is only the cake, EFα (resp., PROPα) reduces to EF (resp., PROP); when goods are all indivisible, EFα (resp., PROPα) reduces to EF1 (resp., PROP1). We can also observe that EFα implies PROPα. As we will show later, an EFα allocation may not exist and a PROPα allocation always exists. For a better understanding of what EFα needs to be relaxed and PROPα can be strengthened, we next introduce the generalizations of EFα and PROPα. Definition 2.5 (EFf(α) & PROPf(α)). An allocation A is - envy-freeness up to one f(α)-fraction of good (EFf(α)) if for any agents i, j ∈ N, there exists an indivisible good o ∈ Mj such that ui(Ai) ≥ ui(Aj)-f(αi)·ui(o). - proportionality up to one f(α)-fraction of good (PROPf(α)) if for any agent i ∈ N, there exists an indivisible good o ∈ M\Mi such that ui(Ai) + f(αi) · ui(o) ≥ 1/n. When f(α) = α, the above notions degenerate to EFα and PROPα. In this paper, we focus on the linear function form f(α) = g(n) · α, where g(n) is a function of the number of agents. One can obtain stronger (resp., weaker) fairness requirements by making g(n) smaller (resp., larger). We also consider the efficiency of the allocations. Definition 2.6 (PO). An allocation A is said to satisfy Pareto optimality (PO) if there is no allocation A′ that Paretodominates A, i.e., ui(A′i ) ≥ ui(Ai) for all agents i ∈ N and ui(A′i ) > ui(Ai) for some agents i ∈ N. Definition 2.7 (MNW). An allocation A is a maximum Nash welfare (MNW) allocation if the number of agents with positive utility is maximized, and subject to that, the product of the positive utilities (∏i∈[n]:ui(Ai)>0 ui(Ai)) is maximized. Finally, we utilize the Robertson-Webb (RW) query model [Robertson and Webb, 1998] for accessing agents' utility functions over the cake. The RW model allows algorithms to query the agents with the following two methods: 1) an evaluation query on [x, y] for agent i returns ui([x, y]), and 2) a cut query of β for agent i from x returns the leftmost point y such that ui([x, y]) = β, or reports no such y exists. In this paper, we assume each RW query using O(1) time. ## 3 Envy-freeness up to a Fractional Good In this section, we focus on envy-freeness up to a fractional good, i.e., EFα and EFf(α). We first present that for two agents, an EFα + PO allocation always exists and an EFα allocation can be found in polynomial time. Then, we proceed to consider the case with n ≥ 3 agents and show that there does not exist EF( n2 4(n-1) - ε)α allocations for any ε > 0. We then explore the best fairness guarantee under EFf(α). In particular, we find that an EFnα allocation always exists which is tight up to a constant factor. When agents have identical utility, we further show that f(α) = n2 4(n-1) α is the exact fraction we can guarantee for EFf(α). ## 3.1 Two Agents In this part, we first make use of the polynomial-time algorithm for finding an EFM allocation with two agents in [Bei et al., 2021a] to provide the existence of EFα allocations for two agents. Theorem 3.1. When n = 2, an EFα allocation exists and can be found in polynomial time. The omitted proofs in this paper can be found in the full version on arXiv. We now proceed to show the compatibility of EFα and PO for two agents. In particular, we first consider an allocation obtained via a variant of the cutand-choose procedure: the first agent partitions the goods into two bundles Ax and Ay as equal as possible (assume max{u2(Ax), u2(Ay)} is maximized if multiple such partitions exist), and the second agent chooses first. Such an allocation can be utilized to return an EFα and PO allocation through Pareto improvements, which leads to the following theorem. Theorem 3.2. When n = 2, an EFα and PO allocation always exists . ## 3.2 General Number of Agents We move on to consider the case of a general number of agents n ≥ 3 in this part. When the resources to be allocated contain only divisible or indivisible goods, EFα allocations always exist. However, when the goods are mixed, we show that EFα allocations fail to exist even when there is only one homogeneous cake 2 and one indivisible good. Theorem 3.3. For n ≥ 3 agents, an EFα allocation does not always exist. Specifically, for any ε > 0, an EF( n2 4(n-1) -ε)α allocation does not always exist. Proof. The proof is derived from the following counterexample where we have n identical agents, one indivisible good o, and one homogeneous cake C. | | o | C | α | |-----------------|-----|-------|-----| | ui(·), ∀i ∈ [n] | 2n | n-2 n | 2n | Suppose the indivisible good o is allocated to agent n. Then there must exist one agent i ∈ [n - 1] such that ui(Ai) ≤ n-2 n(n-1) . For this agent i, 2 We call a cake homogeneous if the utility over a subset of cake C depends only on the length of this subset, i.e., for each i ∈ [n] and any C′ ⊆ C, ui(C′ ) = |C′ | |C| · ui(C), where |C′ | and |C| represents the length of C′ and C, respectively. When n ≥ 3, we have 2n > 1 n-1 , and thus 2(n-2) n2 > n-2 n(n-1) which implies that agent i fails to achieve EFα. The above analysis can be tighter, and we have On the positive side, we will show in Section 6 that EFM implies EFnα (Theorem 6.2) which means that an EFnα allocation can be derived by using the polynomial algorithm for EFM in [Bei et al., 2021a]. This also implies that when n ≥ 3, the best fairness guarantee under EFf(α) notion would be EFΘ(n)α. Further, when all agents are identical, we show that the exact fairness guarantee under EFf(α) notion is EF n2 4(n-1) α. Theorem 3.4. When agents have identical utility functions, an EF n2 4(n-1) α allocation always exist. We achieve this via an algorithm that first finds an EF1 allocation for indivisible goods and leverages the water-filling procedure 3 to allocate the divisible goods. The idea behind the proof is to reduce the hardest case to the counterexample used in the proof of Theorem 3.3. However, such an idea is not applied to the non-identical agents setting, where the presence of multiple indivisible goods may complicate the envy graph and prevent us from reducing it to a case with only one indivisible good. ## 4 Existence and Computation of PROPf(α) In this section, we focus on the proportionality up to a fractional good (i.e., PROPα and PROPf(α)). We first prove by presenting a polynomial algorithm that a PROPα allocation always exists in the mixed good setting. Subsequently, we consider the PROPf(α) notion and show a lower bound of f(α), giving an asymptotically tight characterization for the existence of PROPf(α). ## 4.1 The Algorithm The complete algorithm for finding a PROPα allocation is shown in Algorithm 1. Conceptually, Algorithm 1 performs the "moving-knife" procedure on indivisible goods and the cake separately through n - 1 rounds (Steps 2-14). In each round, one agent is allocated with a bundle that yields a utility that achieves PROPα. The bundle is firstly filled by indivisible goods (Step 4) until there exists an indivisible good o such that after adding o to the bundle, some agent j will be satisfied with the bundle. Then, depending on whether we can make some agent satisfied by only adding some cake to the bundle, we execute either Case 1 (Steps 5-8) or Case 2 (Steps 9-14). - Case 1: when the cake is not large enough to make any agent satisfied, we simply add the indivisible good o to the bundle and allocate it to agent j. 3 Allocating the cake in such a way that the minimum utility among all agents' utilities is maximized. ## Algorithm 1: Finding a PROPα allocation Data: Agents N, indivisible goods M and cake C ``` Result: A PROPα allocation (A1, A2, . . . , An) 1 ˆM ←M, ˆ C ← C; 2 while |N| ≥ 2 do 3 B ← ∅; 4 Add one indivisible good in ˆM at a time to B until adding the next indivisible good o will cause uj(B ∪ {o}) ≥ 1/n - αj · uj(g) for some agent j and some good g ∈ M \ (B ∪ {o}), or M \ (B ∪ {o}) = ∅; 5 if ∀i ∈ N and g ∈M \ B, ui(B ∪ ˆ C) < 1/n-αi · ui(g) then 6 // Case 1: allocate with only indivisible goods; 7 Aj ← B ∪ {o}; 8 N ←N \ {j}, ˆM ← ˆM \ (B ∪ {o}); 9 else 10 // Case 2: allocate with cake; 11 Suppose now ˆ C = [a, b]. For all i ∈ N, if ui(B ∪ [a, b]) ≥ 1/n-αi · ui(g), let xi be the leftmost point such that ui(B ∪ [a, xi)) = 1/n - αi · ui(g) for some good g ∈ M \ B; otherwise, let xi = b; 12 i∗ ← arg mini∈N xi; 13 Ai∗ ← B ∪ [a, xi∗ ); 14 N ←N\{i∗ }, ˆM ← ˆM\B, ˆ C ← ˆ C \[a, xi∗ ); ``` 15 Give all the remaining goods to the last agent; 16 return (A1,A2, . . . ,An); - Case 2: we first find out the minimum required piece of cake for each agent that will make her satisfied (Step 11). This step can be implemented through the RW model. Note that the condition of entering the second case ensures that at least one agent can be satisfied by adding some piece of the cake. we then find the optimal agent i∗ that requires the minimum piece of cake among all agents and allocate the piece of cake together with the bundle of indivisible goods to her. After allocating the bundles to n-1 agents, we give all the remaining goods to the last agent (Step 15). Assume, w.l.o.g., that agents 1, 2, . . . , n receive their bundles in order. We remark that when all goods are indivisible, our algorithm omits Case 2 and thus degenerates to the well-known bag-filling procedure. When the whole good is a divisible cake, the algorithm only executes Case 2 and then becomes the classical moving-knife algorithm. Though Algorithm 1 is a natural extension of the algorithms in the divisible goods setting and the indivisible goods settings, we claim that the analysis is non-trivial as shown in the next subsection. ## 4.2 Analysis Our main result for the existence and computation of PROPα allocations is as follows. Theorem 4.1. For any number of agents, Algorithm 1 returns a PROPα allocation in polynomial time. To prove Theorem 4.1, we will utilize some useful concepts and facts. Let k be the first agent that receives her bundle with only indivisible goods in Steps 5 to 8. In other words, agents 1, . . . , k - 1 are assigned their bundles with some pieces of cake in Steps 9 to 14. Moreover, for distinction, we set k ← n if all the first n - 1 agents are assigned in Steps 9 to 14. The agent k plays an important role in bounding the ratio αi for the agent after k. The relation is shown below. Let oi be the indivisible good o as defined in Step 4 for the i-th iteration of the while-loop. For each agent j, we define gij = argmaxg∈(M\Mi)∪oi uj(g). Intuitively, gij is the good that, when agent i conducts the "moving-knife" procedure (and finally obtains Ai), for agent j, the most valuable good besides the bundle Ai without oi. The next claim makes a connection between the above two definitions. Claim 4.3. uj(gij) ≥ uj(op) for any agents i, j, p with i ̸= n and op ̸= oi-1. We are ready to prove the following lemma. Lemma 4.4. Before the j-th iteration, the remaining goods are enough for j to achieve PROPα. Specifically, we have where ˆM ∪ ˆ C represents the remaining goods just before the j-th iteration. Proof Sketch. The proof unfolds in two cases: when j ≤ k and when j > k. The first case is relatively straightforward. Since all agents before k receive some pieces of cake to meet the PROPα condition exactly from the definition of k, we have uj (Ai) ≤ 1/n-αj ·uj (gij ) for each i < j from Step 11, which implies the required statement. Turning to the second case, due to the potential allocation of an additional good o to some previous bundles at Case 1, we can only have uj (Ai) ≤ 1/n - αj · uj(gij + oi) for each i < j. We then utilize Claims 4.2 and 4.3 to bound the terms αj and uj(oi) and derive the results through some intricate analysis. We now turn our attention to the proof of Theorem 4.1. Proof of Theorem 4.1. It is clear that all the goods are allocated after Step 15 of Algorithm 1. We next consider the correctness of the algorithm. By Lemma 4.4, we know that each iteration of the while-loop of Algorithm 1 is well-defined, which means that each agent in {1, . . . , n - 1} achieves her PROPα, either in Steps 5 to 8 or in Steps 9 to 14. For the last agent, Lemma 4.4 also implies that the PROPα of agent n can be satisfied. Since each step in this algorithm can be executed in polynomial time and the total number of the while loop at Step 2 is exactly n - 1, we can conclude the polynomial running time of the algorithm, which completes the proof. ## 4.3 Impossibility Result From Theorem 4.1, we know that a PROPα allocation always exists. In the following, we give a lower bound on f(α) such that PROPf(α) allocation is not guaranteed to exist. Theorem 4.5. For any ε > 0, a PROP( n-1 n -ε)α allocation does not always exist. This impossibility result with Theorem 4.1 also implies that we obtain an asymptotically tight characterization for the existence of PROPf(α). ## 5 Compatibility of PROPα and PO In this section, we show the compatibility of PROPα and PO. In particular, we prove that any allocation that maximizes Nash welfare (which is trivially PO) must be PROPα, and the implication regarding parameter α is tight. It is important to note that our approach is different from the conventional ones in [Caragiannis et al., 2019; Kawase et al., 2023] since PROPα is not defined using pairwise comparisons between agents. PROPα requires an agent to compare her own bundle and the union of the goods allocated to all the other agents, and moreover, such a comparison, as relaxed by the indivisibility ratio times the value of the largest item outside of her bundle, is sensitive to the overall allocation. To overcome this complexity, we later present a monotone property of Nash welfare maximizing allocations (see Corollary 5.6) to quantify the effect of the reallocation of (fractional) goods. Theorem 5.1. Any MNW allocation satisfies PROPα. The proof of Theorem 5.1 relies on the following nice properties. The first one states that we can remove the goods that yield zero value to all agents without loss of generality. Observation 5.2. In an MNW allocation, if there exists a subset p ⊆ Ai such that ui(p) = 0, then for every j ∈ [n] we have uj(p) = 0. Therefore, we can simply remove p from A. Formally, we assume with out loss of generality that Base on the above assumption, we further show the following reduction that since any agent with zero utility in an MNW allocation must have at most n positive-valued goods and no positive-valued cake, the agent achieves PROPα and we can focus only on other agents with positive utility. Lemma 5.3. Suppose Eq. (2) holds. If Theorem 5.1 holds for every instances admitting an MNW allocation with no agent with zero utility, then Theorem 5.1 holds for every instances. Lemma 5.3 allows us to assume that in the following proofs. In the next lemma, we show that if an agent i does not envy some other agent, then the PROPα criterion can be reduced to the case when agent i envies all other agents. Lemma 5.4. Suppose Eq. (2) and Eq. (3) hold. If Theorem 5.1 holds for any agent that envies all other agents, Theorem 5.1 holds for every agents. In the following proofs, with Lemma 5.4, we suppose without loss of generality that With above three assumptions, we turn to characterize the constraints of MNW allocations on the utility function of a specific agent. We use the property that if we move a set S of goods from one agent to another agent under an MNW allocation, the product of their utilities must not increase. Formally, given agent i, j, for any S ⊂ Ai we have Further, we have the following observation. Observation 5.5. Given agent i, j, if there exists S ⊆ Ai such that fij(S) > 0 and S can be partitioned into two nonempty set S1 and S2, then either fij(S1) > 0 or fij(S2) > 0. This observation directly implies the following corollary. Corollary 5.6. Given agent i, j, for some S ⊆M, if for any g ∈ S we have fij({g}) ≤ 0, then for any subset T ⊆ S we have fij({g}) ≤ 0. We extend the above idea to divisible goods to derive a condition on some agent's utility function, the following lemma. Lemma 5.7. Suppose Eq. (2), Eq. (3), and Eq. (4) hold. In an MNW allocation, for any two (possibly same) agents i and j, Proof. If i = j, it's sufficient to show that Now assume i ̸= j. Suppose P = {p1, · · · , pk} is an arbitrary partition of Aj. The definition of MNW allocation tells that if agent j gives the p ∈ P to agent i, the product of the utilities does not increase. Thus Notice that this inequality holds for every p ∈ P , we have We can improve the above condition by constructing the partition P. From Corollary 5.6, if each of pi ∈ P is small enough, the set of inequalities (6) actually covers almost all the MNW condition on moving a subset p ⊆ Aj . Specifically, given ε > 0, we consider the following partition where PC is a partition of Cj such that |PC| = ⌈ ui(Cj) ε ⌉ and for every p ∈ PC, we have ui(p) = ui(Cj) ⌈ ui (Cj ) ε ⌉ ≤ ε. Such partition can be obtained through |PC| queries in the RWmodel. With this partition, we have Notice from the Sandwich Theorem that Hence, as ε → 0, we have which completes the proof. Given the above nice properties of MNW allocations, it is not hard to prove that these allocations must be PROPα. Finally, we remark that our analysis is tight. Theorem 5.8. For any ε > 0, an MNW allocation may not be a PROP(1 - ε)α allocation. ## 6 Relation with Other Fairness Notions We explore the relation among EFf(α), PROPf(α) and other notions (EFM and MMS) in the mixed goods setting. A summary of the results in this section is provided in Figure 1. Figure 1: Relations among different fairness notions, where X → Y means that an allocation satisfying X must also satisfy Y . ![Image](https://ijcai.org/proceedings/2024/fulltext/318/image_000000_76a099121f4cbc6cb0197f318edb439ff94906893090c429386b53df0cab71c1.png) ## 6.1 Connections to EFM We first discuss the relations of our "up to a fraction" fairness notions with EFM, proposed in [Bei et al., 2021a]. Definition 6.1 (EFM). An allocation A is said to be envy-free for mixed goods (EFM) if for any two agents i, j ∈ N: - if Cj = ∅ and Mj ̸= ∅, there exists o ∈ Mj such that ui(Ai) ≥ ui(Aj\{o}), - otherwise, ui(Ai) ≥ ui(Aj). It is easy to verify that EFM does not imply EFα; recall the example in Section 1. However, EFM can imply a generalized version of EFα, as shown in the theorem below. Theorem 6.2. Any EFM allocation is EFnα. On the other side, we show that EFnα is the best guarantee under EFf(α) that an EFM allocation ensures. Theorem 6.3. For any ε > 0, an EFM allocation may not be EF(n - ε)α. We then consider the relation between PROPα and EFM. Theorem 6.4. An EFM allocation is PROPα. This relation is also tight due to the following result. Theorem 6.5. For any ε > 0, an EFM allocation may not be PROP(1 - ε)α. It is worth noting that Bei et al. [2021a] designed an algorithm for computing an EFM allocation. However, their algorithm utilizes the perfect allocation oracle, which is not in polynomial time when we have a heterogeneous cake, and consists of the intricate envy-graph maintenance and envycycle elimination subroutine. On the contrary, Algorithm 1 runs in polynomial time and is simple to implement. ## 6.2 Connections toMMS We also consider the relation of our "up to a fraction" fairness notions with MMS as defined in the following. Definition 6.6 (β-MMS). Let Πn(A) be the set of all npartitions of A. The maximin share (MMS) of any agent i ∈ N is defined as An allocation that reaches MMSi is called an MMSallocation of agent i. Given any β ∈ [0, 1], allocation A is β-approximate MMS fair (β-MMS) if ui(Ai) ≥ β · MMSi for every agent i ∈ N. When β = 1, we simply write MMS. It is easy to see that when the goods are all divisible, MMS coincides with PROP. When the goods are all indivisible, MMS is strictly weaker than PROP but implies PROP1 [Caragiannis et al., 2023]. Our next result is a generalization that encompasses these two extreme cases. Theorem 6.7. Any MMS allocation is PROPα. Recall that MMS allocations may not exist, however, an approximately MMS allocation may not be PROPα. Theorem 6.8. For any β ∈ (0, 1), a β-MMS allocation may not be PROPα. ## 7 Conclusion We study the fair allocation of a mixture of divisible and indivisible goods. We introduce the indivisibility ratio and fairness notions of envy-free and proportional up to a fractional good, which serves as a smooth connection between EF/PROP and EF1/PROP1. Our results exhibit the limit of the amount of the fractional item that we need to relax so that a fair allocation is guaranteed, which affirm the intuition that the more divisible items we have, the fairer allocations we can achieve. There are some problems left open. For example, there is a constant gap between the upper and lower bounds of the fractional relaxation of EF, and it is not clear whether EFnα and PO are compatible. Our paper also unveils intriguing possibilities for future research. One such avenue is proposing alternative relaxations of the ideal fairness principles to better capture the characteristics of mixed scenarios, such as the customized indivisibility ratio in our model. ## Acknowledgments Shengxin Liu is funded by the National Natural Science Foundation of China (No. 62102117), by the Shenzhen Science and Technology Program (No. GXWD20231129111306002), and by the Guangdong Basic and Applied Basic Research Foundation (No. 2023A1515011188). Bo Li is funded by the National Natural Science Foundation of China (No. 62102333) and Hong Kong SAR Research Grants Council (No. PolyU 25211321). ## References 1. [Amanatidis et al., 2023] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023. 2. [Aziz et al., 2020] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for comput- ing a Pareto optimal and almost proportional allocation. Operations Research Letters, 48(5):573-578, 2020. 3. [Barman and Krishnamurthy, 2019] Siddharth Barman and Sanath Kumar Krishnamurthy. On the proximity of mar- kets with integral equilibria. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 1748- 1755, 2019. 4. [Barman et al., 2018] Siddharth Barman, Sanath Kumar Kr- ishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the ACM Conference on Economics and Computation (EC), pages 557-574, 2018. 5. [Bei et al., 2021a] Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu. Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293:103436, 2021. 6. [Bei et al., 2021b] Xiaohui Bei, Shengxin Liu, Xinhang Lu, and Hongao Wang. Maximin fairness with mixed divisi- ble and indivisible goods. Autonomous Agents and Multi- Agent Systems, 35(2):34, 2021. 7. [Bei et al., 2023] Xiaohui Bei, Shengxin Liu, and Xinhang Lu. Fair division with subjective divisibility. In Proceed- ings of the Conference on Web and Internet Economics (WINE), page 677, 2023. 8. [Bhaskar et al., 2021] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisi- ble chores and mixed resources. In Proceedings of the In- ternational Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 1:1-1:23, 2021. 9. [Brams and Taylor, 1995] Steven J. Brams and Alan D. Tay- lor. An envy-free cake division protocol. The American Mathematical Monthly, 102(1):9-18, 1995. 10. [Budish, 2011] Eric Budish. The combinatorial assign- ment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. 11. [Caragiannis et al., 2019] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3):12:1-12:32, 2019. 12. [Caragiannis et al., 2023] Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, Giovanna Varricchio, et al. New fairness concepts for allocating indivisible items. In Proceedings of the International Joint Conference on Ar- tificial Intelligence (IJCAI), pages 2554-2562, 2023. 13. [Conitzer et al., 2017] Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Pro- ceedings of the ACM Conference on Economics and Com- putation (EC), pages 629-646, 2017. 14. [Foley, 1967] Duncan Karl Foley. Resource allocation and the public sector. Yale Economics Essays, 7(1):45-98, 1967. 15. [Freeman et al., 2019] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable allocations of indivisi- ble goods. In Proceedings of the International Joint Con- ference on Artificial Intelligence (IJCAI), pages 280-286, 2019. 16. [Gourvès et al., 2014] Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. Near fairness in matroids. In Proceed- ings of the European Conference on Artificial Intelligence (ECAI), pages 393-398, 2014. 17. [Kawase et al., 2023] Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Fair allocation with binary valua- tions for mixed divisible and indivisible goods. CoRR, abs/2306.05986, 2023. 18. [Li et al., 2023] Zihao Li, Shengxin Liu, Xinhang Lu, and Biaoshuai Tao. Truthful fair mechanisms for allocating mixed divisible and indivisible goods. In Proceedings of the International Joint Conference on Artificial Intel- ligence (IJCAI), pages 2808-2816, 2023. 19. [Li et al., 2024] Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao. A complete landscape for the price of envy-freeness. In Proceedings of the Interna- tional Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2024. 20. [Lipton et al., 2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 125-131, 2004. 21. [Liu et al., 2024] Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. In Proceedings of the AAAI Conference on Artificial Intelli- gence (AAAI), pages 22641-22649, 2024. Senior Member Presentation Track. 22. [Moulin, 2019] Hervé Moulin. Fair division in the internet age. Annual Review of Economics, 11(1):407-441, 2019. 23. [Murhekar and Garg, 2021] Aniket Murhekar and Jugal Garg. On fair and efficient allocations of indivisible goods. In Proceedings of the AAAI Conference on Artificial Intel- ligence (AAAI), pages 5595-5602, 2021. 24. [Nishimura and Sumita, 2023] Koichi Nishimura and Hanna Sumita. Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods. CoRR, abs/2302.13342v2, 2023. 25. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-Cutting Algorithm: Be Fair If You Can. A K Peters/CRC Press, 1998. 26. [Segal-Halevi and Sziklai, 2019] Erel Segal-Halevi and Balázs R. Sziklai. Monotonicity and competitive equilib- rium in cake-cutting. Economic Theory, 68(2):363-401, 2019. 27. [Steinhaus, 1949] Hugo Steinhaus. Sur la division pragma- tique. Econometrica, 17:315-319, 1949. 28. [Suksompong, 2021] Warut Suksompong. Constraints in fair division. ACM SIGecom Exchanges, 19(2):46-61, 2021. 29. Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63-91, 1974. 30. [Wu et al., 2021] Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum Nash social welfare is almost envy-free. In Proceedings of the International Joint Con- ference on Artificial Intelligence (IJCAI), pages 465-471, 2021.