  We study the fair allocation of indivisible goods among agents with
identical, additive valuations but individual budget constraints. Here, the
indivisible goods--each with a specific size and value--need to be allocated
such that the bundle assigned to each agent is of total size at most the
agent's budget. Since envy-free allocations do not necessarily exist in the
indivisible goods context, compelling relaxations--in particular, the notion of
envy-freeness up to $k$ goods (EFk)--have received significant attention in
recent years. In an EFk allocation, each agent prefers its own bundle over that
of any other agent, up to the removal of $k$ goods, and the agents have
similarly bounded envy against the charity (which corresponds to the set of all
unallocated goods). Recently, Wu et al. (2021) showed that an allocation that
satisfies the budget constraints and maximizes the Nash social welfare is
$1/4$-approximately EF1. However, the computation (or even existence) of exact
EFk allocations remained an intriguing open problem.
  We make notable progress towards this by proposing a simple, greedy,
polynomial-time algorithm that computes EF2 allocations under budget
constraints. Our algorithmic result implies the universal existence of EF2
allocations in this fair division context. The analysis of the algorithm
exploits intricate structural properties of envy-freeness. Interestingly, the
same algorithm also provides EF1 guarantees for important special cases.
Specifically, we settle the existence of 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. Our EF2 result
extends to the setting wherein the goods' sizes are agent specific.
