Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-103 | 8th August 2014 17:44

A Unifying Hierarchy of Valuations with Complements and Substitutes


Authors: Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis
Publication: 8th August 2014 18:52
Downloads: 3026


We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).
Levels of the hierarchy correspond to the degree of complementarity in a given function.
The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all monotone functions. The lowest level, $MPH$-$1$, captures all monotone submodular functions, and more generally, the class of functions known as $XOS$. 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 $MPH$-$k$. Every monotone function that has supermodular degree $k$ (in the sense defined by Feige and Izsak [ITCS 2013]) is in $MPH$-$(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 $MPH$-$k$.

One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the $MPH$ 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 $MPH$-$k$.
The other is an upper bound of $2k$ on the price of anarchy of simultaneous first price auctions.

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

ISSN 1433-8092 | Imprint