  In the budget-feasible allocation problem, a set of items with varied sizes
and values are to be allocated to a group of agents. Each agent has a budget
constraint on the total size of items she can receive. The goal is to compute a
feasible allocation that is envy-free (EF), in which the agents do not envy
each other for the items they receive, nor do they envy a charity, who is
endowed with all the unallocated items. Since EF allocations barely exist even
without budget constraints, we are interested in the relaxed notion of
envy-freeness up to one item (EF1). The computation of both exact and
approximate EF1 allocations remains largely open, despite a recent effort by Wu
et al. (IJCAI 2021) in showing that any budget-feasible allocation that
maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper,
we move one step forward by showing that for agents with identical additive
valuations, a 1/2-approximate EF1 allocation can be computed in polynomial
time. For the uniform-budget and two-agent cases, we propose efficient
algorithms for computing an exact EF1 allocation. We also consider the large
budget setting, i.e., when the item sizes are infinitesimal compared with the
agents' budgets, and show that both the NSW maximizing allocation and the
allocation our polynomial-time algorithm computes have an approximation close
to 1 regarding EF1.
