Tata Institute of Fundamental Research
Improved Prior-Free Auctions with Ordered Bidders
Seminar
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)
Abstract:
A central problem in Microeconomics is to design auctions with good revenue properties. Consider the following setting. Multiple bidders are participating in an auction. The bidders' valuations for the items are private knowledge, but they are drawn from publicly known prior distributions. The goal is to implement a truthful auction (no bidder can gain in utility by misreporting her valuation) that maximizes the expected revenue. Here, the expectation is over the prior distributions of the bidders' valuations, and the random choices made by the auctioneer.
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).
| 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)
Abstract:
A central problem in Microeconomics is to design auctions with good revenue properties. Consider the following setting. Multiple bidders are participating in an auction. The bidders' valuations for the items are private knowledge, but they are drawn from publicly known prior distributions. The goal is to implement a truthful auction (no bidder can gain in utility by misreporting her valuation) that maximizes the expected revenue. Here, the expectation is over the prior distributions of the bidders' valuations, and the random choices made by the auctioneer.
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).
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).