How to Decrease the Degree of Envy in Allocations of Indivisible Goods

摘要

We consider the problem of fairly distributing a number of indivisible goods among agents with additive utility functions. Among the common criteria of fairness, we focus on envy-freeness and its weaker notions. Instead of concentrating on envy-free allocations (which might not always exist), we seek to find an allocation with minimum envy. Based on a notion introduced by Chevaleyre et al. [7], we define several problems of minimizing the degree of envy and study their approximability.