Annual Meeting December-2020

Keynote Speaker: Prof. Vianney Perchet (Centre de recherche en économie et statistique - CREST)

Title: "Selfish Robustness and Equilibria in Multi-Player Bandits"

Abstract: Motivated by cognitive radios, stochastic multi-player multi-armed bandits gained a lot of interest recently. In this class of problems, several players simultaneously pull arms and encounter a collision - with 0 reward - if some of them pull the same arm at the same time. While the cooperative case where players maximize the collective reward (obediently following some fixed protocol) has been mostly considered, robustness to malicious players is a crucial and challenging concern. Existing approaches consider only the case of adversarial jammers whose objective is to blindly minimize the collective reward. We shall consider instead the more natural class of selfish players whose incentives are to maximize their individual rewards, potentially at the expense of social welfare. We provide the first algorithm robust to selfish players (a.k.a. Nash equilibrium) with a logarithmic regret, when the arm performance is observed. When collisions are also observed, Grim Trigger types of strategies enable some implicit communication-based algorithms and we construct robust algorithms in two different settings: the homogeneous (with a regret comparable to the centralized optimal one) and heterogeneous cases (for an adapted and relevant notion of regret). We also provide impossibility results when only the reward is observed or when arm means vary arbitrarily among players.

Bio: Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE since october 2019. Mainly focusing on the interplay between machine learning and game theory, his themes of research are at the junction of mathematics, computer science and economics. The spectrum of his interest ranges from pure theory (say, optimal rates of convergence of algorithms) to pure applications (modeling user behavior, optimisation of recommender systems, etc.) He is also part-time principal researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.

Keynote Speaker: Nicolas Stier-Moses (Facebook Research)

Title: "Pacing Mechanisms For Ad Auctions"

Abstract: Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by pacing mechanisms used in practice by online ad auction platforms, we discuss smoothing procedures that ensure that campaign daily budgets are consistent with maximum bids. Reinterpreting this process as a game between bidders, we introduce the notion of pacing equilibrium, and study properties such as existence, uniqueness, complexity and efficiency, both for the case of second and first price auctions. In addition, we connect these equilibria to more general notions of market equilibria, and study how compact representations of a market lead to more efficient approaches to compute approximate equilibria.

Bio: Nicolas Stier is a Director at Facebook Core Data Science. His work leverages innovative research to drive impact to the products, infrastructure and processes at Facebook, the company. The group draws inspiration from a rich and diverse set of disciplines including Operations, Statistics, Economics, Mechanism Design, Machine Learning, Experimentation, Algorithms, and Computational Social Science (in no particular order). Between 2014 and 2017, he supported the Economics, Algorithms and Optimization team, which is one of the areas of focus of Core Data Science. Prior to joining Facebook, Nicolas was an Associate Professor at the Decision, Risk and Operations Division of Columbia Business School and at the Business School of Universidad Torcuato Di Tella. He received a Ph.D. degree from the Operations Research Center at the Massachusetts Institute of Technology.