MSR Theory Day – Part 2


October 22, 2014


Sebastien Bubeck and Nick Gravin


MSR-Redmond, MSRNE


3:10-3:30 Sebastien Bubeck, MSR-Redmond Title: On the influence of the seed in random recursive trees

Abstract: Let S be a fixed (seed) tree, and T be a large tree grown according to the uniform attachment process initialized on S. We are interested in whether T still contains information about S, even as the size of T goes to infinity. Perhaps surprisingly, we show that different seeds always lead to different distributions for the limiting trees (from a total variation point of view). 3:35-3:55 Nick Gravin, MSRNE Title: Competitive analysis: how to play with your benchmarks

Abstract: Over the past decade the competitive analysis was one of the most prevalent frameworks in algorithmic mechanism design and on-line settings. The problem of designing a competitive auction or an on-line algorithm is usually tailored to the particular benchmark in a given setting. We advocate a more general approach where we (i) design competitive algorithms against an abstract class of benchmarks and (ii) use these algorithms as building blocks to compete against any benchmark of interest. In this talk I will illustrate this approach on a few examples: digital good, position, on-line auctions, and downward-closed permutation environments. All of these settings having the following simple scenario at the core: a single-round, sealed-bid auction for selling an item in unlimited supply. The goal is to design a truthful auction (i.e., encourages buyers to bid truthfully) such that on every input it must generate profit within a constant factor compared to a certain economically meaningful benchmark. A joint work with Ning Chen and Pinyan Lu.