The application of sophisticated algorithms to vast amounts of user data is already transforming our economy and stimulating the growth of innovative industries such as cloud computing. However, learning and optimization using user data face significant challenges stemming from the need to make real-time decisions under uncertainty and the need to account for users’ strategic behavior. In this talk, I study these limitations and show that despite their existence, there are market algorithms that perform almost as well, or require almost as few resources, as if those limitations had not existed.

In the first part of the talk, I focus on dynamic pricing and auction design, inspired by cloud computing spot markets. I will present an algorithm that learns a sequence of pricings/auctions through real-time interaction with bidders, whose average revenue converges to that of the optimal pricing in hindsight even if the bid distribution is heavy-tailed. Furthermore, the number of rounds required for this convergence matches the number of i.i.d. samples required for an offline learning algorithm to attain the same near-optimality guarantee. A consequence is that the constraint of real-time decision making over data, surprisingly, does not increase the sample data complexity of learning near-optimal pricings and auctions.

In the second part of the talk, I will briefly explain my work on transforming any given algorithm for (approximate) social welfare optimization into a Bayesian incentive compatible mechanism, via a computationally efficient black-box reduction. A consequence is that, in principle, engineers designing mechanisms to maximize users’ aggregate welfare can ignore strategic behavior and only focus on the optimization aspect of the problem. I will conclude the talk by surveying my current and future research on further applications of machine learning and optimization to market design, algorithmic tools for exploratory data analysis, and applying game-theoretic techniques to solve a class of non-convex optimization problems arising in machine learning and computer vision.

The talk is based on several joint works with Robert Kleinberg, Jason Hartline, Shaddin Dughmi, Tim Roughgarden, Moses Charikar, Sebastien Bubeck, Nikhil Devanur, Zhiyi Huang, Vaggos Chatziafratis and Joshua Wang.