Research Into the Complexity Theory of Games and Polynomials

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

We propose to work on several areas of theory. The first concerns game theoretic/economic questions. The second concerns several questions about polynomials: zero testing, MOD complexity, and learning. The proposed research will examine a variety of open problems from these areas. Some of the open problems are classic and well known; others are new. The mix between known problems that are often difficult and new problems is important. Both types of problems will, we believe, advance our understanding of these important questions. The first questions concern mainly non-cooperative games as well as fair division problems. These problems have often been studied for years, but only recently have researchers looked closely at their computational complexity. It seems clear that the interface between game theory and economic problems with complexity theory has tremendous potential. The second questions concern mainly classic problems from the foundations of complexity theory. They include the power of polynomial under various complexity restrictions and certain learning problems. The problems are important for two reasons. They are important for their own sake. Further, their solution or even partial solution is likely to yield new insights and potentially new techniques. These could then be used to further our understanding of other problems in other parts of theory. Intellectual Merit: Games and economic problems are extremely challenging. This is especially true for non-zero sum games. Their complex structure raises many important fundamental questions. We expect to learn a great deal from the study of these important problems. This is also true for the more classic questions concerning polynomials. The questions of testing, mod behavior, and learning are difficult problems. Some have been challenging open problems for decades. We believe that any progress on these problems will require us to use old methods in new ways and to invent new methods. Broader Impact: The impact of the proposed research into games and economic problems is clear. Progress on the computational aspects of economic problems has a clear impact on society. As commerce becomes more digital, it is clear that any better understanding of games and economic problems will have impact on a very broad community. The work on polynomials also will have a broad impact. Some of the most fundamental theory questions would be effected by progress on any of the proposed research. The impact would be far beyond the theory community that studies these questions. It could effect other fields like: cryptography, learning theory, and fundamental parts of mathematics.