ORIE Colloquium: Yannai Gonczarowski (Hebrew University) - The Interface between Theoretical Economics and Theoretical Computer Science: Revenue Maximization as a Case Study

Description

Traditional auctions, and more generally, traditional economic transactions, have always been of "manual scale." For example, the number of auctions conducted even in the largest of auction houses was moderate enough (and each item—expensive enough) so that expert appraisers could dedicate time to surveying each item sold, and use their expertise to determine a starting price that is optimized to maximize the revenue of the auction house. Such manual solutions were tangible until the Internet changed our world. For instance, whenever you search for something using your favorite search engine, a split-second auction is performed among advertisers who are related to your search term in order to determine which ads will be shown to you in the results page a mere moment later; the quantity of these auctions (billions per day), together with the low worth of each (many times less than a single cent each, yet in total reaching many billions of dollars), makes any manual intervention (say, in choosing the "starting price") completely impractical.

This explosion in online and computerized economic activity necessitates the study and understanding of economic mechanisms and markets of unprecedented scale. How good can simple mechanisms be? How complex must optimal mechanisms be? And, most substantially, what are the precise trade-offs between simplicity and quality? In this talk, I will survey some of my recent results on such questions for three notions of complexity within the context of the design of high-revenue auctions: the complexity of describing high-revenue auctions, the complexity of the machine-learning of high-revenue auctions, and the communication complexity of running high-revenue auctions. Based also on joint works with Moshe Babaioff, Noam Nisan, and S. Matthew Weinberg.

Bio:
Yannai Gonczarowski conducted his Ph.D. research at the Institute of Mathematics, the School of Computer Science & Engineering, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem, advised by Sergiu Hart and Noam Nisan, as an Adams Fellow of the Israel Academy of Sciences and Humanities. He also holds an M.Sc. in math (summa cum laude) and a B.Sc. in Math, and Computer Science, and the "Amirim Science" honors program (summa cum laude, Class Valedictorian) from the same institution. Yannai is also a professionally trained opera singer, holding a master’s as well as a bachelor’s degree in Classical Singing. Throughout most of his Ph.D. studies, Yannai was also a long-term research intern at MSR in Herzliya.

Yannai's main research interests lie in the interface between the theory of computation, economic theory, and game theory. In particular, he is interested in various aspects of complexity in mechanism design (where mechanism design is defined broadly from auctions to matching markets), including the interface between mechanism design and machine learning. He is the recipient of the SIGecom Award for Best Presentation by a Student or Postdoctoral Researcher at EC'18. For his Ph.D. research, he received the 2018 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society.