Jonathan Schneider will present his PreFPO Thursday, April 19, 2018 at 1:30 CS302 The members of his committee are as follows: Mark Braverman - Adviser, Matt Weinberg,Bernard Chazelle, Elad Hazan and Omri Weinstein(Columbia) All are welcomed to attend. Title: "Learning Algorithms in Strategic Environments" Abstract: Learning algorithms are often analyzed under the assumption their inputs are drawn from stochastic or adversarial sources. Increasingly, these algorithms are being applied in strategic settings, where we can hope for stronger guarantees. My research aims to understand the performance of existing learning algorithms in these settings, and to design new algorithms that perform well in these settings. In the first part of the talk, I will discuss the problem of repeatedly auctioning off an item to a single low-regret buyer. We will show that if the buyer uses classical low-regret learning algorithms such as EXP3 or Multiplicative Weights, it is possible for the seller to extract the full welfare of the buyer; on the other hand, we present a new low-regret learning algorithm for the buyer which guarantees that the seller receives no more than Myerson revenue (the best they can achieve by offering the same price every round). In the second part of the talk, I will discuss the problem of "contextual search", a contextual, multidimensional generalization of binary search. We will use tools from integral geometry (namely, the notion of "intrinsic volumes") to design an algorithm which obtains constant regret bounds for this problem. We then apply these techniques to the problem of dynamic pricing, where we achieve a tight regret bound of O(log log T) (improving exponentially on the best existing algorithm which achieved O(log T) regret). Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University