2016/12/14 by Alon Eden, Michal Feldman, Eden, Alon +7 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1612.04746
openalex publication_date 2016/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a revenue-maximizing seller with m heterogeneous items and a\nsingle buyer whose valuation v for the items may exhibit both substitutes\n(i.e., for some S, T, v(S \∪ T) < v(S) + v(T)) and complements (i.e., for\nsome S, T, v(S \∪ T) > v(S) + v(T)). We show that the mechanism first\nproposed by Babaioff et al. [2014] - the better of selling the items separately\nand bundling them together - guarantees a \Θ(d) fraction of the optimal\nrevenue, where d is a measure on the degree of complementarity. Note that\nthis is the first approximately optimal mechanism for a buyer whose valuation\nexhibits any kind of complementarity, and extends the work of Rubinstein and\nWeinberg [2015], which proved that the same simple mechanisms achieve a\nconstant factor approximation when buyer valuations are subadditive, the most\ngeneral class of complement-free valuations.\n Our proof is enabled by the recent duality framework developed in Cai et al.\n[2016], which we use to obtain a bound on the optimal revenue in this setting.\nOur main technical contributions are specialized to handle the intricacies of\nsettings with complements, and include an algorithm for partitioning edges in a\nhypergraph. Even nailing down the right model and notion of "degree of\ncomplementarity" to obtain meaningful results is of interest, as the natural\nextensions of previous definitions provably fail.\n