Title: Online Auctions, Matroids and Secretary Problems.
Speaker: Moshe Babaioff, Microsoft Research, Silicon Valley.
http://research.microsoft.com/~moshe/
Abstract:
We consider the problem of online auction design (e.g. Priceline.com). Maximizing welfare in such auctions is complicated by the fact that decisions are instantaneous and irrevocable. The classic secretary problem introduced by Dynkin (1963) can be used to design approximately welfare-maximizing auctions in the simple single-unit auction setting, when assuming that bidders arrive in a random order. We generalized the problem to combinatorial settings, specifically; we study matroid domains in which the sets of agents which may be simultaneously satisfied constitute a matroid. We present truthful O(log(k))-competitive auction for any rank k matroid, and constant-competitive auctions for several specific matroids that are of economic interest.
We then consider the discounted secretary problem. There is a time-dependent “discount” factor d(t), and the benefit derived from assigning the item at time t to agent e is d(t) times v(e). For this problem, we show a lower bound of $\Omega(\frac{\log n}{\log \log n})$, and a nearly-matching O(log n)-competitive truthful auction with general (and possibly increasing) d(t). Additionally, we present a constant-competitive truthful auction when the expected optimum is known in advance, proving the large value of knowing this market statistics.
This talk is based on joint work with Immorlica and Kleinberg (SODA’07) and Dinitz, Gupta, Immorlica and Talwar (SODA’09).
Leave a comment