On the Power of Randomization in Algorithmic Mechanism Design Export

@article{citeulike:4464997, abstract = {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-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We also show for the first time that truthful in expectation polynomial-time mechanisms are \emph{provably} stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting in which: (1) there is a non-polynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.}, archivePrefix = {arXiv}, author = {Dobzinski, Shahar and Dughmi, Shaddin}, citeulike-article-id = {4464997}, citeulike-linkout-0 = {http://arxiv.org/abs/0904.4193}, citeulike-linkout-1 = {http://arxiv.org/pdf/0904.4193}, day = {27}, eprint = {0904.4193}, keywords = {algorithms, approximations, deterministic, randomization}, month = {Apr}, posted-at = {2009-07-15 08:28:34}, priority = {2}, title = {On the Power of Randomization in Algorithmic Mechanism Design}, url = {http://arxiv.org/abs/0904.4193}, year = {2009} }

TY - JOUR ID - citeulike:4464997 L3 - citeulike-article-id:4464997 N2 - 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-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We also show for the first time that truthful in expectation polynomial-time mechanisms are \emph{provably} stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting in which: (1) there is a non-polynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists. TI - On the Power of Randomization in Algorithmic Mechanism Design KW - algorithms KW - approximations KW - deterministic KW - randomization AU - Dobzinski, Shahar AU - Dughmi, Shaddin PY - 2009/Apr/27/ UR - http://arxiv.org/abs/0904.4193 ER -