CS Student Colloquium

Speaker 1: Jason Gaitonde
Title: The Price of Anarchy in Stochastic Games
Abstract: Algorithmic and decentralized decision-making increasingly dominates real-world systems ranging from online marketplaces to routing in networks. A key goal of algorithmic game theory is to understand the quality of outcomes reached by selfish, learning agents compared to that of socially optimal outcomes with respect to some measure of welfare. This loss in inefficiency is known as the "price of anarchy," and a deep theory of welfare and learning outcomes has emerged in the last two decades for many games of importance. However, this theory cannot account for dynamic settings (known as “stochastic games”) where the underlying strategic environment itself evolves in response to the actions of the agents, a crucial feature of many real-world systems. I will discuss my work on new techniques and results for the price of anarchy in queuing and auction settings where these complications are prominent, as well as important challenges that remain in understanding the price of anarchy in general stochastic games.
Based on joint works with Éva Tardos, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins.

Bio: Jason Gaitonde is a final-year PhD candidate in Computer Science at Cornell University advised by Éva Tardos. His research studies problems at the intersection of algorithms, learning, and randomness. Much of his work to date focuses on understanding the outcomes of interacting, learning agents in dynamic environments.

Speaker 2: Jesse Goodman
Title: Improving the state-of-the-art in randomness extraction
Abstract: Randomness is everywhere in computer science — from cryptography, to distributed computing, to algorithm design, and more. Unfortunately, all of these applications require access to *perfectly uniform bits*, while randomness found in nature (radioactive decay, atmospheric noise) can have unwanted correlations and biases. This motivates the study of *randomness extractors*, which are deterministic algorithms that extract uniform bits from weak sources of randomness.
Randomness extractors are central objects in the theory of pseudorandomness, and their study has produced a fruitful line of research spanning 30+ years. In this work, we explicitly construct several new extractors that dramatically improve the previous state-of-the-art. In order to build our extractors, we leverage new reductions within pseudorandomness, and exploit new connections to extremal combinatorics. Along the way, we unearth exciting new applications in cryptography, complexity theory, and beyond.

Bio: Jesse Goodman is a fifth year CS PhD student at Cornell, where he is advised by Eshan Chattopadhyay. Previously, he received his BSE from Princeton. His primary interests lie in combinatorics, complexity theory, cryptography, and pseudorandomness.