On the Power of Randomization in Algorithmic Mechanism Design

DOI10.1109/FOCS.2009.42MaRDI QIDQ5171216zbMATH OpenOpenAlexFDO

Authors 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) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited in

(14)

• A simple and fast algorithm for convex decomposition in relax-and-round mechanisms
• 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
• Optimizing maintenance service contracts through mechanism design theory
• The power of randomness in Bayesian optimal mechanism design
• Combinatorial auctions with verification are tractable
• Limitations of randomized mechanisms for combinatorial auctions
• Truthful mechanisms with implicit payment computation
• Truthfulness and approximation with value-maximizing bidders
• scientific article; zbMATH DE number 5309433 (Why is no real title available?)
• Inapproximability of truthful mechanisms via generalizations of the Vapnik-Chervonenkis dimension
• scientific article; zbMATH DE number 7053320 (Why is no real title available?)
• Leveraging possibilistic beliefs in unrestricted combinatorial auctions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171216)