ECCC-Report TR14-103https://eccc.weizmann.ac.il/report/2014/103Comments and Revisions published for TR14-103en-usFri, 08 Aug 2014 18:52:32 +0300
Paper TR14-103
| A Unifying Hierarchy of Valuations with Complements and Substitutes |
Uriel Feige,
Michal Feldman,
Nicole Immorlica,
Rani Izsak,
Lucier Brendan,
Vasilis Syrgkanis
https://eccc.weizmann.ac.il/report/2014/103We 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.Fri, 08 Aug 2014 18:52:32 +0300https://eccc.weizmann.ac.il/report/2014/103