A simple and approximately optimal mechanism for a buyer with complements

DOI10.1287/OPRE.2020.2039MaRDI QIDQ4994150zbMATH OpenOpenAlexFDO

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

Publication date 17 June 2021

Published in Operations Research (Search for Journal in Brave)

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)

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.

Recommendations

• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Approximate revenue maximization with multiple items
• An optimal auction for complements
• On revenue maximization for selling multiple independently distributed items
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer

Cites work

• scientific article; zbMATH DE number 2020165 (Why is no real title available?)
• A duality based unified approach to Bayesian mechanism design
• An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications
• An optimal auction for complements
• Approximate revenue maximization with multiple items
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Assignment problems with complementarities
• Bayesian incentive compatibility via fractional assignments
• Bayesian incentive compatibility via matchings
• Building a good team: secretary problems and the supermodular degree
• Combinatorial auctions via posted prices
• Constrained monotone function maximization and the supermodular degree
• Core-selecting package auctions
• Haggling over substitutes
• Ironing, Sweeping, and Multidimensional Screening
• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Maximal revenue with multiple goods: Nonmonotonicity and other observations
• Multi-parameter mechanism design and sequential posted pricing
• On maximizing welfare when utility functions are subadditive
• On revenue maximization for selling multiple independently distributed items
• Optimal Auction Design
• Optimal mechanism for selling two goods
• Package Auctions and Exchanges
• Pricing lotteries
• Revenue maximization for selling multiple correlated items
• Sampling and Representation Complexity of Revenue Maximization
• Simple mechanisms for subadditive buyers via duality
• Simultaneous auctions are (almost) efficient
• The communication requirements of efficient allocations and supporting prices
• The complexity of optimal mechanism design
• The power of randomness in Bayesian optimal mechanism design
• Truth revelation in approximately efficient combinatorial auctions
• Two Randomized Mechanisms for Combinatorial Auctions
• Welfare maximization and the supermodular degree

Cited in

(7)

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

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)