Asymptotic Analysis of Weighted Fair Division

1 Introduction

The fair allocation of scarce resources is a fundamental problem in economics and has received substantial attention recently in computer science [Brams and Taylor, 1996; Robertson and Webb, 1998; Moulin, 2019]. Research in fair division has sought to quantify fairness via precise mathematical definitions, among which two of the most important are envy-freeness and proportionality. An allocation is said to be envy-free if each agent values her own bundle at least as much as any other agent's bundle [Foley, 1967; Varian, 1974]. It is called proportional if every agent values her bundle at least 1/n of her value for the entire set of resources, where n is the number of agents [Steinhaus, 1948].

When allocating indivisible items, like houses, cars, or musical instruments, an envy-free or proportional allocation may not exist-this is the case, for example, when all items are valuable and the number of items m is smaller than n. In light of this, a line of work has focused on the question of when a fair allocation is likely to exist if the agents' utilities for the items are drawn independently from a probability distribution. 1 For instance, Manurangsi and Suksompong

1 We survey this and another related line of work in Section 1.2.

[2020, 2021] showed that an envy-free allocation exists with high probability 2 provided that m = Ω(n log n/ log log n). Not only is this bound tight, but it can also be achieved by a simple round-robin algorithm which lets the agents take turns picking their favorite item from the remaining items until the items run out. The same authors also proved that a proportional allocation is likely to exist as long as m ≥ n.

The aforementioned results, like most of the work in fair division, assume that all agents have the same entitlement to the resource. In recent years, a number of researchers have explored a more general framework where agents may have varying entitlements represented by weights [Farhadi et al., 2019; Aziz et al., 2023; Chakraborty et al., 2024; Hoefer et al., 2024; Springer et al., 2024]. This broader framework allows us to model scenarios such as distributing resources among communities, where larger communities naturally deserve a larger portion of the resource, as well as dividing inheritance, where closer relatives typically receive a greater share of the bequest. Fortunately, both proportionality and envy-freeness can be extended to the weighted setting in an intuitive manner. As an example, if there are three agents with weights 1, 3, and 6, then weighted proportionality requires the first agent to receive at least 1/10 of her value for the entire set of items, while weighted envy-freeness stipulates that the second agent should not value the third agent's bundle more than twice the value of her own bundle.

In addition to its inherent motivation, interest in weighted fair division stems from the fact that it exhibits several differences and brings a range of new challenges compared to its unweighted counterpart. For instance, in the absence of weights, it is trivial to show that the round-robin algorithm guarantees envy-freeness up to one item (EF1), meaning that if an agent envies another agent, then the envy disappears upon removing some item in the latter agent's bundle. By contrast, while it is possible to extend the roundrobin algorithm to incorporate weights and prove that the resulting algorithm ensures weighted EF1 (WEF1), doing so is far less straightforward [Chakraborty et al., 2021a; Wu et al., 2023]. In this paper, we shall analyze weighted fair division from an asymptotic perspective. Do the same relations between m and n continue to guarantee the existence of fair allocations when agents may have different weights?

2 That is, the probability that it exists converges to 1 as n→∞.

1.1 Our Results

We assume that each agent's utility for each item is drawn independently from a non-atomic distribution D over [0, 1]. For most results, we also assume that D is PDF-bounded, that is, its probability distribution function is bounded between α and β throughout [0, 1] for some constants α, β > 0. All of our existence results come with polynomial-time algorithms.

In Sections 3 and 4, we consider the setting where the ratio between the weights is bounded. In Section 3, we show that if m = Ω(n logn/ log logn), then the weighted picking sequence algorithm of Chakraborty et al. [2021a] produces a weighted envy-free allocation with high probability; this generalizes the corresponding unweighted result by Manurangsi and Suksompong [2021]. Along the way, we provide an alternative proof that the allocation returned by this algorithm always satisfies WEF1; this proof is arguably simpler than existing proofs [Chakraborty et al., 2021a; Wu et al., 2023]. In Section 4, we turn our attention to weighted proportionality and prove that, interestingly, the transition from non-existence to existence depends on the mean of the distribution D: it occurs at m = n/(1 - µ), where µ ∈ (0, 1) denotes the mean of D. This implies that achieving (weighted) proportionality is more difficult than in the unweighted setting, for which the threshold is m = n [Manurangsi and Suksompong, 2021].

In Section 5, we focus on the case of two agents but allow the ratio r ≥ 1 between the agents' weights to grow; in this case, weighted envy-freeness and weighted proportionality are equivalent. We show that if m = ω(√r), then the probability that a weighted envy-free (and therefore weighted proportional) allocation exists approaches 1 as r → ∞. We also establish the tightness of this bound.

1.2 Further RelatedWork

The asymptotic analysis of fair division was initiated by Dickerson et al. [2014], who showed that an envy-free allocation is likely to exist if m = Ω(n logn), but unlikely to exist when m = n + o(n). Manurangsi and Suksompong [2020] strengthened these results by exhibiting that existence is likely as long as m ≥ 2n if m is divisible by n, but unlikely even when m = Θ(n log n/ log log n) if m is not "almost divisible" by n. The gap in the non-divisible case was closed by Manurangsi and Suksompong [2021], who demonstrated the existence with high probability when m = Ω(n logn/ log logn) via the round-robin algorithm. The same authors also proved that a proportional allocation is likely to exist when m ≥ n, generalizing earlier results by Suksompong [2016] and Amanatidis et al. [2017]. Manurangsi and Suksompong [2017] studied envy-freeness when the agents are partitioned into groups, while Yokoyama and Igarashi [2025] performed an asymptotic analysis of "class envy-free" matchings. Beyond envy-freeness and proportionality, Kurokawa et al. [2016] and Farhadi et al. [2019] considered maximin share fairness-a weaker notion than proportionality-the latter authors also allowing unequal entitlements. Bai and G¨olz [2022] considered an extension where different agents may have different distributions, whereas Bai et al. [2022] investigated a "smoothed utility model" in which each agent has a base utility for each item and this utility is "boosted" with some probability. Benad`e et al. [2024] examined a stochastic model where the agents' utility functions can be non-additive. Manurangsi and Suksompong [2025] conducted an asymptotic analysis of fair division for chores (i.e., items that yield negative utilities).

While weighted fair allocation has previously been studied for divisible items [Segal-Halevi, 2019; Crew et al., 2020; Cseh and Fleiner, 2020], it has been intensively examined in the context of indivisible items over the last few years. Several authors have proposed and studied variants of envyfreeness, proportionality, and maximin share in the setting with entitlements [Farhadi et al., 2019; Aziz et al., 2020; Babaioff et al., 2021; Chakraborty et al., 2021b; Wu et al., 2023; Springer et al., 2024; Montanari et al., 2025]. For an extensive overview of weighted fair division, we refer to the survey by Suksompong [2025].

2 Preliminaries

Let [k] := {1, 2, . . . , k} for any positive integer k. We want to allocate a set M = [m] of indivisible items among a set N = [n] of agents. Each agent i ∈ N has a utility ui(g) ≥ 0 for each item g ∈ M, and a positive weight wi ∈ R>0. Let wmax, wmin, and W denote the maximum, minimum, and sum of the agents' weights, respectively. We assume that utilities are additive, i.e., ui(S) = ∑g∈S ui(g) for any subset S ⊆ M. We refer to any subset of items as a bundle. An allocation A = (A1,A2, . . . ,An) is a partition of M into n bundles, where Ai represents the bundle allocated to agent i ∈ N.

We consider a number of fairness notions. An allocation A is said to be weighted envy-free (WEF) if for every pair of agents i, j ∈ N, it holds that ui(Ai) wi ≥ ui(Aj) wj . As a relaxation of WEF, an allocation A is weighted envy-free up to one item (WEF1) if for all i, j ∈ N with Aj ̸= ∅, there exists an item g ∈ Aj such that ui(Ai) wi ≥ ui(Aj\{g}) wj . An allocation A is said to be weighted proportional (WPROP) if ui(Ai) ≥ wi W ·ui(M) for all i ∈ N. Note that every allocation that satisfies WEF also satisfies WPROP.

For each agent i ∈ N and each item g ∈ M, we assume that the utility ui(g) is drawn independently from a probability distribution D over [0, 1]. A distribution is non-atomic if it assigns zero probability to any single point. Let fD denote the probability density function (PDF) of D. For α, β > 0, we say that a distribution D is (α, β)-PDF-bounded if it is nonatomic and α ≤ fD(x) ≤ β for all x ∈ [0, 1] [Manurangsi and Suksompong, 2021]. A distribution D is PDF-bounded if it is (α, β)-PDF-bounded for some constants α, β > 0. A random event is said to occur with high probability if its probability approaches 1 as n → ∞. We use log to denote the natural logarithm (with base e).

We now state two lemmas that will be useful for our purposes. In our analysis of the weighted picking sequence algorithm, we will apply Abel's summation formula.

Lemma 1 (Abel's summation formula). For any sequences of real numbers (a1, a2, . . . , an) and (b1, b2, . . . , bn), we have

The following Chernoff bound is a standard concentration bound which will be used when we analyze the asymptotic existence of WPROP allocations and the case of two agents.

Lemma 2 (Chernoff bound). Let X1,X2, . . . ,Xd be independent random variables such that Xi ∈ [0, 1] for all i ∈ [d], and let X = ∑di=1 Xi. Then, for any δ > 0, we have

3 Weighted Envy-Freeness

In this section, we consider weighted envy-freeness. We provide an alternative proof that the weighted picking sequence algorithm of Chakraborty et al. [2021a] always outputs a WEF1 allocation. Our proof also lends itself to the asymptotic analysis of WEF, which we present as Theorem 1.

3.1 Alternative Proof of WEF1

We first describe the weighted picking sequence algorithm (Algorithm 1). Define a step as an iteration of the while-loop (lines 3-8). Here, ti represents the number of items that agent i has picked so far, and in each step, an agent i who minimizes ti/wi picks her favorite item from the remaining items.

Algorithm 1 Weighted Picking Sequence Algorithm

Require: N,M, (ui(g))i∈N,g∈M, (wi)i∈N

• 1: Ai ← ∅ and ti ← 0 for all i ∈ N
• 2: M0 ←M
• 3: while M0 ̸= ∅ do
• 4: i∗ ← argmini∈N ti wi
• 5: g∗ ← argmaxg∈M0 ui∗(g)
• 6: Ai∗ ←Ai∗ ∪ {g∗ }
• 7: M0 ←M0 \ {g∗ }
• 8: ti∗ ← ti∗ + 1
• 9: return (A1,A2, . . . ,An)

Denote by ti(s) the number of times agent i has picked an item up to (and including) step s. For each i ∈ N and each k ∈ [ti(m)], let si (k) be the step where agent i picks her k-th item, and denote this item by gik ; for convenience, let si (0) = 0. Finally, let A = (A1,A2, . . . ,An) be the allocation returned by Algorithm 1.

Chakraborty et al. [2021a] gave a rather long algebraic proof that Algorithm 1 always returns a WEF1 allocation. Wu et al. [2023] provided an alternative proof involving integrals. We present a relatively succinct algebraic proof of this statement via Abel's summation formula.

Proposition 1 ([Chakraborty et al., 2021a]). The allocation returned by Algorithm 1 is WEF1.

Proof. Consider any two distinct agents i, j ∈ M; it suffices to show that i is WEF1 towards j. Observe that each of i and j picks her first item before the other agent picks her second item. Let τ1 + 1 be the number of items that j picks before step si (2), and denote these items by gj1 , gj1,1 , gj1,2 , . . . , gj1,τ1 . Note that gj1 may be picked either before or after gi1 .

For each k ∈ [ti(m)-1]\{1}, let τk be the number of items that agent j picks between steps si (k) and si (k + 1), and for ℓ ∈ [τk], let gjk,ℓ be the ℓ-th item picked by agent j within this interval. Let τti(m) denote the number of items that j picks after step si (ti(m)), and for ℓ ∈ [τti(m)], let gj ti(m),ℓ be the ℓ-th item picked by j within this interval. Note that τk may be zero for some k. See Figure 1 for an illustration.

We claim that for every k ∈ [ti(m)],

Indeed, if τk ≥ 1, then (1) holds since agent j is allowed to pick item gjk,τk . If τk = 0, for k = 1 we have ∑1k′=1 τk′ wj = 0 ≤ 1 wi , while for k ≥ 2 we have ∑k-1 k′=1 τk′ wj ≤ k-1 wi from the property for k - 1, which implies that ∑kk′=1 τk′ wj = ∑k-1 k′=1 τk′

where the last equality follows from Lemma 1 and the inequality from the fact that ui(gik ) ≥ ui(gik+1 ) for every k. Hence, agent i is WEF1 towards agent j, as desired.

3.2 Asymptotic Result

We now present the main result of this section.

Theorem 1. Suppose that D is PDF-bounded, and let C ≥ 1 be an arbitrary constant. For any weight vector (w1,w2, . . . ,wn) such that wmax/wmin ≤ C, if m = Ω (n log n/ log log n), then Algorithm 1 produces a WEF allocation with high probability.

Before we prove Theorem 1, we introduce some notation. For any c ∈ (0, 1], denote by D≤c the conditional distribution of D on [0, c]. For any positive integer k, denote by Dmax(k) the distribution of the maximum of k independent random variables generated by D.

Fix any two distinct agents i, j ∈ N. We will use the same notation as in Section 3.1. Let Xj 1 = ui(gj1 ). For each k ∈ [ti(m)] and ℓ ∈ [τk], let Xk = ui(gik ) and Xjk,ℓ = ui(gjk,ℓ ). Lemma A.1 of Manurangsi and Suksompong [2021] yields the following lemma, which gives a convenient description of the distributions of Xk and Xjk,ℓ .

Lemma 3 ([Manurangsi and Suksompong, 2021]). Let X0 = 1. Then, (Xk)k∈[ti(m)] and (Xjk,ℓ )k∈[ti(m)], ℓ∈[τk] can be generated according to the following process:

Intuitively, before agent i picks the item gik corresponding to Xk, there are m- si (k) + 1 items remaining, and i's utility for each of them cannot exceed her utility for the item gik-1 corresponding to Xk-1. Moreover, i's utility for each item gjk,ℓ corresponding to Xjk,ℓ picked by j cannot exceed her utility for gik , but otherwise j's picks are independent of i's valuations.

We now proceed to the proof of Theorem 1.

Proof of Theorem 1. Suppose that D is (α, β)-PDF-bounded and m ≥ 106 ˜ β · C · n log n/ log log n, where ˜ β := β/α ≥ 1. Recall that for any k ∈ [ti(m)], we defined

For each k, let θk = 1 - wi wj · τk. By description of the algorithm, Xk ≥ Xjk,ℓ holds for all k ∈ [ti(m)] and ℓ ∈ [τk], so ηk ≥ θk for all k. From (1), we obtain that for any k,

By Lemma 1 combined with (2) and the fact that Xk ≥ Xk+1 for every k, we have

From this, we get

Our goal is to demonstrate that, with high probability, ∑ti(m) k=1 Xk (ηk - θk) - wi wj ≥ 0 holds. To this end, we show that with high probability, there exists a point in the picking sequence where agent i receives an item of sufficiently high value and has accumulated enough advantage over agent j. This is formalized in the following lemma.

Lemma 4. Suppose that D is (α, β)-PDF-bounded, and m ≥ 106 ˜ β · C · n log n/ log log n. For any distinct agents i, j ∈ N, there exists a positive integer T such that

We defer the proof of Lemma 4 to the full version of our paper [Manurangsi et al., 2025]. Using this lemma, we will show that with probability at least 1-O (1/m3 ), agent i does not envy agent j. We have

(by Xk ≥ 0 and ηk ≥ θk for any k, and (a) in Lemma 4)

(with probability at least 1 -O (1/m3 ), by (b) in Lemma 4)

(with probability at least 1 -O (1/m3 ), by (c) in Lemma 4)

= 0.

Finally, by the union bound over all pairs of agents i, j and the fact that m ≥ n, we have that the probability that the allocation A is not WEF is at most n2 · O(1/m3 ) = O(1/n). This completes the proof of the theorem.

4 Weighted Proportionality

In this section, we turn our attention to weighted proportionality, and establish a sharp threshold for the transition from non-existence to existence with respect to this notion.

We start with the non-existence.

Theorem2. Suppose that D is a non-atomic distributionwith mean µ ∈ (0, 1), and let ε ∈ (0, 1/2) be a constant. For any n, there exists a weight vector (w1, w2, . . . , wn) with wmax wmin ≤ 2 (1-µ)2 ε2 such that for any m ≤ (1 - ε) · n 1-µ , with high probability, no WPROP allocation exists.

Proof. When n > m, at least one agent receives no item. Since D is non-atomic, with probability 1, all agents have positive utilities for all items, in which case no WPROP allocation exists. We thus assume that n ≤m≤ (1- ε) · n 1-µ .

Let δ = (1 - µ)ε < 1/2. For sufficiently large n, we have ⌊δn⌋ ≥ 2. Assume that there are ⌈(1 - δ)n⌉ agents with weight δ/⌈(1 - δ)n⌉ each (called agents of the "first type"), and the remaining ⌊δn⌋ agents have weight (1-δ)/⌊δn⌋ each (called agents of the "second type"). Note that the sum of all weights is δ+(1-δ) = 1, and the ratio between the maximum and minimum weights is

Our choice of δ implies that (1 - δ)(1 - µε) > 1 - δ - µε = 1 - ε. Rearranging this yields 1-µε 1-ε - 1 1-δ > 0. Let γ = 12 ( 1-µε 1-ε - 1 1-δ ); by the previous sentence, γ > 0.

Note that E [ui(M)] = mµ for each i ∈ N. Applying Lemma 2, we get

By the union bound, the probability that there exists i ∈ N with ui(M) ≤ (1 - γ)mµ is at most n · exp (-γ 2mµ/2). Since m ≥ n, we have n · exp (-γ 2mµ/2) ≤ n · exp (-γ 2nµ/2), which approaches 0 as n → ∞. Thus, with high probability, ui(M) ≥ (1-γ)mµ holds for all i ∈ N. We assume for the remainder of the proof that this event holds.

For an allocation to satisfy WPROP, each agent of the first type must receive at least one item. Each agent of the second type, given her weight of 1-δ ⌊δn⌋ , must receive a bundle that she values at least 1-δ ⌊δn⌋ ·(1-γ)mµ. Since ui(g) ≤ 1 for all i ∈ N and g ∈ M, for each agent i of the second type, her bundle Ai must contain at least 1-δ ⌊δn⌋ · (1 - γ)mµ items. Therefore, for a WPROP allocation to exist, the total number of items must be at least ⌈(1 - δ)n⌉ + ⌊δn⌋ · 1-δ ⌊δn⌋ · (1 - γ)mµ ≥ (1-δ) (n+ (1 -γ)mµ). Since m≤ 1-ε 1-µ · n, this is at least

a contradiction. We therefore conclude that, with high probability, no WPROP allocation exists.

Next, we exhibit the asymptotic existence of weighted proportional allocations.

Theorem 3. Suppose that D is a PDF-bounded distribution with mean µ ∈ (0, 1), and let C ≥ 1 and ε ∈ (0, 1) be arbitrary constants. For any weight vector (w1, w2, . . . , wn) with wmax wmin ≤ C and any m ≥ (1 + ε) · n 1-µ , a WPROP allocation exists with high probability. Moreover, such an allocation can be found in polynomial time.

As WEF is stronger than WPROP, Theorem 1 already implies that a WPROP allocation exists with high probability when m = Ω(n logn/ log logn). Hence, to prove Theorem 3, we may restrict our attention to the case m = O(n logn). Let D be (α, β)-PDF-bounded, and let τ =

Since E [ui(M)] = mµ for all i ∈ N, we can apply Lemma 2 to get that Pr [ui(M) ≥ (1+ δ)mµ] ≤ exp (- δ2mµ 2+δ ) . By the union bound and the assumption that m ≥ (1 + ε) · n 1-µ ≥ n, with high probability, we have ui(M) ≤ (1+δ)mµ for all agents i ∈ N. We assume for the remainder of this discussion that this event holds.

Recall that W = ∑i∈N wi. For each i ∈ N, define si = ⌈(1 + δ) wi W · µm τ ⌉. If we can construct an allocation A where every agent i receives at least si items that she values at least τ each, then with high probability, ui(Ai) ≥ si · τ ≥ wi W · (1 + δ)mµ ≥ wi W · ui(M) for all i ∈ N, implying that the allocation A satisfies WPROP.

Let s = (s1, s2, . . . , sn). As m≥ (1+ ε) · n 1-µ , we have

This calculation shows that the total number of required items does not exceed the number of available items.

To find a desired allocation, we use a matching-based approach, which extends an algorithm of Manurangsi and Suksompong [2020] to the weighted setting. Before describing the algorithm, we define a generalized notion of a matching that allows vertices on one side to be matched multiple times.

Definition 1. Let G = (L∪R,E) be a bipartite graph with |L| = n and |R| = m. For a vector of positive integers s = (s1, s2, . . . , sn) with ∑ni=1 si ≤ m, an s-matching in G is a set of edges F ⊆ E such that each vertex i ∈ L is incident to at most si edges in F and each vertex in R is incident to at most one edge in F. An s-matching is called left-saturating if every vertex i ∈ L is incident to exactly si edges in the matching.

Algorithm 2 Matching-Based Algorithm for WPROP

Require: N,M, (ui(g))i∈N,g∈M, s = (si)i∈N, threshold τ

• 1: for i ∈ N do
• 2: M≥τ(i) ← {j ∈M | ui(j) ≥ τ}
• 3: Let G≥τ = (N,M,E≥τ) be the bipartite graph where (i, j) ∈ E≥τ if and only if j ∈ M≥τ (i).
• 4: if G≥τ contains a left-saturating s-matching then
• 5: return any left-saturating s-matching in G≥τ (with the unmatched items allocated arbitrarily)
• 6: else
• 7: return NULL

Our algorithm, described as Algorithm 2, first constructs a bipartite graph G≥τ where an edge exists between an agent and an item if and only if the agent values the item at least the threshold τ. The algorithm then determines whether a left-saturating s-matching exists in this graph. If so, it simply assigns each matched item to the agent matched with it, and any unmatched item can be assigned arbitrarily. Note that determining whether a left-saturating s-matching exists, and finding one in case it does, can be done in polynomial time by creating si copies of each agent i and computing a maximum matching in the resulting graph.

We now state a lemma that establishes the existence of a left-saturating s-matching.

Lemma 5. Suppose that D is (α, β)-PDF-bounded, there exists a constant C ≥ 1 such that wmax wmin ≤ C, and m = O(n logn). Set τ = 1 - 8(C+1) logm αn in Algorithm 2. Then, with high probability, Algorithm 2 outputs a left-saturating s-matching.

From our earlier discussion, Lemma 5 implies that a WPROP allocation exists (and can be found in polynomial time) with high probability, thereby yielding Theorem 3.

To prove Lemma 5, we first recall basic results from matching theory. For a bipartite graph G = (L∪R, E) and a subset Y ⊆ L, denote by NG(Y ) the set of vertices in R that are adjacent to at least one vertex in Y . A matching in a graph is a set of edges no two of which share a vertex. A matching is called left-saturating if every vertex in L is incident to exactly one edge in the matching. We now state Hall's marriage theorem, a classical result in matching theory.

Lemma 6 (Hall's marriage theorem). Let G = (L ∪ R,E) be a bipartite graph with |L| ≤ |R|. If |NG(Y )| ≥ |Y | for all subsets Y ⊆ L, there exists a left-saturating matching in G.

To extend this result to our setting with s-matchings, we construct a new bipartite graph G′ from G = (L ∪ R, E) by replacing each vertex i ∈ L with si copies, where each copy is connected to all neighbors of i in G. This immediately leads to the following proposition.

Proposition 2. Let G = (L ∪ R,E) be a bipartite graph with n = |L| ≤ |R| = m. For any vector of positive integers s = (s1, s2, . . . , sn) such that ∑ni=1 si ≤ m, if

|NG(Y )| ≥ ∑i∈Y si for all subsets Y ⊆ L, then there exists a left-saturating s-matching in G.

Next, we recall the Erd˝os-R´enyi random bipartite graph model [Erd˝os and R´enyi, 1964]. For any p ∈ [0, 1], let G(|L|, |R|, p) denote the probability distribution over bipartite graphs with vertex sets L and R such that for each pair of vertices i ∈ L and j ∈ R, the edge (i, j) exists independently with probability p. Let smax = maxi∈N si and smin = mini∈N si. The probability that no left-saturating s-matching exists can be upper-bounded by the probability that there exists a subset violating the condition in Proposition 2. Based on this insight, we establish the following lemma, whose proof is deferred to the full version of our paper [Manurangsi et al., 2025].

Lemma 7. Let B ≥ 1 be a constant, and let G be a bipartite graph sampled from G(n,m, p) with n ≤ m and 8B log m n ≤ p ≤ 1. For any vector of positive integers s = (s1, s2, . . . , sn) such that ∑ni=1 si ≤ m and smax smin ≤ B, with high probability, G contains a left-saturating s-matching.

We can now complete the proof of Lemma 5.

Proof of Lemma 5. To apply Lemma 7, we verify two conditions: firstly, that smax smin ≤ C + 1, and secondly, that the graph G≥τ follows the Erd˝os-R´enyi random bipartite graph model. Recall that si = ⌈(1+ δ) wi W · µm τ ⌉. Since smin ≥ 1 and wmax wmin ≤ C, we have

Moreover, since D is (α, β)-PDF-bounded, the events {ui(j) ≥ τ} occur independently for all pairs (i, j) ∈ N ×M, each with probability

Therefore, by setting B = C + 1 in Lemma 7, we conclude that the graph G≥τ contains a left-saturating s-matching with high probability, as desired.

5 Two Agents

In this section, we focus on the case of n = 2 agents-note that WEF and WPROP are equivalent in this case. We let r = w2/w1 ≥ 1 and consider the asymptotics as r → ∞. Our main result is that if the number of items grows asymptotically faster than √r, a WEF allocation is likely to exist.

Theorem 4. Suppose that there are two agents with weights (w1,w2) where r := w2/w1 ≥ 1, and that D is PDFbounded. If m = ω(√r), then a WEF allocation exists with probability approaching 1 as r → ∞, and such an allocation can be found in polynomial time. The same holds for WPROP.

Proof. Since WEF and WPROP are equivalent for n = 2, it suffices to focus on WPROP. Suppose that D is (α, β)-PDFbounded with mean µ ∈ (0, 1).

We present an allocation algorithm. Set p = αµ 2√r+1 ∈ (0, 1), and define τ as the threshold such that Pr[X ≤ τ ] = p for X ∼ D. The algorithm allocates each item whose value to agent 2 is less than τ to agent 1, and the remaining items to agent 2. Clearly, this algorithm runs in polynomial time. Let A = (A1,A2) denote the resulting allocation. To show that A is WPROP with probability 1 - o(1), it suffices to prove that each of the two inequalities (r+1)u1(A1) < u1(M) and (r + 1)u2(A1) > u2(M) holds with probability o(1).

First, consider agent 1. For any sufficiently large r, we have p(r + 1) ≥ 3. When this holds, the union bound yields

We may bound each term above via Lemma 2. In particular, u1(M) is a sum of m independent random variables drawn from D, so E[u1(M)] = mµ; Lemma 2 then implies that Pr[u1(M) > 32 mµ] ≤ exp (- 1 10 mµ) = o(1). Meanwhile, since each item is independently allocated to agent 1 with probability p, u1(A1) is a sum of independent random variables with E[u1(A1)] = mpµ, so Lemma 2 implies that Pr [u1(A1) < 1 2 mpµ] ≤ exp (- 18 mpµ), which is o(1) since m = ω(√r). Combining these, we get Pr[(r + 1)u1(A1) < u1(M)] = o(1), as desired.

Next, consider agent 2. By the union bound, we have

For the first term, we can again use Lemma 2 in a similar way as above to conclude that Pr [u2(M) < 12 mµ] ≤ exp (- 18 mµ) = o(1).

We now focus on the second term Pr [u2(A1) > mµ 2(r+1) ]. For every item g ∈ M, define Xg to be a random variable such that Xg = 1 if g ∈ A1, and Xg = 0 otherwise. Note that each Xg is an independent random variable with E[Xg] = p. Since D is (α, β)-PDF-bounded, we have ατ ≤ Pr[X ≤ τ] = p, and so τ ≤ µ 2√r+1 . By definition of the allocation, every item g ∈ A1 satisfies u2(g) ≤ τ . Therefore, we have u2(A1) = ∑g∈A1 u2(g) ≤ τ · ∑g∈M Xg ≤ µ 2√r+1 ∑g∈M Xg. Observe that 32 E [∑g∈M Xg ] = 32 mp = 3mαµ 4√r+1 ≤ m √r+1 since α ≤ 1 and µ < 1. Using this inequality and the bound on u2(A1), we obtain

where we use Lemma 2 for the last inequality. This probability is o(1) since m = ω(√r).

Hence, combining our bounds for both agents, we conclude that A is WPROP with probability 1 - o(1).

Next, we establish the tightness of the bound in Theorem 4. In particular, the following theorem implies that the probability that no WEF allocation exists is at least constant if m = O(√r), and approaches 1 if m = o(√r).

Theorem 5. Suppose that there are two agents with weights (w1,w2) where r := w2/w1 ≥ 1, and that D is PDFbounded. With probability at least 1 - O(m2 /r), no WEF allocation exists. The same holds for WPROP.

Proof. SinceWEF andWPROP are equivalent for the case of n = 2, it suffices to focus on WEF. Suppose that D is (α, β)- PDF-bounded, and let Y = ming∈M u2(g). If 1-βm/r ≤ 0, then 1 - βm2 /r ≤ 0 ≤ Pr[Y > m/r]. Else, we have

where we use the (α, β)-PDF-boundedness of D for the first inequality and Bernoulli's inequality for the second.

When Y > m/r, since any WEF allocation (A1, A2) must give at least one item to agent 1, we have r ·u2(A1) ≥ r ·Y > m > u2(A2). This means that no WEF allocation exists.

6 Conclusion and FutureWork

In conclusion, our work analyzes weighted fair division from an asymptotic perspective and establishes tight or asymptotically tight bounds on the existence of weighted envy-free and weighted proportional allocations. Notably, a larger number of items is required for weighted proportionality than in the unweighted setting, and this number depends on the mean of the distribution from which the utilities are drawn. We also investigated the relationship between the number of items and the weight ratio in the case of two agents.

Since we have considered settings where the weight ratio is bounded and where the number of agents is bounded separately, a natural next step is to obtain a more complete understanding when both parameters are allowed to grow. For example, if all but one agents have the same (fixed) weight while the last agent's weight grows, what is the required number of items in terms of the number of agents and the last agent's weight? Another interesting direction is to extend our results to a more general model where the items are allocated among groups of agents rather than individual agents. While asymptotic fair division for groups was previously explored [Manurangsi and Suksompong, 2017], the study thus far has focused on groups with equal entitlements. Permitting different entitlements can help us model applications where the groups have varying importance, e.g., depending on their sizes.

Acknowledgments

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