A Unifying Hierarchy of Valuations with Complements and Substitutes


  • Uriel Feige Weizmann Institute of Science
  • Michal Feldman Tel-Aviv University
  • Nicole Immorlica Microsoft Research
  • Rani Izsak Weizmann Institute of Science
  • Brendan Lucier Microsoft Research
  • Vasilis Syrgkanis Microsoft Research




Combinatorial Auctions, Complementarities, Welfare Maximization, Price of Anarchy, Hypergraph Valuations


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.




How to Cite

Feige, U., Feldman, M., Immorlica, N., Izsak, R., Lucier, B., & Syrgkanis, V. (2015). A Unifying Hierarchy of Valuations with Complements and Substitutes. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9314



AAAI Technical Track: Game Theory and Economic Paradigms