The Taub Faculty of Computer Science Events and Talks

Goldberg, Hartline and Wright [SODA 2001] introduced the notion of 'competitive analysis' into 'auction theory' when dealing with 'unlimited supply', 'unit demand', 'single item' auctions. They proved that there exists random auctions that guaranty constant 'competitive ratio' and that no deterministic auction can guaranty that.

Aggarwal, Fiat, Goldberg, Hartline, Immorlica and Sudan [STOC 2005] showed that the 2001 conclusion was wrong and that there exist deterministic asymmetric auction with constant competitive ratio. They also show an elegant derandomization that uses some intermediate 'hat guessing games' and have a factor 4 loss from the random expectation.

We show a new derandomization using the 'Lovasz's local lemma' that eliminate this loss. We also show a specific setting for which there exists an elegant polynomial deterministic auction accompanied with a matching lower bound. For this we solve a different 'hat guessing game'. This answers an open question of Feige [2004].

The talk is based on works done jointly with Guy Wolfovitz and Ilan Newman.