Machine Learning-Aided Economic Design

Abstract

Nowadays, online markets (e.g. online advertising market and online two-sided markets) grow larger and larger everyday. Designing an efficient and near-optimal market is an intricate task. Market designers are facing challenges not only in regard to scalability, but also coming from the use of data to better understand the behavior of strategic participants. At the same time, these participants are trying to understand how these markets work and to maximize reward. For these reasons, we continue to need improved frameworks for the design of online markets. One challenge for market design is to make effective use of data in order to design better markets. For the players, a central problem is how to optimize their strategy, adaptively learning from feedback and incorporating this along with other side information.

To handle these challenges, my thesis focuses on two topics, \emph{Economic Design via Machine Learning} and \emph{Learning in Online Markets}. For the first topic, I propose a unified computational framework for data-driven mechanism design that can help a mechanism designer to automatically design a good mechanism to satisfy incentive constraints and achieve a desired objective (e.g. revenue, social welfare). I provide different approaches to guarantee Incentive Compatibility and prove the generalization bounds. This deep-learning framework is very general and can be extended to handle other constraints, e.g., private budget constraints. In addition, I investigate how to transform an approximately incentive compatible mechanism to a fully BIC mechanism without loss of welfare and with only negligible loss of revenue. For the second topic, I analyze the convergence of the outcome achieved by strategic bidders when they adopt mean-based learning algorithms to bid in repeated auctions. I also propose a new online learning algorithm for a bidder to use when bidding in repeated auctions, where the bidder's own value, evolving in an arbitrary manner, and observed only if the bidder wins an auction. This algorithm has exponentially faster convergence in terms of its dependence on the action space than the generic bandit algorithm.