60 citations · 140 across the 33 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.GT2009★ 4 cited
A Note on the Power of Truthful Approximation Mechanisms
Shahar Dobzinski
We study the power of polynomial-time truthful mechanisms comparing to polynomial time (non-truthful) algorithms. We show that there is a setting in which deterministic polynomial-…
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…