60 citations · 140 across the 33 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012★ 3 cited
On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations
Shahar Dobzinski, Jan Vondrak
We present a new type of monotone submodular functions: \emph{multi-peak submodular functions}. Roughly speaking, given a family of sets $\cF$, we construct a monotone submodular f…
cs.GT2012★ 1 cited
The Computational Complexity of Truthfulness in Combinatorial Auctions
Shahar Dobzinski, Jan Vondrak
One of the fundamental questions of Algorithmic Mechanism Design is whether there exists an inherent clash between truthfulness and computational tractability: in particular, wheth…