Asymptotic Fair Division: Chores Are Easier Than Goods

1 Introduction

In applications of dividing items among agents, such as distributing teaching loads to faculty members or splitting household tasks between partners, fairness is often a key consideration [Brams and Taylor, 1996; Moulin, 2003]. To formally reason about fairness, one must define what it means to be "fair". Among the plethora of fairness notions proposed in the literature, two of the most widely used are envy-freeness and proportionality. An allocation is called envy-free if no agent prefers to swap her bundle of items with that of another agent, and proportional if every agent receives no worse than her proportionally fair share, defined as 1/n of her value for the entire set of items with n denoting the number of agents.

When the items to be allocated are indivisible-that is, each item must be allocated in its entirety to one agent-an envy-free or proportional allocation may not exist. For example, when m valuable goods are divided among n > m agents, at least one agent will be left empty-handed; such an agent will be envious and deprived of her proportional share. In light of this, Dickerson et al. [2014] asked the following natural question: if the agents' utilities for goods are drawn at random from a distribution, for which asymptotic relations between m and n does an envy-free allocation exist with high probability (meaning that the probability of existence approaches 1 as n → ∞)? They showed that the asymptotic existence occurs when m = Ω(n log n), but not when m = n + o(n). Manurangsi and Suksompong [2020, 2021] closed this gap by proving that if m is divisible by n, an envym ≥ 2n, whereas if m is not "almost divisible" 1 by n, existence is guaranteed only when m = Ω(n log n/ log log n). For proportionality, Manurangsi and Suksompong [2021] showed that existence is likely whenever m ≥ n; this is tight since no proportional allocation exists when m < n.

In this paper, we investigate asymptotic fair division of chores, i.e., items that yield disutility to agents. Due to its broad applicability-including the division of teaching loads, medical shifts, and household tasks-chore allocation has received significant attention in the fairness literature [Guo et al., 2023]. As we shall demonstrate, the asymptotic results for chores are markedly different from those for goods, with respect to both envy-freeness and proportionality.

1.1 Our Contributions

In our model, each agent's disutility for each chore is drawn independently from a non-atomic distribution D supported on [0, 1], and the agents' disutilities are additive across chores. Following prior work in this domain, we assume for most of our results that D is PDF-bounded, meaning that its probability density function is bounded below and above by some positive constants α and β, respectively [Manurangsi and Suksompong, 2021; Bai and G¨olz, 2022; Yokoyama and Igarashi, 2025]. We describe the model formally in Section 2.

Our first result is that an envy-free allocation of the chores exists (and can be computed efficiently) with high probability as long as m ≥ 2n.

Theorem 1.1. For any PDF-bounded distribution D, if m≥ 2n, then with high probability, an envy-free allocation exists. Moreover, there is a polynomial-time algorithm that computes such an allocation.

Theorem 1.1 stands in contrast to the case of goods, where if m is not almost divisible by n, then m needs to be at least Ω(n log n/ log log n) for an envy-free allocation to exist with high probability [Manurangsi and Suksompong, 2020]. On the other hand, if m < n, clearly no envy-free allocation of the chores exists. We strengthen this observation by showing that when m exceeds n by a small (multiplicative) constant factor, an envy-free allocation is still unlikely to exist. This result does not require the PDF-boundedness assumption.

1 This means that the remainder upon dividing m by n is neither less than no(1) nor greater than n-no(1) .

Theorem 1.2. Let ν ≥ 1.1256 be the (unique) positive solution to the equation

For any constant ϵ ∈ (0, ν), if m ≤ (ν - ϵ)n, then with high probability, no envy-free allocation exists.

On the proportionality front, we establish that a surprisingly small number of chores-any superconstant numberis already sufficient to ensure existence.

Theorem 1.3. For any PDF-bounded distribution D, if m= ω(1), then with high probability, a proportional allocation exists. Moreover, there is a polynomial-time algorithm that computes such an allocation.

We also provide a matching bound, which shows that if m is constant, then there is a constant probability that no proportional allocation exists.

Theorem 1.4. For any (α, β)-PDF-bounded distribution D and any m, n such that mn ≤ 1 2β , the probability that no proportional allocation exists is at least e-2βm.

Theorems 1.3 and 1.4 essentially complete our understanding of the asymptotic existence of proportional allocations for chores. Again, this demonstrates a stark difference from the case of goods: for goods, no proportional allocation exists if m < n, whereas for chores, we have existence even when m is much smaller than n (e.g., m = Θ(log log n)).

Overall, our findings indicate that achieving fairness is, interestingly, easier for chores than for goods when viewed from an asymptotic perspective.

1.2 Overview of Proofs

We now provide a high-level overview of our proofs, starting with the existence of envy-free allocations (Theorem 1.1). The proof of this theorem involves handling three cases.

• Case I: m = Ω(n log n). In this case, we can use a similar approach to Dickerson et al. [2014], namely, we assign each chore to an agent with the lowest disutility for it, thereby minimizing social cost. A standard application of concentration inequalities shows that this yields an envy-free allocation with high probability.
• Case II: m = O(n logn) and m is divisible by n. In this case, the algorithm of Manurangsi and Suksompong [2020] for goods directly yields an envy-free allocation for chores. The reason is that their algorithm always outputs a balanced allocation, where every agent receives the same number of items. We may therefore view each chore as a "good" whose utility is a complement of the disutility of the chore; this transformation preserves the envy-freeness of allocations.
• Case III: m = O(n log n) and m is not divisible by n. This is the key novelty we contribute to the proof. Our algorithm starts by running the algorithm from Case II on the first ⌊m/n⌋ · n chores. We then show that most of

the agents have a sufficiently large "gap" between their own disutility and their disutility for any other agent's bundle. For these agents, such a gap allows us to assign the remaining chores to them as long as the disutilities are sufficiently low; we use a matching-based algorithm for this second step. It is worth noting that this case precisely captures the difference between goods and chores: for goods, such a gap would not allow us to assign an additional good to the agent, as some other agent might envy this agent as a result.

As for the non-existence of envy-free allocations (Theorem 1.2), we take inspiration from the corresponding result of Dickerson et al. [2014]. In particular, we consider chores that are "favorite" (i.e., yield the lowest disutility) for multiple agents. We observe that each of these chores cannot be in a singleton bundle in an envy-free allocation; otherwise, one such agent would envy the agent who receives the chore. By establishing a lower bound on the number of such chores, we arrive at our result.

We remark that there are two important differences between our non-existence result and that of Dickerson et al. [2014]. Firstly, in the case of goods, if a good is the favorite good for k agents, then at least k-1 of the agents must receive at least two goods in order to be envy-free. This is not true for chores, so we use the aforementioned observation instead. Secondly, to derive a high probability bound, Dickerson et al. relied on an application of Markov's inequalitythis leads to a lower bound of only m ≥ n + o(n). In this paper, we utilize a more refined approach based on the socalled Efron-Stein inequality, which allows us to obtain a high probability bound even for m ≥ n + Θ(n). We note that our approach can also be applied to the case of goods; however, we do not provide the details as it does not give us the tight bound (and the tight bound in that case has already been established by Manurangsi and Suksompong [2020]).

Next, we consider proportionality, again starting with existence (Theorem 1.3). Observe that if m ≥ 2n, the existence of envy-free allocations (Theorem 1.1) immediately implies that of proportional allocations. Thus, we may focus on the setting where m < 2n. It is further useful to distinguish between two cases: the "small-m" case where m = O(n/ logn) and the "medium-m" case where m = Ω(n/ logn). In the small-m case, we restrict our attention to allocations in which each agent receives either one or no chore. With this restriction, we can create a bipartite graph that indicates whether a chore can be assigned to an agentthat is, a graph with the agents on one side and the chores on the other side, such that there is an edge between an agent and a chore exactly when the chore can be assigned to the agent without violating proportionality-and then find a right-saturated matching in this graph. However, this algorithm is somewhat challenging to analyze, as the edges are dependent and we cannot simply apply results from random graph theory (e.g., [Erd˝os and R´enyi, 1964]).

To mitigate this technical challenge, we modify the algorithm slightly by considering the subgraph of the bipartite graph where each agent is (potentially) connected to only her favorite chore. The advantage here is that, since every vertex on the left has degree at most one, a right-saturated matching exists as long as no vertex on the right is isolated. The latter event is simple and the probability that it occurs can be conveniently bounded.

For the medium-m case, the strategy above does not quite work, as there is a constant probability that some vertex on the right will be isolated. To circumvent this issue, we partition the chores into subsets so that we reduce the problem to the small-m case. We then run the previously described algorithm on each subset and let the final allocation be the union of the allocations output on these subsets.

Finally, we address the non-existence of proportional allocations (Theorem 1.4). Our proof is based on the following observation: if a chore has disutility larger than m/n for an agent i, then it cannot be assigned to i in a proportional allocation. We then show that for any chore, such an event occurs for all agents i with a constant probability-when this happens, no proportional allocation exists.

2 Preliminaries

Let N = {1, . . . , n} be the set of agents and M = {1, . . . ,m} be the set of chores, where n,m ≥ 2. For each (i, j) ∈ N × M, we use di(j) ≥ 0 to denote the disutility (or cost) of chore j for agent i. We assume throughout the paper that the disutilities are additive, that is, di(M ′ ) = ∑j∈M′ di(j) for all M ′ ⊆M.

An allocation A = (A1, . . . ,An) is a partition of M into n disjoint subsets, where the bundle Ai is assigned to agent i. We say that an allocation A is envy-free if for every pair of agents i, i′ , it holds that di(Ai) ≤ di(Ai′). When this condition does not hold for some pair i, i′ (i.e., di(Ai) > di(Ai′ )), we say that i envies i′ (with respect to the allocation A). We say that an allocation A = (A1, . . . ,An) is proportional if di(Ai) ≤ di(M)/n for all i ∈ N.

We assume that each disutility di(j) is drawn independently at random from a distribution D. The support of D lies in [0, 1] and D is non-atomic, i.e., PrX∼D[X = x] = 0 for every x ∈ [0, 1]. For the sake of brevity, we will not repeat these assumptions in our formal statements. Due to non-atomicity, with probability 1, all disutilities are positive (i.e., di(j) > 0 for all i ∈ N and j ∈ M) and distinct (i.e., di(j) ̸= di′(j ′ ) for all i, i′ ∈ N and j, j ′ ∈ M such that (i, j) ̸= (i′ , j ′ )); in particular, each agent has a unique "favorite chore" (i.e., the set argminj∈Mdi(j) has size 1). We will assume that this is the case throughout the paper, and slightly abuse notation by using argminj∈Mdi(j) to denote an item rather than a set. In addition, for most of our results, we assume that D is PDF-bounded. This means that there exist constants α, β > 0 such that fD(x) ∈ [α, β] for all x ∈ [0, 1], where fD denotes the probability distribution function of D. We sometimes write (α, β)-PDF-bounded if we want to specify the constants α, β explicitly. Notice that α ≤ 1 and β ≥ 1 hold for every distribution D; the uniform distribution on [0, 1] has α = β = 1 (and is the only distribution with this property).

We use log to denote the natural logarithm, and say that an event occurs "with high probability" if the probability that it occurs approaches 1 as n → ∞.

2.1 Concentration Inequalities

We now list two concentration inequalities that we will make use of. The first is the well-known Chernoff bound.

Lemma 2.1 (Chernoff bound). Let X1, . . . ,Xk be independent random variables that are bounded in [0, 1], and let X := X1 + · · · +Xk. Then, for any δ ≥ 0,

and

The second inequality is the so-called Efron-Stein inequality (e.g., [Boucheron et al., 2013, Corollary 3.2]). Given a set Z and a real number c ≥ 0, we say that a function F : Z n → R is c-difference bounded if for all i ∈ {1, . . . , n} and z1, . . . , zn, z′i ∈ Z, it holds that

Lemma 2.2 (Efron-Stein inequality). Let c ≥ 0 be a real number, and let Z1, . . . , Zn be independent random variables from sample space Z. If F : Z n → R is a c-difference bounded function, then

2.2 Matchings in RandomGraphs

Next, we state some definitions and results on matchings in random graphs.

Definition 2.3. Let G be a bipartite graph and r be a positive integer. An r-matching of G is a subgraph obtained by removing some edges from G so that every left vertex has degree at most r and every right vertex has degree at most 1. When r = 1, we simply call an r-matching a matching.

An (r-)matching is said to be right-saturated if every right vertex has degree exactly 1. It is said to be perfect if every left vertex has degree exactly r and every right vertex has degree exactly 1.

Recall that an Erd˝os-R´enyi random bipartite graph is a random graph in which each edge between a pair of left and right vertices is included with probability p, independently of other edges. We write G(nL, nR, p) to denote the distribution of such a random graph with nL left vertices and nR right vertices. A classic result, due to Erd˝os and R´enyi themselves, is that a perfect matching in G(n, n, p) exists with high probability as long as p is noticeably above log n/n.

Lemma 2.4 (Erd˝os and R´enyi [1964]). Suppose that G ∼ G(n, n, p) where p = (logn + ω(1))/n. Then, with high probability, G contains a perfect matching.

In this work, we will use the high-probability existence of a right-saturated 2-matching in the setting where the right side has at most twice as many vertices as the left side. The proof of this lemma can be found in the full version of our paper [Manurangsi and Suksompong, 2025].

Lemma 2.5. Suppose that G ∼ G(nL, nR, p) where n/2 ≤ nL ≤ n, nR ≤ n, and p = 2(log n + ω(1))/n. Then, with high probability, G contains a right-saturated 2-matching.

3 Envy-Freeness

In this section, we prove our results on envy-freeness (Theorems 1.1 and 1.2).

3.1 Non-Existence

We start with the non-existence (Theorem 1.2). For each agent i ∈ N, let Zi denote i's favorite chore. For each chore j ∈M, let N fav j denote the set of agents whose favorite chore is j, i.e., N fav j := {i ∈ N | Zi = j}. We say that a chore j is a repeated favorite chore if it is a favorite chore of more than one agent, i.e., |N fav j | > 1. Let T denote the number of repeated favorite chores. The following lemma relates T to whether an envy-free allocation can exist.

Lemma 3.1. If the number of repeated favorite chores is more than 2(m- n), then no envy-free allocation exists.

Proof. Suppose for contradiction that there exists an envyfree allocation with more than 2(m - n) repeated favorite chores. Since every disutility is positive, no agent can receive an empty bundle. If at most 2n-m-1 chores are in a bundle of size one, then the total number of chores is at least

a contradiction. Therefore, at least 2n -m chores must be in a bundle of size one. If no repeated favorite chore is in a bundle of size one, then the total number of chores is more than (2n -m) + 2(m- n) = m, a contradiction. Hence, there is a repeated favorite chore in a bundle of size one. This means that there exists an agent who does not receive this chore but for whom the chore is her favorite chore. This agent will therefore envy the agent who receives this chore, yielding the desired contradiction.

Next, we calculate the expectation of T , the number of repeated favorite chores. The details can be found in the full version of our paper [Manurangsi and Suksompong, 2025].

We are now ready to prove Theorem 1.2.

Proof of Theorem 1.2. Let ˜ ν = m/(n - 1) and

We have

so f is decreasing on (0,∞). Since m/n ≤ ν - ϵ, it holds that ˜ ν ≤ ν -ϵ/2 when n is sufficiently large. By Lemma 3.2, we have

Since f is decreasing on (0,∞) and f(ν) = 0, we deduce that f(ν - ϵ/2) is a positive constant, and E[T ] ≥ 2(m- n).

Observe that T is a function of Z1, . . . ,Zn which is 1bounded (i.e., changing a single Zi changes the value of T by at most one). By Lemma 2.2, we have Var(T) ≤ n/4. Applying Chebyshev's inequality, we get

Finally, by Lemma 3.1, this implies that with high probability, no envy-free allocation exists.

3.2 Existence

We now proceed to the existence (Theorem 1.1). As discussed in Section 1.2, this is based on two theorems depending on whether m is "large" relative to n.

Theorem 3.3. For any PDF-bounded distribution D, there exists a constant c such that, if m ≥ cn logn, then there exists a polynomial-time algorithm that finds an envy-free allocation with high probability.

Theorem 3.4. For any PDF-bounded distribution D, if 2n ≤ m ≤ n8/7 , then there exists a polynomial-time algorithm that finds an envy-free allocation with high probability.

Note that Theorem 1.1 is an immediate consequence of these two theorems.

For Theorem 3.3, we use the "cost-minimizing algorithm", which allocates each chore j to the agent with the smallest disutility for it, that is, the agent argmini∈Ndi(j). Clearly, this algorithm runs in polynomial time. The proof of its correctness is an adaptation of the analogous proof for the welfare-maximizing algorithm in the case of goods [Dickerson et al., 2014]; we defer it to the full version of our paper.

Next, we will establish Theorem 3.4 via a matching-based approach. We start with the case where m is divisible by n. We say that an allocation A = (A1, . . . ,An) is balanced if |A1| = · · · = |An|. When m = rn for some integer r ≥ 2, the algorithm by Manurangsi and Suksompong [2020] finds a balanced allocation that is envy-free for the case of goods. It is not difficult to see that this implies a similar algorithm for chores, as we may simply set the "utility" ui(j) to be 1 - di(j); a balanced allocation is envy-free with respect to these utilities if and only if it is envy-free with respect to the disutilities. Moreover, their algorithm ensures that every agent's total utility for the goods that she receives is at least r (1 - O ( log(rn) n )); in the chore setting, this translates to a total disutility of at most O ( r log(rn) n ). We summarize these properties more formally below.

Theorem 3.5 (Manurangsi and Suksompong [2020]). Suppose that m = rn for some integer r such that 2 ≤ r ≤ en0.1 . For any (α, β)-PDF-bounded distribution D, there exists a polynomial-time algorithm ALGdiv that, with high probability, finds a balanced envy-free allocation A = (A1, . . . , An) such that di(Ai) ≤ cr log(rn) n for all i ∈ N, where c > 0 is a constant depending only on α, β.

We now proceed to the case where m is not divisible by n. Recall that ALGdiv is the algorithm from the divisible case in Theorem 3.5. Our algorithm for the non-divisible case is presented as Algorithm 1, where τ is a parameter that we will choose below. Note that the algorithm runs in polynomial time since ALGdiv runs in polynomial time and a rightsaturated 2-matching can be found by creating two copies of each left vertex and finding a maximum matching.

Algorithm 1 Matching for Envy-Free Allocation

• 1: procedure TWOSTAGEALGORITHMτ(N,M, {di}i∈N)
• 2: r = ⌊m/n⌋
• 3: M 0 ← the first rn chores
• 4: A0 = (A01 , . . . ,A0n ) ←ALGdiv(M 0 )
• 5: M 1 ←M \M 0
• 6: N 1 ← {i ∈ N | di(A0i ) ≤ mini′∈N\{i} di(A0i′) - 2τ }

• 8: if a right-saturated 2-matching exists in the graph G = (N 1 ,M 1 , E) then
• 9: A1 = (A11 , . . . ,A1n ) ← the allocation corresponding to a right-saturated 2-matching
• 10: return A = (A01 ∪ A11 , . . . , A0n ∪ A1n )
• 11: else
• 12: return NULL

Proof of Theorem 3.4. Let D be (α, β)-PDF-bounded, and let r := ⌊m/n⌋ ≤ n1/7 . We use Algorithm 1 with τ = 3 log n βn . For convenience, let ξ := cr log(rn) n , where c is the constant in Theorem 3.5. From that theorem, with high probability, the output (partial) allocation A0 = (A01 , . . . , A0n ) satisfies the following conditions with high probability:

For the remainder of this proof, we will assume that these conditions are satisfied.

We claim that if Algorithm 1 does not return NULL, then the output is envy-free. To see this, fix any distinct i, i′ ∈ N and consider two cases.

• Case I: i /∈ N 1 . In this case, we have

• Case II: i ∈ N 1 . In this case, we have

where the first inequality follows from the definition of E and the fact that |A1i | ≤ 2, and the second inequality from the definition of N 1 .

Thus, it suffices to show that a right-saturated 2-matching exists in G with high probability. To this end, we will prove that

Before we prove (4), let us argue why it gives us the desired result. Notice that for fixed N 1 , the graph G is drawn according to G(|N 1 |, m- rn, p) with p = PrX∼D[X ≤ τ ] ≤ βτ = 3 log n/n, where the inequality follows from the (α, β)-PDFboundedness of D and the last equality from our choice of τ . As a result, if |N 1 | ≥ n/2, Lemma 2.5 implies that a rightsaturated 2-matching exists in G with high probability. From this and (4), letting Q denote the event that G has a rightsaturated 2-matching, we have

as desired.

We are now left to prove (4). First, using Markov's inequality, (3), and the union bound, we have

Next, for any γ > 0 and i ∈ N, let M 0 i,≤γ denote the set {j ∈ M 0 | di(j) ≤ γ}. From (3), for any i′ ∈ N, we have A0i′ ⊆M 0 i′ ,≤ξ . Meanwhile, if di(A0i′) < ξ +2τ, then it holds that A0i′ ⊆ M 0 i,≤ξ+2τ ; together with the previous sentence, this implies that |M 0 i′ ,≤ξ ∩M 0 i,≤ξ+2τ | ≥ r. Hence, for any distinct i, i′ ∈ N, we have

where the last inequality follows from the union bound.

Notice that each chore belongs to M 0 i′ ,≤ξ and M 0 i,≤ξ+2τ independently with probability PrX∼D[X ≤ ξ] ≤ βξ and PrX∼D[X ≤ ξ + 2τ] ≤ β(ξ + 2τ), respectively. Plugging this into the estimate above, we get

where the latter inequality follows from ξ, τ ≤ O ( r log(rn) n ). Plugging this back into (5), we obtain

which is o(1) due to our assumption that r ≤ n1/7 .

4 Proportionality

In this section, we turn our attention to proportionality (Theorems 1.3 and 1.4).

4.1 Non-Existence

We start with our non-existence result, whose simple proof follows precisely the outline in Section 1.2.

Proof of Theorem 1.4. Consider the first chore 1. Notice that if di(1) > m/n for all agents i ∈ N, then no proportional allocation exists, since the agent who is assigned this chore will incur disutility greater than m/n ≥ di(M)/n. Thus,

Pr[No proportional allocation exists]

where the second inequality follows from the (α, β)-PDFboundedness of D, the third inequality from our assumption 2β · mn ≤ 1 and the bound (1 + x)(1 - x/2) ≥ 1 which holds for all x ∈ [0, 1], and the last inequality from the bound 1 + x ≤ ex which holds for all real numbers x.

4.2 Existence

Next, we establish the existence of proportional allocations (Theorem 1.3). As discussed in Section 1.2, we first give an algorithm for the "small-m" case, shown as Algorithm 2.

Theorem4.1. Let D be an (α, β)-PDF-bounded distribution with mean µ, and let m logm ≥ 80 αµ and mlogm ≤ n/40. There exists a polynomial-time algorithm ALGPROP-small that finds a proportional allocation with probability at least 1 - 1/m4 .

Proof. First, note that if Algorithm 2 does not return NULL, then the output allocation must be proportional-this is because either di(Ai) = 0 (agent i does not receive any chore) or di(Ai) ≤ di(M)/n (agent i receives one chore corresponding to an edge in E). Thus, it suffices to show that a right-saturated matching exists in G with probability at least 1 - 1/m4 .

Algorithm 2 Matching for Proportional Allocation

• 1: procedure ALGPROP-small (N,M, {di}i∈N) 2: E = {(i, j) ∈ N ×M | di(j) ≤ di(M)/n and j = argminj ′∈Mdi(j ′ )} 3: if a right-saturated matching exists in the graph G = (N,M,E) then 4: A ← the allocation corresponding to a rightsaturated matching 5: return A 6: else 7: return NULL

Observe that each i ∈ N has degree at most one, since it can be connected to only argminj ′∈Mdi(j ′ ). This means that there exists a right-saturated matching in G if and only if no right vertex is isolated (i.e., has degree zero). Hence, by the union bound, we have

Pr[No right-saturated matching exists in G]

Let FD denote the cumulative distribution function of D, and let τ be such that FD(τ) = 20 logm n . Note that the (α, β)- PDF-boundedness of D implies that τ ≤ 1α · 20 logm n .

Fix i ∈ N and j ∈ M. We can bound Pr[(i, j) ∈ E] as follows:

where the second equality follows from the independence across different items, the last equality from our choice of τ, and the last inequality from Bernoulli's inequality along with our assumption that n/40 ≥ m log m.

Now, observe that di(M \ {j}) ≥ n · τ and di(j ′ ) ≥ τ for j ′ ∈ M \ {j} are positively correlated events. Applying this to the bound above, we get

Note that di(M \{j}) = ∑j ′∈M\{j} di(j ′ ) is a sum of m-1 independent random variables; its expectation is (m-1)µ ≥ mµ/2. From our condition on m, we have mµ/2 ≥ 40 log m· 1/α ≥ 2nτ , so (m - 1)µ/2 ≥ nτ . Hence,

where the second inequality follows from Lemma 2.1 and the fourth inequality from our assumption that m logm ≥ 80 αµ .

Finally, combining (6), (7), and (8), we get

Pr[No right-saturated matching exists in G]

where the second inequality follows from the inequality 1 + x ≤ ex , which holds for all real numbers x.

We are now ready to prove Theorem 1.3 by considering whether the value of m is "small", "large", or "medium".

Proof of Theorem 1.3. Suppose that the distribution D is (α, β)-PDF-bounded with mean µ. Note that the (α, β)-PDFboundedness of D implies that

We will assume throughout that m is sufficiently large-more specifically, that m logm ≥ 80 αµ . Consider the following cases.

• Case I: mlogm ≤ n/40. In this case of "small" m, we may directly apply Theorem 4.1.
• Case II: m ≥ 2n. In this case of "large" m, we may apply Theorem 1.1, which allows us to find an envyfree allocation with high probability. Since an envy-free allocation is also proportional, we get the desired result.
• Case III: mlogm > n/40 and m < 2n. In this case of "medium" m, let m0 be the largest integer such that m0 logm0 ≤ n/40. Note that m0 = Θ(n/ log n). Our algorithm works as follows.
• Let r = ⌈n/m0⌉.
• Partition M into M 1 , . . . ,M r , each of size either ⌈n/r⌉ or ⌊n/r⌋.
• Apply ALGPROP-small (Algorithm 2) to each M i to obtain an allocation Ai = (Ai1 , . . . , Ain ).
• Output A = (A11 ∪ · · · ∪ Ar1 , . . . , A1n ∪ · · · ∪ Arn ).

Observe that if each allocation Ai for i ∈ {1, . . . , r} is proportional with respect to the set of chores M i , then the final allocation A is also proportional with respect to the set of all chores M. Now, by our choice of r, we have n/r ≤ m0; since m0 is an integer, this means that ⌈n/r⌉ ≤ m0. It follows that |M i | log |M i | ≤ n/40. Furthermore, |Mi | log |Mi | = Θ ( n log2 n ), which is at least 80 αµ for any sufficiently large n. Thus, we may apply Theorem 4.1 to each invocation of ALGPROP-small , which implies that the probability that Ai is proportional with respect to M i is at least 1 - 1/|M i |4 ≥ 1 -O(1/m40 ). Thus, the probability that the above algorithm fails to find a proportional allocation is at most

5 Discussion

In this work, we have derived asymptotically tight bounds on the existence of envy-free and proportional chore allocations when the disutilities are sampled from a probability distribution. Interestingly, these bounds reveal that far fewer items are required to achieve fairness when dealing with chores in comparison to goods. We remark that our results also have implications on two other important fairness notions: maximin share (MMS) fairness [Budish, 2011; Aziz et al., 2017] and envy-freeness up to any chore (EFX) [Aziz et al., 2022; Kobayashi et al., 2025]. Specifically, for each of these notions, an allocation satisfying it exists with high probability for any relation between m and n. In more detail, for MMS fairness, if m ≤ n then every allocation that gives at most one chore to each agent is MMS-fair, while if m > n, since proportionality is stronger than MMS fairness, Theorem 1.3 implies that an MMS-fair allocation is again likely to exist. Similarly, for EFX, if m ≤ 2n, it is known that an EFX allocation always exists [Kobayashi et al., 2025]; if m > 2n, since envy-freeness is stronger than EFX, Theorem 1.1 implies that an EFX allocation exists with high probability.

A technical question left by our work is to tighten the gap in the constant factor between Theorems 1.1 and 1.2, in particular, to determine whether the factor of 2 in Theorem 1.1 can be improved. One could also consider allocating a combination of goods and chores [Aziz et al., 2022]-Benad`e et al. [2024] presented results on this model but only for two agents. Finally, it would be interesting to examine whether similar results continue to hold if we relax certain assumptions on the model, as has been done for goods [Bai et al., 2022; Bai and G¨olz, 2022; Benad`e et al., 2024].

Acknowledgments

This work was partially supported by the Singapore Ministry of Education under grant number MOE-T2EP202210001 and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.