As Computer Science struggles to understand the Internet and its capabilities, computer scientists are incorporating concepts and methodologies from Economics and Game Theory into their discipline. In the past decade, there has been a tremendous growth in research, centering around the following questions: what game-theoretic tools are applicable to computer systems? How far is the performance of a system from optimality due to the conflict of interests of its users and administrators? And, how can we design a system whose performance is robust with respect to the potential conflict of interests inside the system? The proposed research aims to tackle some of the fundamental problems at the interface of Computer Science and Game Theory, with a focus on networked interactions.
The tools that game theorists have traditionally used to model behavior in systems of interacting individuals, such as the Nash and the market equilibria, have been recently shown to be computationally intractable. The intractability of these concepts limits their applicability to policy making since their predictions, although mathematically well-defined, are hard to compute. Moreover, this intractability result raises suspicion as to whether these predictions arise in actuality: if the behavior predicted by some equilibrium concept cannot be found efficiently, how is it that rational individuals find it and adopt it?
The goal of this project is to develop a theory of networked interactions that does not run into the computational complexity barrier, answering such questions as: In what settings is it possible to use existing tools, such as the Nash equilibrium, to predict selfish behavior computationally efficiently? How does the structure of the interaction graph affect the tractability of equilibria? When computing Nash equilibria is intractable, is it possible to make approximate predictions efficiently? And if this is infeasible, are there other concepts of equilibrium that are both plausible and tractable? Also, in the context of trading: What kind of market equilibrium comes about in a trading network? Is it always identical to the market equilibrium assuming full information? If so, how does it come to arise in the presence of the communication constraints imposed by the network structure? If not, how different is it? And for what kinds of networks is it similar to the full-information one?
The development of a successful theory of networked interactions will necessitate answering deep questions within the theory of computation. Equilibrium concepts typically correspond to fixed points of continuous maps, which have proven to be a challenging computational object for present techniques. In recent years, algorithmic progress on computing equilibria has brought new techniques to the theoretical computer science community. Likewise, characterizing the complexity of game-theoretic concepts has broadened the computational complexity landscape beyond traditional complexity classes. Several questions, such as the approximation complexity of Nash equilibria, the complexity of simple stochastic games as well as other fixed points at the intersection of the complexity classes known as PLS and PPAD, and the complexity of market equilibria for constant elasticity of substitution (CES) utility functions, are evading existing techniques. Furthering our understanding of rational behavior in large systems will necessarily involve developing novel algorithmic and complexity-theoretic tools to meet the challenges posed by these problems.
