Date of Award

Spring 1-1-2025

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Cai, Yang

Abstract

Motivated by the growing number of applications at the intersection of game theory and machine learning, including alignment, AI agents like automated bidders, training generative models, and high-dimensional mechanism design, this dissertation explores the interplay between the two fields. Specifically, we show how machine learning can gain insights from game-theoretic multi-agent optimization techniques and how game theory can benefit from machine learning techniques. The first part of this work focuses on leveraging game-theoretic insights to improve optimization algorithms in multi-agent machine learning. Traditional methods, such as gradient descent, often fail to converge when training multi-agent systems with competing objectives. This challenge raises the key question: can simple first-order methods efficiently converge to equilibrium in such settings? We answer this question by proving that two classical algorithms from the Variational Inequalities literature, namely the extragradient method by Korpelovich and the optimistic gradient descent method by Popov, achieve efficient convergence to equilibrium. Through a novel Sum-of-Squares based analysis, we prove tight last-iterate convergence rates for these methods, and further extend our analysis to their accelerated variants. We conclude the first part, by applying insights from convergent algorithms in games to alignment of Large Language Models, leveraging a recent reformulation as a two-player game and observe improved performance over competing approaches. The second part addresses critical limitations in the classical mechanism design literature. On one front, literature often overlook the correlations in buyer valuations in multi-item auctions. To tackle this, we use insights from machine learning, we develop a framework that uses graphical models to effectively capture dependencies between items. Our results demonstrate that simple mechanisms, such as selling items individually, degrade gracefully as correlations increase. On the other front, literature typically offer only existential guarantees without providing constructive methods. To bridge the gap between existential guarantees and computational feasibility by introducing a set of optimization-based tools to compute approximately optimal mechanisms. These tools leverage compact representations of the problem space, enabling the efficient design of mechanisms even in high-dimensional settings.

Download

Share

COinS