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 N P-hard, and moreover, at least as hard to approximate as set-packing. Better approximation guarantees are known for restricted classes of valuation functions. In this work we introduce a new parameter, the supermodular degree of a valuation function, which is a measure for the extent to which the function exhibits supermodular behavior. We design an approximation algorithm for the welfare maximization problem whose approximation guarantee is linear in the supermodular degree of the underlying valuation functions.
Feige and Izsak REF introduced a hierarchy of monotone set functions, parameterized by the so-called supermodular degree.
Welfare maximization and the supermodular degree
ITCS '13
Mathematics Computer Science