Doctoral Thesis Proposal - Ioannis Anagnostides
August 27, 2026 12:30PM—2:00PM
Location:
4405 & Zoom
-
Gates and Hillman Centers
Speaker:
IOANNIS ANAGNOSTIDES,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.andrew.cmu.edu/user/ianagnos/
As interacting algorithms increasingly permeate multibillion-dollar markets, demystifying their behavior becomes a central challenge. This thesis contributes to the foundations of multiagent learning, examining through the lens of algorithms and complexity the regret, convergence, and welfare of learning dynamics. In the first part, we establish near-optimal no-regret guarantees across a range of equilibrium concepts, characterizing the frontier of efficient learnability. Complementing these algorithmic results, we obtain computational lower bounds on the number of rounds needed for no-regret learners to approximate an equilibrium.
The second part provides new results on the convergence of learning algorithms in central classes of problems, such as constrained optimization, team zero-sum games, autobidding, and performative prediction. These results identify structural conditions that enable convergence, while also revealing new separations between foundational learning algorithms. En route, we also uncover fruitful connections with optimization, culminating in the first polynomial-time algorithm for solving variational inequalities under the Minty condition. In the last part, we focus on the application of heart transplant allocation. Our main contribution here is the development of theoretically grounded, non-myopic policies that significantly outperform the current status quo in the US.
Thesis Committee:
Tuomas Sandholm (Chair)
Maria Florina Balcan
Vincent Conitzer
Constantinos Daskalakis (Massachusetts Institute of Technology)
Christos H. Papadimitriou (Columbia University)
In-person and Zoom
Contact
Matt Stewart