On the Power of Randomization in Algorithmic Mechanism Design

DOI10.1109/FOCS.2009.42zbMath1292.91081OpenAlexW2142495422MaRDI QIDQ5171216

Shahar Dobzinski, Shaddin Dughmi

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.42

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (13)

A simple and fast algorithm for convex decomposition in relax-and-round mechanisms ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ A universally-truthful approximation scheme for multi-unit auctions ⋮ Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets ⋮ On the hardness of designing public signals ⋮ Leveraging possibilistic beliefs in unrestricted combinatorial auctions ⋮ Truthful Mechanisms with Implicit Payment Computation ⋮ Combinatorial auctions with verification are tractable ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Optimizing maintenance service contracts through mechanism design theory ⋮ Truthfulness and Approximation with Value-Maximizing Bidders ⋮ Unnamed Item ⋮ The power of randomness in Bayesian optimal mechanism design

This page was built for publication: On the Power of Randomization in Algorithmic Mechanism Design