Abie Flaxman (CMU)
“Random Sampling Auctions”
September 29, 15:00-16:00, PPB 300
ABSTRACT:
Random sampling is the most prevalent technique for designing incentive-compatible auctions to maximize the auctioneer’s profit when the bidders’ valuations are a priori unknown. The first and simplest application of random sampling to auctions is in the context of auctioning a digital good. For this problem, the random sampling optimal price auction works by selecting a bipartition of the bidders uniformly at random and offering the optimal sale price for each part to the other part.
We give a simple analysis of the competitive ratio of the random sampling auction. The random sampling auction was previously known to be worst-case competitive with a bound of 7600; our analysis improves the bound to 15. It is believed that the auction is in fact 4-competitive, and we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.
This is joint work with Uri Feige, Jason Hartline, and Bobby Kleinberg.
Speaker: Maverick Woo
Time: Wednesday 12pm-1pm
Place: NSH 1507
Title: A Tale of Two Simple Data Structures
Abstract:
Among the numerous designs for meldable heaps, Fat Heaps by Kaplan and Tarjan (1998) stand out to be almost perfect. Fat Heaps retain the simplicity of Fibonacci Heaps, but the time bounds are worst-case instead of amortized (although they don’t match Fibonacci Heaps in the Meld operation.) The key ingredient in this design is an abstraction known as redundant counters, introduced by Clancy and Knuth back in 1977. I will show how Fat Heaps work, and more importantly, how we can understand its design from a deamortization point of view. This part of the talk will be self-contained.
In the Dynamic Connectivity problem, we are given a set of $n$ fixed vertices on which we have to maintain a dynamic graph supporting an intermixed sequence of edge insertions, edge deletions and connectivity queries (“Are $u$ and $v$ connected?”). A long line of papers have been written on this problem, but I will focus on the conceptually simple design by Holm, de Lichtenberg and Thorup (1998) that supports each operation in deterministic amortized $O(log^2 n)$ time. This part of the talk will depend on an abstraction known as Dynamic Trees. I will explain the abstraction but will not go into the details of its implementation and analysis.
Notes from Maverick:
Coincidentally, Danny Sleator is teaching how to implement Dynamic Trees with Splay Trees in his Advanced Data Structure course right after this talk. The class starts at 1:30pm in Wean 4623.
