

\section{Conclusion and Future Work}
The current work makes notable progress towards efficient computation (and, hence, universal existence) of exact ${\sf EFk}$ allocations under budget constraints. Our algorithmic results are obtained via a patently simple algorithm, which lends itself to large-scale and explainable implementations. The algorithm's analysis, however, relies on novel insights, which are different from the ideas used for ${\sf EFk}$ guarantees in prior works and also from the ones used in approximation algorithms for the knapsack problem. 

In budget-constrained fair division (among agents with identical valuations) the existence and computation of ${\sf EF1}$ allocations is an intriguing open problem. We note that, interestingly, a constrained setting's computational (in)tractability does not reflect the fairness guarantee one can expect. For instance, the knapsack problem is {\rm NP}-hard for proportional instances and, at the same time, ${\sf EF1}$ allocations can be computed for such instances in polynomial time (Section \ref{section:efone-proportional-instances}). With this backdrop, obtaining ${\sf EFk}$ guarantees in the GAP formulation\footnote{As mentioned previously, in the GAP version of the problem, the goods have agent-specific sizes and values.} is another interesting direction for future work.   
\section{The Distinct-Densities Assumption}
\label{appendix:distinct-densities}
As mentioned previously, for budget-constrained fair division, one can assume, without loss of generality, that the densities of the goods are distinct. We prove this assertion in the proposition below. 
\begin{proposition}
Given any fair division instance with budget constraints $\mathcal{I}=\langle [m], [n], \{ v(g) \}_{g\in [m]}, \{s(g)\}_{g \in [m]}, \allowbreak \{B_a\}_{a\in [n]} \rangle$, we can compute in polynomial-time another instance $\mathcal{I}'=\langle [m], [n], \{ v'(g) \}_{g\in [m]}, \{s'(g)\}_{g \in [m]}, \{B_a'\}_{a\in [n]} \rangle$ with the properties that 
\begin{enumerate}
\item All the goods in $\mathcal{I}'$ have distinct densities.
\item If $\mathcal{A} = (A_1, \ldots, A_{n+1})$ is an ${\sf EF2}$ allocation in the constructed instance $\mathcal{I}'$, then $\mathcal{A}$ is an ${\sf EF2}$ allocation in $\mathcal{I}$ as well.
\end{enumerate}
\end{proposition}
\begin{proof}
From the instance $\mathcal{I}$, we obtain $\mathcal{I}'$ in two steps. First, we obtain an instance $\widehat{\mathcal{I}} =\langle [m], [n], \{ \widehat v(g) \}_{g\in [m]}, \allowbreak \{\widehat s(g)\}_{g \in [m]}, \left\{\widehat{B}_a \right\}_{a\in [n]} \rangle$ in which the values and sizes of all the goods are integral, $\widehat v(g)\in \mathbb{Z}_+$ and $\widehat{s}(g) \in\mathbb{Z}_+$, for all $g\in[m]$, and so are the agents' budgets $\widehat{B}_a \in \mathbb{Z}_+$, for all $a \in [n]$. Then, in the second step,
we obtain the desired instance $\mathcal{I}'$ from $\widehat{\mathcal{I}}$. Both the transformations---i.e., obtaining $\widehat{\mathcal{I}}$ from $\mathcal{I}$
and obtaining $\mathcal{I}'$ from $\widehat{\mathcal{I}}$---take polynomial time.

Recall that the values and sizes of all the goods in the given instance $\mathcal{I}$ are rational, $v(g) \in \mathbb{Q}_+$ and $s(g) \in \mathbb{Q}_+$ for all $g\in[m]$. To obtain instance $\widehat{\mathcal{I}}$ from $\mathcal{I}$ we simply scale the rational values ($v(g)$'s), sizes ($s(g)$'s), and budgets ($B_a$'s) such that they become integral. Note that, considering the rational representation of the inputs, we can efficiently find integers $\Gamma, \Gamma' \in \mathbb{Z}_+$, with polynomial bit-complexity, such that, for each good $g \in [m]$ and each agent $a \in [n]$ the scaled values and sizes are integers: $\widehat v(g) \coloneqq \Gamma \ v(g) \in \mathbb{Z}_+$ along with $\widehat s(g) \coloneqq  \Gamma' \ s(g) \in \mathbb{Z}_+$ and $\widehat{B}_a \coloneqq \Gamma' \ B_a \in \mathbb{Z}_+$. 
Such a scaling can be computed in polynomial time.
 
Now, we perform the second transformation to obtain the desired instance $\mathcal{I}'$. Write $M\coloneqq m\prod_{g\in[m]}\widehat s(g)$. Furthermore, for every good $g\in[m]$ and and agent $a \in [n]$, let
\begin{align*}
v'(g)\coloneqq \widehat v(g)+\frac{1}{M^g}, \quad s'(g)\coloneqq \widehat s(g),\quad\text{ and }\quad B_a'\coloneqq \widehat{B}_a.
\end{align*}
This completes the construction of the instance $\mathcal{I}'$, and we will now prove the stated properties for $\mathcal{I}'$. 
First, note that each of $v'(g)$, $s'(g)$, $B_a'$ can be computed in polynomial time, since the factor $M \in \mathbb{Z}_+$ is of polynomial bit-complexity and the additive term $\frac{1}{M^g}$ can be computed in polynomial time as well.

Now, to prove that, in instance $\mathcal{I}'$, all the goods have distinct densities, consider any two goods $g, h \in [m]$ such that $g<h$. Since $M>\widehat s(g)$ and $M > \widehat{s}(h)$, we have
\begin{align*}
\frac{\widehat s(g)}{M^h} \neq \frac{\widehat s(h)}{M^g}, \  \quad \frac{\widehat s(g)}{M^h}\in(0,1), \quad \text{ and } \ \frac{\widehat s(h)}{M^g}\in(0,1).
\end{align*}
By construction, $\widehat v(\cdot)$ and $\widehat s(\cdot)$ are integer-valued functions. Hence, 
\begin{align*}
\widehat v(h)\widehat s(g)+\frac{\widehat s(g)}{M^h}\ne \widehat v(g)\widehat s(h)+\frac{\widehat s(h)}{M^g}.
\end{align*}
Therefore, we obtain
\begin{align*}
\frac{v'(h)}{s'(h)}=\frac{\widehat v(h)+(1/M^h)}{\widehat s(h)}\ne \frac{\widehat v(g)+(1/M^g)}{\widehat s(g)}=\frac{v'(g)}{s'(g)}.
\end{align*}
That is, all the goods in $\mathcal{I}'$ have distinct densities.

Next, we complete the proof by showing that, if $\mathcal{A} = (A_1, \ldots, A_{n+1})$ is an ${\sf EF2}$ allocation in $\mathcal{I}'$, then $\mathcal{A}$ is an ${\sf EF2}$ allocation in $\mathcal{I}$ as well. Since $\mathcal{A}$ is an ${\sf EF2}$ allocation in $\mathcal{I}'$, for any two agents $a, b \in [n+1]$ and any subset $F \subseteq A_b$, with $s'(F) \leq B'_a$, the following inequality holds, for two goods $f, f' \in F$:
\begin{align}
v'(A_a) \geq v'(F - f - f') \label{ineq:vprime}
\end{align}

In case $|F| \le 2$, then the ${\sf EF2}$ property is clearly satisfied. Hence, we assume that $|F|>2$. Furthermore, note that $s'(F) = \widehat{s}(F) = \Gamma' \ s(F)$ and $B'_a = \widehat{B}_a = \Gamma' \ B_a$. Therefore, subset $F \subseteq A_b$ is considered for the ${\sf EF2}$ guarantee in $\mathcal{I}$ iff it is considered in $\mathcal{I}'$. This observation implies that, to establish the ${\sf EF2}$ guarantee for allocation $\mathcal{A}$ in instance $\mathcal{I}$, it suffices to show that $v(A_a) \geq v(F - f - f')$. We will prove this bound using inequality (\ref{ineq:vprime}).

Assume, towards a contradiction, that $v(A_a) < v(F-f - f')$. Equivalently, we have $\widehat{v}(A_a) < \widehat{v}(F-f - f')$; recall that $\widehat{v}(\cdot)$ is obtained by multiplicatively scaling $v(\cdot)$. Since $\widehat v(\cdot)$ is an integer-valued function, the last inequality reduces to 
\begin{align}
\widehat v(A_a) & \leq \widehat v(F- f - f') - 1 \nonumber \\
&<\widehat v(F- f - f' )- \left(\sum_{g\in A_a} \frac{1}{M^g} - \sum_{h\in (F-f-f') } \frac{1}{M^h}\right) \label{ineq:almost}
\end{align}
The last step follows from the fact that $|A_a| \leq m < M$. In addition, for any subset $X \subseteq [m]$, we have $v'(X) = \widehat{v}(X) + \sum_{g \in X} \frac{1}{M^g}$. Therefore, inequality (\ref{ineq:almost}) reduces to 
\begin{align*}
v'(A_a) < v'(F - f - f').
\end{align*}
This bound, however, contradicts inequality (\ref{ineq:vprime}). Therefore, it must be the case that $v(A_a) \geq v(F - f - f')$, i.e., the ${\sf EF2}$ guarantee holds for allocation $\mathcal{A}$ in the underlying instance $\mathcal{I}$ as well. This completes the proof.  
\end{proof}

\section{The Density Greedy Algorithm for Finding Fair Allocations}
This section develops a greedy algorithm (Algorithm \ref{algo:dense} - $\mathtt{DensestGreedy}$) that allocates goods in decreasing order of density, while maintaining the budget constraints. We will prove that the algorithm achieves  ${\sf EF2}$ for general budget-constrained instances and ${\sf EF1}$ for multiple special cases. 

\begin{theorem}
\label{thm:densestgreedy-ef2}
For any given fair division instance with budget constraints $\langle [m], [n], \{ v(g) \}_{g\in [m]}, \{s(g)\}_{g \in [m]}, \{B_a\}_{a\in [n]} \rangle$, Algorithm \ref{algo:dense} ($\mathtt{DensestGreedy}$) computes an ${\sf EF2}$ allocation in polynomial time.
\end{theorem}

\begin{algorithm}
\caption{$\mathtt{DensestGreedy}$ -- Given instance $\langle [m], [n], \{ v(g) \}_{g}, \{s(g)\}_{g}, \{B_a\}_{a} \rangle$,  
allocate the goods $[m]$ among agents $[n+1]$, including the charity agent $n+1$ (with budget $B_{n+1} \coloneqq \infty$).}  \label{algo:dense}
\begin{algorithmic}[1]
\STATE Initialize allocation $(A_1, \dots, A_{n+1}) \leftarrow (\emptyset, \ldots, \emptyset)$. Also, define the set of active agents $N \coloneqq [n+1]$ and the set of unallocated goods $G \coloneqq [m]$. 
\WHILE{$G \neq \emptyset$}
\STATE Select arbitrarily a minimum-valued agent $a \in N$, i.e., $a = {\displaystyle \arg \min_{b \in N} v(A_b)}$.
\IF{for all goods $g\in G$ we have $s\left( A_a + g \right) > B_a$}
\STATE Set agent $a$ to be inactive, i.e., $N \leftarrow N \setminus \{a\}$.
\ELSE
\STATE \label{line:assign-good} Write $g' = {\displaystyle \argmax_{g \in G :\  s(A_a + g) \leq B_a} \rho(g)}$ 
and update $A_a \leftarrow A_a + g'$ along with $G \leftarrow G - g'$.
\ENDIF
\ENDWHILE
\RETURN $(A_1,A_2,\dots,A_{n+1})$
\end{algorithmic}
\end{algorithm}
Recall the assumption that the goods have distinct densities and, hence, in Line \ref{line:assign-good} we obtain a unique good $g'$ (among the ones that fit within agent $a$'s available budget). While our goal is to find a fair, integral allocation of the (indivisible) goods, for analytic purposes, we will consider fractional assignment of goods to agents. Towards this, for any scalar $\alpha \in[0,1]$ and good $g \in [m]$, we define $\alpha \cdot g$ to be a new good whose size and value are $\alpha$ times the size and value of good $g$, respectively. With fractional goods, we obtain set difference between subsets $I$ and $J$ by adjusting the fractional amount of each good present in $I$. Formally, for subsets $I = \{g_1, g_2, \ldots, g_k\}$ and $J$, let $\alpha_i$ denote the fraction of the good $g_i$ present in $J$,\footnote{Note that, if $\alpha_i = 0$, then the good $g_i$ is not included in $J$. Complementarily, if $\alpha_i = 1$, then the good $g_i$ is completely included in $J$. Also, $g_i$ itself could be a fractional good.} then $I \setminus J \coloneqq \cup_{i=1}^k \left\{ (1-\alpha_i) \cdot g_i \right\}$.  

We next define key constructs for the analysis. For any subset of goods $S$, we define two density-wise prefix subsets of $S$; in particular, $S^{(i)}$ is the subset of the $i$ densest goods in $S$ and $S^{[B]}$ consists of the densest goods in $S$ of total size $B$. Formally, for any subset of goods $S = \{s_1, s_2, \ldots, s_k \}$, indexed in decreasing order of density, and any index $1 \leq i \leq |S|$, write $S^{(i)} \coloneqq \{s_1, \ldots, s_i \}$. Furthermore,
\begin{definition}[Prefix Subset $\Size{S}{B}$]
\label{definition:prefix-subset}
For any subset of goods $S = \{g_1, g_2, \ldots, g_k \}$, indexed in decreasing order of density, and for any nonnegative threshold $B < s(S)$, let $P=\{g_1, \ldots, g_{\ell-1} \}$ be the (cardinality-wise) largest prefix of $S$ such that $s(P) \leq B$. Then, we define $\Size{S}{B} \coloneqq P \cup \left\{ \alpha \cdot g_{\ell} \right\}$, where $\alpha = \frac{B-s(P)}{s(g_{\ell})}$.  
\end{definition}
If the threshold $B \geq s(S)$, then we simply set $\Size{S}{B}=S$. Note that in $\Size{S}{B}$ at most one good is fractional and, for $B \leq s(S)$, the size of $\Size{S}{B}$ is exactly equal to $B$. It is also relevant to observe that, if $A_a$ is the subset of goods assigned to agent $a \in [n]$ at the end of Algorithm \ref{algo:dense}, then $A^{(i)}_a$ is in fact the set of the first $i$ goods assigned to agent $a$ in the algorithm; recall that the algorithm assigns the goods in decreasing order of density. The following two propositions provide useful properties of Algorithm \ref{algo:dense} and are based on the algorithm's selection criteria. The proofs of these propositions are direct and, hence, omitted.

\begin{proposition}\label{greedyproperty}
Let $A_a=\{g_1, g_2, \ldots, g_k\}$ and $A_b=\{h_1, h_2, \ldots, h_\ell\}$ denote, respectively, the sets of goods assigned to agents $a, b \in [n+1]$ at the end of Algorithm \ref{algo:dense}; the goods in these sets are indexed in decreasing order of density (i.e., in order of allocation in Algorithm \ref{algo:dense}).  Also, for indices $i < |A_a|$ and $j < |A_b|$, suppose  $v\left(A^{(i)}_a \right) < v\left(A^{(j)}_b\right)$ and $s\left(A^{(i)}_a + h_{j+1}\right) \leq B_a$. Then, $\rho(g_{i+1}) > \rho(h_{j+1})$. 
\end{proposition}
\begin{proposition}\label{greedyproperty-full}
Let $A_a,A_b$ denote, respectively, the sets of goods assigned to agents $a, b \in [n+1]$ at the end of Algorithm \ref{algo:dense}. Also, let $A_b=\{h_1,h_2,\dots,h_\ell\}$ be the goods in $A_b$, indexed in decreasing order of density. If, for any index $j\in\left[\abs{A_b}-1\right]$, the size $s\left(A_a+h_{j+1}\right)\le B_a$, then we have $v\left(A_a\right)\geq v\left(A_b^{(j)}\right)$.
\end{proposition}

We define the function ${\sf EFCount}(\cdot)$ to capture envy count, i.e., the number of goods that need to be removed in order to achieve envy-freeness. Specifically, 
for any subset of goods $X,Y$, we define ${\sf EFCount}(X,Y)$ as the minimum number of goods whose removal from $Y$ yields a subset of goods with value at most $v(X)$,  
\begin{align}
{\sf EFCount}(X,Y) \coloneqq \min_{R \subseteq Y: \ v({Y \setminus R} ) \leq v(X)} \  |R| \label{eqn:efcount-defn}
\end{align}

\subsection{Structural Properties of Envy Counts}
\label{section:structural-props}

This section develops important building blocks for the algorithm's analysis. 
\begin{lemma}\label{lemma:lipschitz}
For any subset of goods $X$ and $Y$ along with any index $i < |Y|$, let $T \coloneqq s\left(Y^{(i)}\right)$ and $\widehat{\structlb} \coloneqq s\left(Y^{(i+1)}\right)$. 
Then, ${\sf EFCount}\left(\Size{X}{\widehat{\structlb}}, \Size{Y}{\widehat{\structlb}}\right) \leq {\sf EFCount}\left(\Size{X}{T}, \Size{Y}{T}\right) + 1$.
\end{lemma}
\begin{proof}
Write $c \coloneqq {\sf EFCount}\left(\Size{X}{T}, \Size{Y}{T}\right)$. Therefore, by definition, there exists a size-$c$ subset $R \subseteq Y^{[T]}$ with the property that 
$v(X^{[T]}) \geq v(Y^{[T]} \setminus R)$. Define subset $R' := R \cup \{h_{i+1}\}$,  where $h_{i+1}$ is the good in the set $Y^{(i+1)}\setminus Y^{(i)}$. For this set $R'$ of cardinality $c+1$, we have
\begin{align*}
v\left(X^{[\widehat{\structlb}]}\right) &\geq v\left(X^{[T]}\right) 
     \geq v\left(Y^{[T]} \setminus R\right) 
     = v\left(Y^{[\widehat{\structlb}]} \setminus R'\right).
\end{align*}
This implies ${\sf EFCount}\left(\Size{X}{\widehat{\structlb}}, \Size{Y}{\widehat{\structlb}}\right)\leq c + 1$, and the lemma stands proved. 
\end{proof}

The following lemma shows that if ${\sf EFCount}$ from a subset $X$ to a subset $Y$ is more than two, then we can select prefix subsets of $X$ and $Y$ such that the count becomes exactly equal to two.  
\begin{lemma}\label{existenceof2cut}
Let $X$ and $Y$ be any subsets of goods with the property that ${\sf EFCount}(X,Y) \geq 2$. Then, there exists an index $t \leq |Y|$ such that, with $T \coloneqq s\left(\Goods{Y}{t}\right)$, we have  ${\sf EFCount}\left(\Size{X}{T}, \Size{Y}{T}\right) = 2$.
\end{lemma}
\begin{proof}
The lemma essentially follows from a discrete version of the intermediate value theorem. For indices $t \in \{0,1,2,\ldots, |Y|\}$, define the function $h(t) \coloneqq s\left(\Goods{Y} {t}\right)$, i.e., $h(t)$ denotes the size of the $t$ densest goods in $Y$. Extending this function, we consider the envy count at different size thresholds; in particular, write $H(t) \coloneqq {\sf EFCount}\left(\Size{X}{h(t)}, \Size{Y}{h(t)}\right)$ for each $t \in \{0,1,2,\ldots, |Y|\}$. Note that $H(0) = 0$. We will next show that $(i)$ $H(|Y|) \geq 2$ and $(ii)$ the discrete derivative of $H$ is at most one, i.e., $H(t+1) - H(t) \leq 1$ for all $0 \leq t < |Y|$. These properties of the integer-valued function $H$ imply that there necessarily exists an index $t^*$ such that $H(t^*) = 2$. This index $t^*$  satisfies the lemma.

Therefore, we complete the proof by establishing properties $(i)$ and $(ii)$ for the function $H(\cdot)$. For $(i)$, note that the definition of the prefix subset gives us $v(X)\ge v\left(\Size{X}{s(Y)}\right)$. Hence, ${\sf EFCount}\left(\Size X {s(Y)}, Y\right) \geq {\sf EFCount}(X, Y) \geq 2$; the last inequality follows from the lemma assumption.  Since $h(|Y|) = s(Y)$, we have $H(|Y|) \geq 2$. Property $(ii)$ follows directly from Lemma \ref{lemma:lipschitz}. This completes the proof. 
\end{proof}


The next lemma will be critical in our analysis. At a high level, it asserts that if we have two subsets $X'$ and $Z'$ with ${\sf EFCount}(X',Z') = 2$ and one adds more value into $X'$ than $Z'$, then the envy count does not increase. 

\begin{lemma}\label{envy_diff}
Given two subsets of goods $X$ and $Z$ along with two nonnegative size thresholds $T,\widehat{\structlb} \in \mathbb{R}_+$ with the properties that  
\begin{itemize}
\item ${\sf EFCount}\left(\Size{X}{T}, \Size Z {\widehat{\structlb}}\right) = 2$ \ and
\item $v\left(X \setminus \Size X {T}\right) \geq  v\left(Z \setminus \Size Z {\widehat{\structlb}}\right)$.
\end{itemize}
Then, ${\sf EFCount}(X,Z) \leq {\sf EFCount}\left(\Size X {T}, \Size Z {\widehat{\structlb}}\right)=2$.
\end{lemma}
\begin{proof}
Given that ${\sf EFCount}\left(\Size X {T}, \Size Z {\widehat{\structlb}}\right) = 2$, there exist two goods $g_1', g_2' \in \Size Z {\widehat{\structlb}}$
such that $v\left(\Size{Z}{\widehat{\structlb}} - g_1' - g_2'\right)  \leq v\left(\Size X {T}\right)$. Now, using the definition of the prefix subsets (Definition \ref{definition:prefix-subset}) we get
\begin{align}
	v(X) &= v\left(\Size X {T}\right) + v\left(X \setminus \Size X {T}\right) \nonumber \\
	& \geq v\left(\Size Z {\widehat{\structlb}} - g_1' - g_2'\right) + v\left(X \setminus \Size X {T}\right) \nonumber \\
	& \geq v\left(\Size Z {\widehat{\structlb}} - g_1' - g_2'\right) +  v\left(Z \setminus \Size Z {\widehat{\structlb}}\right) \tag{via lemma assumption} \\
	& = v(Z)  -\left( v(g'_1) + v(g'_2) \right) \label{ineq:interim}
\end{align}
The definition of the prefix subset $\Size{Z}{\widehat{\structlb}}$ ensures that, corresponding to goods $g'_1, g'_2 \in \Size{Z}{\widehat{\structlb}}$, there exist two goods $g_1, g_2 \in Z$ such that $v(g_1) + v(g_2) \geq v(g'_1) + v(g'_2)$. This bound and inequality (\ref{ineq:interim}) give us $v(X) \geq v(Z - g_1 - g_2)$. This implies ${\sf EFCount}(X,Z) \leq 2$ and completes the proof of the lemma. 
\end{proof}
\begin{remark}
Lemma \ref{envy_diff} continues to hold when ${\sf EFCount}\left(\Size{X}{T}, \Size{Z}{\widehat{\structlb}}\right) = c$, for a general integer $c\geq1$.
\end{remark}


\subsection{Proof of Theorem \ref{thm:densestgreedy-ef2}: $\mathtt{DensestGreedy}$ achieves EF2}
\label{section:proof-of-main-theorem}

This subsection establishes Theorem \ref{thm:densestgreedy-ef2}. The runtime analysis of the algorithm is direct. Therefore, we focus on proving that $\mathtt{DensestGreedy}$ necessarily finds an ${\sf EF2}$ allocation. Towards this, fix any two agents $a, b \in [n+1]$, and let $A_a$ and $A_b$ be the subsets of goods allocated to them, respectively, at the end of $\mathtt{DensestGreedy}$.
For ease of notation, we will denote $A_a$ by $X = \{x_1, x_2, \dots, x_k \}$ and $A_b$ by $Y =  \{y_1, y_2, \dots, y_{\ell} \}$; the goods in both these sets are indexed in decreasing order of density. Proving ${\sf EF2}$ between the two agents corresponds to showing that, for any subset of goods $Z \subseteq Y$, with $s(Z) \leq B_a$, we have ${\sf EFCount}(X,Z) \leq 2$. 

Consider any such subset $Z$ and index its goods in decreasing order of density, $Z = \{z_1,z_2,\dots,z_{\ell'} \}$. Note that, if ${\sf EFCount}(X, Z) \leq 1$, we already have the ${\sf EF2}$ guarantee. Therefore, in the remainder of the proof we address the case wherein ${\sf EFCount}(X, Z) \geq 2$. We will in fact show that this inequality cannot be strict, i.e., it must hold that the envy count is at most $2$ and, hence, we will obtain the ${\sf EF2}$ guarantee. Our proof relies on carefully identifying certain prefix subsets, showing that they satisfy relevant properties, and finally invoking Lemma \ref{envy_diff}.  

We start by considering function $h(i)$ which denotes the size of the $i$ densest goods in set $Z$, i.e., $h(i) \coloneqq s(\Goods{Z}{i})$ for $i \in \{0,1,2,\ldots, |Z|\}$. Furthermore, define index
\begin{align}
\label{eq:ef2}
t \coloneqq \min\left\{ i : {\sf EFCount}\left(\Size{X}{h(i)}, \Goods{Z}{i}\right) = 2\right\}
\end{align}

\begin{figure}[h]
\centering
\includegraphics[scale=1]{ef2-dia-three.pdf} 
\caption{Figure illustrating size thresholds $\tau$, $\widehat{\tau}$, and the good $g_{Z}$.} \label{figure:cut-offs}
\end{figure}
Existence of such an index $t \ge 2$ follows from Lemma \ref{existenceof2cut}. Also, note that $\Goods{Z}{i} = \Size{Z}{h(i)}$. 
We will denote the $t$th good in $Z$ by $g_{Z}$, i.e., $g_{Z} = z_{t}$. In addition, using $t$ we define the following two size thresholds (see Figure \ref{figure:cut-offs})
\begin{align}
\tau \coloneqq s\left(\Goods Z {t-1}\right) \quad \text{ and } \quad \widehat{\tau} \coloneqq s\left(\Goods Z t\right)\label{eq:defn-tau}
\end{align}
That is, $\tau = h(t-1)$ and $\widehat{\tau} = h(t)$. Now, Lemma \ref{lemma:lipschitz} and the definition of $t$ (equation (\ref{eq:ef2})) give us ${\sf EFCount}\left(\Size X {\tau}, \Size Z {\tau}\right) \ge 1$. Furthermore, using the minimality of $t$ we get ${\sf EFCount}\left(\Size X {\tau}, \Size Z {\tau}\right) < 2$.
Hence, 
\begin{align}
{\sf EFCount}\left(\Size X {\tau}, \Size Z {\tau}\right) = 1 \label{eqn:xtau-ztau}
\end{align}  


We will establish two properties for the sets $X$ and $Z$ under consideration and use them to invoke Lemma \ref{envy_diff}. Specifically, in Lemma \ref{small_ef2} we will show that  ${\sf EFCount}\left(\Size X {\tau}, \Size Z \widehat{\tau}\right) = 2$ and in Lemma \ref{lemma} we prove $v\left(X \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$. These are exactly the two properties required to apply Lemma \ref{envy_diff} with $  T = \tau$ and $ \widehat{\structlb} = \widehat{\tau}$. 

\begin{lemma}\label{small_ef2}
${\sf EFCount}\left(\Size X {\tau}, \Size Z \widehat{\tau}\right) = 2$.
\end{lemma}
\begin{proof}
Since ${\sf EFCount}\left(\Size X \tau, \Size Z \tau\right) = 1$ (see equation (\ref{eqn:xtau-ztau})), there exists a good $g_1 \in \Size Z \tau$ such that $v\left(\Size{X}{\tau}\right) \geq v\left(\Size{Z}{\tau} - g_1\right)$.  
Also, by definition, we have have $ \Size{Z}{\widehat{\tau}} = \Size{Z}{\tau} \cup \{ g_{Z} \}$. Hence, the previous inequality reduces to $v\left(\Size{X}{\tau}\right) \geq v\left(\Size Z \widehat{\tau} -  g_{Z} - g_1\right)$. That is, removing $g_1$ and $g_{Z}$ from $\Size{Z}{\widehat{\tau}}$ gives us a set with value at most that of $\Size{X}{\tau}$. Therefore, we have ${\sf EFCount}\left(\Size X {\tau}, \Size Z \widehat{\tau}\right) = 2$. The lemma stands proved. 
\end{proof}

We define $\gamma$ as the size of the goods in $X$ that are at least as dense as $g_{Z}$, i.e.,  
\begin{align}
\gamma \coloneqq \sum_{g \in X: \rho(g) \geq \rho(g_{Z})} s(g) \label{eq:def-g}
\end{align}

We will establish bounds considering $\gamma$ and use them to prove Lemma \ref{lemma} below. 

\begin{claim} \label{lemma5}
It holds that $\gamma \leq \widehat{\tau}$ and $v\left(\Size X \gamma\right) < v\left(\Size Z \tau\right)$. 
\end{claim}
\begin{proof}
We will first establish the stated upper bound on $\gamma$. Assume, towards a contradiction, that $\gamma > \widehat{\tau}$. By definition of $\gamma$, we have that all the goods in $\Size{X}{\gamma}$ have density at least $\rho(g_{Z})$. Now, given that $\gamma > \widehat{\tau}$, we get that the density of each good in $\Size{X}{\widehat{\tau}}$ is at least $\rho(g_{Z})$. In particular, all the goods in the set $\Size{X}{\widehat{\tau}} \setminus \Size{X}{\tau}$ are at least as dense as $g_{Z}$. Hence, $v\left(\Size X \widehat{\tau} \setminus \Size X \tau\right) \geq v\left(\Size Z \widehat{\tau} \setminus \Size Z \tau\right) = v(g_{Z})$. This inequality and equation (\ref{eqn:xtau-ztau}) give us ${\sf EFCount}(\Size{X}{\widehat{\tau}}, \Size{Z}{\widehat{\tau}}) \leq 1$; see Lemma \ref{envy_diff}. This bound, however, contradicts the definition of $t$ (and, correspondingly, $\widehat{\tau}$) as specified in equation (\ref{eq:ef2}). This gives us the desired upper bound, $\gamma \leq \widehat{\tau}$.  

Next, we prove the second inequality from the claim. For a contradiction, assume that $v\left(\Size X \gamma\right) \geq v\left(\Size Z \tau\right)$. Since $\gamma \leq \widehat{\tau}$, we further get $v\left(\Size{X}{\widehat{\tau}}\right) \geq v\left(\Size Z \tau\right) =  v\left(\Size Z \widehat{\tau} - g_{Z}\right)$. That is, ${\sf EFCount}\left(\Size X \widehat{\tau}, \Size Z \widehat{\tau}\right) \leq 1$. This envy count contradicts the definition of $t$ (and, correspondingly, $\widehat{\tau}$); see equation (\ref{eq:ef2}). Therefore, by way of contradiction, we obtain the second part of the claim. 
\end{proof}

We will now prove Lemma \ref{lemma}.

\begin{lemma}\label{lemma}
$v\left(X \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$.
\end{lemma}
\begin{proof}
Since $Z \subseteq Y$, the good $g_{Z}$ appears in the subset $Y$. Recall that the goods in the subsets $Z$ and $Y = \{y_1, y_2, \ldots, y_\ell \}$ are indexed in order of decreasing density. Write $t' \in [|Y|]$ to denote the index of $g_{Z}$ in $Y$ (i.e., $g_{Z} = y_{t'}$). Lemma \ref{lemma5} gives us 
$v\left(\Size X \gamma\right) < v\left(\Size Z \tau\right) = \sum_{i=1}^{t-1} v(z_i)\le\sum_{i=1}^{t'-1} v(y_i)$. That is, $v\left(\Size X \gamma\right) < v\left(\Goods Y {t'-1} \right)$.  Also, by definition of $\gamma$ (equation \ref{eq:def-g}), we have that the goods in $X \setminus {\Size{X}{\gamma}}$ (if any) have density less than $\rho(g_{Z})$. These observations and Proposition \ref{greedyproperty} imply that including $g_{Z}$ in ${\Size{X}{\gamma}}$ must violate agent $a$'s budget $B_a$, i.e., it must be the case that  
\begin{align}
	\gamma + s(g_{Z}) > B_a\label{eq:gz-doesnt-fit}
\end{align}

Using inequality (\ref{eq:gz-doesnt-fit}), we will prove that $v\left(\Size X \gamma \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$. This bound directly implies the lemma, since $\Size{X}{\gamma} \subseteq X$. In particular, the size of the concerned set satisfies 
\begin{align}
s\left(\Size X \gamma \setminus \Size X \tau\right) & = \gamma - \tau  \nonumber \\
&  = \gamma - \widehat{\tau} + s(g_{Z}) \tag{$\widehat{\tau} - s(g_{Z}) = \tau$} \\
& > B_a - \widehat{\tau} \tag{via inequality (\ref{eq:gz-doesnt-fit})}\\
& \geq s\left(Z \setminus \Size Z \widehat{\tau}\right) \label{ineq:sizelb}
\end{align}
The last inequality follows from the facts that $s(Z) \leq B_a$ and $s( \Size Z \widehat{\tau}) = \widehat{\tau}$. 
Furthermore, by definition of $\gamma$, we have that every good $g \in \Size X \gamma \setminus \Size X \tau$ has density $\rho(g) \geq \rho(g_{Z})$. In addition, for every good $g' \in Z \setminus \Size Z \widehat{\tau}$, the density $\rho(g') \leq \rho(g_{Z})$. These bounds on the densities and the sizes of the subsets ${\Size{X}{\gamma}} \setminus \Size X \tau$ and $Z \setminus \Size Z \widehat{\tau}$ give us $v\left( {\Size{X}{\gamma}} \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$. As mentioned previously, this inequality and the containment $\Size{X}{\gamma} \subseteq X$ imply $v\left(X \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$. The lemma stands proved. 
\end{proof}


Overall, Lemma \ref{small_ef2} gives us ${\sf EFCount}\left(\Size X {\tau}, \Size Z \widehat{\tau}\right) = 2$. In addition, via Lemma \ref{lemma}, we have $v\left(X \setminus \Size X \tau\right) \geq v\left(Z \setminus \Size Z \widehat{\tau}\right)$. Therefore, applying Lemma \ref{envy_diff}, we conclude that ${\sf EFCount}(X, Z) \leq 2$. This establishes the desired ${\sf EF2}$ guarantee for the allocation computed by Algorithm \ref{algo:dense} and completes the proof of Theorem \ref{thm:densestgreedy-ef2}.

\section{${\sf EF2}$ for Goods with Agent-Specific Sizes}
\label{appendix:mini-GAP}
This section addresses budget-constrained fair division settings wherein the goods' sizes are agent-specific. We obtain the ${\sf EF2}$ guarantee for such settings via a direct   generalization of Algorithm \ref{algo:dense} ($\mathtt{DensestGreedy}$). 

In this section, an instance of the budget-constrained fair division problem is a tuple $\langle [m], [n], \{ v(g) \}_{g}, \allowbreak \{s_a(g)\}_{a,g}, \{B_a\}_{a} \rangle$. Here, we need to partition $m$ indivisible goods among $n+1$ agents (including the charity agent with $B_{n+1} = \infty$). The agents' valuations are identical and additive; in particular, every agent values each good $g \in [m]$ at $v(g)$. Sizes of the goods, however, are nonidentical: each good $g \in [m]$ has a size $s_a(g) \in \mathbb{Q}_+$ with respect to the agent $a$. The $m$ goods need to be partitioned into pairwise-disjoint subsets, $A_1, A_2, \ldots, A_{n+1}$, such that, for each agent $a \in [n]$, the assigned bundle $A_a \subseteq [m]$ is of total size at most the agent's budget $B_a \in \mathbb{Q}_+$, i.e., the assigned bundle $A_a$ satisfies $s_a(A_a) = \sum_{g \in A_a} s_a(g) \leq B_a$. For the charity agent $n+1$, we set $s_{n+1}(g) = 1$ for all goods $g \in [m]$. 

We define the notion of ${\sf EF2}$ for this setting. The solution concept here generalizes Definition \ref{defn:eftwo}.  
\begin{definition}[{\sf EF2}]
An allocation $\mathcal{A} = (A_1, A_2, \ldots, A_n, A_{n+1})$ is said to be {envy-free up to two goods} (${\sf EF2}$) iff for all agents $a, b \in [n+1]$ and every subset $F \subseteq A_b$, with $s_a(F) \leq B_a$ (and $|F| \geq 2$), there exist two goods $g_1, g_2 \in F$ such that $v(A_a) \geq v(F \setminus \{g_1,g_2\})$. 
\end{definition}

Agents perceive the size of a good differently and, hence, the density of a good is also agent-specific. To accommodate this, we denote the density of a good $g \in [m]$, with respect to an agent $a \in [n+1]$, as $\rho_a(g) \coloneqq \frac{v(g)}{s_a(g)}$. Since the densities are agent-specific, the notion of the densest good across agents is not well formed.  However, the notion of the minimum-valued agent \emph{does} exist, since the agents' valuations are identical. Furthermore, the function ${\sf EFCount}()$ is well-defined (see equation (\ref{eqn:efcount-defn})).

We obtain the ${\sf EF2}$ guarantee in the current context via Algorithm \ref{algo:dense_gap}. As mentioned previously, this algorithm is obtained by generalizing the $\mathtt{DensestGreedy}$ algorithm. The key difference between the two algorithm is in Line \ref{line:assign-good_gap} Algorithm \ref{algo:dense_gap}, where we allocate the densest good (that fits) from the selected agent $a$'s perspective, i.e., densest with respect to $\rho_a(\cdot)$.

The analysis of Algorithm \ref{algo:dense_gap} is similar to that of the $\mathtt{DensestGreedy}$ algorithm. Though, multiple arguments (e.g., Lemma \ref{lemma_gap}) are more involved. For a self-contained treatment, we provide a complete analysis and even repeat the common parts. Formally, we establish the following guarantee 
\begin{theorem}
\label{thm:densestgreedy-ef2_gap}
For any given fair division instance with budget constraints $\langle [m], [n], \{ v(g) \}_{g\in [m]}, \{s_a(g)\}_{a \in [n],g \in [m]}, \allowbreak \{B_a\}_{a\in [n]} \rangle$, Algorithm \ref{algo:dense_gap} computes an ${\sf EF2}$ allocation in polynomial time.
\end{theorem}


\begin{algorithm}
\caption{Given instance $\langle [m], [n], \{ v(g) \}_{g}, \{s_a(g)\}_{a,g}, \allowbreak \{B_a\}_{a} \rangle$, allocate the $m$ goods among $n+1$ agents, including the charity agent $n+1$ (with budget $B_{n+1} \coloneqq \infty$).}  \label{algo:dense_gap}
\begin{algorithmic}[1]
\STATE Initialize allocation $(A_1, \dots, A_{n+1}) \leftarrow (\emptyset, \ldots, \emptyset)$. Also, define set of active agents $N \coloneqq [n+1]$ and set of unallocated goods $G \coloneqq [m]$.
\WHILE{$G \neq \emptyset$}
\STATE Select arbitrarily a minimum-valued agent $a \in N$, i.e., $a = {\displaystyle \arg \min_{b \in N} v(A_b)}$
\IF{for all goods $g\in G$ we have $s_a\left( A_a + g \right) > B_a$}
\STATE Set agent $a$ to be inactive, i.e., $N \leftarrow N \setminus \{a\}$.
\ELSE
\STATE \label{line:assign-good_gap} Write $g' = {\displaystyle \argmax_{g \in G :\  s_a(A_a + g) \leq B_a} \rho_a(g)}$ 
and update $A_a \leftarrow A_a + g'$ along with $G \leftarrow G - g'$.
\ENDIF
\ENDWHILE
\RETURN $(A_1,A_2,\dots,A_{n+1})$
\end{algorithmic}
\end{algorithm}

In every iteration of the while-loop in Algorithm \ref{algo:dense_gap}, either a good is allocated to an agent or an agent is marked as inactive. Throughout this section, we will write $\sigma \in \mathbb{S}_m$ to denote the order in which the goods are allocated (among the agents) by the algorithm. That is, $\sigma: [m] \rightarrow [m]$ is the  permutation with the property that, for any two indices $t, t' \in [m]$, with $t < t'$, the good $\sigma(t)$ was allocated in an earlier iteration (of Algorithm \ref{algo:dense_gap}) than good $\sigma(t')$.\footnote{Note that goods $\sigma(t)$ and $\sigma(t')$ might have been assigned to different agents.}  

We now define prefix-subsets for the current context. For any subset of goods $S = \{s_1, s_2, \ldots, s_k \}$, indexed according to the allocation order $\sigma$, and any index $1 \leq i \leq |S|$, write $S^{(i)} \coloneqq \{s_1, \ldots, s_i \}$.
\begin{definition}[Prefix Subset $\Size{S_a}{B}$]
\label{definition:prefix-subset_gap}
For any agent $a \in [n+1]$ and a subset of goods $S = \{g_1, g_2, \ldots, g_k \}$, indexed according to the allocation order $\sigma$, and for any threshold $B < s_a(S)$, let $P=\{g_1, \ldots, g_{\ell-1} \}$ be the (cardinality-wise) largest prefix of $S$ such that $s_a(P) \leq B$. Then, we define $S_a^{[B]} \coloneqq P \cup \left\{ \alpha \cdot g_{\ell} \right\}$, where $\alpha = \frac{B-s_a(P)}{s_a(g_{\ell})}$.  
\end{definition}

If the threshold $B \geq s_a(S)$, then we set $\Size{S_a}{B}=S$. The following proposition directly follows from the selection criteria of Algorithm \ref{algo:dense_gap}.
\begin{proposition}\label{greedyproperty_gap}
Let $A_a=\{g_1, g_2, \ldots, g_k\}$ and $A_b=\{h_1, h_2, \ldots, h_\ell\}$ denote, respectively, the sets of goods assigned to agents $a, b \in [n+1]$ at the end of Algorithm \ref{algo:dense_gap}; the goods in these sets are indexed according to $\sigma$ (i.e., in order of allocation in Algorithm \ref{algo:dense_gap}).  Also, for indices $i < |A_a|$ and $j < |A_b|$, suppose  $v\left(A^{(i)}_a \right) < v\left(A^{(j)}_b\right)$ and $s_a\left(A^{(i)}_a + h_{j+1}\right) \leq B_a$. Then, $\rho_a(g_{i+1}) > \rho_a(h_{j+1})$. 
\end{proposition}

The following three lemmas provide generalizations of the ones provided in the Section \ref{section:structural-props}. 

\begin{lemma}\label{lemma:lipschitz_gap}
For any agent $a \in [n+1]$, any subset of goods $X$ and $Y$ along with any index $i < |Y|$, let $T \coloneqq s_a\left(Y^{(i)}\right)$ and $\widehat{\structlb} \coloneqq s_a\left(Y^{(i+1)}\right)$. 
Then, ${\sf EFCount}\left(\Size{X_a}{\widehat{\structlb}}, \Size{Y_a}{\widehat{\structlb}}\right) \leq {\sf EFCount}\left(\Size{X_a}{T}, \Size{Y_a}{T}\right) + 1$.
\end{lemma}
\begin{proof}
Write $c \coloneqq {\sf EFCount}\left(\Size{X_a}{T}, \Size{Y_a}{T}\right)$. Therefore, by definition, there exists a size-$c$ subset $R \subseteq \Size{Y_a}{T}$ with the property that 
$v(\Size{X_a}{T}) \geq v(\Size{Y_a}{T} \setminus R)$. Define subset $R' \coloneqq  R \cup \{h_{i+1}\}$,  where $h_{i+1}$ is the good in the set $Y^{(i+1)}\setminus Y^{(i)}$. For this set $R'$ of cardinality $c+1$, we have
\begin{align*}
v\left( \Size{X_a}{\widehat{\structlb}} \right) &\geq v\left( \Size{X_a}{T} \right) 
     \geq v\left(\Size{Y_a}{T} \setminus R\right) 
     = v\left(\Size{Y_a}{\widehat{\structlb}} \setminus R'\right).
\end{align*}
This implies ${\sf EFCount}\left(\Size{X_a}{\widehat{\structlb}}, \Size{Y_a}{\widehat{\structlb}}\right)\leq c + 1$, and the lemma stands proved. 
\end{proof}


\begin{lemma}\label{existenceof2cut_gap}
Let $a \in [n+1]$ be an agent and $X$ and $Y$ be any subsets of goods with the property that ${\sf EFCount}(X,Y) \geq 2$. Then, there exists an index $t \leq |Y|$ such that, with $T \coloneqq s_a\left(\Goods{Y}{t}\right)$, we have  ${\sf EFCount}\left(\Size{X_a}{T}, \Size{Y_a}{T}\right) = 2$.
\end{lemma}
\begin{proof}
The lemma follows from a discrete version of the intermediate value theorem. For indices $t \in \{0,1,2,\ldots, |Y|\}$, define the function $h(t) \coloneqq s_a\left(\Goods{Y} {t}\right)$. Extending this function, we consider the envy count at different size thresholds; in particular, write $H(t) \coloneqq {\sf EFCount}\left(\Size{X_a}{h(t)}, \Size{Y_a}{h(t)}\right)$ for each $t \in \{0,1,2,\ldots, |Y|\}$. Note that $H(0) = 0$. We will next show that $(i)$ $H(|Y|) \geq 2$ and $(ii)$ the discrete derivative of $H$ is at most one, i.e., $H(t+1) - H(t) \leq 1$ for all $0 \leq t < |Y|$. These properties of the integer-valued function $H$ imply that there necessarily exists an index $t^*$ such that $H(t^*) = 2$. This index $t^*$  satisfies the lemma.  

Therefore, we complete the proof by establishing properties $(i)$ and $(ii)$ for the function $H(\cdot)$. For $(i)$, note that the definition of the prefix subset gives us $v(X)\ge v\left(\Size{X_a}{s_a(Y)}\right)$. Hence, ${\sf EFCount}\left(\Size {X_a} {s_a(Y)}, Y\right) \geq {\sf EFCount}(X, Y) \geq 2$; the last inequality follows from the lemma assumption.  Since $h(|Y|) = s_a(Y)$, we have $H(|Y|) \geq 2$. Property $(ii)$ follows directly from Lemma \ref{lemma:lipschitz_gap}. This completes the proof. 
\end{proof}

The following lemma essentially asserts that if we have two subsets $X'$ and $Z'$ with ${\sf EFCount}(X',Z') = 2$ and one adds more value into $X'$ than $Z'$, then the envy count does not increase. 

\begin{lemma}\label{envy_diff_gap}
Given an agent $a\in [n+1]$ and two subsets of goods $X$ and $Z$ along with two nonnegative size thresholds $T,\widehat{\structlb} \in \mathbb{R}_+$ with the properties that  
\begin{itemize}
\item ${\sf EFCount}\left(\Size{X_a}{T}, \Size {Z_a}{\widehat{\structlb}}\right) = 2$  and 
\item $v\left(X \setminus \Size {X_a} {T}\right) \geq  v\left(Z \setminus \Size {Z_a} {\widehat{\structlb}}\right)$.
\end{itemize}
Then, ${\sf EFCount}(X,Z) \leq {\sf EFCount}\left(\Size {X_a} {T}, \Size {Z_a} {\widehat{\structlb}}\right)=2$.
\end{lemma}
\begin{proof}
Given that ${\sf EFCount}\left(\Size {X_a} {T}, \Size {Z_a} {\widehat{\structlb}}\right) = 2$, there exist two goods $g_1', g_2' \in \Size {Z_a} {\widehat{\structlb}}$
such that $v\left(\Size{Z_a}{\widehat{\structlb}} - g_1' - g_2'\right)  \leq v\left(\Size {X_a} {T}\right)$. Now, using the definition of the prefix subsets (Definition \ref{definition:prefix-subset_gap}) we get
\begin{align}
	v(X) &= v\left(\Size {X_a} {T}\right) + v\left(X \setminus \Size {X_a} {T}\right) \nonumber \\
	& \geq v\left(\Size {Z_a} {\widehat{\structlb}} - g_1' - g_2'\right) + v\left(X \setminus \Size {X_a} {T}\right) \nonumber \\
	& \geq v\left(\Size {Z_a} {\widehat{\structlb}} - g_1' - g_2'\right) +  v\left(Z \setminus \Size {Z_a} {\widehat{\structlb}}\right) \tag{via lemma assumption} \\
	& = v(Z)  -\left( v(g'_1) + v(g'_2) \right) \label{ineq:interim_gap}
\end{align}
The definition of the prefix subset $\Size{Z_a}{\widehat{\structlb}}$ ensures that, corresponding to goods $g'_1, g'_2 \in \Size{Z_a}{\widehat{\structlb}}$, there exist two goods $g_1, g_2 \in Z$ such that $v(g_1) + v(g_2) \geq v(g'_1) + v(g'_2)$. This bound and inequality (\ref{ineq:interim_gap}) give us $v(X) \geq v(Z - g_1 - g_2)$. This implies ${\sf EFCount}(X,Z) \leq 2$ and completes the proof of the lemma. 
\end{proof}


\subsection{Proof of Theorem \ref{thm:densestgreedy-ef2_gap}}
This section establishes Theorem \ref{thm:densestgreedy-ef2_gap}. Fix any two agent $a, b \in [n+1]$, and let $A_a$ and $A_b$ be the subsets of goods allocated to them, respectively, at the end of Algorithm \ref{algo:dense_gap}.    
For ease of notation, we will denote $A_a$ by $X = \{x_1, x_2, \dots, x_k \}$ and $A_b$ by $Y =  \{y_1, y_2, \dots, y_{\ell} \}$; the goods in both these sets are indexed according to the allocation order $\sigma$. Proving ${\sf EF2}$ between the two agents corresponds to showing that, for any subset of goods $Z \subseteq Y$, with $s_a(Z) \leq B_a$, we have ${\sf EFCount}(X,Z) \leq 2$. 

Consider any such subset $Z$ and index its goods in order of $\sigma$. Note that, if ${\sf EFCount}(X, Z) \leq 1$, we already have the ${\sf EF2}$ guarantee. Therefore, in the remainder of the proof we address the case wherein ${\sf EFCount}(X, Z) \geq 2$. We will in fact show that this inequality cannot be strict, i.e., it must hold that the envy count is at most $2$ and, hence, we will obtain the ${\sf EF2}$ guarantee.

We start by considering function $h_a(i)$ which denotes the size---with respect to $s_a(\cdot)$---of the first (order according to the $\sigma$) $i$ goods in set $Z$, i.e., $h_a(i) \coloneqq s_a(\Goods{Z}{i})$ for $i \in \{0,1,2,\ldots, |Z|\}$. Furthermore, define index 
\begin{align}
\label{eq:t-repeat}
t \coloneqq \min\left\{ i : {\sf EFCount}\left(\Size{X_a}{h_a(i)}, \Goods{Z}{i}\right) = 2\right\}
\end{align}

\begin{figure}[h]
\centering
\includegraphics[scale=1]{ef2-dia-three.pdf} 
\caption{Figure illustrating size thresholds $\tau$, $\widehat{\tau}$, and the good $g_{Z}$ with respect to agent $a$.} \label{figure:cut-offs}
\end{figure}
Existence of such an index $t \ge 2$ follows from Lemma \ref{existenceof2cut_gap}. Also, note that $\Goods{Z}{i} = \Size{Z_a}{h_a(i)}$. 
We will denote the $t^{th}$ good in $Z$ by $g_{Z}$, i.e., $g_{Z} = z_{t}$. In addition, using $t$ we define the following two size thresholds (see Figure \ref{figure:cut-offs})
\begin{align}
\tau \coloneqq s_a\left(\Goods Z {t-1}\right) \quad \text{ and } \quad \widehat{\tau} \coloneqq s_a\left(\Goods Z t\right)\label{eq:defn-tau_gap}
\end{align}
That is, $\tau = h_a(t-1)$ and $\widehat{\tau} = h_a(t)$. Now, Lemma \ref{lemma:lipschitz_gap} and the definition of $t$ (equation (\ref{eq:t-repeat})) give us ${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} {\tau}\right) \ge 1$. Furthermore, using the minimality of $t$ we get ${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} {\tau}\right) < 2$.
Hence, 
\begin{align}
{\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} {\tau}\right) = 1 \label{eqn:xtau-ztau_gap}
\end{align}  


We will establish two properties for the sets $X$ and $Z$ under consideration and use them to invoke \cref{envy_diff_gap}. Specifically, in \cref{small_ef2_gap} we will show that  ${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} \widehat{\tau}\right) = 2$ and in \cref{lemma_gap} we prove $v\left(X \setminus \Size {X_a} \tau\right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$. These are exactly the two properties required to apply \cref{envy_diff_gap} with $  T = \tau$ and $ \widehat{\structlb} = \widehat{\tau}$. 

\begin{lemma}\label{small_ef2_gap}
${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} \widehat{\tau}\right) = 2$.
\end{lemma}
\begin{proof}
Since ${\sf EFCount}\left(\Size {X_a} \tau, \Size {Z_a} \tau\right) = 1$ (see equation (\ref{eqn:xtau-ztau_gap})), there exists a good $g_1 \in \Size {Z_a} \tau$ such that $v\left(\Size{X_a}{\tau}\right) \geq v\left(\Size{Z_a}{\tau} - g_1\right)$.  
Also, by definition, we have have $ \Size{Z}{\widehat{\tau}} = \Size{Z}{\tau} \cup \{ g_{Z} \}$. Hence, the previous inequality reduces to $v\left(\Size{X}{\tau}\right) \geq v\left(\Size Z \widehat{\tau} -  g_{Z} - g_1\right)$. That is, removing $g_1$ and $g_{Z}$ from $\Size{Z}{\widehat{\tau}}$ gives us a set with value at most that of $\Size{X}{\tau}$. Therefore, we have ${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} \widehat{\tau}\right) = 2$. The lemma stands proved. 
\end{proof}

We define $\gamma$ as the size of the goods in $X$ that are at least as dense as $g_{Z}$ with respect to agent $a$, i.e.,  
\begin{align}
\gamma \coloneqq \sum_{g \in X: \rho_a(g) \geq \rho_a(g_{Z})} s(g) \label{eq:def-g_gap}
\end{align}

We will establish bounds considering $\gamma$ and use them to prove Lemma \ref{lemma_gap} below. 

\begin{claim} \label{lemma5_gap}
It holds that $\gamma \leq \widehat{\tau}$ and $v\left(\Size {X_a} \gamma\right) < v\left(\Size {Z_a} \tau\right)$. 
\end{claim}
\begin{proof}
We will first establish the stated upper bound on $\gamma$. Assume, towards a contradiction, that $\gamma > \widehat{\tau}$. By definition of $\gamma$, we have that all the goods in $\Size{X_a}{\gamma}$ have density at least $\rho(g_{Z})$. Now, given that $\gamma > \widehat{\tau}$, we get that the density of each good in $\Size{X}{\widehat{\tau}}$ is at least $\rho(g_{Z})$. In particular, all the goods in the set $\Size{X_a}{\widehat{\tau}} \setminus \Size{X_a}{\tau}$ are at least as dense as $g_{Z}$ with respect to agent $a$. Hence, $v\left(\Size {X_a} \widehat{\tau} \setminus \Size {X_a} \tau\right) \geq v\left(\Size {Z_a} \widehat{\tau} \setminus \Size {Z_a} \tau\right) = v(g_{Z})$. This inequality and equation (\ref{eqn:xtau-ztau_gap}) give us ${\sf EFCount}(\Size{X_a}{\widehat{\tau}}, \Size{Z_a}{\widehat{\tau}}) \leq 1$; see Lemma \ref{envy_diff_gap}. This bound, however, contradicts the definition of $t$ (and, correspondingly, $\widehat{\tau}$) as specified in equation (\ref{eq:t-repeat}). This gives us the desired upper bound, $\gamma \leq \widehat{\tau}$.  

Next, we prove the second inequality from the claim. For a contradiction, assume that $v\left(\Size {X_a} \gamma\right) \geq v\left(\Size {Z_a} \tau\right)$. Since $\gamma \leq \widehat{\tau}$, we further get $v\left(\Size{X_a}{\widehat{\tau}}\right) \geq v\left(\Size {Z_a} \tau\right) =  v\left(\Size {Z_a} \widehat{\tau} - g_{Z}\right)$. That is, ${\sf EFCount}\left(\Size {X_a} \widehat{\tau}, \Size {Z_a} \widehat{\tau}\right) \leq 1$. This envy count contradicts the definition of $t$ (and, correspondingly, $\widehat{\tau}$); see equation (\ref{eq:t-repeat}). Therefore, by way of contradiction, we obtain the second part of the claim.
\end{proof}

\begin{claim}\label{goods_density_gap}
For each good $g \in \Size {X_a} \gamma$ and any good $g' \in Z \setminus \Size {Z_a} \widehat{\tau}$, we have $\rho_a(g) \geq \rho_a(g')$.
\end{claim}
\begin{proof}
We will use Proposition \ref{greedyproperty_gap} to prove the claim. Recall that the goods in subsets $X$ and $Y$ are indexed in the allocation order $\sigma$.  Let $t_1$ denote the index of the given good $g$ in $X$, and let $t_2$ denote the index of good $g'$ in $Y$. 

We first show that $v\left(X^{(t_1-1)} \right) < v\left(Y^{(t_2-1)} \right)$. Note that good $g \in \Size {X_a} \gamma$. Hence, all the goods included in $X$, before $g$, in the algorithm (i.e., all the goods in $X^{(t_1-1)}$) are also contained in $\Size {X_a} \gamma$. That is, $X^{(t_1-1)} \subseteq \Size {X_a} \gamma$. Using this containment, we obtain 
\begin{align}
v\left(X^{(t_1-1)} \right) & \leq v\left(\Size {X_a} \gamma\right) \nonumber \\ 
& < v\left(\Size {Z_a} \tau\right) \tag{via Claim \ref{lemma5_gap}} \\
& < v\left( \Size {Z_a} {\widehat{\tau}}\right) \label{ineq:something}
\end{align}
Furthermore, since $g' \in Z \setminus \Size {Z_a} \widehat{\tau}$, we have $v\left(\Size {Z_a} {\widehat{\tau}} \right) \leq v\left(Y^{(t_2-1)} \right)$. This bound and inequality (\ref{ineq:something}) imply $v\left(X^{(t_1-1)} \right) < v\left(Y^{(t_2-1)} \right)$. 

The above-mentioned containment also gives us $s_a \left(X^{(t_1-1)} \right) \leq s_a \left(\Size {X_a} \gamma\right) = \gamma$. Since $\gamma \leq \widehat{\tau}$ (Claim \ref{lemma5_gap}), we get that the good $g'$ can be included in the subset $X^{(t_1-1)}$ without violating agent $a$'s budget constraint: $ s_a \left(X^{(t_1-1)} + g' \right) \leq \gamma + s_a(g') \leq \widehat{\tau} + s_a(g') \leq s_a(Z) \leq B_a$. 

Now, invoking Proposition \ref{greedyproperty_gap} (with $i = t_1 - 1$ and $j = t_2 -1$), we obtain the desired inequality, $\rho_a(g) \geq \rho_a(g')$.
The claim stands proved.
\end{proof}

We are now prove Lemma \ref{lemma_gap}. 

\begin{lemma}\label{lemma_gap}
$v\left(X \setminus \Size {X_a} \tau\right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$.
\end{lemma}
\begin{proof}
Since $Z \subseteq Y$, the good $g_{Z}$ appears in the subset $Y$. Recall that the goods in the subsets $Z$ and $Y = \{y_1, y_2, \ldots, y_\ell \}$ are indexed according to the allocation order $\sigma$. Write $t' \in [|Y|]$ to denote the index of $g_{Z}$ in $Y$ (i.e., $g_{Z} = y_{t'}$). \cref{lemma5_gap} gives us 
$v\left(\Size {X_a} \gamma\right) < v\left(\Size {Z_a} \tau\right) = \sum_{i=1}^{t-1} v(z_i)\le\sum_{i=1}^{t'-1} v(y_i)$. That is, $v\left(\Size {X_a} \gamma\right) < v\left(\Goods Y {t'-1} \right)$.  Also, by definition of $\gamma$ (equation \ref{eq:def-g_gap}), we have that the goods in $X \setminus {\Size{X_a}{\gamma}}$ (if any) have density less than $\rho(g_{Z})$. These observations and \cref{greedyproperty_gap} imply that including $g_{Z}$ in ${\Size{X_a}{\gamma}}$ must violate agent $a$'s budget $B_a$, i.e., it must be the case that  
\begin{align}
    \gamma + s_a(g_{Z}) > B_a\label{eq:gz-doesnt-fit_gap}
\end{align}

Using inequality (\ref{eq:gz-doesnt-fit_gap}), we will prove that $v\left(\Size {X_a} \gamma \setminus \Size {X_a} \tau\right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$. This bound directly implies the lemma, since $\Size{X_a}{\gamma} \subseteq X$. In particular, the size of the concerned set satisfies 
\begin{align}
s_a\left(\Size {X_a} \gamma \setminus \Size {X_a} \tau\right) & = \gamma - \tau  \nonumber \\
&  = \gamma - \widehat{\tau} + s_a(g_{Z}) \tag{$\widehat{\tau} - s_a(g_{Z}) = \tau$} \\
& > B_a - \widehat{\tau} \tag{via inequality (\ref{eq:gz-doesnt-fit_gap})}\\
& \geq s_a\left(Z \setminus \Size {Z_a} \widehat{\tau}\right) \label{ineq:sizelb_gap}
\end{align}
The last inequality follows from the facts that $s_a(Z) \leq B_a$ and $s_a( \Size {Z_a} \widehat{\tau}) = \widehat{\tau}$. 

Furthermore, from Claim \ref{goods_density_gap} we have that each good $g \in \Size {X_a} \gamma \setminus \Size {X_a} \tau$ is denser than each good $g' \in Z \setminus \Size {Z_a} \widehat{\tau}$. These bounds on densities and sizes of the subsets ${\Size{X_a}{\gamma}} \setminus \Size {X_a} \tau$ and $Z \setminus \Size {Z_a} \widehat{\tau}$ give us $v\left( {\Size{X_a}{\gamma}} \setminus \Size {X_a} \tau\right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$. As mentioned previously, this inequality and the containment $\Size{X_a}{\gamma} \subseteq X$ imply $v\left(X \setminus \Size {X_a} \tau\right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$. The lemma stands proved.
\end{proof}

Overall, Lemma \ref{small_ef2_gap} gives us ${\sf EFCount}\left(\Size {X_a} {\tau}, \Size {Z_a} \widehat{\tau}\right) = 2$. In addition, via Lemma \ref{lemma_gap}, we have $v\left(X \setminus \Size{X_a}{\tau} \right) \geq v\left(Z \setminus \Size {Z_a} \widehat{\tau}\right)$. Therefore, applying \cref{envy_diff_gap}, we conclude that ${\sf EFCount}(X, Z) \leq 2$. This establishes that desired ${\sf EF2}$ guarantee for the allocation computed by Algorithm \ref{algo:dense_gap} and completes the proof of Theorem \ref{thm:densestgreedy-ef2_gap}.


\section{Introduction}
Discrete fair division is an actively growing field of research at the interface of computer science, mathematical economics, and multi-agent systems \cite{handbook2016,aziz2022algorithmic,amanatidis2022fair}. This study is motivated, in large part, by resource-allocation settings in which the underlying resources have to be assigned integrally and cannot be fractionally divided among the agents. Notable examples of such settings include fair allocation of courses \cite{Budish2011TheCA,Othman2010}, public housing units \cite{deng2013story}, and inheritance \cite{Spliddit}. 

A distinguishing feature of discrete fair division is its development of fairness notions that are applicable in the context of indivisible goods. A focus on relaxations is necessitated by the fact that existential guarantees, under classic fairness notions, are scarce in the context of indivisible goods. In particular, the fundamental fairness criterion of envy-freeness---which requires that each agent values the bundle assigned to her over that of any other agent---cannot be guaranteed in the indivisible-goods setting; consider the simple example of a single indivisible good and multiple agents. Interestingy, such pathology can be addressed by considering a natural relaxation: prior works have shown that, among agents with monotone valuations, there necessarily exists an allocation in which envy towards any agent can be resolved by the removal of a good \cite{LMMS042,Budish2011TheCA}.

More generally, recent research in discrete fair division has addressed existential and algorithmic questions related to the notion of envy-freeness up to $k$ goods ({\sf EFk}); see, e.g., the survey \cite{suksompong2021constraints} and references therein. In an ${\sf EFk}$ allocation, each agent prefers its own bundle over that of any other agent, up to the removal of $k$ goods from the other agent's bundle. A mature understanding has been developed in recent years specifically for allocations that are envy-free up to one good (${\sf EF1}$), e.g., it is known that, under additive valuations, Pareto efficiency can be achieved in conjunction with ${\sf EF1}$ \cite{caragiannis2019unreasonable,barman2018finding}. 

However, most works on ${\sf EF1}$, and further relaxations, assume that all possible assignments of the indivisible goods (among the agents) are feasible. On the other hand, combinatorial constraints are an unavoidable requirement in many resource-allocation settings. As an illustrative example to highlight the significance of constraints in discrete fair division settings, consider a curator tasked with fairly partitioning  artwork among different museums (i.e., among different agents).\footnote{This stylized example is adapted from \cite{gourves2014near}} Each artifact (indivisible good) has an associated value and a space requirement (depending on its size). Note that the artifacts assigned to a particular museum must fit within its premises and, hence, in this setting not all allocations are feasible. Indeed, here the curator needs to identify a partition of the artifacts that is not only fair but also feasible with respect to the museums' space constraints. The current work addresses an abstraction of this problem. 

A bit more formally, we study the fair allocation of $m$ indivisible goods among $n$ agents with identical, additive valuations but individual budget constraints. Here, each good $g \in [m]$ has a size $s(g) \in \mathbb{Q}_+$ and value $v(g) \in \mathbb{Q}_+$, and the goods need to be partitioned such that bundle assigned to each agent $a \in [n]$ is of total size at most the agent's budget $B_a \in \mathbb{Q}_+$. Note that in this setting with constraints, one might not be able to assign all the $m$ goods among the $n$ agents. Specifically, consider a case wherein the total size of all the goods $s([m]) > \sum_{a=1}^n B_a$. To account for goods that might remain unallocated, we utilize the construct of \emph{charity}. This idea has been used in multiple prior works; see, e.g., \cite{wu2021budget,chaudhury2021little}. The subset of goods that are not assigned to any of the $n$ agents are, by default, given to the charity.

In this framework, we consider envy-freeness up to $k$ goods ({\sf EFk}) while respecting the budget constraints. Recall that in the current model, the agents have identical, additive valuations, i.e., for any agent $a \in [n]$ the value of any subset of goods $S \subseteq [m]$ is the sum of values of the goods in it, $v(S) \coloneqq \sum_{g \in S} v(g)$. Also, we say that---for an agent $a \in [n]$ with assigned bundle $A_a \subseteq [m]$---${\sf EFk}$ holds against a subset $F$ iff the value of the assigned bundle, $v(A_a)$, is at least as much as the value of $F$, up to the removal of $k$ goods from $F$. Overall, an allocation $A_1, A_2, \ldots A_n$ (in which agent $a \in [n]$ receives subset $A_a$) is deemed to be ${\sf EFk}$ iff, for each pair of agents $a, b \in [n]$ and every subset $F \subseteq A_b$ of size at most $B_a$, the ${\sf EFk}$ guarantee holds for agent $a$ against subset $F$. That is, while evaluating envy from agent $a$ towards agent $b$, we consider, within $A_b$, all subsets of size at most $a$'s budget $B_a$.

The fair-division model with budget constraints was proposed by Wu et al.~\cite{wu2021budget}. Addressing agents with distinct, additive valuations, Wu et al.~\cite{wu2021budget} show that an allocation that satisfies the budget constraints and maximizes the Nash Social Welfare is $1/4$-approximately ${\sf EF1}$. A manuscript by Gan et al.~\cite{gan2021approximately} improves this guarantee to $1/2$-approximately ${\sf EF1}$ for agents with identical, additive valuations. In addition, Gan et al.~\cite{gan2021approximately} show that if all the agents have the same budget and in the case of two agents, an ${\sf EF1}$ allocation can be computed efficiently. However, for a general number of agents with distinct budgets, the computation (or even existence) of \emph{exact} ${\sf EFk}$ allocations remained an intriguing open problem.  \\

\noindent 
{\bf Our Results and Techniques.}
We make notable progress towards this open question by proposing a simple, greedy, polynomial-time algorithm that computes ${\sf EF2}$ allocations under budget constraints (Theorem \ref{thm:densestgreedy-ef2}). Our algorithmic result  implies the universal existence of ${\sf EF2}$ allocations in this fair division context. The same algorithm also provides ${\sf EF1}$ guarantees for important special cases. Specifically, we settle the existence of ${\sf EF1}$ allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all goods have the same size, or (iii) all the goods have the same value; see Theorems \ref{thm:unit-density-ef1}, \ref{thm:unit-size-ef1}, and \ref{theorem:cardinality}. That is, we prove that, if the densities, values, or sizes of the goods are homogeneous, then an ${\sf EF1}$ allocation is guaranteed to exist. Furthermore, our ${\sf EF2}$ result even extends to the setting wherein the goods' sizes are agent specific (see Theorem \ref{thm:densestgreedy-ef2_gap} in Appendix \ref{appendix:mini-GAP}).

Our algorithm (Algorithm \ref{algo:dense}) allocates goods in decreasing order of density,\footnote{The density of a good $g$ is defined to be its value-by-size ratio, $v(g)/s(g)$.} while maintaining the budget constraints. It is relevant to note that, while the design of the algorithm is simple, its analysis rests on  intricate structural properties of envy-freeness under budget constraints. We obtain the ${\sf EF2}$ and ${\sf EF1}$ guarantees using ideas that are notably different for the ones used in the unconstrained settings; in particular, different from analysis of the envy-cycle-elimination method or the round-robin algorithm \cite{aziz2022algorithmic}. 

Complementing the robustness of the algorithm, we also provide an example that shows that the greedy algorithm might not find an ${\sf EF1}$ allocation, i.e., the ${\sf EF2}$ guarantee is tight (Section \ref{section:tightness}).  \\

\noindent
{\bf The Knapsack Problem.}
The budget constraints, as considered in this work, are the defining feature of the classic knapsack problem. The knapsack problem and its numerous variants have been extensively studied in combinatorial optimization, approximation and online algorithms \cite{martello1990knapsack, knapbook, albers2021improved}. The knapsack problem finds many applications in practice \cite{skiena1999interested}. Recall that the objective in the knapsack problem is to find a subset with maximum possible value, subject to a single budget constraint. That is, the goal in the standard knapsack problem is utilitarian and not concerned with fairness.   

Algorithmic aspects of the special cases considered in the current paper have been addressed in prior works: (i) knapsack instances in which the value of each good is proportional to its size are known as proportional instances~\cite{cygan2016online} or subset-sum instances~\cite{pisinger2005hard}, (ii) instances where all the goods have the same value are referred to as cardinality \cite{galvez2021approximating, Galvez00RW21, K0001MSW21} or unit \cite{cygan2016online} instances. In addition, we also study the special case wherein all the goods have the same size. 

Proportional and cardinality versions of the knapsack problem are known to be technically challenging by themselves. In particular, in the context of online algorithms it is known that there does not exist a deterministic algorithm with bounded competitive ratio for these two versions \cite{lueker1998average, marchetti1995stochastic}. 

The knapsack problem has also been studied from the perspective of group fairness \cite{Patel0L21} and fairness in aggregating voters' preferences \cite{FluschnikSTW19}. In these works, there is only one knapsack and the single, selected subset of goods induces (possibly distinct) valuations among the agents. By contrast, the current work addresses multiple knapsacks, one for each agent. \\

\noindent{\bf Generalized Assignment Problem (GAP).} We also address instances in which the goods' sizes are agent specific. While such instances constitute a generalization of the formulation considered in the rest of the paper, they themselves are a special case of GAP \cite{shmoys1993approximation}. GAP consists of goods both whose sizes and values are agent specific. For GAP, it is known that value maximization is {\rm APX}-hard. In fact, even with common values and agent-specific sizes, the value-maximization objective does \emph{not} admit a polynomial-time approximation scheme \cite{chekuri2005polynomial}. \\  

\noindent
{\bf Additional Related Work.}
As mentioned previously, ${\sf EFk}$ allocations have been studied in various discrete fair division contexts~\cite{suksompong2021constraints}. In particular, Bil{\`o} et al.~\cite{bilo2022almost} consider settings in which the indivisible goods correspond to vertices of a given graph $G$ and each agent must receive a connected subgraph of $G$. It is shown in \cite{bilo2022almost} that if the graph $G$ is a path, then, under the connectivity constraint, an ${\sf EF2}$ allocation is guaranteed to exist. Under connectivity constraints imposed by general graphs $G$, Bei et al.~\cite{bei2022price} characterize the smallest $k$ for which an ${\sf EFk}$ allocation necessarily exists among two agents (i.e., this result addresses the $n=2$ case). We also note that exact ${\sf EFk}$ guarantees are incomparable with multiplicative approximations, as obtained in \cite{wu2021budget}.  

The current work focusses on settings in which the agents have an identical (additive) valuation over the goods. We note that, in the context of budget constraints, identical valuations already provide a technically-rich model. Fair division with identical valuations has been studied in multiple prior works; see, e.g.,~\cite{plaut2020almost,barman2021uniform}. Indeed, in many application domains each agent's cardinal preference corresponds to the monetary worth of the goods and, hence, in such setups the agents share a common valuation.

\section{Notation and Preliminaries}
We study the problem of fairly allocating a set of indivisible goods $[m] = \{1,2, \dots, m\}$ among a set of agents $[n] = \{1,2, \dots, n \}$ with budget constraints.
In the setup, every good $g \in [m]$ has a size $s(g) \in \mathbb{Q}_+$ and a value $v(g) \in \mathbb{Q}_+$. The density of any good $g \in [m]$ will be denoted as $\rho(g) \coloneqq v(g)/s(g)$. Furthermore, every agent $a \in [n]$ has an associated budget $B_a \in \mathbb{Q}_+$ that specifies an upper bound on the cumulative size of the set of goods that agent $a$ can receive. We conform to the framework wherein the valuations and sizes of the goods are additive; in particular, for any subset of goods $S \subseteq [m]$, we write the value $v(S) \coloneqq  \sum_{g \in S} v(g)$ and the size $s(S) \coloneqq  \sum_{g \in S} s(g)$. Hence, in this setup, a subset $S \subseteq [m]$ can be assigned to agent $a \in [n]$ only if $s(S) \leq B_a$, and the subset has value $v(S)$ for the agent. An instance of the fair division problem with budget constraints is specified as a tuple $\langle [m], [n], \{ v(g) \}_{g\in [m]}, \{s(g)\}_{g \in [m]}, \{B_a\}_{a\in [n]} \rangle$. 

Note that in fair division settings with constraints, one might not be able to assign all the $m$ goods among the $n$ agents. Specifically, consider a setting wherein $s([m]) > \sum_{a=1}^n B_a$. To account for goods that might remain unallocated, we utilize the construct of \emph{charity}. We will unify charity with the assigned subsets of goods by introducing a `fictional' agent, which we will refer to as the charity agent and use index $n+1$ for this agent. The goods that are not assigned to any of the $n$ agents are, by default, given to the charity agent. The charity agent is defined to have an infinite budget, $B_{n+1} = \infty$, and, hence, any subset of goods can be assigned to it, while trivially maintaining its budget constraint. Such a treatment of charity will aid in the design and the analysis of the algorithm. Also, fairness guarantees obtained while considering charity agent, $n+1$, as just another agent will continue to hold for the underlying instance (with $n$ agents).

An allocation $\mathcal{A} = (A_1, A_2, \ldots, A_n, A_{n+1})$ refers to an $(n+1)$-partition of the goods $[m]$, where $A_a$ is the subset of goods assigned to agent $a \in [n+1]$.
Throughout, we will maintain allocations $\mathcal{A} = (A_1, A_2, \ldots, A_n, A_{n+1})$ that are feasible, i.e., satisfy the budget constraints of all the agents, $s(A_a) \leq B_a$ for all agent $a \in [n+1]$. 

The notions of fairness studied in this work are defined next. An allocation $\mathcal{A} = (A_1, A_2, \ldots, A_n, A_{n+1})$ is said to be \emph{envy-free up to one good} (${\sf EF1}$) iff for all agents $a, b \in [n+1]$ and every subset $F \subseteq A_b$, with $s(F) \leq B_a$ (and $|F| \geq 1$), there exists a good $f \in F$ such that $v(A_a) \geq v(F \setminus \{f\})$.  Analogously, we define ${\sf EF2}$:

\begin{definition}[${\sf EF2}$]
\label{defn:eftwo}
An allocation $\mathcal{A} = (A_1, A_2, \ldots, A_n, A_{n+1})$ is said to be {envy-free up to two goods} (${\sf EF2}$) iff for all agents $a, b \in [n+1]$ and every subset $F \subseteq A_b$, with $s(F) \leq B_a$ (and $|F| \geq 2$), there exist two goods $f, f' \in F$ such that $v(A_a) \geq v(F \setminus \{f,f'\})$.
\end{definition}
Note that here the definitions of ${\sf EF1}$ and ${\sf EF2}$ consider the charity agent $n+1$ as well and, hence, envy against the charity set ($A_{n+1}$) is also addressed.

Throughout, we will assume that the goods have distinct densities -- this assumption holds without loss of generality and can be enforced by perturbing the densities (and appropriately the values) by sufficiently small amounts (see Appendix \ref{appendix:distinct-densities}). The assumption ensures that, in any nonempty subset $S \subseteq [m]$, the good with the maximum density ${\argmax_{g \in S} \ \rho(g)}$ is uniquely defined. Also, indexing the goods, in any subset $S =\{g_1, g_2, \ldots, g_k \}$, in decreasing order of density results in a unique ordering with $\rho(g_1) > \rho(g_2) > \ldots > \rho(g_k)$. For any subset $S \subseteq [m]$ and good $g \in [m]$, we will use the shorthands $S + g \coloneqq S \cup \{g \}$ and $S - g \coloneqq S \setminus \{g\}$. 

\subsection{Fair Division in Proportional Instances}
\label{section:efone-proportional-instances}

This section shows that, if all the goods have the same density, then an ${\sf EF1}$ allocation can be computed in polynomial time. 
While in the rest of the paper we assume that the goods have distinct densities, in this section we in fact address goods with exactly the same densities. We address this technical difference, by simply including any consistent tie breaking rule in Algorithm \ref{algo:dense}. That is, for proportional instances, the $\mathtt{DensestGreedy}$ algorithm applies a tie breaking rule (e.g., lowest index first) while selecting among the unallocated goods in Line \ref{line:assign-good}. With this minor modification, all the previously established results (specifically, Lemma \ref{lemma}) continue to hold for proportional instances. Next, we establish the ${\sf EF1}$ guarantee for proportional instances.  

\begin{theorem}
\label{thm:unit-density-ef1}
For any given budget-constrained fair division instance $\langle [m], [n], \{ v(g) \}_{g}, \{s(g)\}_{g}, \{B_a\}_{a} \rangle$ in which all the goods have the same density (i.e., ${v(g)}/{s(g)} = {v(g')}/{s(g')}$ for all $g, g' \in [m]$), Algorithm \ref{algo:dense} ($\mathtt{DensestGreedy}$) computes an ${\sf EF1}$ allocation in polynomial time.
\end{theorem}
\begin{proof}
We use the constructs defined in Sections \ref{section:structural-props} and \ref{section:proof-of-main-theorem}. In particular, for any two agents $a, b \in [n+1]$, let $X$ and $Y$ denote the
set of goods allocated to the two agents, respectively, at the end of Algorithm \ref{algo:dense}. Consider any subset $Z \subseteq Y$, with size $s(Z) \leq B_a$ (and $|Z| \geq 2$). By way of contradiction,
we will show that ${\sf EFCount}(X,Z) \leq 1$ and, hence, obtain the stated ${\sf EF1}$ guarantee.


Assume, towards a contradiction, that ${\sf EFCount}(X,Z) \geq 2$. In such a case, the constructs (specifically, $t$, $\tau$, $\widehat{\tau}$, and the good $g_{Z}$) considered in Sections \ref{section:structural-props} and \ref{section:proof-of-main-theorem} are well-defined. Using the previously-established properties of these constructs, we will show that there necessarily exists
a good $g \in Z$ such that $v(X) \geq v(Z - g)$. Hence, by contradiction, we will get that ${\sf EFCount}(X, Z) <2$, i.e., ${\sf EF1}$ holds between $X$ and $Z$. 

We first note that the size of the set $X$ is at least $\tau$. This follows from inequality (\ref{ineq:sizelb}), which gives us $s\left(\Size{X}{\gamma} \setminus \Size{X}{\tau}\right)  > 0$ and, hence, we have  $s(X) - \tau \geq s\left(\Size{X}{\gamma}\right) - \tau > 0$. This lower bound on the size of $X$ implies that the prefix subset $\Size{X}{\tau}$ has size exactly equal to $\tau$. 
In addition, $s(\Size{Z}{\tau}) = \tau$. Now, given that all the goods have the same density, we obtain
\begin{align}
v(\Size{X}{\tau}) = v(\Size{Z}{\tau}) \label{ineq:valxtau-ztau}
\end{align}
Therefore, 
\begin{align*}
v(X) &= v\left(\Size X \tau\right) + v\left(X \backslash \Size X \tau\right) \\
         &= \  v\left(\Size Z \tau\right) + v\left(X \backslash \Size X \tau\right) \tag{via equation (\ref{ineq:valxtau-ztau})}\\
         &\geq  v\left(\Size Z \tau\right) + v\left(Z \backslash \Size Z \widehat{\tau} \right) \tag{via Lemma \ref{lemma}} \\
        &=  v\left(\Size Z \tau\right) + v\left(Z \backslash \Size Z \tau\right) - v(g_{Z}) \tag{since $\Size{Z}{\widehat{\tau}} \setminus \Size{Z}{\tau} = \{g_{Z}\}$} \\
         &\geq  v(Z - g_{Z}) 
\end{align*}
Hence, we obtain that ${\sf EFCount}(X,Z)\le 1$, which is a contradiction. This establishes the theorem.
\end{proof}

\subsection{Fair Division {of Equal-Sized Goods}}
This section shows that the $\mathtt{DensestGreedy}$ algorithm finds ${\sf EF1}$ allocations for
instances in which all the goods have equal sizes.\footnote{As in the general case, the values of the goods can be distinct. Here, we also retain the assumption that all the goods have distinct densities.}

\begin{theorem}
\label{thm:unit-size-ef1}
For any given budget-constrained fair division instance $\langle [m], [n], \{ v(g) \}_{g}, \{s(g)\}_{g}, \{B_a\}_{a} \rangle$ in which all the goods have the same size (i.e., $s(g) = s(g')$ for all $g, g' \in [m]$), Algorithm \ref{algo:dense} ($\mathtt{DensestGreedy}$) computes an ${\sf EF1}$ allocation in polynomial time.
\end{theorem}
\begin{proof}
For instances in which that goods have the same size, ordering the goods in decreasing order of densities is equivalent to ordering them in decreasing order of values. Hence, the $\mathtt{DensestGreedy}$ algorithm allocates the goods in decreasing order of value, while considering the budget constraints. Also, write $\beta$ to denote the common size of the goods and note that, in the current context, for any subset of goods $S \subseteq [m]$, we have $s(S)  = \beta \abs{S}$. 

To establish the ${\sf EF1}$ guarantee, consider any two agents $a,b \in [n+1]$ with budgets $B_a$ and $B_b$, respectively. Also, let $X$ and $Y$, respectively, be the subsets assigned to these agents by the algorithm. We will prove that for any subset of goods $Z \subseteq Y$, with $s(Z) \leq B_a$, we have ${\sf EFCount}(X,Z) \leq 1$. Towards this, we consider the following two complementary and exhaustive cases \\
\noindent
Case {\sf 1}:  $\abs X \leq \abs{Z}-1$. \\
\noindent
Case {\sf 2}: $\abs X \geq \abs{Z}$. \\

\noindent
Case {\sf 1}: $\abs X \leq \abs{Z}-1$. Write $Y=\{y_1,y_2,\dots,y_{\ell}\}$ to denote the goods in set $Y$, indexed in decreasing order of densities. Furthermore, let $y_{\ell'}$ denote the good in $Z$ with minimum density. Equivalently, for the instance in hand, $y_{\ell'}$ is the minimum valued good in $Z \subseteq Y$. Also, note that $v(Z -y_{\ell'} ) \leq v \left(\Goods{Y}{\ell'-1} \right)$. 

Recall that $\beta$ denotes the size of each good. In the current case, we have $\abs X\le\abs{Z}-1$ and, hence, $s(X)\le s(Z)-\beta \le B_a-\beta=B_a-s\left(y_{\ell'}\right)$. That is, $s\left(X+y_{\ell'}\right)\le B_a$. Now, using Proposition \ref{greedyproperty-full}, we obtain $v(X)\gev\left(\Goods{Y}{\ell'-1}\right)\gev\left(Z-y_{\ell'}\right)$.
This shows that ${\sf EFCount}(X,Z)\le 1$. \\

\noindent
Case {\sf 2}: $\abs X \geq \abs{Z}$. Here, we will consider prefix subsets $\Goods{X}{i}$ and
$\Goods{Z}{i}$ for all $i \in \{1,2,\ldots, |Z|\}$ and establish, via induction over $i$,
that ${\sf EFCount}\left(\Goods{X}{i},\Goods{Z}{i}\right) \leq 1$.
This bound (with $i = |Z|$) gives us the ${\sf EF1}$ guarantee.

For the base case, $i=1$, the stated bound ${\sf EFCount}\left(\Goods{X}{i},\Goods{Z}{i}\right) \leq 1$ holds directly,
since $\abs{\Goods{Z}{1}}=1$. Now, for the induction step, assume that for an index $i \in \{2, 3, \ldots, \abs{Z}\}$, the envy count satisfies ${\sf EFCount}\left(\Goods{X}{i-1},\Goods{Z}{i-1}\right) \leq 1$.

Write $T \coloneqq s(\Goods Z {i-1})$ and $\widehat{\structlb} \coloneqq s(\Goods Z i)$. Since all the goods have the same size $\beta$,  we have $T = (i-1) \beta$ and
$\widehat{\structlb} = i \beta$. Furthermore, note that $\Goods{X}{i-1} = \Size{X}{T}$ and $\Goods{X}{i} = \Size{X}{\widehat{\structlb}}$. Therefore, the desired inequality ${\sf EFCount}(\Goods{X}{i},\Goods{Z}{i}) \leq 1$ is equivalent to ${\sf EFCount}\left(\Size X \widehat{\structlb}, \Size Z \widehat{\structlb}\right) \leq 1$.

By the induction hypothesis, we have
${\sf EFCount}\left(\Goods{X}{i-1},\Goods{Z}{i-1}\right) \leq 1$, i.e.,
${\sf EFCount}\left(\Size X T, \Size Z T\right) \leq 1$.
First, we note that if ${\sf EFCount}\left(\Size X T, \Size Z T\right) = 0$,
the induction step follows from Lemma \ref{lemma:lipschitz}:
\begin{align*}
    {\sf EFCount}\left(\Size X \widehat{\structlb}, \Size Z \widehat{\structlb}\right)
    \leq {\sf EFCount}\left(\Size X T, \Size Z T\right) + 1 = 1.
\end{align*}
In the complementary case, wherein ${\sf EFCount}\left(\Size X T, \Size Z T\right) = 1$,
we have $v\left(\Size X T\right) < v\left( \Size Z T\right)$.
Write $x_i$ and $z_i$ to, respectively, denote the $i^{\mathrm{th}}$ good (indexed in decreasing order of densities)
in the sets $X$ and $Z$. Since all the goods are of size $\beta$, we have
$s\left(\Size X T\right) + s(z_i) = T + s(z_i) = (i-1)  \beta + \beta = \widehat{\structlb} \leq s(Z) \leq B_a$.
That is, good $z_i$ can be included in $\Size X T$ while maintaining agent $a$'s budget constraint.
Using this observation along with the inequality $v(\Size X T) < v( \Size Z T)$
and Proposition \ref{greedyproperty}, we get $\rho(x_i) \geq \rho(z_i)$. This inequality reduces to $v(x_i) \geq v(z_i)$, since the goods have the same size. Furthermore, note that
$\Size X \widehat{\structlb} = \Size X T \cup \{x_i\}$ and $\Size Z \widehat{\structlb} = \Size Z T \cup \{z_i\}$. Hence, using $v(x_i)\gev(z_i)$, we obtain
\begin{align*}
    {\sf EFCount}\left(\Size X \widehat{\structlb}, \Size Z \widehat{\structlb}\right)
    \leq {\sf EFCount}\left(\Size X T, \Size Z T\right) = 1.
\end{align*}
Therefore, for all $1\leq i \leq |Z|$, we have  ${\sf EFCount}(\Goods{X}{i},\Goods{Z}{i}) \leq 1$ and,
in particular, ${\sf EFCount}(X, Z) \leq 1$. This gives use the stated ${\sf EF1}$ guarantee and completes the proof.
\end{proof}

\subsection{Fair Division in Cardinality Instances}
This section establishes the existence of ${\sf EF1}$ allocations in instances wherein each good has the same value.\footnote{As in the general case, the goods can have different sizes.} Note that, in such a setup, the densest good is the one with the smallest size. 
We establish the following theorem for cardinality instances. 

\begin{theorem} \label{theorem:cardinality}
For any given budget-constrained fair division instance $\langle [m], [n], \{ v(g) \}_{g}, \{s(g)\}_{g}, \{B_a\}_{a} \rangle$ in which all the goods have the same value (i.e., $v(g) = v(g')$ for all $g, g' \in [m]$), Algorithm \ref{algo:dense} ($\mathtt{DensestGreedy}$) computes an ${\sf EF1}$ allocation in polynomial time.
\end{theorem}

Before proving Theorem \ref{theorem:cardinality}, we provide useful properties of the allocation returned by Algorithm \ref{algo:dense} for cardinality instances. First, note that the goods are allocated in the increasing order of their sizes, i.e., if goods $g_1$ and $g_2$ were, respectively, allocated in iterations $t_1$ and $t_2$ of the while-loop, with $t_1 < t_2$, then $s(g_1) \leq s(g_2)$. {This inequality holds even among goods $g_1$ and $g_2$ that are allocated to different agents.} The following lemma provides another observation on the sizes of the allocated subsets.   

\begin{lemma} \label{round-robin_size}
For any two agents $a, b \in [n+1]$ and any index $i \leq \min\{ |A_a|, |A_b|-1\}$, we have $s(A_a^{(i)}) \leq s(A_b^{(i+1)})$.
\end{lemma}
\begin{proof}
For agents $a, b \in [n+1]$ and any index $j \leq \min \{ |A_a|, |A_b|-1\}$, write $g_a^j$ to denote the  $j^{th}$ densest good in $A_a$ and  $g_b^{j+1}$ to denote the $(j+1)^{\mathrm{th}}$ densest good in  $A_b$. Also, let $\nu$ denote the common value of the goods. In this cardinality case, any agent's value after receiving $\ell$ goods is $\ell \nu$. Hence, agent $a$ is assigned good $g_a^j$ before (i.e., in an earlier iteration) agent $b$ is assigned good $g_b^{j+1}$. As mentioned previously, the goods are assigned in increasing order of size. Hence, for each $j \leq \min \{ |A_a|, |A_b|-1\}$, we have  
\begin{align}
s(g_a^j) \leq s(g_b^{j+1}) \label{ineq:goods-size}
\end{align}
Furthermore, consider index $i \leq \min\{ |A_a|, |A_b|-1\}$. Summing inequality (\ref{ineq:goods-size}) over $j \in \{1, 2, \ldots, i\}$, we obtain $s(A_a^{(i)}) \leq s(A_b ^{(i+1)})$. This proves the  lemma.
\end{proof}

We now establish Theorem \ref{theorem:cardinality}. 

\begin{proof}[Proof of Theorem \ref{theorem:cardinality}]
Consider any two agents $a, b \in [n+1]$, with respective budgets $B_a$ and $B_b$. Let $A_a$ and $A_b$ be the subsets of the goods assigned to these two agents, respectively,  by Algorithm \ref{algo:dense}. We will show that the ${\sf EF1}$ guarantee holds from agent $a$ towards agent $b$, i.e., holds between $A_a$ and $A_b$. 

Write $\nu$ to denote the common value of the goods, and note that $v(A_a)  = \nu |A_a|$ and $v(A_b) = \nu |A_b|$. Hence, if $|A_a| \geq |A_b|$, then agent $a$ does not envy agent $b$ and the ${\sf EF1}$ guarantee holds. 

Therefore, for the rest of the proof we will consider the case $|A_a| < |A_b|$. Let $F$ be any subset of $A_b$, with size $s(F) \leq B_a$. We will prove that $|F| \leq |A_a| + 1$. Since all the goods have the same value $\nu$, this cardinality bound implies ${\sf EFCount}(A_a, F) \leq 1$ and gives us the desired ${\sf EF1}$ guarantee. 

Assume, towards a contradiction, that $|F| \geq |A_a| + 2$ and let $f$ be the $(|A_a| + 2)^{\mathrm{th}}$-densest good in $F$. We will show that the existence of good $f$ contradicts Proposition \ref{greedyproperty-full} and, hence, complete the proof. In the current case, we have $|A_a| < |A_b|$ and, hence, invoking Lemma \ref{round-robin_size} with index $i = |A_a|$, we obtain  
\begin{align}
s(A_a)  \leq s(A_b^{(|A_a| + 1)}) \label{ineq:tm}
\end{align}
As mentioned previously, for cardinality instances, the goods are assigned in increasing order of size. Furthermore, increasing order of densities corresponds to decreasing order of sizes. Hence, the $(|A_a| + 1)$ most densest goods in $A_b$---i.e., the goods that constitute $A_b^{(|A_a|+1)}$---are in fact the ones with the smallest sizes. Hence, $s(A_b^{(|A_a| + 1)}) \leq s(F^{(|A_a| + 1)})$. This bound and inequality (\ref{ineq:tm})  give us 
\begin{align*}
s(A_a) +  s(f) &\leq s(A_b^{(|A_a| + 1)}) + s(f) \\
&\leq s(F^{(|A_a| + 1)}) + s(f) \\ 
&\leq B_a.
\end{align*} 
By definition, $f$ is the $(|A_a| + 2)^{\mathrm{th}}$ densest good in $F$. Hence, for some index $j \geq |A_a| +1$, good $f$ is the $(j+1)^{\mathrm{th}}$ densest good in $A_b \supseteq F$. With this index $j$ in hand (i.e., with $h_{j+1} = f$), we invoke Proposition \ref{greedyproperty-full} to obtain $v(A_a) \geq v(A_b^{(j)})$. Since the value of each good is $\nu$, the last inequality reduces to $\nu |A_a|  \geq j \nu$. This bound, however, contradicts the fact that $j \geq |A_a| +1$. Hence, it must be the case that $|F| \leq |A_a| +1$. As mentioned previously, this cardinality bound implies ${\sf EFCount}(A_a, F) \leq 1$ and gives us the desired ${\sf EF1}$ guarantee. The theorem stands proved. 
\end{proof}
\subsection{Tightness of the Analysis}
\label{section:tightness}
In this section we provide an example for which Algorithm \ref{algo:dense} does not find an ${\sf EF1}$ allocation. This shows that  the ${\sf EF2}$ guarantee obtained for the algorithm (in Theorem \ref{thm:densestgreedy-ef2}) is tight. 


We consider an instance with two agents and three indivisible goods, i.e., $n = 2$ and $m = 3$. Both the agents have a budget of one, $B_1 = B_2 = 1$. We set the sizes and values of the three goods as shown in the following table; here $\varepsilon \in (0,1/2)$ is an arbitrarily small parameter.  

\begin{center}
\begin{tabular}{|c|c|c|} 
 \hline
 Good & Size & Value \\ [0.5ex] 
\hline
$g_1$ & $\varepsilon$ & $10$ \\ 
 \hline
$g_2$ & $0.5$ & $0.5$ \\
 \hline
$g_3$ & $1- \varepsilon$ & $1 - 2\varepsilon$ \\ [1ex] 
\hline
\end{tabular}
\end{center}

The densities of the goods satisfy $\rho(g_1) > \rho(g_2) > \rho(g_3)$. Also, note that Algorithm \ref{algo:dense} returns the allocation with $A_1 = \{g_1, g_3\}$ and $A_2 = \{g_2\}$.  Since $v(g_1) > v(g_2)$ and $v(g_3) > v(g_2)$, the retuned allocation is not ${\sf EF1}$. 