What Is Game Theory?

It is a branch of applied mathematics that deals with the analysis of situations involving parties (called players) that make interdependent decisions. The formal origin of game theory can be attributed to mathematician John von Neumann and economist Oskar Morgenstern. In their book, The Theory of Games and Economic Behavior (1944), they asserted that game theory is better suited to describe economic behavior than physical sciences.¹ But the seeds for the discipline could be found alongside the emergence of probability theory back in 1654.²

What Does a Game Theory Problem Look Like?

Just like a game can be described by its characteristics of the number of players (1,2…n players), information sharing between players (perfect or imperfect), and conflict of interest between players (constant sum or variable sum), game theory problems and the subsequent approaches can be distinguished by the underlying parameters.

The following is a classic example of a two-player constant sum game with imperfect information – i.e. two competing candidates in an election must decide on how to react to a pressing issue to maximize their vote share. Each candidate can choose to support, oppose, or evade the issue. Depending on what each candidate chooses, the payoff matrix looks like this:

Candidate 1

Table 1: Payoff matrix for two-player constant sum game with imperfect information

The rational decision both players should choose involves maximizing their own vote share against any and every action of the opponent. This can simply be achieved using either the minimax or maximin approach.

Here is the solution using the minimax approach: For Candidate 2, the minimum vote that can be achieved for each action is 20% (Support), 25% (Oppose), and 30% (Evade). The maximum of those is 30% (corresponding to evasion). The rational decision for this candidate would be to evade the issue. Similarly, for Candidate 1 the rational decision would be to oppose the issue.

This type of solution is called a saddle-point, where the maximum of the column is the minimum of the row (or vice-versa). It derives its name from the shape of a saddle and while it may or may not exist in the game of imperfect information, it always exists in games of perfect information. In the game of perfect information, payoff at this point is the value of the game.

The Nash Equilibrium

Another aspect that can drastically affect the outcome or the strategies chosen by the players is whether the game is cooperative or not. Cooperative game theory describes (at a high level) the structure, strategies, and payoffs of coalitions in cooperative games.⁴ For non-cooperative games, the Nash equilibrium defines a strategy profile, a set of strategies (one for each player) so that no player can do better by unilaterally changing their strategy given that the strategy of other players is fixed.

Formally, let S_i  be the set of all possible strategies for player i, where i = 1,…,N . Let s^⃰ = (s^⃰_i ,s^⃰_-i) be a strategy profile, a set consisting of one strategy for each player, where  s^⃰_-I  denotes the  N-1  strategies of all the players except  i . Let u_i(s^⃰_i ,s^⃰_-i)  be player i’s payoff as a function of the strategies. The strategy profile s^⃰  is a Nash equilibrium if

u_i(s^⃰_i ,s^⃰_-i)  ≥  u_i(s_i ,s^⃰_-i)  Ɐ s_i ϵ S_i ⁵

If the equality doesn’t hold, the strategy profile is known as a strict Nash equilibrium; otherwise, it is termed a weak Nash equilibrium.

Modern Applications

Game theory is used in conjunction with a variety of other disciplines; the applications depend on the complexity of the problem. Some of the most notable ones are:

1. Price wars in oligopoly markets.
2. Analyzing and designing political campaigns (as seen in the example in this article).
3. Auction algorithms and analysis. These are extensively used for ad bidding by search engines. This is an example of algorithmic game theory.
4. Cost-sharing algorithms and analysis. These are commonly used in building inter-community resources.
5. A flights assignment model based on zero-sum sequential game and CDM mechanisms.⁶
6. Dynamic pricing strategies for demand-side management in smart grids.⁷

References:

1. Encyclopedia Brittanica: Game Theory
2. Apostal, Tom M. Calculus, Volume II “A Short History of Probability”
3. Example of Saddle Point
4. Wikipedia: Cooperative Game Theory
5. Wikipedia: Nash Equilibrium
6. Liu, Junqiang. Flights Assignment Model of Multiple Airports Based on Game Theory and CDM Mechanism
7. Srinivasan, et al. Game-Theory based dynamic pricing strategies for demand side management in smart grids

Authored By: Aishwarya Kukrety, Analyst at Absolutdata