60 citations · 82 across the 3 of their papers we have counts for
3 papers
cs.GT2011
A Truthful Randomized Mechanism for Combinatorial Public Projects via Convex Optimization
Shaddin Dughmi
In Combinatorial Public Projects, there is a set of projects that may be undertaken, and a set of self-interested players with a stake in the set of projects chosen. A public plann…
cs.GT2011★ 22 cited
From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions
Shaddin Dughmi, Tim Roughgarden, Qiqi Yan
We design an expected polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our resul…
cs.GT2009★ 60 cited
On the Power of Randomization in Algorithmic Mechanism Design
Shahar Dobzinski, Shaddin Dughmi
In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem. In particular, we construct an FPTAS for multi-u…