Two-person zero-sum game

from Wikipedia, the free encyclopedia

A two-person zero-sum game is a zero-sum game with two players in game theory . Zero-sum games are characterized by the fact that the losers 'losses are exactly the same as the winners' profits. Most of the popular games for money such as skat , poker , etc. are examples. If only two players are involved in a zero-sum game, there are no opportunities for cooperative behavior at the expense of third parties. For this reason, two-person zero-sum games represent an easy-to-understand model for game-theoretical strategy and equilibrium concepts that has been regularly examined since the beginning of game theory. As a special feature, the terms Nash equilibrium , equilibrium in Maximin strategies and equilibrium in Minimax strategies coincide.

The terms maximin and minimax strategy are not used uniformly in the literature, however, it should always be stated which conceptual content is associated with it: strategy of the worst possible punishment of the opponent (in this article minimax) or maximization of the worst possible result (in this article Maximin).

The article defines the basic terms and deals with the two central sentences for determining equilibria. The concepts are explained using the examples “Matching Pennies” and “ Scissors, Rock, Paper ”.

Definitions

Play in normal form

To describe a game in normal form (game theory) , one determines which players are involved in the game; this is called the player crowd . A strategy set is assigned to each player . The strategy set contains all strategies from which the player selects a strategy when carrying out the game . Finally, there is a payout function for each player that assigns a payout for players to each strategy combination.

Definition: A game in normal form is a triple , where .

Constant sum game

In a constant sum game, the same payout amount is paid out to all players for every strategy combination, i.e. every game result .

Definition: A game is constant sum game with payout if: .

Constant sum games arise in particular when a fixed amount of resources or a fixed amount of money is divided among the players as a game result.

Zero sum game

Definition: A constant-sum game payout is a zero-sum game if: .

In terms of game theory, there is no essential difference between constant-sum and zero-sum games: A constant-sum game with payout results in an equivalent zero-sum game by assigning any player the amount that he will lose and thus receive after the game begins . The payouts in the game then add up to 0. For this reason, it can be said that the winners 'winnings are equal to the losers' losses.

Two-person zero-sum game

Definition: A zero-sum game is two-person zero-sum game if: .

In two-person zero-sum games, the payout of the second player is already fully determined by the payout of the first player: If you denote the two players with and , that is , the following applies .

It is therefore possible to simplify the definition of a two-person zero-sum game:

Definition: A two-person zero-sum game is a triple where .

The amount of players here is natural ; the payout function relates to player 1, player 2 then has the payout function .

Examples

Two-person zero-sum games, in which each player only has a finite number of strategies, are often represented in the form of a bimatrix or, in simplified form, as a matrix . Each row corresponds to a strategy for player 1, i.e. one element from , and each column corresponds to a strategy for player 2. The payouts and are in the fields of the bimatrix . The bimatrix therefore represents a table of values ​​of the functions and, according to the first definition, a two-person zero-sum game.

Since the payout of player 2 is already clearly defined by the payout of player 1, it is actually sufficient to specify the payout for player 1; this leads to the matrix representation according to the 2nd definition. The matrix is ​​then a table of values ​​for the function .

as a bimatrix
, ,
, ,

In the simplified representation you get:

The matrix of the game is then called the matrix A:

Matching Pennies (A)

In game theory, matching pennies is often viewed as a zero-sum game: two players put a coin on the table at the same time. If both coins are heads (K) or both coins are tails (Z), the two coins belong to player 1; if the two coins show different sides, then the two coins belong to player 2. Since the winner wins the loser's coin, it is a zero-sum game. The following representation results as a bimatrix:

Payout matrix for player 1 and player 2
head number
head 1 , −1 −1 , 1
number −1 , 1 1 , −1

The following matrix is ​​obtained in the simplified representation:

Scissors, rock, paper (B)

" Scissors, stone, paper " is more common in Germany . The strategies in this game are called like the name of the game. This is associated with the idea that the scissors (S) break if you try to cut a stone (St) with them, whereas the scissors cut the paper (P) into pieces without any problems. The paper can be used to wrap the stone. The result is that scissors win against paper, paper against stone and stone against scissors. If both players have the same strategy, there will be a tie. For the game theory treatment, victory with a point gain, draw with 0 and defeat with a loss of points is usually rated.

So the players' strategy amounts are . The set of all possible strategy combinations ( Cartesian product ) is then:

.

In the form of a bimatrix, the game then looks like this:

Payout matrix for player 1 and player 2
scissors stone paper
scissors 0 , 0 -1 , 1 1 , -1
stone 1 , -1 0 , 0 -1 , 1
paper -1 , 1 1 , -1 0 , 0

In the simplified matrix representation, "Scissors, stone, paper" then looks like this:

Further examples (C), (D)

For further discussion the following two games (C) and (D) should be introduced. In example (C) we see a zero-sum game that contains a Nash equilibrium in pure strategies, which is solved in the Solution Concepts section. (D) is the Matching Pennies game in which mixed strategies can be chosen.

Game (C) is also specified first as a bimatrix and then as a matrix.

Payout matrix for player 1 and player 2
Left center Right
Above −2 , 2 0 , 0 −3 , 3
Below 3 , −3 2 , −2 4 , −4

Example (D) shows a game in which the players' strategy sets are not finite; the players' strategy sets are based on the unit interval , i.e. a continuum.

(D) with and .

Equilibrium concepts

The equilibrium concepts are only defined here for two-person zero-sum games .

Nash equilibrium

A central concept of game theory is the best reaction a player can do to an opposing strategy combination. In the 2-player game, this is the answer to the question of which strategy a player uses to maximize his payout when the opponent's strategy is given. The reaction function or reaction correspondence of a player thus indicates for each opposing strategy what the best strategic answer is; the term reaction correspondence is the set of all the best answers to the opponent's strategy.

Definition: The reaction correspondence from player 1 to player 2 is the set- valued function .

Note that the simplified representation minimizes rather than maximizes the definition of a best response for player 2:

Definition: The reaction correspondence from player 2 to player 1 is the set-valued function .

A Nash equilibrium is a combination of strategies in which each player maximizes his payout for the given strategy of the opponent, i.e. each player plays the best reaction to the opponent. For a two-person zero-sum game in normal form, this means the following:

Definition: The combination of strategies is a Nash equilibrium if: .

For the simplified representation, the definition changes to:

Definition: The combination of strategies is a Nash equilibrium if: .

Minimax

One can also assume that the players are essentially interested in keeping their opponent's profit as low as possible. For player 1 this means that he chooses a strategy with the following definition:

Definition: The strategy is a minimax strategy for player 1 if: .

In the simplified representation this becomes:

Definition: The strategy is a minimax strategy for player 1 if: .

This explains why the terms minimax and maximin strategy ( min-max theorem ) are not used uniformly in the literature.

A minimax strategy in the sense of the definition given here is also referred to as a strategy of worst possible punishment. Player 1 can use a minimax strategy to ensure that player 2 receives at most . Since this is a zero-sum game, this means that player 1 wins at least .

For player 2, when using a minimax strategy, he can limit the profit of player 1 to with a minimax strategy . So it applies . If true, one speaks of an equilibrium in minimax strategies.

Maximin

If the players are very pessimistic, they assume that whatever strategy they choose will lead to the most unfavorable outcome for them. You should then try to optimize this minimum result. This leads to the following definition:

Definition: The strategy is a maximin strategy for player 1 if: .

In the simplified representation this becomes:

Definition: The strategy is a maximin strategy for player 1 if: .

If you compare the second definition variant with the definition of a minimax strategy, you can see that there is no difference in two-person zero-sum games.

The definitions of , and the concept of equilibrium are also carried over and agree with the concepts introduced under Minimax; One speaks of an equilibrium in Maximin strategies only if . When there is an equilibrium, it denotes the value of the game. is the win for player 1 and the loss for player 2 if they play the game; the term value of the game refers to the perspective of player 1.

In general, one calls the lower play value and the upper play value of the game.

The fact that there is no difference between minimax and maximin strategies in two-person zero-sum games, combined with the fact that some authors consider the order in which the optimization operators are used, while others consider the order in the typeface to be decisive, and not least The fact that a loss function is often used as a game result instead of a payout means that one cannot rely on the meaning of the terms Minimax and Maximin. Rather, it is crucial whether the choice of strategy is based on the worst possible punishment of the opponent or on minimizing one's own maximum loss. In the field of two-person zero-sum games, however, this distinction is irrelevant.

Relationship between the concepts

The close relationship between minimax and maximin equilibria in two-person zero-sum games is already evident from the definitions. But even the following sentence applies, which ensures the equivalence of all three concepts.

Theorem: In a two-person zero-sum game, the sets of Nash equilibria, the equilibria in minimax strategies and the equilibria in maximin strategies match.

The requirement that it is a two-person zero-sum game is crucial. In general, the terms “best reaction”, “minimax strategy” and “maximin strategy” do not coincide. For the concrete calculation of equilibria in 2 person zero-sum games, the sentence means that it is sufficient to determine the equilibria according to any of the three concepts.

Solution concepts

Finite strategy sets

With a finite set of strategies, the best reactions, minimax and maximin strategies can be found by trial and error. Then you can also try to determine whether it is a balance.

In example (C) and . In the matrix, the best reaction of player 1 to player 2 is indicated by an underline, the best reaction of player 2 to player 1 by a line above the number. So if player 1 plays o, player 2 should answer r, so it gets an overline. The matrix field is also the best reaction for both players and thus a Nash equilibrium. Since there are no other such matrix fields, it is the only Nash equilibrium of this game. In Nash equilibrium, player 1 receives a payout of and player 2 receives a payout of .

For "Matching Pennies" (A), the best reactions look like this:

Neither strategy combination represents a Nash equilibrium, since both never play a best reaction to the opposing strategy.

To determine the maximin strategies for player 1, first determine the line minima ZMin, see last column.

Both line minima are the same size, so that both K and Z represent a maximin strategy for player 1. It applies ; Player 1 can therefore ensure that he does not lose more than 1. For player 2, the column maxima SpMax must be determined in the same way:

For him, too, both strategies are Maximin strategies; it applies . But now there is no equilibrium in Maximin strategies either.

For "scissors, rock, paper" the situation is similar to that for "matching pennies":

The determination of the Maximin strategies also leads to the result that each of his strategies is a Maximin strategy for every player; it also applies here: .

“Matching Pennies” and “Scissors, Rock, Paper” therefore have no equilibrium in the amount of given strategy combinations. Mixed strategies are used to remedy this shortcoming.

Mixed strategies

Definition: A mixed strategy for player 1 in a game is a probability distribution over the set of strategies .

If mixed strategies are allowed for both players, an extended zero-sum game is created in which each player chooses the probabilities for his strategies. For a better differentiation, one describes the strategies from or as pure strategies of the players. These are special mixed strategies in which one strategy has a probability of 1. If one wants to emphasize that no strategy has the probability 1, one speaks of a genuinely mixed strategy.

The payoff for the extended zero-sum game is the expected value that results from assuming that the probability distributions of the players are independent .

For matching pennies this leads to the following expansion to mixed strategies: Let the probability that the player chooses heads. In the event of independence, the following probabilities then result for the various strategy combinations:

The expected value for the payout is then:

.

If you compare this with example (D) you can see that (B) is the expansion of matching pennies to mixed strategies ( ).

If one generally denotes the probabilities that player 1 selects for his pure strategies with and also the probabilities for player 2 with , then one can write as a matrix product; refers to the game's payout matrix:

.

So to find a best response from player 1 to player 2's mixed strategy , the linear optimization problem

be solved     under the constraint     .

Conversely, a best response from player 2 to player 1's mixed strategy can be found by solving the following linear optimization problem:

    .

A maximin strategy (in two-person zero-sum games equivalent to the minimax strategy) for player 1 can be found by solving the following optimization problem:

    under the secondary condition     .

Conversely, for a Maximin strategy of player 2, one has to solve the following optimization problem:

    under the secondary condition     .

The existence of equilibria after the extension to mixed strategies is ensured by the following minimax theorem by John von Neumann (1928):

Theorem: Let it be a real matrix. Then there is a triple such that

and
.

Here, or stand for probability distributions over the rows of , or for probability distributions over the columns of .

Thus every two-person zero-sum game with finite sets of strategies has at least one equilibrium in mixed strategies for both players. Every equally weighted or minimax or maximin strategy of a player forms an equilibrium with every equally weighted or minimax or maximin strategy of the other player (in the expansion of the game to mixed strategies).

Examples (continued)

Matching pennies

For "Matching Pennies" (A) the Maximin strategies for player 1 should now be determined in mixed strategies:

First of all, for each given strategy of player 1, his minimum payout must be determined, which results from optimal behavior of player 2:

.

The following applies:

.

In terms of minimization , it only depends on whether the expression in the last bracket is positive, zero or negative. This expression is positive if . Then the minimum for is reached and amounts to . The expression in brackets is negative if . Then the minimum for is reached and amounts to . The expression in brackets is zero, if , then has no influence on the minimum, then it is always independent of 0.

graphic

This can be written as follows:

The following optimization problem is thus obtained for determining the Maximin strategy for player 1:

.

is strictly monotonically increasing on the interval and strictly monotonically decreasing on the interval ; the maximum of is therefore . So this is the definite Maximin strategy for player 1 in mixed strategies. For reasons of symmetry, there is only one Maximin strategy for player 2, namely .

The value of the game is . Because of the equivalence theorem, this is also the only Nash equilibrium and also the only equilibrium in minimax strategies.

Scissors stone paper

The argument for "scissors, rock, paper" is as follows. If player 1 does not play all three pure strategies with the same probability, then player 2 can ensure that the expected payout from player 1 is negative by choosing a suitable strategy. For example , suppose at least one of the inequalities is strict. In particular, then . If player 2 now plays "stone", the expected payout from player 1 is .

If, on the other hand, player 1 chooses all three probabilities the same , his expected payout is 0 for each mixed strategy of player 2. His expected payout is then:

.

If the probabilities for player 1 are distributed among scissors, stone and paper in a different order of sizes, an analogous argument applies if player 2 plays the strategy with the medium probability.

For each of the different strategies there is a strategy of player 2, which gives player 1 a negative payout. Thus, Player 1's clear Maximin strategy.

For symmetry reasons, this also applies to player 2. So this strategy combination is the only mixed equilibrium and the value of the game is .

literature

  • Avinash K. Dixit Barry J. Nalebuff, Game Theory for Beginners Schäffer Poeschl Stuttgart, (1997)
  • Christian Rieck, game theory. An introduction , Christian Rieck Verlag, (1993), pp. 102-104
  • Diether Coenen, Quasi-zero-sum games and dominated equilibrium points in bimatrix games , Westdeutscher Verlag, (1967)
  • G.Owen, Game Theory , Springer-Verlag, (1971)
  • Morton D. Davis, Game Theory for Non-Mathematicians , Oldenburg Verlag, (1993) pp. 15-35
  • Rauhut, Schmitz, Zachow, game theory , Teubner Stuttgart, (1979)
  • Sylvain Sorin, A First Course on zero-sum Repeated Games , Springer (2002)
  • Thomas Riechmann, Game Theory , Verlag Franz Vahlen, (2002) pp. 63–67
  • Werner Krabs, Game Theory , Teubner Wiesbaden, (2005)

Individual evidence

  1. G. Owen, Game Theory, Springer-Verlag, 1971 p. 11
  2. Holler, Illing, Introduction to Game Theory, Springer, 2008 p.4
  3. ^ Sylvain Sorin, A First Course on Zero-Sum Repeated Games Springer-Verlag, Berlin, Heidelberg, 2002 p. 151
  4. ^ Christian Rieck, Game Theory An Introduction, Christian Rieck Verlag, 1993 p. 80
  5. G. Owen, Game Theory, Springer Verlag, 1971 p. 17
  6. B. Rauhut, N. Schmitz, E.-W. Zachow, Game Theory, Teubner Stuttgart, 1979 p. 138
  7. G. Owen, Game Theory, Springer-Verlag Berlin, Heidelberg, New York, 1997 p. 16
  8. ^ Sylvain Sorin, A First Course on Zero-Sum Repeated Games, Springer-Verlag Berlin, Heidelberg, New York, p. 154