# Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2019.

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

- [Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism](https://mlsanity.com/paper/2205.14798/) (2022)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Deep Reinforcement Learning for Sequential Combinatorial Auctions](https://mlsanity.com/paper/2407.08022/) (2024)

## Abstract (arXiv)

A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC'06] who gave an O(log2m)-approximation where m is the number of items. This problem has been studied extensively since, culminating in an O(√logm)-approximation mechanism by Dobzinski [STOC'16]. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an O((loglogm)3)-approximation in expectation, uses only O(n) demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether Theta(√logm) is the best approximation ratio in this setting in negative.