Using Game Theory in AI to Thwart Adversaries
https://www.technologyreview.com/s/612054/fei-fang-carnegie-mellon-artificial-intelligence/
This article describes the application of game theory in computer science, specifically in AI: Fei Fang from Carnegie Mellon University has developed an AI which randomizes patrol routes to thwart attacks on ferry boats traveling between Staten Island and Manhattan. The impact is huge, as this has reduced the number of successful attacks by half.
Fang describes the underlying game used by the AI as a zero-sum two-person game. A zero-sum game means that the payoffs are structured such that if player one gains x, then player two loses x. Putting this in context of the game theory we’ve learned in class, the randomization of the patrol routes is like playing a mixed strategy — There are many strategies, as there are many possible routes. Nevertheless, the patrols don’t just use one pure strategy (i.e. follow the same route all the time) because then the adversary can always find their best response, given their set of strategies. If the patrols play a mixed strategy, then the opponent is less likely to win and attack successfully, because there is always uncertainty as to which route the patrols choose.
This article shows us that game theory concepts have a greater impact far beyond toy problems like Prisoner’s Dilemma — Game theory can and should be used to solve real-world problems, like minimizing the number of successful ferry boat attacks, even outside of the business context. Game theory is a very powerful tool that crosses many disciplines, with AI, and as a result, the issues AI impacts, just being a few of them.