Joan Feigenbaum, AT&T Labs
"Games, Complexity Classes, and Approximation Algorithms"
March 12, 1998
Game theory provides a framework in which to model and analyze
conflict and cooperation among independent decision makers. Many
areas of computer science have benefitted from this framework,
including artificial intelligence, distributed computing, security and
privacy, and lower bounds. Games are particularly important in
computational complexity, where they are used to characterize
complexity classes, to understand the power and limitations of those
classes, and to interpret the complete problems for those classes. In
this talk, I will present game-theoretic characterizations of several
standard complexity classes. I will then use these characterizations
to show that certain natural maximization and minimization functions,
drawn from domains such as boolean logic, graph searching, graph
reliability, and stochastic optimization, are as hard to approximate
closely as they are to compute exactly. These results demonstrate
that modern complexity theoretists' emphasis on interaction and
randomness and modern algorithm designers' emphasis on approximation
algorithms can benefit from a game-theoretic framework.
Joan Feigenbaum
AT&T Labs
Florham Park, NJ 07932
jf@research.att.com