Learning-augmented mechanism design

Xizhi Tan

doi:10.17918/00011084

The central theme of this thesis is the design of multi-agent systems that interact with self-interested agents, aiming to overcome strategic manipulation and information asymmetries. The design of such systems is typically guided by traditional analytical frameworks. While worst-case analysis offers robust guarantees, it can be overly pessimistic; Bayesian methods, in contrast, depend on precise distributional knowledge, limiting their real-world applicability. With the increasing availability of data and predictive tools, there is now an opportunity to improve outcomes by leveraging predictions, even though they are unreliable. This thesis systematically develops the framework of learning-augmented mechanism design, which integrates potentially unreliable predictions to achieve strong guarantees when predictions are accurate, while maintaining robust worst-case performance when they are not. By combining theoretical rigor with practical relevance, this approach significantly enhances mechanism performance in data-driven environments. Through detailed studies of canonical problems including auctions, decentralized network protocols, job scheduling, and social choice, this work demonstrates how integrating predictions can fundamentally improve outcomes. For instance, we develop combinatorial clock auctions that achieve near-optimal social welfare when predictions are accurate, while still preserving best-known worst-case guarantees. We also introduce prediction-augmented strategies for scheduling and procurement settings, achieving constant approximation ratios under accurate predictions, and robust linear guarantees otherwise. In the domain of social choice, this thesis derives new general upper bounds for metric distortion problems, offering improved performance unattainable through traditional deterministic methods alone. Moreover, this thesis contributes novel analytical techniques of broader interest, including general lower-bound constructions and smooth, error-dependent analyses applicable to related theoretical domains, such as sample complexity and learning theory. Collectively, these results highlight the power and versatility of predictions in mechanism design, providing both foundational insights and practical guidelines for future research in robust, data-driven economic systems.

Learning-augmented mechanism design

Files and links (1)

Abstract

Metrics

Details

Learning-augmented mechanism design

Files and links (1)

Abstract

Metrics

Details

Drexel University Social media