We introduce a new hierarchy over monotone set functions, that we refer to as MP H (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MP H - m (where m is the total number of items) captures all monotone functions. The lowest level, MP H - 1 , captures all monotone submodular functions, and more generally, the class of functions known as XO S . Every monotone function that has a positive hypergraph representation of rank k (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in MP H - k . Every monotone function that has supermodular degree k (in the sense defined by Feige and Izsak [ITCS 2013]) is in MP H - ( k + 1 ) . In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of MP H - k .

One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MP H hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k + 1 if all players hold valuation functions in MP H - k . The other is an upper bound of 2 k on the price of anarchy of simultaneous first price auctions.

Being in MP H - k can be shown to involve two requirements -- one is monotonicity and the other is a certain requirement that we refer to as PL E (Positive Lower Envelope). Removing the monotonicity requirement, one obtains the PL E hierarchy over all non-negative set functions (whether monotone or not), which can be fertile ground for further research.