Simple mechanisms for subadditive buyers via duality

DOI10.1145/3055399.3055465MaRDI QIDQ4977970zbMATH OpenOpenAlexFDO

Authors Yang Cai, Mingfei Zhao

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

dualityrevenuesimple and approximately optimal auctionssubaddtive valuations

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, we prove that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential posted price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentive Compatible mechanisms, when buyers' valuations are XOS over independent items. If the buyers' valuations are subadditive over independent items, the approximation factor degrades to $O(logm)$, where $m$ is the number of items. We obtain our results by first extending the Cai-Devanur-Weinberg duality framework to derive an effective benchmark of the optimal revenue for subadditive bidders, and then analyzing this upper bound with new techniques.

Recommendations

• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Budget-constrained auctions with heterogeneous items
• Multi-parameter mechanism design and sequential posted pricing
• Approximate revenue maximization with multiple items
• A Duality-Based Unified Approach to Bayesian Mechanism Design

Cited in

(26)

• scientific article; zbMATH DE number 7651221 (Why is no real title available?)
• Multi-Item Nontruthful Auctions Achieve Good Revenue
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications
• From pricing to prophets, and back!
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions
• A simple and approximately optimal mechanism for a buyer with complements
• A Duality-Based Unified Approach to Bayesian Mechanism Design
• Tight revenue gaps among simple mechanisms
• Risk-robust mechanism design for a prospect-theoretic buyer
• Buy-many mechanisms for many unit-demand buyers
• Bayesian auctions with efficient queries
• Optimal item pricing in online combinatorial auctions
• On symmetries in multi-dimensional mechanism design
• Welfare-preserving \(\varepsilon \)-BIC to BIC transformation with negligible revenue loss
• Buy-many mechanisms are not much better than item pricing
• On the approximability of simple mechanisms for MHR distributions
• Optimal item pricing in online combinatorial auctions
• Approximation algorithms for the partial assignment problem
• A duality based unified approach to Bayesian mechanism design
• Persuasion and incentives through the lens of duality
• A constant factor prophet inequality for online combinatorial auctions
• Revenue submodularity
• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• Optimal mechanisms for selling two items to a single buyer having uniformly distributed valuations

This page was built for publication: Simple mechanisms for subadditive buyers via duality

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