# Simple Mechanisms for Subadditive Buyers via Duality

arXiv: https://arxiv.org/abs/1611.06910 · HTML: https://mlsanity.com/paper/1611.06910/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2016.

## Built on by (most cited first, 6 of 6)

- [Differentiable Economics for Randomized Affine Maximizer Auctions](https://mlsanity.com/paper/2202.02872/) (2022)
- [A Context-Integrated Transformer-Based Neural Network for Auction Design](https://mlsanity.com/paper/2201.12489/) (2022)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [Deep Reinforcement Learning for Sequential Combinatorial Auctions](https://mlsanity.com/paper/2407.08022/) (2024)
- [Bridging the Gap Between Estimated and True Regret Towards Reliable Regret Estimation in Deep Learning based Mechanism Design](https://mlsanity.com/paper/2601.13489/) (2026)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)

## Abstract (arXiv)

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(log m), 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.