Algorithmic Game Theory

By Elkind, Edith; Leyton-Brown, Kevin | AI Magazine, Winter 2010 | Go to article overview

Algorithmic Game Theory

Elkind, Edith, Leyton-Brown, Kevin, AI Magazine

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. …

The rest of this article is only available to active members of Questia

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

Project items include:
  • Saved book/article
  • Highlights
  • Quotes/citations
  • Notes
  • Bookmarks
Cite this article

Cited article

Citations are available only to our active members.
Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25,

Note: primary sources have slightly different requirements for citation. Please see these guidelines for more information.

Cited article

Algorithmic Game Theory


Text size Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Full screen

matching results for page

    Questia reader help

    How to highlight and cite specific passages

    1. Click or tap the first word you want to select.
    2. Click or tap the last word you want to select, and you’ll see everything in between get selected.
    3. You’ll then get a menu of options like creating a highlight or a citation from that passage of text.

    OK, got it!

    Cited passage

    Citations are available only to our active members.
    Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

    1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25,

    New feature

    It is estimated that 1 in 10 people have dyslexia, and in an effort to make Questia easier to use for those people, we have added a new choice of font to the Reader. That font is called OpenDyslexic, and has been designed to help with some of the symptoms of dyslexia. For more information on this font, please visit

    To use OpenDyslexic, choose it from the Typeface list in Font settings.

    OK, got it!

    Cited passage

    Thanks for trying Questia!

    Please continue trying out our research tools, but please note, full functionality is available only to our active members.

    Your work will be lost once you leave this Web page.

    Buy instant access to save your work.

    Already a member? Log in now.

    Author Advanced search


    An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.