Game theory

Theory of Games and Economic Behavior
Theory of Games and Economic Behavior
Theory of Games and Economic Behavior, published in 1944 by Princeton University Press, is a book by mathematician John von Neumann and economist Oskar Morgenstern which is considered the groundbreaking text that created the interdisciplinary research field of game theory. In the introduction of its 60th anniversary commemorative edition from the Princeton University Press, the book is described as "the classic work upon which modern-day game theory is based." The book is based on prior research by von Neumann, published in 1928 under the German title "Zur Theorie der Gesellschaftsspiele" ("On the Theory of Parlor Games"). The derivation of expected utility from its axioms appeared in an appendix to the Second Edition (1947). Von Neumann and Morgenstern used objective probabilities, supposing that all the agents had the same probability distribution, as a convenience. However, von Neumann and Morgenstern mentioned that a theory of subjective probability could be provided, and this task was completed by Johann Pfanzagl in 1967.

• The Essay topic: Game Theory
• Class:4IT496 Simulation of Systems (WS 2014/2015)
• Author: Kristýna Gubišová

The beginning of the mathematical game theory was originated in 1944, when the book called The Game Theory and Economic Behavior by mathematician John von Neumann and economist Oskar Morgenstern was written and published by Princeton University Press. Game theory is a discipline of the applied mathematics, that analyzes the spectrum of conflict decision situations, that may occur, wherever there is a conflict of interests. Game theory models try to analyze these conflict situations and by building a mathematical model of the conflict and computing are trying to find the best strategies for specific parties of the conflict

Game theory is a branch of, originally, applied mathematics, used mostly in economics and political science, a little bit in biology, that gives us a mathematical taxonomy of social life and it predicts what people are likely to do and believe others will do in cases where everyone's actions affect everyone else. That's a lot of things: competition, cooperation, bargaining, games like hide-and-seek, and poker.

Basic concepts

The basis of most mathematical models of the game theory is the assumption of rationality. Every each player acts such that he maximizes its profit (its win).

• The player based on stable preferences sets objectives and strategies to elect the most efficient possible to achieve these objectives.
• The player is confronted by a number of situations and he is able to sort them according to their preferences from the most advantageous to the least advantageous.

The assumption of rationality (of each player) is the factor which distinguishes the game theory from the theory of decision.

This alignment must be complete, ie. must cover all situations and transitive, ie. if a player prefer the situation A before the situation B and situation C, and must prefer the situation A before the situation C. Based on the preferences of the situation is derived utility function of player. The sole objective of the player is then maximize the value of the utility function.

Games in Extensive Form

Types of games

All the games that we are considering in this chapter have certain things in common and these are:

• There is a finite set of players assumed (who may be people, groups of people holding the same opinion, or more abstract entities like computer programs or “nature” or “the house”). The least possible number of players is 2.
• Number of applied strategies may be finite and infinite. For endless strategy plays a role timing of moves. (for game theory consider games with a finite number of strategies)
• Winning types are divided into games with constant sum and games with non-constant sum.
• Each player has complete knowledge of the rules of the game.
• At different points in the game, each player has a range of choices or moves. This set of choices is finite.
• The game ends after a finite number of moves.
• After the game ends, each player receives a numerical payoff. This number may be negative, in which case it is interpreted as a loss of the absolute value of the number. For example, in a game like chess the payoff for winning might be +1, for losing -1, and for a draw 0.

In addition, the following are properties which a game may or may not have:

• There may be chance moves. In a card game, the dealing of the hands is such a chance move. In chess there are no chance moves.
• In some games, each player knows, at every point in the game the entire previous history of the game. This is true of tic-tac-toe and backgammon but not of bridge (because the cards dealt to the other players are hidden). A game with this property is said to be of perfect information. Note that a game of perfect information may have chance moves. Backgammon is an example of this because a die is rolled at points in the game.

It has been just said that the players receive a numerical payoff at the end of the game. In real conflict situations, the payoff is often something nonquantitative like "happiness", "satisfaction", "prestige", or their opposites. In order to study games with such psychological payoffs, it is first necessary to replace these payoffs with numerical ones.

• A week in Paris.
• A week in Hawaii.
• Eight hours in a dentist‘s chair.

Different people would assign different “happiness ratings” to these prizes. For a person with an interest in French culture, rating them as 100, 25, -100, respectively, might be reasonable. To a surfer, the ratings might be 10, 100, -100. The point is that we are assuming that this conversion of nonquantitative payoffs to numerical ones can always be done in a sensible manner.

Normal form game

Game in the normal form is defined by set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ Q, X_1, ..., X_n, u_1 (x_1,...X_n),..., u_n (x_1,..., x_n) \}}

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q = \{1,..., n\}} are involved players, sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1,...,X_n} are sest of strategies and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u_i(x_1,..., x_n)} are winnings of the player Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} for individual strategies. The normal form game is usually represented as a matrix.

The game for two players in normal form is shown below:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}t_1 & t_2 & t_t \end{matrix}\\ pl. 1, \begin{matrix}\mbox{s 1}\\\mbox{s 2}\\\mbox{s k}\end{matrix} \begin{pmatrix}u_{11} & u_{12} & ... u_{1t} \\u_{21} & u_{22} & ... u_{23} \\u_{k1} & u_{k2} & ... u_{kt} \end{pmatrix}}

Here the player number 1 chose from strategies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_1,..., s_k} and the player number 2 chose from strategies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_1,..., t_t} . There is an assumption that this is a zero-sum game, and in this game apllies:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u_1(s_i,t_j) = -u_2(s_i,t_j)}

and therefore there is need to write only the value of the prize (utility function) for one player.

Example of the enrolment of the unspecified game:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}t_1 & t_2\end{matrix}\\\\ player 1 \begin{matrix}\mbox{s1}\\\mbox{s2}\end{matrix} \begin{pmatrix}2 & 3\\3 & 4\end{pmatrix}}

Example of the rock-paper-scissors rock-paper-scissors game:

Rock paper scissors scheme

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}R & P & S \end{matrix}\\ pl. 1, \begin{matrix}\mbox{R}\\\mbox{P}\\\mbox{S}\end{matrix} \begin{pmatrix}0 & 1 & -1 \\-1 & 0 & 1 \\1 & -1 & 0 \end{pmatrix}}

Normal form describes possible strategies and winnings of each player and allows the study of the question of optimal strategies. If there is interested in finding a way appropriate strategies there is need to use enrollment of the games in explicit form.

Explicit form game

Explicit form of the game is used for the formalization of these games, in which plays a role the order of moves. These games are represented as trees. Each node represents the place where one player chooses stroke and each edge corresponds to a possible move.

NIM game in explicit form

The enrolment of the game NIM in explicit form shown below. In this game of two players at the beginning there are two stacks of two matches. Players are taking turns and they are taken from one of the piles either one or two matches. The player who removes the last match lose the game.

There are two true sentences: Every game in explicit form can be transferred to just one game in normal form For each game in normal form can be found more games in explicit form.

Optimal strategies

Antagonistic games

The goal of every rational player is to win the game, other words to maximize their winnings. Consider the only strategy antagonistic games between two players that are written in normal form.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}t_1 & t_2 & t_t \end{matrix}\\ pl. 1, \begin{matrix}\mbox{s 1}\\\mbox{s 2}\\\mbox{s k}\end{matrix} \begin{pmatrix}u_{11} & u_{12} & ... u_{1t} \\u_{21} & u_{22} & ... u_{23} \\u_{k1} & u_{k2} & ... u_{kt} \end{pmatrix}}

This matrix reflects values of the player number 1 winnings. This player chooses between these strategies (rows Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} of matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u (s_i, t_j)} ) so that his winnings are maximal.

Also he knows that his opponent, player number 2 will choose its strategy to minimize winnings of the player number 1. Player number 1 chooses a strategy s*, for which the minimum value of his winning (in this row) will be the maximal one from all lines.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s*= max_i, min_j u (s_i, t_j)}

The player number 2 progresses analogously. Between its strategies (column j and matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u (s_i, t_j)} ) he chooses the strategy t*, for which the maximal value of his looses (in this column) will be the minimal one from all columns.

I applies that: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle max_i min_j u (s_i, t_j) \leq < min_j max_i u (s_i, t_j)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle max_i min_j u(s_i, t_j)} is called the lower price of the game

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle min_j max_i u(s_i, t_j)} is called the upper price of the game

Definition: Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s*, t*) = max_i min_j u(s_i, t_j) = min_j max_i u(s_i, t_j)} , there u Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (s*, t*)} i called saddle point of the matrix and presents the price of the game.

Game theory tries to find the equilibrium point in every game, where players chooses strategies. Players chooses such strategies and anyone of them does not have the reason to change its strategy assuming, that nobody else does not change the strategy. If there is a point of equilibrium, optimal strategies of both players are called pure strategy

Example with the equilibrium point:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}t_1 & t_2\end{matrix}\\\\ player 1 \begin{matrix}\mbox{s1}\\\mbox{s2}\end{matrix} \begin{pmatrix}2 & 3\\3 & 4\end{pmatrix}}

For this normal form game, the equilibrium point takes a form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (s_2, t_1)} . For the player number 1 is min Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s_1, t_j) = 2} and minFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s_2,t_j) = 3} and then max min Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u (s,t) = u(s_2, t_1)} what corresponds to strategy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_2} . For the player number 2 is max Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s_i, t_1) = 3} and max Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s_i, t_2) = 4} and then mina max Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u(s,t) = u(s_2,t_1)} what corresponds to strategy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_1} .

Example with saddle point:

Sometimes the equilibrium point and then the pure strategy does not exist. In the game shown by the matrix below:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle player 2 - \begin{matrix}t_1 & t_2\end{matrix}\\\\ player 1 \begin{matrix}\mbox{s1}\\\mbox{s2}\end{matrix} \begin{pmatrix}11 & 5\\7 & 9\end{pmatrix}}

The player number 1 chooses strategy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_2} , because the for him Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle min_j, u_{ij}} the biggest element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u_{21} = 7} . The player number 2 chooses strategy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_1} , because for him Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle max_i, u{ij}} the smallest element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u{21}=9} . In this case the lower price of the game is less than the upper price of the game.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle max_i, min_j, u(s_i, t_j) < min_j, max_i u(s_i, t_j).}

This game does not have the equilibrium point a that is why there are no pure strategies.

Definition: Where there is matrix game described of this matrix:

Non-antagonistic games

In the case of non-antagonistic games the winning of one player is not at the expense on the other one. Players can (cooperative games) or can not (non-cooperative games) negotiate about their strategies.