Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Hats Auctions and Derandomization
event speaker icon
Oren Ben-Zwi (Haifa University)
event date icon
Wednesday, 17.11.2010, 12:30
event location icon
Room 337-8 Taub Bld.
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.