Closing Gaps in Asymptotic Fair Division

Introduction

One of the most frequently occurring tasks in our society is that of allocating scarce resources among interested agents or entities. Indeed, whether it be apportioning government funds among public organizations, allotting office space to research groups in a university, or assigning houses to residents of a city, one is faced with the decision of how to best allocate the limited resource. A central concern when making such decisions is fairness: it is desirable that all agents view the share they receive as fair.

Among the plethora of fairness notions that have been proposed in the literature, perhaps the two best-known ones are envy-freeness and proportionality. An allocation is said to be envy-free if it does not induce envy between any pair of agents, and proportional if it gives every agent at least $1/n$ of their value for the entire resource, where $n$ denotes the number of agents among whom the resource is divided. When the resource to be allocated is divisible, such as advertisement space or broadcast time, it is known that envy-free and proportional allocations are guaranteed to exist (Dubins and Spanier 1961; Stromquist 1980). However, in many situations we need to allocate indivisible resources like houses, cars, electronics, and musical instruments. For such discrete items, neither envy-freeness nor proportionality can always be satisfied; this can be most easily seen when two quarrelling siblings try to divide a single toy between themselves.

In this paper, we present several new results on asymptotic fair division and in the process close a number of gaps left open by previous work. We assume that agents are endowed with additive utilities, and the utility of each agent for each item is drawn independently from a continuous distribution $\mathcal{D}$ supported on $$whose probability density function is bounded above and below. We say that an event happens “with high probability” if the probability that it happens converges to$1$as$n$ goes to infinity.

First (Section 3), we show that when $m=\Omega(n\log n/\log\log n)$, the round-robin algorithm, which lets the agents take turns picking their favorite item from the remaining items, outputs an envy-free allocation with high probability. This improves upon the aforementioned upper bound of $m=\Omega(n\log n)$ and, perhaps more importantly, matches the non-existence result in the case that $m$ is not “almost divisible” by $n$. Hence, except for the case where $m$ is “almost divisible” by $n$, our result essentially resolves the question of when envy-free allocations exist. Furthermore, our result gives a separation between the round-robin allocation and the welfare-maximizing allocation: while the latter is likely to be envy-free when $m=\Omega(n\log n)$ (Dickerson et al. 2014), it is unlikely to be even proportional, let alone envy-free, when $m=o(n\log n)$ (Manurangsi and Suksompong 2019).

Second (Section 4), we show that if the distribution $\mathcal{D}$ has mean at most $1/2$, We comment on the necessity of this condition in Section 4. a proportional allocation exists with high probability as long as $m\geq n$; this completely closes the gap for propotionality with respect to such distributions (cf. footnote 1). The result for $m\geq 2n$ is obtained by using the round-robin algorithm and generalizes a prior result of Amanatidis et al. 2017, which holds only when $\mathcal{D}$ is the uniform distribution on $$. On the other hand, the case$n\leq m\leq 2n$ is handled using a matching-based algorithm inspired by previous work.

Third (Section 5), we consider envy-freeness up to any item (EFX): an allocation satisfies this property if any envy that an agent has towards another agent can be eliminated by removing any item from the latter agent’s bundle (Caragiannis et al. 2019b). While it is currently an important open problem whether an EFX allocation always exists, we show that such allocations are likely to exist for any relation between $m$ and $n$. This complements recent lines of work which show the (non-asymptotic) existence of approximate EFX allocations (Plaut and Roughgarden 2018; Amanatidis et al. 2020) and exact EFX allocations when items can be discarded (Caragiannis et al. 2019a; Chaudhury et al. 2020b).

Fourth (Section 6), we analyze the related but slightly different setting of assignments, also known as house allocation, where each agent is assigned exactly one item and the remaining items are left unassigned. In this setting, Gan et al. 2019 proved that an envy-free assignment is present with high probability if $m=\Omega(n\log n)$, and left open the question of where the transition between non-existence and existence occurs. We essentially settle this question by showing that this transition occurs at $m=en$: for any constant $\varepsilon>0$, an envy-free allocation is likely to exist if $m/n\geq e+\varepsilon$, and unlikely to exist if $m/n\leq e-\varepsilon$.

Besides closing the gaps themselves, our results also reveal qualitative insights on the relative fairness guarantees provided by different algorithms. For example, the classical round-robin algorithm performs optimally with respect to envy-freeness, whereas a matching-based algorithm is better suited for proportionality when the number of items is small.

Fair division is a fascinating topic whose formal study stretches back over half a century (Steinhaus 1948); see the books by Brams and Taylor 1996 and Moulin 2003 for an overview of its long and intriguing history. While early work in the subject focused on allocating divisible resources (a problem often referred to as cake cutting), the fair allocation of indivisible resources has attracted substantial interest from different research communities in the last few years (Thomson 2016; Markakis 2017; Moulin 2019). After the work of Dickerson et al. 2014 that initiated the study of asymptotic fair division, Kurokawa et al. 2016 and Farhadi et al. 2019 established the probabilistic existence of allocations satisfying a weakening of proportionality called maximin share fairness, the latter work also allowing agents to have unequal entitlements. Manurangsi and Suksompong 2017 extended Dickerson et al.’s results on envy-freeness to a more general setting where items are allocated to groups instead of to individual agents.

In addition to EFX, another (weaker) relaxation of envy-freeness that has been extensively studied is envy-freeness up to one item (EF1), which requires that any envy that an agent has towards another agent can be eliminated by removing some item from the latter agent’s bundle (Lipton et al. 2004; Budish 2011). Unlike EFX, whose guaranteed existence remains an open question, EF1 can be easily attained for additive utilities using the round-robin algorithm.

Preliminaries

In our model, a set $M=[m]$ of indivisible items is to be allocated to a set $N=[n]$ of agents, where $[k]:=\{1,2,\dots,k\}$ for any positive integer $k$. Each agent $i\in N$ has a utility $u_{i}(j)\geq 0$ for each item $j\in M$. We assume without loss of generality that $u_{i}(j)\in$ for all $i,j$, since otherwise we can simply scale down the utilities by their maximum. The utilities are additive, meaning that $u_{i}(M^{\prime})=\sum_{j\in M^{\prime}}u_{i}(j)$ for all $M^{\prime}\subseteq M$. Additivity is a common assumption in fair division; in particular, to the best of our knowledge, it is assumed in all of the works on asymptotic fair division thus far.

A bundle refers to any subset $M^{\prime}\subseteq M$ of items. An allocation is a partition of the items into $n$ bundles $(M_{1},\dots,M_{n})$, where agent $i$ receives bundle $M_{i}$. An allocation is said to be envy-free if $u_{i}(M_{i})\geq u_{i}(M_{i^{\prime}})$ for all $i,i^{\prime}\in N$, and envy-free up to any item (EFX) if $u_{i}(M_{i})\geq u_{i}(M_{i^{\prime}}\backslash\{j\})$ for all $i,i^{\prime}\in N$ and all $j\in M_{i^{\prime}}$. For the sake of convenience, when the allocation under consideration is clear, we say that agent $i$ is envy-free (resp., EFX) with respect to agent $i^{\prime}$ if the corresponding inequality is satisfied for $i$ and $i^{\prime}$, and that agent $i$ is envy-free (resp., EFX) if the corresponding inequality is satisfied for $i$ and all $i^{\prime}\in N$. An allocation is said to be proportional if $u_{i}(M_{i})\geq u_{i}(M)/n$ for all $i\in N$. When discussing proportionality, we will sometimes allow allocations to be partial, i.e., leave some items unallocated. It is clear that if a partial allocation is proportional, then by allocating the remaining items arbitrarily, we obtain a complete proportional allocation.

For agents $i\in N$ and items $j\in M$, the utilities $u_{i}(j)$ are drawn independently from a given distribution $\mathcal{D}$ supported on $$. A distribution is said to be non-atomic if it does not put positive probability on any single point. For a non-atomic distribution$\mathcal{D}$, we denote by$F_{\mathcal{D}}$and$f_{\mathcal{D}}$the cumulative distribution function (CDF) and the probability density function (PDF) of$\mathcal{D}$ respectively. Throughout this work, the assumption that we place on the distributions we consider is that their PDFs are bounded, as stated more precisely below.

For $\alpha,\beta>0$, we say that a distribution $\mathcal{D}$ supported on $$is$(\alpha,\beta)$-PDF-bounded if$\mathcal{D}$is non-atomic and$\alpha\leq f_{\mathcal{D}}(x)\leq\beta$for all$x\in$. We say that$\mathcal{D}$is PDF-bounded if it is$(\alpha,\beta)$-PDF-bounded for some$\alpha,\beta>0$.

It follows from the definition that any $(\alpha,\beta)$-PDF-bounded distribution must have $\alpha\leq 1$ and $\beta\geq 1$. Note that many common distributions, including the uniform distribution on $$(henceforth denoted by$U$) and a normal distribution (with any mean and variance) truncated at$0$and$1$are PDF-bounded. For the sake of convenience, we may use the notations$F_{X}$and$f_{X}$for a random variable$X$to refer to the CDF and PDF of its associated distribution. Similarly, we say that$X$is$(\alpha,\beta)$-PDF-bounded if its distribution is$(\alpha,\beta)$-PDF-bounded. In this paper, we think of$\mathcal{D}$as a fixed distribution that does not change with$n$and$m$; specifically, the parameters$\alpha,\beta$are constants and our big-O notation may include terms that depend on these parameters. We say that an event happens with high probability if the probability that it happens approaches$1$as$n\rightarrow\infty$. Furthermore, when we write$\log n$, the logarithm is assumed to have base$2$.

In the round-robin algorithm, the agents take turns picking their favorite item from the remaining items. We assume without loss of generality that the order in which the agents pick the items is $1,2,\dots,n,1,2\dots$ until the items run out. The $t$-th “round” consists of each agent’s $t$-th pick (so in the last round, not every agent may get to pick).

In the analysis of the round-robin algorithm, we will often find ourselves dealing with distributions restricted to some range. We provide some useful notation and facts for such distributions next.

For any distribution $\mathcal{D}$ and any real number $c\in(0,1]$, we use $\mathcal{D}_{\leq c}$ to denote the conditional distribution of $\mathcal{D}$ on $[0,c]$ (provided that $F_{\mathcal{D}}(c)>0$). Notice that the CDF and PDF of this distribution are

Now, let $Y$ be a random variable generated as follows: we draw $X$ from $\mathcal{D}_{\leq c}$ and set $Y=X/c$. Then, from the above expression of $f_{\mathcal{D}_{\leq c}}$, we have

The following proposition follows almost immediately from the above expression. (Recall from Definition 2.1 that a PDF-bounded distribution is implicitly assumed to be supported on $$.)

For any $(\alpha,\beta)$-PDF-bounded distribution $\mathcal{D}$ and any $c\in(0,1]$, suppose that $Y$ is a random variable where we draw $X$ from $\mathcal{D}_{\leq c}$ and let $Y=X/c$. Then, $Y$ is $\left(\alpha/\beta,\beta/\alpha\right)$-PDF-bounded.

Since $\mathcal{D}$ is $(\alpha,\beta)$-PDF-bounded, we have $\alpha\leq f_{\mathcal{D}}(x)\leq\beta$ for all $x\in[0,c]$. This implies that $F_{\mathcal{D}}(c)\in[c\cdot\alpha,c\cdot\beta]$. Hence, for all $y\in$, we have

Hence $Y$ is $\left(\alpha/\beta,\beta/\alpha\right)$-PDF-bounded, as desired. ∎

For any real number $c<1$ (such that $F_{\mathcal{D}}(c)<1$), we also define $\mathcal{D}_{>c}$ in a similar manner as $\mathcal{D}_{\leq c}$ above.

2. (Anti-)Concentration Inequalities

We will need a few (anti-)concentration inequalities for sums of independent random variables. Our first inequality is the standard Chernoff bound:

Let $X_{1},\dots,X_{k}$ be independent random variables taking values in $$, and let$S:=X_{1}+\cdots+X_{k}$. Then, for any$\delta\geq 0$,

Our last inequality is of the opposite nature from the above bounds: it says that the probability that $X_{1}+\cdots+X_{k}$ is “far” from its expectation is still large (i.e., anti-concentration).

Let $X_{1},\dots,X_{k}$ be independent random variables sampled from $\mathcal{D}$ whose support is a subset of $$, and let$S:=X_{1}+\cdots+X_{k}$. Suppose that$\mathcal{D}$has variance$\sigma^{2}>0$and mean at most$1/2$. Then,

where the constant in the big-O notation can depend on $\sigma$.

Let $\mu\leq 1/2$ denote the mean of $\mathcal{D}$. Consider $S^{\prime}:=\frac{1}{\sigma\sqrt{k}}(S-k\cdot\mu)$. From the Berry-Esseen theorem (Berry 1941; Esseen 1942), the CDF of $S^{\prime}$ and that of the standard normal distribution $\Phi$ differ by at most $O(1/\sqrt{k})$ pointwise. It follows that

3. An Inequality for the Round-Robin Algorithm

We now present a lemma related to the round-robin algorithm. To state this lemma, let us introduce another notation: for any distribution $\mathcal{D}$ and any positive integer $k$, we use $\mathcal{D}^{\max(k)}$ to denote the distribution of the maximum of $k$ independent random variables distributed according to $\mathcal{D}$.

In the round-robin algorithm, consider any agent $i$ and let $X_{r}$ be his value for the item that he gets in round $r$ (and $X_{0}=1$ for convenience). We will show later (in Lemma 3.2) that $X_{1},X_{2},\dots$ are distributed as if they were drawn from the following process: for $r=1,2,\dots$, sample $X_{r}$ from $\mathcal{D}^{\max(m+1-i-n(r-1))}_{\leq X_{r-1}}$. We often want to show that $X_{r}$ is large for a specified $r$. We make a generic calculation below, which will be used multiple times in this work.

Let $T$ be a positive integer and let $s_{1},\dots,s_{T}$ be any positive integers. Consider the random variables $X_{0}=1$ and $X_{1},\dots,X_{T}$ generated by the following process: for every $t=0,1,\dots,T-1$, sample $X_{t+1}$ according to $\mathcal{D}^{\max(s_{t+1})}_{\leq X_{t}}$. If $\mathcal{D}$ is $(\alpha,\beta)$-PDF-bounded, then for any parameter $p\in(0,1)$ we have

The inequality trivially holds if the expression $1-\frac{\beta}{\alpha}\cdot\frac{T\ln(T/p)}{s}$ is negative, so we may assume that this expression is nonnegative, which means that $1-\frac{\beta}{\alpha}\cdot\frac{\ln(T/p)}{s}$ is also nonnegative. For every $t=0,1,\dots,T-1$, Proposition 2.2 implies that if we sample $Z\sim\mathcal{D}_{\leq X_{t}}$ and let $Y=Z/X_{t}$, then $Y$ is $(\alpha/\beta,\beta/\alpha)$-PDF-bounded. As a result, we have

From the above inequality and since $X_{t+1}$ is sampled from $\mathcal{D}_{\leq X_{t}}^{\max(s_{t+1})}$, we have

where the second inequality follows from the well-known inequality $1-x\leq e^{-x}$, which holds for any real number $x$.

Hence, by union bound, with probability at least $1-p$, we have $X_{t+1}\geq\left(1-\frac{\beta}{\alpha}\cdot\frac{\ln(T/p)}{s}\right)X_{t}$ for all $t=0,1,\dots,T-1$. When this is the case, we get

where we use Bernoulli’s inequality for the second inequality and the assumption that $X_{0}=1$. This completes the proof of the lemma. ∎

Envy-freeness

In this section, we consider envy-freeness. Our main result is the following theorem:

Suppose that $\mathcal{D}$ is PDF-bounded. For $m=\Omega\left(\frac{n\log n}{\log\log n}\right)$, the round-robin algorithm outputs an envy-free allocation with high probability.

Since an envy-free allocation is unlikely to exist even when $m=\Theta(n\log n/\log\log n)$ if $m$ is not “almost divisible” by $n$ and the constant in the asymptotic notation is sufficiently small (Manurangsi and Suksompong 2019), the bound in Theorem 3.1 is asymptotically tight.

Let us introduce an additional notation, which we will use in this section as well as in Section 4. For any agents $i,i^{\prime}$, denote by $X^{i,i^{\prime}}_{t}$ agent $i$’s utility for the $t$-th item received by agent $i^{\prime}$ in the round-robin algorithm, and let $X^{i,i^{\prime}}_{0}=1$ for convenience. When $i=i^{\prime}$, we abbreviate $X^{i,i^{\prime}}_{t}$ as $X^{i}_{t}$. The following lemma, which was alluded to before Lemma 2.6, allows us to consider a simple random process that generates $(X^{i,i^{\prime}}_{t})_{i,i^{\prime}\in[n],t\in\left[1+\left\lfloor\frac{m-i^{\prime}}{n}\right\rfloor\right]}$ rather than dealing with the round-robin algorithm directly.

$(X^{i,i^{\prime}}_{t})_{i,i^{\prime}\in[n],t\in\left[1+\left\lfloor\frac{m-i^{\prime}}{n}\right\rfloor\right]}$ has the same distribution as if it is generated as follows:

Sample $X^{i}_{t}\sim\mathcal{D}_{\leq X^{i}_{t-1}}^{\max(m+1-(t-1)n-i)}$.

For every $1\leq i^{\prime}<i$, sample $X^{i^{\prime},i}_{t}\sim\mathcal{D}_{\leq X^{i^{\prime}}_{t}}$.

For every $i<i^{\prime}\leq n$, sample $X^{i^{\prime},i}_{t}\sim\mathcal{D}_{\leq X^{i^{\prime}}_{t-1}}$.

The proof of Lemma 3.2 is deferred to the appendix. We note here that each loop in Step 1a should be thought of as agent $i$ choosing his/her $t$-th item. Observe also that $m+1-(t-1)n-i$ is simply the number of remaining items before agent $i$’s choice is made, and Step 1(a)i can be thought of as picking the best among these items.

Before we prove Theorem 3.1, let us give the high-level intuition behind the proof. Consider any pair of agents $i,i^{\prime}$. If $i<i^{\prime}$, then clearly $i$ does not envy $i^{\prime}$, so we focus on the case where $i>i^{\prime}$. For $i$ to envy $i^{\prime}$, we must have $u_{i}(M_{i^{\prime}})-u_{i}(M_{i})>0$. Note that $u_{i}(M_{i^{\prime}})-u_{i}(M_{i})$ is at most

where $z$ is the last round in which $i^{\prime}$ picks an item. In other words, $X^{i,i^{\prime}}_{1}$ is the amount that $i^{\prime}$ “gains” with her first item from $i$’s viewpoint, and $(X^{i}_{1}-X^{i,i^{\prime}}_{2}),(X^{i}_{2}-X^{i,i^{\prime}}_{3}),\dots,(X^{i}_{z-1}-X^{i,i^{\prime}}_{z})$ are the gains of $i$ that $i$ will use to try to “catch up”, so that $i$ does not envy $i^{\prime}$ in the end. Note that the first gain $X^{i,i^{\prime}}_{1}$ of $i^{\prime}$ is rather small, i.e., no more than $1$. Moreover, each of the gains $(X^{i}_{t}-X^{i,i^{\prime}}_{t+1})$ can be written as $X^{i}_{t}(1-X^{i,i^{\prime}}_{t+1}/X^{i}_{t})$. Lemma 2.6 ensures that these “scaling factors” $X^{i}_{t}$ are relatively large, which allows us to apply the concentration of sums of independent random variables from Lemma 2.4 to $X^{i,i^{\prime}}_{t+1}/X^{i}_{t}$. The proof below implements this idea with the appropriate selection of parameters.

Observe that, if $i<i^{\prime}$, then clearly $i$ does not envy $i^{\prime}$. As a result, we may henceforth assume that $i>i^{\prime}$. In this case, from Lemma 3.2, we may view the values $X^{i,i^{\prime}}_{1},X^{i}_{1},X^{i,i^{\prime}}_{2},\dots$ as being generated by the following process:

Randomly sample $X^{i,i^{\prime}}_{1}$ from $\mathcal{D}$.

For $t=1,2,\dots,1+\left\lfloor\frac{m-i}{n}\right\rfloor$:

Randomly sample $X^{i}_{t}$ from $\mathcal{D}_{\leq X^{i}_{t-1}}^{\max(m+1-i-n(t-1))}$.

Randomly sample $X^{i,i^{\prime}}_{t+1}$ from $\mathcal{D}_{\leq X^{i}_{t}}$.

Note that in the last iteration it may be possible that $X^{i,i^{\prime}}_{t+1}$ is not actually selected in the round-robin algorithm if all the items are already assigned. In this case we overestimate $i$’s value for $i^{\prime}$’s bundle; hence, we will still get an upper bound on the probability that $i$ envies $i^{\prime}$.

Let us also define $Y^{i,i^{\prime}}_{t}:=X^{i,i^{\prime}}_{t+1}/X^{i}_{t}$. Recall that $i$ does not envy $i^{\prime}$ if $u_{i}(M_{i})\geq u_{i}(M_{i^{\prime}})$. To bound the probability that this happens, let us rearrange $u_{i}(M_{i})-u_{i}(M_{i^{\prime}})$ as

: The event that $Y^{i,i^{\prime}}_{1}+\cdots+Y^{i,i^{\prime}}_{T}\geq T-2$.

where $f_{X_{1}^{i},...,X_{T}^{i}}$ denotes the PDF of the joint distribution over $X_{1}^{i},...,X_{T}^{i}$ (which are not independent random variables).

As for the event E2, notice that the sequence $X^{i}_{0},X^{i}_{1},\dots,X^{i}_{T}$ is sampled in the same way as that in Lemma 2.6 with $s_{t}=m+1-i-n(t-1)$ for $t=1,\dots,T$. Observe also that, for sufficiently large $m$, we have $\frac{\beta}{\alpha}\cdot\frac{T\ln(T\cdot m^{3})}{m/2}\leq 1/2$ and $s_{1},\dots,s_{T}\geq m+1-i-n(T-1)\geq m-nT\geq m/2$, where the last inequality follows from (3). As a result, by plugging in Lemma 2.6 with $p=1/m^{3}$, we have $\Pr[\text{E2 occurs}]\leq\frac{1}{m^{3}}$.

Hence, by union bound, the probability that at least one of the two bad events occurs is at most $O(1/m^{3})$. Now, when neither E1 nor E2 occurs, we can further bound (2) as

meaning that $i$ does not envy $i^{\prime}$. As a result, the probability that $i$ does not envy $i^{\prime}$ is at least $1-O(1/m^{3})$. By taking a union bound over all pairs $i,i^{\prime}$, we have that the allocation is envy-free with probability at least $1-O(1/m)$, completing the proof. ∎

Proportionality

In this section, we investigate another fundamental fairness notion, proportionality, and establish the following result:

Suppose that $\mathcal{D}$ is PDF-bounded and has mean at most $1/2$. For any $m\geq n$, there is a polynomial-time algorithm that outputs a proportional allocation with high probability.

The assumption that $\mathcal{D}$ has mean at most $1/2$ is necessary to guarantee the existence of a proportional allocation for all $m\geq n$ with high probability. To see this, suppose that $\mathcal{D}$ has mean $1/2+\varepsilon$ for some constant $\varepsilon>0$, and let $m=2n-1$. In this case, the expected value of $u_{1}(M),\dots,u_{n}(M)$ is $n(1+2\varepsilon-o(1))$; by standard Chernoff and union bounds, we have that with high probability, $u_{i}(M)>n$ simultaneously for all $i$. When this happens, any allocation cannot be proportional—indeed, it is not proportional for an agent who receives at most one item (since each item has value at most $1$), and such an agent always exists due to the pigeonhole principle.

The proof of Theorem 4.1 will be divided into two parts according to the range of $m$. For the case $m\geq 2n$ we will again employ the round-robin algorithm (Theorem 4.2), while the case $n\leq m\leq 2n$ will be handled using a matching-based algorithm (Theorem 4.4).

We begin by showing that the allocation produced by the round-robin algorithm, in addition to satisfying EF1 with certainty and envy-freeness with high probability, is also likely to be proportional even for a modest number of items.

Suppose that $\mathcal{D}$ is PDF-bounded and has mean at most $1/2$. When $m\geq 2n$, the round-robin algorithm outputs a proportional allocation with high probability.

Theorem 4.2 generalizes a result of Amanatidis et al. 2017, who showed an analogous existence but only for the uniform distribution $U$. We remark here that the requirement $m\geq 2n$ is tight. In particular, suppose that $m=2n-1$ and that $\mathcal{D}=U$. Then there is at least a constant probability that $u_{n}(M)>n$. When this happens, the round-robin algorithm will surely fail, as it only assigns one item (of value at most 1) to the last agent $n$.

When $m=\Omega\left(\frac{n\log n}{\log\log n}\right)$, Theorem 3.1 already implies that the round-robin algorithm produces an envy-free (and therefore proportional) allocation with high probability. Hence, it suffices to prove the statement for the case where $m=O(n\log n)$.

Suppose that $\mathcal{D}$ is an $(\alpha,\beta)$-PDF-bounded distribution with mean at most $1/2$. One can check using Chernoff and union bounds that with high probability, we have

for all agents $i\in N$. We will henceforth assume that (4) holds for all $i\in N$.

Let us write $m$ as $nr+q$, where $r=\lfloor m/n\rfloor\geq 2$ and $r=O(\log n)$. We will consider two cases, depending on whether $q\leq n^{0.1}$. (Note that the threshold for $q$ can be any value that is $\omega(\log^{2}n)$ and $o(n)$; we simply select $n^{0.1}$ for concreteness.) Define the notation $X^{i}_{t}$ as in Section 3. By Lemma 3.2, the sequence $X^{i}_{0},X^{i}_{1},\dots,X^{i}_{r}$ is sampled in the same way as that in Lemma 2.6 with $s_{t}=m+1-i-n(t-1)\geq q$ for $t=1,\dots,r$.

Consider an agent $i$. Substituting $p=1/n^{2}$ in Lemma 2.6 implies that the following holds with probability at least $1-1/n^{2}$:

This means that the agent receives an item of value at least $1-O(\log^{2}n/n^{0.1})$ in each of the first $r$ rounds. As a result, $i$’s utility for his bundle is at least $r\left(1-O(\log^{2}n/n^{0.1})\right)$. Furthermore, (4) ensures that $u_{i}(M)/n$ is at most

where we use our assumption $m=O(n\log n)$. Since $r\geq 2$, we have $r>\frac{r+1}{2}$. It follows that for sufficiently large $n$, the allocation is proportional for $i$. By taking a union bound over all agents, we conclude that the allocation is proportional with high probability.

Case 2: q<n0.1q<n^{0.1}.

In this case, we will have to give a more refined bound which differs for each agent $i\in N$, with the agents near the end of the round-robin ordering having a worse probability bound. This bound is stated formally below.

For each $i\in N$, the allocation output by the round-robin algorithm is proportional for $i$ with probability at least $1-O(1/n^{\min\{0.05(n-i+1),2\}})$.

Observe that $s_{t}\geq n$ for $t=1,\dots,r-1$. Substituting $p=1/n^{2}$ in Lemma 2.6 implies that the following holds with probability at least $1-1/n^{2}$:

This means that agent $i$ receives an item of value at least $1-O(\log^{2}n/n^{0.1})$ in each of the first $r-1$ rounds. Hence, from the first $r-1$ rounds, the agent already has a bundle with utility at least $(r-1)\left(1-O(\log^{2}n/n^{0.1})\right)$. From (4), it suffices for the agent to receive the following utility in the $r$-th round for him to consider the allocation to be proportional:

Recall from Lemma 3.2 that the item that agent $i$ receives in the $r$-th round has value distributed as the maximum of $m+1-i-n(r-1)\geq n-i+1$ i.i.d. random variables from $\mathcal{D}_{\leq X^{i}_{r-1}}$. As a result, conditioned on (5) occurring, the probability that the allocation is proportional for $i$ is at least

From this and the fact that (5) occurs with probability at least $1-O(1/n^{2})$, we get the desired claim. ∎

Thus, by union bound, the allocation produced by the round-robin algorithm fails to be proportional with probability at most

which concludes Case 2 and therefore our proof. ∎

2. The Case n≤m≤2​nn\leq m\leq 2n

We now address the case where the number of items is between $n$ and $2n$. As discussed at the beginning of Section 4.1, the round-robin algorithm fails in this regime. Nevertheless, we devise an alternative algorithm that computes a proportional allocation with high probability using some ideas from previous work together with an additional new idea.

Suppose that $\mathcal{D}$ is PDF-bounded and has mean at most $1/2$. For $n\leq m\leq 2n$, there is a polynomial-time algorithm that outputs a proportional allocation with high probability.

We first explain the intuition leading up to the algorithm. In prior work of Suksompong 2016, a matching-based algorithm is used to find proportional allocations. The most basic case of the algorithm is the case $m=n$, where the algorithm can be stated as follows:

A classic result of Erdős and Rényi states that a random balanced bipartite graph is likely to contain a perfect matching when the probability of each edge occurring is, say, $\frac{1.1\log n}{n}$. We use the notation $\mathcal{G}(a,b,p)$ to denote a distribution over bipartite graphs where the two vertex sets have size $a$ and $b$, and each edge occurs with probability $p$ independently of other edges.

Let $G=(A,B,E)$ be a graph sampled from the Erdős-Rényi random bipartite graph distribution $\mathcal{G}(n,n,p)$ where $p=(\log n+\omega(1))/n$. Then, with high probability, $G$ contains a perfect matching.

Notice here that the guaranteed lower bound of $\tau$ on each agent’s utility is quite strong. In particular, if, say, $m=1.999n$ and we just run the above algorithm on the first $m$ items, then the resulting (partial) allocation is already proportional with high probability, because each agent values the whole set $M$ roughly $0.9995n\pm o(n)$.

As a result, we are only left with the case where $m=(2-o(1))n$. For simplicity of discussion, let us focus on the case $m=2n-1$. In this case, Algorithm 1 is not yet sufficient for us: recall from the beginning of Section 4 that in this regime, there are likely to be agents who need at least two items in order to be proportional. This motivates our algorithm, which consists of two stages. Initially, we run Algorithm 1 on the first $n$ items. We then use the remaining $m-n$ items to help “fix” the agents for whom the allocation is not yet proportional. In particular, we create a graph where the left vertices correspond to these agents, the right vertices to the remaining $m-n$ items, and there is an edge between an agent and an item exactly when adding that item to the agent’s bundle results in the bundle being proportional for that agent. The pseudocode of the algorithm is presented as Algorithm 2.

Note that when the algorithm does not output NULL, it always outputs a proportional allocation. Hence, to complete the proof of Theorem 4.4, it suffices to show that it rarely outputs NULL when we set an appropriate value for the parameter $\tau$, which we do in the following lemma.

Suppose that $\mathcal{D}$ is an $(\alpha,\beta)$-PDF-bounded distribution with mean at most $1/2$. For $n\leq m\leq 2n$, Algorithm 2 with $\tau=1-\frac{1.1\log n}{\alpha n}$ outputs NULL with $o(1)$ probability.

To formalize the above ideas, we need an additional bound regarding the existence of matchings, which is more tailored towards our application. It says that, if we sample a (non-balanced) random bipartite graph $(A,B,E)$, where $A$ is slightly larger than $B$, with sufficiently large probability $p$, then any subset $S\subseteq A$ of size noticeably smaller than $B$ is likely to contain a matching to $B$. The bound is stated below; note that we do not attempt to optimize any parameters here, and instead only prove a version which suffices for our application. For a graph $G$ and a set $S$ of vertices, we denote by $Z_{G}(S)$ the set of vertices adjacent to at least one vertex in $S$.

Let $G=(A,B,E)$ be a graph sampled from the Erdős-Rényi random bipartite graph distribution $\mathcal{G}(n,q,p)$, where $p\geq 0.5$ and $0.9n\leq q\leq n$. Then, with high probability, for every $S\subseteq A$ of size at most $0.6n$, we have $|Z_{G}(S)|\geq|S|$.

We can bound the probability that the “bad event” occurs as follows:

For sufficiently large $n$, we have $2^{0.1n}\geq n^{2}$. We can use this to further bound the above summation as

With this setup ready, we can now proceed to the proof of Lemma 4.6.

Let $G_{\geq\tau}=(N,M^{0},E_{\geq\tau})$ be the graph as defined in Algorithm 1 with our threshold $\tau=1-\frac{1.1\log n}{\alpha n}$. As in the proof of Theorem 4.2, one can check that Chernoff and union bounds imply that, with high probability, we have

for all agents $i\in N$. We will henceforth assume that (6) holds for all $i\in N$. Furthermore, Lemma 4.5 immediately implies that a perfect matching in $G_{\geq\tau}$ exists with high probability; we will also assume that this is the case from now on.

Let $q=m-n$ (so $0\leq q\leq n$). We consider two cases, based on the value of $q$.

For sufficiently large $n$, (6) implies that $u_{i}(M)/n\leq 0.996<\tau$ for all $i\in N$. Hence, the partial allocation $(M^{0}_{1},\dots,M^{0}_{n})$ is already proportional for every agent, and the algorithm outputs this allocation without going into the second stage.

Case 2: q≥0.9​nq\geq 0.9n.

In this case, we will need to consider two more “good” events. Let $G^{1}_{\geq 0.5/\beta}=(N,M^{1},E^{1}_{\geq 0.5/\beta})$ be such that $(i,j)\in E^{1}_{\geq 0.5/\beta}$ if and only if $u_{i}(j)\geq 0.5/\beta$.

: For every $S\subseteq N$ of size at most $0.6n$, we have $|Z_{G^{1}_{\geq 0.5/\beta}}(S)|\geq|S|$.

Before we prove that E1 and E2 hold with high probability, let us argue that if they hold, then the algorithm outputs a proportional allocation. To this end, first observe that since E1 and E2 hold, Hall’s marriage theorem implies that there exists a matching from $N^{\text{violated}}$ to $M^{1}$ that uses all vertices in $N^{\text{violated}}$. Moreover, notice that for sufficiently large $n$, $u_{i}(M)/n$, which is at most $1+o(1)$ by (6), is less than $0.5/\beta+\tau=(1+0.5/\beta)-o(1)$ for all $i\in N$. As a result, the aforementioned matching remains a matching in the graph $G^{\text{fix}}$. The algorithm thus outputs a proportional allocation as desired.

It remains to show that both E1 and E2 occur with high probability. This is obvious for E2, since the graph $G^{1}_{\geq 0.5/\beta}$ is generated in exactly the same way as in Lemma 4.7 (with $p=1-F_{\mathcal{D}}(0.5/\beta)\geq 0.5$).

As for E1, let us consider each agent $i\in N$. Let $\sigma^{2}>0$ be the variance of $\mathcal{D}$. For sufficiently large $n$, Lemma 2.5 implies that

where the first inequality follows from $n\geq m/2$ and the fact that $1.1\log n/\alpha=\Theta(\log n)$ is smaller than $0.01\sigma\sqrt{m}=\Theta(\sqrt{n})$ for any sufficiently large $n$.

By Chernoff bound, with high probability, at most $0.6n$ agents $i$ have $u_{i}(M)/n>\tau$. Only these agents can be included into $N^{\text{violated}}$. Hence, E1 holds with high probability.

Thus, the algorithm outputs a proportional allocation with high probability in both cases. ∎

Envy-freeness up to Any Item

In this section, we turn our attention to an important relaxation of envy-freeness: envy-freeness up to any item (EFX). While the worst-case existence of EFX is an intriguing open problem, we show that an EFX allocation is likely to exist for any relation between the number of agents and the number of items:

Suppose that $\mathcal{D}$ is PDF-bounded. There is a polynomial-time algorithm that outputs an EFX allocation with high probability.

Let $r=\lfloor m/n\rfloor$ and $q=m-nr$. An EFX allocation obviously exists when $m\leq n$ (by assigning at most one item to each agent), In fact, Amanatidis et al. 2020 showed that an EFX allocation always exists even when $m\leq n+2$. so we may restrict our attention to the case $m>n$. Furthermore, since an envy-free (and therefore EFX) allocation exists with high probability when $r=\Omega\left(\frac{\log n}{\log\log n}\right)$ (see Section 3), or when $r\geq 2$ and $q=0$ (Manurangsi and Suksompong 2019), we may assume that $r=O(\log n)$ and $q\geq 1$.

As with proportionality (Section 4), the existence of EFX allocations will be shown via two kinds of algorithms: round-robin-based and matching-based. The former will work whenever the remainder $q$ is $\omega(1)$. On the other hand, for the case $q=O(1)$, we in fact present two matching-based algorithms: the first works for $r\geq 2$ and the second specifically for $r=1$. These three algorithms and their corresponding proofs of correctness are given in Sections 5.1–5.3; we then combine them to deduce Theorem 5.1 in Section 5.4.

We start by describing the round-robin-based algorithm. The algorithm works in exactly the same way as round-robin for the first $r$ rounds: in each round, we let agents $1,2,\dots,n$ choose their most preferred item in this order. However, in the final round, we reverse the order and let agents $n,n-1,\dots,n-q+1$ chooses their most preferred item in this order.

We show that if $q=\omega(1)$, then this algorithm, which we will refer to as the round-robin algorithm with reversed last round, is likely to produce an EFX allocation.

With probability $1-O(1/\sqrt{q})$, the allocation output by the round-robin algorithm with reversed last round is EFX.

Before we proceed to prove Theorem 5.2, let us note that using different agent orderings in the algorithm is intuitively a fairer way of distributing items. For instance, by letting agent $n$ pick first in the last round, we somewhat “balance out” the unfairness of the previous rounds. On a more formal level, it is also the case that the standard round-robin algorithm fails to give a guarantee as in Theorem 5.2. A simple example is when $r=1$ and $q=\Omega(n)$. In this case, the output allocation is not EFX for agent $n$ if his most preferred item was picked by one of the first $q$ agents; this bad event happens with constant probability (i.e., $\Omega(q/n)$). However, as Theorem 5.2 shows, reversing the order allows us to rule out such bad events with high probability.

Another remark we would like to make is that when $q\geq 2$ is constant, there is a constant probability that round-robin with reversed last round fails to find an EFX allocation. To see this, consider the case where $r=1$ (i.e., $m=n+q$). Observe that there is an $\exp(-O(q))$ probability that each of the last $q+1$ items remaining has value at most, say, $0.1$ for agent $n$. In this case, agent $n$’s bundle has value at most $0.2$ to him/her. On the other hand, there is a constant probability that agent $(n-1)$’s first item is of value more than $0.2$ to agent $n$. This means that with probability at least $\exp(-O(q))$, agent $n$ would not be EFX; this probability is constant when $q$ is constant.

We now proceed to the proof of Theorem 5.2. To start with, note that a particularly worrying case when proving that EFX is satisfied for an agent is when this agent receives strictly fewer items than some other agent. Our algorithm is specifically designed to handle this issue: the output allocation is always EFX for $i$ with respect to $i^{\prime}$ for every pair of agents $i,i^{\prime}$ such that $i$ receives $r$ items and $i^{\prime}$ receives $r+1$ items, as stated below. (Note that this guarantee is not probabilistic.)

For every $i\in\{1,\dots,n-q\}$ and every $i^{\prime}\in\{n-q+1,\dots,n\}$, in the allocation output by the round-robin algorithm with reversed last round, $i$ is EFX with respect to $i^{\prime}$.

Now, consider any $M^{\prime}=M_{i^{\prime}}\backslash\{j\}$ for some item $j\in M_{i^{\prime}}$. Suppose that $j$ is the item that $i^{\prime}$ chooses in the $t$-th round. Then, we have

As a result, $i$ is EFX with respect to $i^{\prime}$. ∎

Next, we demonstrate that agents with the same number of items are EFX with respect to each other. We show this by proving that with high probability, $u_{i}(M_{i})\geq|M_{i}|-1$ for all $i$. Notice that if $|M_{i}|=|M_{i^{\prime}}|$ for some $i,i^{\prime}$, then this immediately implies that $u_{i}(M_{i})\geq|M_{i}|-1\geq\max_{j\in M_{i^{\prime}}}u_{i}(M_{i^{\prime}}\setminus\{j\})$, i.e., that $i$ is EFX with respect to $i^{\prime}$.

The proof that $u_{i}(M_{i})\geq|M_{i}|-1$ with high probability is divided into two claims, based on whether $i$ receives $r$ items (Claim 5.4) or $r+1$ items (Claim 5.5). The proofs of these claims share some similarities with the proof in Section 4 which shows that round-robin produces a proportional allocation with high probability. Nonetheless, the proofs here are slightly different due to the different lower bounds needed and the reversed order in the last round, so we state them in full below.

With probability $1-O(1/n)$, $u_{i}(M_{i})\geq r-1$ for all $i\in\{1,\dots,n-q\}$ simultaneously.

We will bound the probability that $u_{i}(M_{i})\geq r-1$ for a fixed $i\in\{1,\dots,n-q\}$ and apply the union bound in the end. Observe that, similarly to the standard round-robin algorithm (i.e., Lemma 3.2), $X_{1}^{i},\dots,X_{r}^{i}$ are distributed as follows. First, $X_{1}^{i}$ is drawn from $\mathcal{D}^{\max(m+1-i)}$. Then, for each $t=1,\dots,r-1$, $X_{t+1}^{i}$ is sampled according to $\mathcal{D}_{\leq X_{t}^{i}}^{\max(m+1-i-nt)}$.

To prove the desired bound, we use Lemma 2.6 on $X_{1}^{i},\dots,X_{r-1}^{i}$, which implies that the following holds with probability at least $1-1/n^{2}$:

where we use the assumption that $r=O(\log n)$. When this holds, the bundle from the first $r-1$ rounds already yields value at least $(r-1)\left(1-O\left(\frac{\log^{2}n}{n}\right)\right)$ to agent $i$. Hence, in order to have $u_{i}(M_{i})\geq r-1$, it suffices to have $X_{r}^{i}\geq r\cdot O\left(\frac{\log^{2}n}{n}\right)=O\left(\frac{\log^{3}n}{n}\right)$. Recall that $X_{r}^{i}$ is distributed as the maximum of $m+1-i-n(r-1)\geq 2q+1\geq 3$ random variables independently drawn from $\mathcal{D}_{\leq X_{r-1}^{i}}$. Thus, for $n$ large enough such that $X_{r-1}^{i}$ is at least, say, $0.5$, Proposition 2.2 implies that the probability that $X_{r}^{i}<O\left(\frac{\log^{3}n}{n}\right)$ is at most $O\left(\frac{\log^{3}n}{n}\right)^{3}\leq O\left(\frac{1}{n^{2}}\right)$. As a result, we have $\Pr[u_{i}(M_{i})\geq r-1]\geq 1-O(1/n^{2})$.

Taking a union bound over all $i\in\{1,\dots,n-q\}$ completes our proof. ∎

With probability $1-O(1/\sqrt{q})$, $u_{i}(M_{i})\geq r$ for all $i\in\{n-q+1,\dots,n\}$ simultaneously.