Towards optimal subsidy bounds for envy-freeable allocations

We study the fair division of indivisible items with subsidies among n agents, where the absolute marginal valuation of each item is at most one. Under monotone nondecreasing valuations (where each item is a good), Brustle et al. [9] demonstrated that a maximum subsidy of 2 ( n − 1 ) and a total subsidy of 2 ( n − 1 ) 2 are sufficient to guarantee the existence of an envy-freeable allocation. In this paper, we improve upon these bounds, even in a wider model. Namely, we show that, given an EF1 allocation, we can compute in polynomial time an envy-free allocation with a subsidy of at most n − 1 per agent and a total subsidy of at most n ( n − 1 ) / 2 . Moreover, when the valuations are monotone nondecreasing, we provide a polynomial-time algorithm that computes an envy-free allocation with a subsidy of at most n − 1.5 per agent and a total subsidy of at most ( n 2 − n − 1 ) / 2 .