Speaker: |
Sayan Bhattacharya (Duke University Department of Computer Science N303, North Building 304 Research Drive Durham, NC 27708 United States of America) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Thursday, 6 Sep 2012, 14:00 to 15:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

Naturally, to execute the auction with optimal expected revenue, the auctioneer first needs to know the prior distributions. An intriguing question is to design a truthful auction that is oblivious to these priors, and yet manages to get a constant factor of the optimal revenue. Such auctions are called {\em prior-free}. This question was posed in a seminal paper by Goldberg et al. [SODA 2001].

Goldberg et al. presented a constant approximate prior-free auction when there are identical copies of an item available in unlimited supply, bidders are unit-demand, and their valuations are drawn from i.i.d. distributions. Very recently, Leonardi et al. [STOC 2012] generalized this setting to non i.i.d. bidders when the auctioneer knows the ordering of their reserve prices. Leonardi et al. presented a prior-free auction that achieves a $O(\log^* n)$ approximation. We improve upon this result and give a simple prior-free auction with constant approximation guarantee (joint work with Janardhan Kulkarni, Kamesh Munagala and Xiaoming Xu).