Eliminating Envy in Multigraphs Through Subsidy

摘要

Envy-free (EF) allocation is a fundamental problem at the intersection of theoretical computer science and economics. When resources are indivisible, achieving an EF allocation is often impossible. A common remedy is to compensate agents with subsidies. Brustle et al. proved that a total subsidy of n-1 is both necessary and sufficient to guarantee EF in the worst case, where n is the number of agents and each agent has additive valuations with marginal values of at most 1 per item. In this paper, we consider a constrained setting, namely graph orientation, that was recently introduced by Christodoulou et al. In this model, agents correspond to vertices in a multigraph, and resources correspond to edges, with each edge allocated to one of its two incident agents. Despite extensive study of the graph orientation model, it remains unclear how much subsidy is sufficient to guarantee EF. We show that a total subsidy of n/2 is always sufficient to guarantee EF in any multigraph, halving the subsidy required in the unconstrained setting, and provide a polynomial-time algorithm to compute such an allocation. We show that this bound is tight, even for simple graphs.