BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/304
DTSTAMP:20230914T125918Z
SUMMARY:Improved Prior-Free Auctions with Ordered Bidders
DESCRIPTION:Speaker: Sayan Bhattacharya (Duke University\nDepartment of Com
 puter Science\nN303\, North Building\n304 Research Drive\nDurham\, NC 2770
 8\nUnited States of America)\n\nAbstract: \nA central problem in Microecon
 omics is to design auctions with good revenue properties. Consider the fol
 lowing setting. Multiple bidders are participating in an auction. The bidd
 ers' valuations for the items are private knowledge\, but they are drawn f
 rom publicly known prior distributions. The goal is to implement a truthfu
 l auction (no bidder can gain in utility by misreporting her valuation) th
 at maximizes the expected revenue. Here\, the expectation is over the prio
 r distributions of the bidders' valuations\, and the random choices made b
 y the auctioneer.\n\nNaturally\, to execute the auction with optimal expec
 ted revenue\, the auctioneer first needs to know the prior distributions. 
 An intriguing question is to design a truthful auction that is oblivious t
 o these priors\, and yet manages to get a constant factor of the optimal r
 evenue. Such auctions are called {\\em prior-free}. This question was pose
 d in a seminal paper by Goldberg et al. [SODA 2001].\n\nGoldberg et al. pr
 esented 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 recent
 ly\, Leonardi et al. [STOC 2012] generalized this setting to non i.i.d. bi
 dders when the auctioneer knows the ordering of their reserve prices. Leon
 ardi 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 au
 ction with constant approximation guarantee (joint work with Janardhan Kul
 karni\, Kamesh Munagala and Xiaoming Xu).\n \n
URL:https://www.tcs.tifr.res.in/web/events/304
DTSTART;TZID=Asia/Kolkata:20120906T140000
DTEND;TZID=Asia/Kolkata:20120906T150000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR