Simple mechanisms for subadditive buyers via duality

DOI10.1145/3055399.3055465zbMATH Open1369.91065arXiv1611.06910OpenAlexW2549743857MaRDI QIDQ4977970FDOQ4977970

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)

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.

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

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

zbMATH Keywords

dualityrevenuesimple and approximately optimal auctionssubaddtive valuations

Mathematics Subject Classification ID

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

Cited In (26)

• Title not available (Why is that?)
• 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
• Buy-many mechanisms for many unit-demand buyers
• Risk-robust mechanism design for a prospect-theoretic buyer
• Optimal item pricing in online combinatorial auctions
• Bayesian auctions with efficient queries
• 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
• A duality based unified approach to Bayesian mechanism design
• Optimal item pricing in online combinatorial auctions
• Approximation algorithms for the partial assignment problem
• 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)