Tractable and Learnable Notions of Equilibria in Auctions and Games

• Applicant: Dr. Mete Ahunbay
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 558988238

The successes of machine learning in recent years have motivated obtaining theoretical guarantees of learning algorithms. Unfortunately, present theory falls short of establishing such guarantees with respect to convergence to equilibrium or welfare bounds. Auctions and non-concave games are two prime examples. This has recently motivated research in establishing the limits of traditional no-regret learning in explaining convergence to equilibrium. This proposal contains two lines of inquiry to extend these advances. The first seeks tighter guarantees for commonly used learning algorithms in auction settings, leveraging stronger notions of equilibrium. Recent work suggests that in any normal-form game, whenever players use online gradient ascent as their learning algorithm, they incur vanishing regret against any strategy deviation generated by gradient fields of functions. Some of these functions generate linear equilibrium constraints. Thus, in this setting, learners converge to a notion of equilibrium between that of a coarse correlated equilibrium and a correlated equilibrium. Therefore, stronger guarantees with respect to convergence as well as more traditional price of anarchy bounds may be obtained via duality of convex programming in a suitable primal-dual framework. Since the correlated equilibrium of these auctions are unique, this would provide a hitherto unknown explanation of observed learning behaviour. The second inspects notions of local correlated equilibrium generated by vector fields, with the goal of characterising, its expressivity, its computational complexity, as well as its associated dynamical behaviour. First, we seek to investigate strengthenings of coarse correlated equilibria, allowing description of learnable behaviour for a wider variety of learning algorithms than online gradient ascent. Second, when the generators of regret are not conservative vector fields, with access to fixed-point computation regret minimisation is still possible. This raises the question of complexity of finding such no-regret outcomes. Third, via considering regret against vector fields with non-zero curl, we seek to study the extent cyclic behaviour in learning may be avoided.

• DFG Programme: WBP Fellowship
• International Connection: United Kingdom
• Host: Professor Paul Goldberg