News

Colloquia

Complex Systems, Computation and Game Theory

Luis Ortiz
Computer Science and Artificial Intelligence Laboratory
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology

Monday, April 2, 2007

The growing interest in the study of strategic interactions in complex large-population settings has led to novel generalizations of classical models in game theory and economics. The new models explicitly encode the rich structure of interactions inherent in many natural systems such as economic, social and biological, and in artificial systems like the Internet. While these models provide succinct representations, they require practical algorithms to achieve full power. The broader goal of my work is to build computational tools to solve important problems in complex systems. The general principle is to exploit the available structure to produce practical algorithms that, to the degree possible, formally ensure efficiency and solution-quality guarantees. This talk will exemplify this principle using my work in games in the context of (1) models of the voluntary decisions of people or corporations about security, e.g., whether to vaccinate, or invest in airline or computer security; and (2) our ongoing work on developing models and algorithms to understand where proteins bind along the DNA. I will present successful experimental illustrations on specific models we built for airline security and the lambda-phage biological subsystem. The work presented in this talk, along with other recent work and the resulting computational methods, extends our ability to solve problems in complex systems to new large-population domains.