Algorithmic Game Theory

Article excerpt

Game theory is a branch of mathematics devoted to studying interaction among rational and self-interested agents. The field took on its modern form in the 1940s and 1950s (von Neumann and Morgenstern 1947; Nash 1950, Kuhn 1953), with even earlier antecedents (such as Zermelo 1913 and von Neumann 1928). Although it has had occasional and significant overlap with computer science over the years, game theory received most of its early study by economists. Indeed, game theory now serves as perhaps the main analytical framework in microeconomic theory, as evidenced by its prominent role in economics textbooks (for example, Mas-Colell, Whinston, and Green 1995) and by the many Nobel prizes in economic sciences awarded to prominent game theorists.

Artificial intelligence got its start shortly after game theory (McCarthy et al. 1955), and indeed pioneers such as von Neumann and Simon made early contributions to both fields (see, for example, Findler [1988], Simon [1981]). Both game theory and AI draw (nonexclusively) on decision theory (yon Neumann and Morgenstern 1947); for example, one prominent view defines artificial intelligence as "the study and construction of rational agents" (Russell and Norvig 2003), and hence takes a decision-theoretic approach when the world is stochastic. However, artificial intelligence spent most of its first 40 years focused on the design and analysis of agents that act in isolation, and hence had little need for game-theoretic analysis.

Starting in the mid to late 1990s, game theory became a major topic of study for computer scientists, for at least two main reasons. First, economists began to be interested in systems whose computational properties posed serious barriers to practical use, and hence reached out to computer scientists; notably, this occurred around the study of combinatorial auctions (see, for example, Cramton, Shoham, and Steinberg 2006). Second, the rise of distributed computing in general and the Internet in particular made it increasingly necessary for computer scientists to study settings in which intelligent agents reason about and interact with other agents. Game theory generalizes the decision-theoretic approach, which was already widely adopted by computer scientists, and so was a natural choice. The resulting research area, fusing a computational approach with game theoretic models, has come to be called algorithmic game theory (Nisan et al. 2007). This field has grown considerably in the last few years. It has a significant and growing presence in major AI conferences such as the International Joint Conference on Artificial Intelligence (UCAI), the Conference of the Association for the Advancement of Artificial Intelligence (AAAI), and International Conference on Autonomous Agents and Multiagent System (AAMAS), and in journals such as Artificial Intelligence (AIJ), the Journal of Artificial Intelligence Research (JAIR) and Autonomous Agents and MultiAgent Systems (JAAMAS). It also has three dedicated archival conferences of its own: the ACM Conference on Electronic Commerce (ACM-EC), the Workshop on Internet and Network Economics (WINE), and the Symposium on Algorithmic Game Theory (SAGT).

It is necessary to distinguish algorithmic game theory from a somewhat older and considerably broader research area within AI--multiagent systems (Weiss 1999; Vlassis 2007; Wooldridge 2009; Shoham and Leyton-Brown 2009; Vidal 2010). While multiagent systems indeed encompasses most game-theoretic work within AI, it has a much wider ambit, also including nongame-theoretic topics such as software engineering paradigms, distributed constraint satisfaction and optimization, logical reasoning about other agents' beliefs and intentions, task sharing, argumentation, distributed sensing, and multirobot coordination.

Algorithmic game theory has received considerable recent study outside artificial intelligence. The term first gained currency among computer science theorists, and is now used beyond that community in networking, security, learning, and operating systems. …