Welfare maximization and the supermodular degree
Uriel Feige, Rani Izsak · 2013
Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items, the welfare maximization problem requires that every item be allocated to exactly one player, and one wishes to maximize the sum of values obtained by the players, as computed by applying the respective valuation function to the bundle of items allocated to the player. This problem in its full generality is NP-hard, and moreover, at least as hard to approximate as set-packing. Better approximation guarantees are known for restricted classes of valuation functions.