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.

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 problemwhose approximation guarantee is linear in the supermodular degree of the underlying valuation functions