Frontiers in Algorithmic Game Theory

Recent years have seen much of the world's economic activity transferred to the Internet through old markets that obtained online presence and new markets that are directly inspired and enabled by the Internet, such as sponsored search and ad auctions. Driven by the increasing importance of online economic activity, there has been much interest in investigating its joint computational and economic characteristics through research at the interface of Computer Science and Economics. Economics brought to the table quantitative models and methodology for studying economic systems. But it soon became clear that these models and methodology required adaptation, since the intention was to study systems that are computational while involving thousands or millions of participants. This thinking gave rise to the field of Algorithmic Game Theory (AGT), which has in the past fifteen years grown into a mature research discipline.

This project will identify and investigate new frontiers of research in this field, focusing on the following:

(*) Furthering our understanding of multi-item mechanisms by (i) weakening the distributional assumptions required for optimizing important objectives such as revenue; (ii) overcoming well-established computational intractability barriers for welfare maximization by moving away from truthful mechanisms to mechanisms solvable via online learning; and (iii) using optimal transport theory to characterize the structure of optimal mechanisms.

()* Discerning the role of learning and signaling in auction settings, by understanding how to (i) learn a revenue-optimal auction from weak forms of sample access to the bidders' distributions, (ii) test the near-optimality of a given auction from samples, and (iii) further a line of research going back to classical works of Akerlof and Milgrom-Weber by investigating how to design optimal signaling schemes for the auctioneer to use in common settings, such as sponsored search, where the auctioneer owns information about the properties of the items that the bidders do not have.

(*) Finally, revisiting the computational foundations of the field, investigating the relation between Factoring and Nash equilibrium.

The work in Algorithmic Game Theory is inherently interdisciplinary. This project will further the interaction between Computer Science and Economics through the publication of the research outcomes in high-impact Economics journals, organization of interdisciplinary research meetings, interdisciplinary research collaborations, and research surveys. The educational component of the project will involve the mentoring and education of researchers who intend to pursue their own careers in research or industry, and the design of pioneering classes in the interface of Computer Science and Economics. Furthering the educational and outreach impact of the project, the PI will be mentoring high school students in Computer Science research through the MIT PRIMES program, will be engaged in Computer Science Unplugged activities at local elementary schools, and will engage with the broader public through public lectures.