A Simple and Approximately Optimal Mechanism for a Buyer with Complements

DOI10.1287/OPRE.2020.2039zbMATH Open1470.91071arXiv1612.04746OpenAlexW3111651183MaRDI QIDQ4994150FDOQ4994150

Inbal Talgam-Cohen, Michal Feldman, S. Matthew Weinberg, Ophir Friedler, Alon Eden

Publication date: 17 June 2021

Published in: Operations Research (Search for Journal in Brave)

Abstract: 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(ScupT)<v(S)+v(T)$) and complements (i.e., for some $S,T$, $v(ScupT)>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 $Theta(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.

Full work available at URL: https://arxiv.org/abs/1612.04746

zbMATH Keywords

approximationmechanism designcomplementsrevenue

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Mechanism design theory (91B03)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ironing, Sweeping, and Multidimensional Screening
• Haggling over substitutes
• Optimal Auction Design
• Core-selecting package auctions
• Multi-parameter mechanism design and sequential posted pricing
• Assignment problems with complementarities
• Truth revelation in approximately efficient combinatorial auctions
• The communication requirements of efficient allocations and supporting prices
• Maximal revenue with multiple goods: Nonmonotonicity and other observations
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• Simultaneous auctions are (almost) efficient
• An optimal auction for complements
• Approximate revenue maximization with multiple items
• Optimal mechanism for selling two goods
• Two Randomized Mechanisms for Combinatorial Auctions
• On revenue maximization for selling multiple independently distributed items
• An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
• The Complexity of Optimal Mechanism Design
• On Maximizing Welfare When Utility Functions Are Subadditive
• Pricing lotteries
• Package Auctions and Exchanges
• The power of randomness in Bayesian optimal mechanism design
• Simple mechanisms for subadditive buyers via duality
• A duality based unified approach to Bayesian mechanism design
• Combinatorial Auctions via Posted Prices
• Constrained Monotone Function Maximization and the Supermodular Degree
• Welfare maximization and the supermodular degree
• Revenue Maximization for Selling Multiple Correlated Items
• Sampling and Representation Complexity of Revenue Maximization
• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Building a Good Team: Secretary Problems and the Supermodular Degree

Cited In (6)

• Obvious strategyproofness, bounded rationality and approximation
• A note on the buyer's problem
• A Duality-Based Unified Approach to Bayesian Mechanism Design
• Risk-robust mechanism design for a prospect-theoretic buyer
• On symmetries in multi-dimensional mechanism design
• A Simple and Approximately Optimal Mechanism for an Additive Buyer

This page was built for publication: A Simple and Approximately Optimal Mechanism for a Buyer with Complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994150)