The Internet is undoubtedly one of the most significant innovations of our era. Beyond serving as a medium of communication, it also enables huge opportunities for new markets and business. The study of the Internet and e-commerce has been one of the most exciting and challenging research areas in computer science during the past few decades. Recently, concepts and methodologies from game theory and economics have found numerous successful applications in this area.
The main goal of this proposal is to bridge the algorithmic gap between game theory, economics and computer science. While computational efficiency has always been a critical issue in the design of any computer system, the study within game theory and economics has been almost entirely non-algorithmic. The PI will work to develop efficient algorithms for some of the fundamental models and solution concepts and to understand the computational difficulties inherent within them, with the aim to inspire and enable the next-generation e-commerce systems.
For this purpose, the PI will perform a systematic study of both algorithmic and complexity-theoretic questions related to Nash equilibria and market equilibria. This includes the search of a polynomial-time approximation scheme for two-player Nash equilibria and the development of new techniques to understand the computation of market equilibria with various utility functions and with social influence. The PI will also work to improve our current understanding of PPAD and FIXP, two complexity classes for (discrete and continuous) fixed point computation, on which many of the hardness results of equilibrium computation rely. As two of the most fundamental solution concepts, the proposed research on Nash and market equilibria will contribute to a more solid algorithmic and complexity-theoretic foundation for the interdisciplinary field of Algorithmic Game Theory. Finally, the PI will tightly integrate education with the research activities by, e.g., developing new (introductory and advanced) courses on Algorithmic Game Theory and on its use in analyzing social networks; mentoring Ph.D. students; and promoting undergraduate research.
