Game Theory Is Useful, Except When It Is Not

Ariel D. Procaccia

Game Theory Is Useful, Except When It Is Not
Nobel prize laureate John Forbes Nash, mathemetician and game theorist, in May, 2005. (China Photos/Getty Images)

The study of strategic interactions is gaining popularity across disciplines, but that does not mean its relevance is universal.

 

Note: This article was originally published on July 8, 2013.

Although game theory is now a household name, few people realize that game theorists do not actually study “games” — at least not in the usual sense of the word. Rather, we interpret a “game” as a strategic interaction between two or more rational “players.” These players can be people, animals, or computer programs; the interaction can be cooperative, competitive, or somewhere in between. Game theory is a mathematical theory and, as such, provides a slew of rigorous models of interaction and theorems to specify which outcomes are predicted by any given model.

Sounds useful, doesn’t it? After all, many people are familiar with one of game theory’s most famous test cases: the Cold War. It is well-known that game theory informed U.S. nuclear strategy, and indeed, the interaction between the two opposing sides — NATO and the Warsaw Pact — can be modeled as the following game, which is a variation of the famous “Prisoner’s Dilemma.” Both sides can choose to either build a nuclear arsenal or avoid building one. From each side’s point of view, not building an arsenal as the other side builds one is the worst possible outcome, because it leads to strategic inferiority and, potentially, destruction. By the same token, from each side’s point of view, building an arsenal while the other side avoids building one is the best possible outcome.

However, if both sides avoid building an arsenal, or both sides build one, neither side has an advantage over the other. Both sides prefer the former option because it frees them from the enormous costs of a nuclear arms race. Strangely enough, though, the only rational strategy is to build an arsenal, whether the other side builds one (in which case you are saving yourself from possible annihilation) or does not (in which case you are gaining the strategic upper hand). This analysis gave rise to the doctrine of MAD: Mutually Assured Destruction. The simple idea is that the use of nuclear weapons by one side would result in full-scale nuclear war and the complete annihilation of both sides. Given that nuclear stockpiling is unavoidable, MAD at least guaranteed that no side could afford to attack the other.

So it would seem that game theory has saved the world from thermonuclear war. But does one really need to be a game theorist to come up with these insights? Game theory tells us, for example, that different forms of stable outcomes exist in a wide variety of “games” and computational game theory gives us tools to compute them. But the type of strategic reasoning underlying Cold War policy does not directly leverage deep mathematics — it is just common sense.

More generally, one can argue that game theory — as a mathematical theory — cannot provide concrete advice in real-life situations. In fact, one of the most forceful advocates of this point is the well-known game theorist Ariel Rubinstein, who claims that “applications” of game theory are nothing more than attaching labels to real-life situations. In an article that rehashes his well-known views, Rubinstein cites the euro zone crisis, which some say is a version of the Prisoner’s Dilemma, to argue that “such statements include nothing more profound than saying that the euro crisis is like a Greek tragedy.” In Rubinstein’s view, game theory is first and foremost a mathematical theory with a “nearly magical connection between the symbols and the words.” By contrast, he contends, for the purpose of application, we should see game theory as a “collection of fables and proverbs” that can provide an interesting perspective on real-life situations but not give specific recommendations.

Michael Chwe, a professor of political science at the University of California, Los Angeles, offers a different take, arguing in his latest book that novelist Jane Austen is, in fact, a game theorist. After describing a scene from Mansfield Park, Chwe writes: “With this episode, Austen illustrates how in some situations, not having a choice can be better. This is an unintuitive result well known in game theory.” Another of Austen’s game-theoretic insights has explicit applications: “When a high-status person interacts with a low-status person, the high-status person has difficulty understanding the low-status person as strategic. … This can help us understand why, for example, after the U.S. invaded Iraq, the resulting Iraqi insurgency came as a complete surprise to U.S. leaders.”

To Chwe, Austen studied the principles of strategic interaction on the level of Rubinstein’s “fables and proverbs.” But if we take his conclusion — this makes Austen a game theorist — this means that these fables and proverbs lie at the core of game theory, rather than at game theory’s periphery, where it interfaces with popular culture. Chwe makes a convincing case that Austen was keenly interested in studying how people manipulate each other — and, indeed, that is one of the things that make Austen a great writer. But that does not necessarily make her a great game theorist.

In fact, as a mathematical and scientific theory, game theory often falls short when it is applied to complex situations like international relations or parliamentary balance of power. However, in some situations, game theory can be useful in the scientific, prescriptive sense. For example, game theory is useful for, well, playing games. Modern software agents that play games like poker (such as the ones from Tuomas Sandholm’s group at Carnegie Mellon University) do in fact use rather advanced game theory, augmented with clever equilibrium-computation algorithms. Game theory actually works better when the players are computer programs, because these are completely rational, unlike human players, who can be unpredictable.

Game theory is also useful for designing auctions. To give a concrete example from my own experience, consider the surprisingly lively Pittsburgh real-estate market, where multiple buyers typically submit simultaneous bids for one house without seeing each other’s offers. The house is sold to the highest bidder, and the price is equal to the highest bid. In this procedure, which is called a first-price auction, buyers try to second-guess each other, and their bids are normally lower than the price they are actually willing to pay.

Suppose that, instead, the seller chooses to sell the house to the highest bidder for a price that is equal to the second-highest bid. This seemingly far-fetched idea is known as the second-price auction. In a second-price auction, one can never benefit from submitting a bid that is different from one’s true value for the house. Indeed, intuitively, a buyer’s bid does not affect the price he pays if he wins, so the buyer’s bid should be no lower than his true value in order to maximize his chances of winning. But bidding a value that is higher than the buyer’s true value will change the outcome only if the second-highest bid is higher than the buyer’s true value (otherwise, the buyer could have won by bidding his true value), in which case the buyer does not want to win the auction, and he overpays. In game-theoretic terms, the second-price auction is incentive compatible.

The beautiful idea underlying the second-price auction has inspired similar insights that guide the design of sophisticated auctions for goods worth billions of dollars, such as rights to transmit over bands of the electromagnetic spectrum. And while this application of game theory seems fundamentally different from playing poker, the two are in fact similar: both involve interactions taking place in closed, controlled environments, where the rules of the game are specified exactly.

But not all of game theory’s success stories are like that. An especially exciting example comes from Milind Tambe’s group at the University of Southern California, a project I have collaborated on. Their work models security situations as a game between a defender (e.g., airport security) and an attacker (e.g., a terrorist organization or a smuggling ring). The defender’s strategy is a randomized deployment of its resources (e.g., cameras, patrols) specifying how likely it is that each of its resources would defend each of the possible targets (e.g., airport terminals).

The defender moves first by committing to a security strategy, which the attacker then observes via surveillance. The attacker must choose which target to pursue knowing the likelihood that it will be defended, but without knowing whether a specific target is defended on the actual day of attack. The defender must therefore anticipate the attacker’s response and commit to a strategy that guarantees the best outcome by deploying resources randomly and broadly. This forces the attacker to be less effective.

Similar game-theoretic models have been around since the 1960s, but it is only in the last decade that researchers have begun to understand the computational aspects of these games. Tambe and his group have gone as far as implementing and deploying algorithms that prescribe a security policy by computing the defender’s optimal strategy. These algorithms are currently in use by the Los Angeles International Airport, the U.S. Coast Guard, and the Federal Air Marshal Service.

These success stories explain game theory’s relevance, but not its huge popularity. The latest edition of a massive open online course (MOOC) on game theory, taught by professors from Stanford and the University of British Columbia, had 130,000 registered students. Are many of these students hoping that game theory will help them in their jobs or their daily lives? If so, they are in for a disappointment. Game theory is typically not useful, but when it is, it shines.

 

 

Share This
About The Author:

Ariel D. Procaccia is assistant professor of Computer Science at Carnegie Mellon University. He writes frequently for the blog Turing’s Invisible Hand.

  • Pingback: Game theory is not useful, except when it is | Turing's Invisible Hand

  • Andrew Gelman

    Is the popularity of game theory really booming? I had no idea. My impression is that game theory peaked in the late 1950s. Two classics from that area are Solar Lottery and Luce and Raiffa’s Games and Decisions. The latter is charming in its retro attitude that all that remained were some minor technical problems that were on the edge of being solved.

    I’ll also plug my own paper from 2008 (most of which was from 1986), “Game theory as ideology: some comments on Robert Axelrod’s ‘The Evolution of Cooperation.’”

    • Helen Fessenden

      A correction from the editor: The article summary has been changed to reflect the latest version of the article. The current version is correct.

    • Ariel Procaccia

      Andrew, as Helen says the choice of words in the article summary is an editorial decision, but I don’t think game theory has peaked in the 1950s. First, in the last decade game theory has become immensely popular in computer science. Every year many hundreds of new papers by computer scientists deal with game theory or other closely related topics at the interface of computation and microeconomics, and this interaction is also making a significant impact (as I explain in the article). Also, the fact that 130,000 students registered for the game theory MOOC shows unprecedented exposure, fueled in part by popular movies and books, e.g., “A Beautiful Mind”.

  • Leo

    “If so, they are in for a disappointment. Game theory is typically not useful, but when it is, it shines.”

    You are wrong. Game theory is very useful for daily decisions, in personal and business settings, and there are plenty of examples of sucessful applications. It is a tool,as any tool, you can’t use it for what it is not designed to. It is not just because you do not know how to apply the tool that you can claim that it is not typically useful. It is!

    Rubinstein is a pure mathematician, he does not know about real world applications. Mathematicians do not need to know how to apply the theory, and there’s no problem with that. But there’s a problem when they generalize their own ignorance about applied mathematics, treating it as evidence as that there’s no room for application.

    See what he respondend when people asked him about the recent Nobel Prize in Game Theory, a pure applied problem. He answered that it is not “real” game theory. If, for him, “real” game theory is the pure abstract model that he does, then, of course, there’s no application with that.

    • Ariel Procaccia

      When Rubinstein said Al Roth’s work on market design is not game theory, it wasn’t because it’s an applied problem. He said it because most of Roth’s recent market design work — which deals with kidney exchange — does not involve incentives at all, but rather focuses on economic efficiency. In fact, I know of only two recent kidney exchange papers (among dozens) that study incentives: One is by Ashlagi and Roth, and the other is by Ashlagi, Fischer, Kash, and yours truly (http://www.cs.cmu.edu/~arielpro/papers/mixnmatch.pdf).

    • Ariel Procaccia

      When Rubinstein said Al Roth’s work on market design is not game theory,
      it wasn’t because it’s an applied problem. He said it because most of
      Roth’s recent market design work — which deals with kidney exchange —
      does not involve incentives at all, but rather focuses on economic
      efficiency. In fact, I know of only two recent kidney exchange papers that study
      incentives; one is by Ashlagi and Roth, and the other is by Ashlagi,
      Fischer, Kash, and yours truly: http://www.cs.cmu.edu/~arielpro/papers/mixnmatch.pdf

      • http://www.franchise-info.ca michael_webster

        Rubinstein is just wrong about Roth’s work on kidney exchanges as applied game theory, but it doesn’t matter.

        Rubinstein is right that people skilled in game theory should not be touted as experts in political relations -as it appears to be the case in Israel.

        One needs only to compare Bob Aumann and Thomas Schelling – Aumann is adept and skilled with game theory, but nobody has written practical work informed by game theory than Schelling. See their Nobel Prize speeches for a demonstration of the difference.

  • Leo

    Yes, and market design is applied game theory in its purest form, in a really useful manner, that can be generalized to all kinds of settings where there is no market, from big problems to small problems (for example, for management inside a business).

    So, “it is particularly useful”.

    • http://www.franchise-info.ca michael_webster

      Apart from Roth’s work on market design, when price doesn’t serve as a sufficient condition to enable trade, there is work on platforms or multi-sided markets where you need the right mix of buyers, sellers and different prices to get a market.

      This is just critical mass modeling.

  • Pingback: Somewhere else, part xxxxx | Freakonometrics

  • Pingback: Links 7/14/13 « naked capitalism

  • http://carolabinder.blogspot.com/ Carola Binder

    I’m an economics graduate student at Berkeley. I recently wrote about how game theory has been used for decades in thinking about and designing central banking institutions, and why that approach is becoming problematic. The post is here: http://carolabinder.blogspot.com/2013/07/divided-fed-broken-models.html

  • Pingback: Symposium Magazine « Pink Iguana

  • mkt42

    “An especially exciting example comes from Milind Tambe’s group at the University of Southern California [...] Similar game-theoretic models have been around since the 1960s”

    Weren’t similar models of attackers and defenders used during WW II, in particular during the Allies’ strategic bombing offensive against Germany? I thought that the methods and models they used helped lay the foundations of both modern game theory and operations research, e.g. they led directly to not just the work of the RAND Corporation, but the founding of the corporation itself.