Algorithmic Mechanism Design via Multi-Unit Auctions
Speaker
Shahar Dobzinski
Date
18/12/2013 - 12:00 - 10:00Add To Calendar
2013-12-18 10:00:00
2013-12-18 12:00:00
Algorithmic Mechanism Design via Multi-Unit Auctions
Abstract: In this talk we study the clash between computational efficiency and truthfulness: are polynomial-time truthful mechanisms better than polynomial-time (non-truthful) algorithms? To simplify the discussion, we restrict our attention to the problem of multi-unit auctions. We present a truthful deterministic algorithm that provides an approximation ratio of 2 for this problem. Proving that no polynomial time truthful mechanism can achieve better approximation ratio is a major open problem in Algorithmic Mechanism Design. Attempts to resolve the problem yielded in particular (surprising) characterizations of truthful mechanisms, and we will discuss those attempts as well.
אוניברסיטת בר-אילן - Department of Economics
Economics.Dept@mail.biu.ac.il
Asia/Jerusalem
public
Affiliation
Weizmann Institute
Abstract
Abstract: In this talk we study the clash between computational efficiency and truthfulness: are polynomial-time truthful mechanisms better than polynomial-time (non-truthful) algorithms? To simplify the discussion, we restrict our attention to the problem of multi-unit auctions. We present a truthful deterministic algorithm that provides an approximation ratio of 2 for this problem. Proving that no polynomial time truthful mechanism can achieve better approximation ratio is a major open problem in Algorithmic Mechanism Design. Attempts to resolve the problem yielded in particular (surprising) characterizations of truthful mechanisms, and we will discuss those attempts as well.
Last Updated Date : 05/12/2013
