Learning & Games Reading Group: Equilibrium Computation and Machine Learning
Denizalp (Deni) Goktas (Brown University) and Juan Carlos Perdomo (UC Berkeley)
Calvin Lab Room 116
Title: Convex-Concave Min-Max Stackelberg Games
Speaker: Denizalp (Deni) Goktas
Abstract: Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games.
In this talk, I will present our recent work which introduced two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald’s maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. Additionally, in our paper, we observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.
Bio: Deni is a third-year PhD student in the computer science department at Brown advised by Amy Greenwald. He is interested in decentralized multi-agent learning in markets and games, with the ultimate goal of building decentralized welfare improving technology based on these algorithms. Prior to coming to Brown, he received a bachelor’s degree in computer science-statistics from Columbia, and a bachelor’s degree in political science-economics from the Paris Institute of Political Studies (Sciences Po). He is a recipient of the JP Morgan fellowship.
List of related papers:
Denizalp Goktas and Amy Greenwald (2021), “Convex-Concave Min-Max Stackelberg Games”. Proceedings of Conference on Neural Information Processing Systems (NeurIPS'21).
Denizalp Goktas, Sadie Zhao and Amy Greenwald (2022), “Robust No-Regret Learning in Min-Max Stackelberg Games”, The AAAI-22 Workshop on Adversarial Machine Learning and Beyond, Forthcoming in International Conference on Autonomous Agents and Multi-Agent Systems 2022 (AAMAS'22)
========================================================================
Abstract: In this talk, I'll give a self-contained introduction to performative prediction, a recently developed framework for thinking about prediction systems in social settings and the underlying feedback loops they generate. This talk will be focused on the motivations and basic results. As part of the discussion, I hope to highlight connections with other common frameworks (e.g RL, algorithmic game theory) for dealing with predictions in dynamical systems. Time permitting, I'll give an overview of various technical extensions that have been established so far and outline ongoing research directions.
