A Simple and Approximately Optimal Mechanism for a Buyer with Complements

We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation v for the items may exhibit both substitutes (i.e., for some S,T, v(S∪T)<v(S)+v(T)) and complements (i.e., for some S,T, v(S∪T)>v(S)+v(T)). We show that the mechanism first proposed by Babaioff et al. [2014] – the better of selling the items separately and bundling them together – guarantees a Θ(d) fraction of the optimal revenue, where d is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity, and extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations.
Our proof is enabled by the recent duality framework developed in Cai et al. [2016], which we use to obtain a bound on the optimal revenue in this setting. Our main technical contributions are specialized to handle the intricacies of settings with complements, and include an algorithm for partitioning edges in a hypergraph. Even nailing down the right model and notion of “degree of complementarity” to obtain meaningful results is of interest, as the natural extensions of previous definitions provably fail.