Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

A zero-sum game

A zero-sum game, also known as a zero-sum game or zero-sum game, is a non-cooperative game as opposed to a non-zero-sum game. A zero-sum game is a game in which the sum of the benefits of all players is zero or a constant, meaning that if one player gains, the others lose.

In a finite zero-sum game, different game theories such as Nash equilibrium and minimum-maximum algorithms give the same solution. The player has to use a mixed strategy. Examples of zero-sum games are gambling, futures, and voting.

Pure strategy Nash equilibrium

In the complete information game, if only one specific strategy can be selected for each given information, this strategy is pure strategy. Pure strategy is a special case of mixed strategy. The return of pure strategy can be expressed by utility, while the return of mixed strategy can only be expressed by expected utility.

In the complete information game, the player can only choose the only definite strategy in the strategy space. How can the player choose his own strategy to get better returns in the game

Expression of a zero-sum game


G = { S 1 . S 2 ; A } G = \{ S_1,S_2; A \}

In a two-person non-cooperative game, the strategy sets of two middle players, A and B, are S1S_1S1 and S2S_2S2


S 1 = { A 1 . A 2 . A 3 } S 2 = { B 1 . B 2 . B 3 } \begin{aligned} S_1 = \{A_1,A_2,A_3\}\\ S_2 = \{B_1,B_2,B_3\}\\ \end{aligned}

Return matrix


B 1 B_1
B 2 B_2
B 3 B_3

A 1 A_1 		6, – 6 – 1, 1 0, 0

A 2 A_2 		3,-3 1,-1 2, – 2

A 3 A_3 		– 3, 3 0, 0 – 1, 1

Player A’s payoff matrix is A


[ ( 6 . – 6 ) ( – 1 . 1 ) ( 0 . 0 ) ( 3 . – 3 ) ( 1 . – 1 ) ( 2 . – 2 ) ( – 3 . 3 ) ( 0 . 0 ) ( – 1 . 1 ) ] \ begin {bmatrix} (6, 6) & (1, 1) and (0, 0) \ \ (3, 3) & (1, 1) and (2, 2) \ \ (3, 3) & (0, 0) and (1, 1) {bmatrix} \ \ \ end

A = [ 6 – 1 0 3 1 2 – 3 0 – 1 ] A= \begin{bmatrix} 6 & -1 & 0\\ 3 & 1 & 2\\ -3 & 0 & -1\\ \end{bmatrix}

How should players choose their own strategies to ensure that they gain a favorable position in the game

  • Take the minimum value for each row of the matrix and the maximum value within the minimum value


max ⁡ 1 Or less j Or less 3 min ⁡ 1 Or less i Or less 3 = { – 1 . 1 . – 3 } = 1 = a 22 \ max_ {1 \ le j \ le 3} \ min_ I \ {1 \ le le 3} = \ {1, 1, 3 \} = 1 = a_ {and}

  • Take the maximum value of each column of the matrix, and take the minimum value of the maximum

The return matrix has the saddle point element, a22a_{22}a22 saddle point element


min ⁡ 1 Or less j Or less 3 max ⁡ 1 Or less i Or less 3 = { 6 . 1 . 2 } = 1 = a 22 \ min_ {1 \ le j \ le 3} \ max_ I \ {1 \ le le 3} = \ 6,1,2 \ {} = 1 = a_ {and}