What is the best way to win rock, paper, scissors? Game theory -- the study of how to optimally "play" in a situation where multiple people or machines interact -- suggests it is to play a random assortment of one-third rock, one-third paper, and one-third scissors. But what about a higher stakes "game," like assigning a limited number of security guards across multiple airport terminals to cast the optimal safety net? Do you randomize their movements? Do you concentrate their time in vulnerable locations?
"The larger a game gets, the more difficult it is to solve, even for a computer," says Vince Conitzer, assistant professor of computer science and economics at Duke. Conitzer is a 2010 recipient of a prestigious National Science Foundation CAREER Award, a competitive $500,000 grant distributed over five years to support the early career work of effective and exemplary faculty. Striving to push the computational boundaries of game theory, Conitzer plans to tackle difficult problems in the field by developing unique and efficient algorithms specifically designed for various game settings.
"How do we write computer agents that can act strategically?" asks Conitzer. In his coming research, this economics-minded computer scientist will tackle commitment advantage events, situations in which one agent is allowed to commit to a strategy before another agent can act. Researchers at the University of Southern California have already built on Conitzer's early work in this area to create an application used to deploy security forces at Los Angeles International Airport. There, planners have the advantage of determining how forces are assigned to various locations prior to the arrival of an attacker. Conitzer, Ph.D. student Dima Korzhyk, and professor Ron Parr are now working together with the USC group on these problems.
In the spirit of the CAREER award, which focuses on integrating research and education, Conitzer will also use the funding to further build connections at Duke between computer science and economics, including interdisciplinary classes, seminars, and more.
Department of Computer Science