On the Power of Randomization in Algorithmic Mechanism Design

Details On the Power of Randomization in Algorithmic Mechanism Design On the Power of Randomization in Algorithmic Mechanism Design

2009-04-27

arxiv.org/abs/0904.4193v2

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Power of Randomization in Algorithmic Mechanism Design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Power of Randomization in Algorithmic Mechanism Design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Power of Randomization in Algorithmic Mechanism Design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-323090