AF: Small: Problems in Algorithmic Game Theory for Online Markets

A quarter of a century ago, research in Theoretical Computer Science was transformed by the advent of the Internet. This new and crucial computational artifact requires for its study a new arsenal of mathematical modeling, ideas and techniques. Since markets and incentives play an important role in the function and evolution of the new computational environment, computational branches of Game Theory and Microeconomics were eventually developed, inspired by the Internet. The new field thus created, dubbed Algorithmic Game Theory, combined algorithmic thinking with economic considerations, and has produced crucial insights into today's complex computational environment, which encompasses both the Internet and artificial intelligence (AI). The goal of this project is to address a new generation of open questions in Algorithmic Game Theory that have emerged in recent years. Results from this research are likely to have an impact beyond Theoretical Computer Science to Economics and Game Theory, as well as Machine Learning. The research directions that will be explored in this project include the following: (1) Develop new solution concepts that are more pertinent to the new applications of games and more friendly to computation, based on the dynamics of games; and address the complexity of some basic open questions regarding equilibria in games and markets. (2) Investigate novel formulations and problems in on-line markets and platforms, as well as address certain computational problems related to achieving various notions of equilibrium in matching markets. (3) Study certain novel problems related to fairness and inequity in online markets and machine learning systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.