Speaker: Rebecca Reiffenhäuser (ILLC, University of Amsterdam)
Date and Time: Thursday, September 19th 2024, 16:30-18:00
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: How to sell your items online – with almost no prior info.
Abstract. The problem of allocating a set of items to a set of buyers in a way that maximizes an objective, like the overall valuation of participants for the items they receive (social welfare), is a central setting with numerous applications.
We consider the harder, but very prevalent case where buyers/bids arrive over time in some fixed order, and decisions have to be made immediately (online) on their arrival. It is impossible to get close to the optimal value that would be achievable for a prophet who can see future participants valuations beforehand, and giving all items to some random person is actually the best you can do. Therefore, we additionally assume to get a tiny piece of information on each of the future participants beforehand: For every buyer to arrive, we assume to have a single sample of what his valuation function might be, e.g. from when he participated in an earlier auction.
We show that this suffices to achieve an expected, constant-factor approximation to the value of the future-seeing prophet for buyers with XOS valuation functions, and also consider the case that buyers might misreport their values strategically – which so far we can only deal with if we have some more samples.
(Based on joint work with Paul Duetting, Thomas Kesselheim, Brendan Lucier and Sahil Singla, to appear in FOCS 2024.)