The Solution of Scalar Bimatrix Games in Preferred Pure Strategies

Game theory is a modern, rapidly developing field of the mathematical theory for making a decision [1,2,3,4]. From the point of view of a mathematical description under the making decision it is meant choosing of u (element) strategy from the definite U set. In this relation it is defined a rule of choosing advisable of u e U element. The complete mathematical theory of making the optimal, (rational, advisable) decisions in case of participation of several individuals (or party) is a “Game Theory”. Theory of Games is defined as a mathematical theory of making decisions of conflict. Content-ly under “conflict we should mean such a phenomenon about which we can say, who and how does he participates in this phenomenon, what kind of results can have this phenomenon, who and how he is interested in these results”. Thus, game theory studies any form of social contradiction - differences of ideas, strategic (nonanta-gonistic and antagonistic), cooperation. In game theory for all these is formed the mechanism of making fair solutions in condition of conflict i.e. the mechanisms for making optimal strategy of conflict.

Traditionally, game theory has been seen as a theory of how rational actors behave [5]. Game theory, the mathematical theory of how to analyse games and how to play them optimally. Although “game” usually implies fun and leisure, game theory is a serious branch of mathematics. Games like blackjack, poker, and chess are obvious examples, but there are many other situations that can be formulated as games. Whenever rational people must make decisions within a framework of strict and known rules, and where each player gets a payoff based on the decisions of all players, we have a game. The theory was initiated by mathematicians in the first half of the last century, but since then much research in game theory has been done outside of mathematics [6].

Game theory is divided into two parts: one is a non-coalitive (as the same as noncooperative, strategic) game theory, and the second is a cooperative game theory. Such division is based on the premise that the main unit of a noncooperative game's analysis is a rational indivi-dual participant, who tries clearly, with defined rules and possibilities to get maximal utility (payoff) from the game independently. If individuals use such actions that can be named as “cooperation” in the ordinary sense of the word then this is because, that such cooperative behavior is in the interest of all individuals: each avoids cooperative breach [ 4 ].

Unlike noncooperative, the main unit of analysis of a cooperative game theory is the group of participants that is, the coalition and if such game is defined, it should be described, what all coalition can achieve without specifyng how it final result will act on concrete coalition. However, suc h divisions should not be considered as seperate and independent theories - divisions only point to two approaches to the same problem.

Strategic theory is strategicaly oriented. Therefore, according to this approach, the players' result depend on their abilities in the game. But the cooperative approach is concerned with the multitude of possible outcomes, not how they can be achieved. Noncooperative theory is a pecular microtheory that provides a detailed description of what is happening in the process of the game. Thus, cooperative theory is a macrotheory compared to noncooperative, the basis of which is the theory of noncooperative games .

At the same time, game theory deals with the modelling of socio-economic processes, and is oriented toward socio-economic applications. Consequently, the methodological and metaphysical aspect is even more essential for game theory than for other branches of mathematics, and demands move careful consideration [3].

A strategic game has two forms of presence. One is a positional form, another one is normal form. We will discuss the game in its normal form. There is no dynamics in them; each player makes only one decision (makes one move), and all players make decisions simultaneously and independently from each other, however none of them knows what decisions have made or will make their partners. Therefore, such game is static game, where the player's strategy and move are the same. The difference can only arise in dinamic (inclu-ding positional) games. In general, a player's strategy in game theory is to plan his action throughout the game, taking into account all the information recieved.

Definition 1.1. A normal (or strategic) form of a noncooperative game is called triple (model)

Г =< N ,{ S J i ^ N ,{ H i } i _e N > , (1)

where n = {1,..., n} is a set of players, i.e. each player has its own number; S i is i e N player's set of pure strategies (moves) and h : S = П S ^ R1 is i e N i e N player's function of payoff (utility func-tion). This function to every s = (Sj,..., sn) set of the players strategies that is called the game's result, i.e. situation, i.e. profile, matches this player's payoff (utility) -H(s), i e N, that is a numerical value in our case.

S ( i = 1,..., n ) can be any set of nature - the set from

R ⁿ , the set of measurable function and so on.

If there are two players participate in the (1) game, i.e. the set of players' n = {1,2}, and their sets of strategies are finite and they respectively are S = {1,..., m} and S2 = {1,..., n}, there exists at least one situation (i, j) e S, x S where the payoffs sum of players' is not zero - H, (i, j) + H2 (i, j) * 0, we get two players strategy game, called m x n bimatrix game.

In m x n bimatrix game in the role of solution, Nash equilibrium situation is used, that always exists in pure or mixed strategies. In pure strategies its finding is easy, but if there doesn’t exist any of them it is necessary to find an equilibrium situation in mixed strategies that always exists. Its finding is also necessary in that case, if there exists an equilibrium situation in pure strategies. But this statement doesn’t give us the possibility of finding an equilibrium situation in mixed strategies. That causes a certain complexities especially when m >  2 or (and) n >  2, but finding such situation for 2x2 game is easier and available for everybody. Methods of their solution and algorithms are studied and also are being studied we will talk about them below. Our approach to the solution of a bimatrix game is different and it will be discussed in the present article.

• II.    Solution of Bimatrix Games in Equilibrium Situations

In bimatrix game the players' interest may be diametrically opposed, as well their interest may partially coincide. Designate the players' functions of payoff H_x = A = ( a^ ), H₂ = B = ( b_tj ) and from (1) thus received bimatrix game let be г ( A , B ) (or ( A , B ) bimatrix game), that will be written payoff's seperately A and B matrices, or by one matrix that is composed by the pairs of players' payoffs:

A =

Г ^a 11

| a 21

.

| a m1

^a 12

^a 22

( A , B ) = 2

m

a 1 n ^         < b11     b12    •••    b 1 n^

a 2 n I           I   ^Ь 21      ^Ь 22     “‘     ^Ь 2 n I

M —*

. I • BI a              b b... mn              m1m2

(a11, b11)     (a12, b12)    .    (a1n, b1n)

( a ₂₁, b ₂₁)     ( a ₂₂, b ₂₂)    .    ( a _{2 n} , b _{2 n} ) .

....

( a   , b )    ( a , b )    .   ( a , b )

m 1 m 1         m 2 m 2             mn mn

In (2) payoff's A and B matrices may be nume-ral or other elements of nature (for example vectorial , their comparison is being produced by a lexicographic rule [7]). In the first case we have scalar bimatrix game. Both types of games are very topical with their theoretical and practical values. There are many scientific papers dedicated to solving their studies nowadays, but there are a lot of problems in such games and it is imposible to complete them. In this article we will only discuss the problems of solving the first types of games with some point of view ( In this paper we will study only the question about the solution of scalar bimatrix games with certain opinions).

Consider m x n bimatrix game Г ( A , B ) with A and

B matrices of scalar payoff. It will have following form:

	1	2	. n
1	( a 11 , b 11 )	( a 12, b 12)	.     ( a 1 n , b 1 n )
( A , B ) = 2	( a 21, b 21)	( a 22 , b 22 )	.   ( a 2 n , b 2 n ).      (3)
. m	. ( a , b ) m 1 , m 1	. ( a , b ) m 2 , m 2	.. .    ( a , b ) mn , mn

As we mentioned, in the strategic (1) game and therefore in (3) bimat-rix game in the role of solution Nash equilibrium (or shortly equilibrium ) situation is considered. Define it in (3) game.

Definition 2.1. The situation (i* , j* ) in (3) game is called an equilibrium, if the following inequalities are fulfilled a . . > a . , V i = 1,..., m ;(4)

i jij

• b. . > b. , Vj = 1,..., n . ijij

Therefore, in order the situation ( i ^* , j ^* ) in (3) bimatrix game be an equilibrium, it is necessary a must be the biggest in A matrix j ^* column an b -the biggest in the B matrix i ^* row.

The equilibrium situation in the (3) game may not exist in pure strategies and the equilibrium situation in the mixed strategies always exists according to the Nash theorem. Define an equilibrium situation in mixed strategies.

Like matrix games, in the given (3) г ( A , B ) game let's note the first and the second player's mixed strategies ^note respectively P = ( p 1 ,..., p m ) T and Q = ( q , ,..., q n ) ^T .

In (P, Q) situation the player's mixed payoffs (average payoffs, expected payoffs, expected utilities) respectively are equal mn

v ⁽ A ) = A ( P , Q ) = ^^ a u xty j = P T AQ ,     ⁽⁵⁾

• - = 1 j = 1

mn

• - = 1 j = 1

Definition 2.2. In Г ( A , B ) game, the situation ( P ^* , Q ^* ) is called an equilibrium in mixed strate-gies, if for V P , V Q strategies the following inequali-ties are fulfilled:

P T AQ >  P T AQ , P BQ >  P BQ .  (6)

Bimatrix games unlike matrix games have many types of characteristics. For example, if in matrix game every situation of equilibrium (both pure and mixed strategies) gives the players one and the same payoffs, bat in bimatrix game in different kinds of equilibrium situations (both in pure and mixed) the players match the different payoffs. Therefore sometimes it is not possible to determine accurately the expecting payoff's meaning. One reason for this is the lack of a linc between players and payoffs a and b . Because of this one side's influence weakens over the other, therefore the players only focus on their payoffs independently from their partners. Such behavior can put the other side in a difficult position. However, sometimes such independence, deceive and betray can be expensive for the player. Also, Nash theorem asserts that in any bimatrix game there exists at least one equilibrium situation in mixed strategies, does not give the ways of finding the equilibrium situation in mixed strategies.

• III.    Related Works

Finding an equilibrium situation in bimatrix games is an important problem, that is solved by different algorithms - Vorob'ev [ 8 ], Kuhne [ 9 ] and Mangasarian [ 10 ]. For n player's case there are algorithms for Lemke - Howson [1 1 ] and Rosenmuller [1 2 ] for noncoalition (1) games. All of these algorithms are quite complex and can not be used by students. It is relatively easy to solve a bimatrix 2 x 2 game, for it a graphical method is used. This requires elmentary actions. 2 x 2 bimatrix games simulate many simple social - political situations. In particular, their usage have been studied in a teaching organization [1 3 ,1 4 ]. A lot of needs however, require the resolution of more dimensional games, for which algorithm K. Lemke [1 5 ] is formed.

In addition to the listed algorithms, different met-hods and algorithms are used to find Nash equilibrium in bimatrix games. For example in Savani's doctoral thesis [1 6 ] the methods of calculating the equilibrium in a bimatrix game are studied. Besides in the same thesis an extension of the standard version of Lemke's algorithm is studied, that allous one more freedom than before when starting the algorithm.

Also in doctoral thesis [1 7 ] geometric methods and algorithms are used for the analysis of bimatrix games. A lexicographically perturbed game is studied.

• IV.    Principles Of Dominance In Scalar Bimatrix Games

All of the listed algorithm need to solve bimatrix games contain a very complex mathematical apparatus and is very difficult to use. So we tried to discuss different approaches to solve this problem.

Firstly, note that in the strategic game each player's task is to make a prediction other players' behavior. At first the player discusses which strategy not to use. So we have to find some way of compearing of two strategies. Obviously, none of the players will choose a strategy, if another strategy brings him more payoff. Therefore the simpliest and the most natural principle to compare strategies with, is the principle of dominance.

Therefore, we will discuss below the dominance and some of the basic principles, that help us to choose optimal strategies in any finite dimensional bimatrix game.

First of all, consider the problem of domination in bimatrix game. In order to do this we have to deter-mine the pure strategies' the strict dominance and weak dominance.

Definition 4.3 (strict dominance). In the bimatrix Г ( A , B ) game (3): the first player's i_x strategy (line) strictly dominates on i strategy (line), if the following inequalities are fulfieled:

% >  ^a i₂j ^{, V} j = ^1,...^, n ; ⁽⁷⁾

Second player's j strategy (column) strictly dominates on the j strategy (column), if the following inequalities are fulfielled:

b >  b , V i = 1,..., m . (8) ij ₁ ij ₂ ^{, , ,}

If in the inequalities (7) at least one inequality is not strict, than i strategi nonstrictly dominates on i strategy. Also if in the inequalities (8) at least one inequality is not strict, than j strategy nonstrictly dominates on j strategy.

In the case of both strict and weak domination, we would say that we are dealing with domination.

If there is an equilibrium in the given game in pure strategies, then it gives a pretty reasonable prediction of the players' actions. This is not the case in every game. Sometimes it is possible to make predictions with sequential dominance procedure. Consider this procedure based on the following example.

Example 4.1. 3 x 3 bimatrix game г ( a , в ) is given

s	t 1	t 2	t 3	(9)
	(1,2)	(2,1)	(1,0)
( A , B ) =   1			.
s 2	(0,5)	(1,2)	(7,4)
s 3	( - 1,1)	(3,0)	(5, 2)

In this game we have one equilibrium situation in pure strategies (1,1). The 1st player has no preffered strategy, that is, none of the line items is more or equal to the other line items.The 2nd player's t strategy is strictly dominated the t strategy. Therefore, if it is rational, it certainly will not play t . If the 1st player knows that the 2nd player is rational, then he excludes choosing t by the 2nd player. Therefore the 1st player determines the 3 x 2 game:

	t 1	t 3	(10)
( A , B ) = 5 1	(1,2)	(1,0)
s 2	(0,5)	(7,4)
s 3	( - 1,1)	(5,2)

If the 1st payer is rational and knows that the 2nd player is rational too, then the 1st player will not choose s , because it is strictly dominated by s strategy. By the second player's point of wiew

	t 1	t 3
( A , B ) = 5 1	(1,2)	(1,0) .	(11)
s 2	(0,5)	(7,4)

The second player will not play strictly dominated t column, i.e. he will always play t . In order to do this he must be sure that the first knows the 2nd player's rationality. If the 1st player is sure that the 2nd will not play t , then the game will have the following form

( A , B ) = 5 ,

t ₁

(1,2)

s ₂    (0,5)

Here the 1st player has to play s and wins 1, the 2nd one wins 2. So in the Г ( A , B ) game we have a predi ction, that the 1st will choose s strategy and the 2nd will choose t strategy. Such predictio led us to the equilibrium (1,1) situation. That means, the players interaction in the game is repeated for many times.

Hence, in the given game we have eliminated the sequential of strictly dominated strategies. In this case the question arises: Has such line got sense for the maintenance of not dominated strategies? It turned out that in the case of strictly dominance such line has no sense.

Weak dominated strategies can be excluded as in the case of strictly dominated ones. But in this case we have one important difference. In particular, that remain in the end may depend on the number of exclu-ded strategies. So, consider the game t1t2

( A , B ) = 5 ,

(1,1)   (0,0).

(1,1)    (2,1)

s ₃   (0,0)   (2,1)

At first exclude s , that is weakly dominated by s . We have the game

( A , B ) = s 2

s ₃

t ₁            t ₂

(1,1)   (2,1).

(0,0)   (2,1)

Solution. (mixed strategy) In matrix A = ( ²   0 | game,

10   1J the firs't maximin mixed strategy is X» J12j   but

1 3,3 J *

Here t is weakly dominated t :

v ( a ) = ² The second player's maximin mixed strategy

	t 2
( A , B ) = s 2	(2,1)
s 3	(2,1)

т I 1 ⁱⁿ B^t = I

I 0

T

0 j                      2  1

I game is у ⁰ = I — — I but the value of

2 ]                   I 3,3 J ’

The players' payoff in the given game are (2,1).

From the very beginning let's exclude s , that is weakly dominated by s , we will have the game

a game v ( b^t ) = -

In the given bimatrix г ( A , B ) game there are two Nash's equilibrium situations in pure strategies -  (1,1)

and (2,2) with players payoffs respectively (2,1) and (1,2). In mixed strategies we have only one equilibrium

(A, B) = s 1 t1 t (0,0). (16) (1,1) s2 (1,1) (2,1) situation *  *

are v ( a ) = -, v ( в ) = -.

TT

| ²¹ j I ¹² j | and the players payoff

( 3,3 J ’ 1 3,3 J I

V                    J

Now if we exclude weakly dominated t strategy, then we will have the game

( A , B ) = s ₂

s ₃

t ₁

(1,1)

(1,1)

and the payoffs will be (1,1).

Note, that in г ( A , B ) game each player primarily has his own interest in order to do so he can act different principles in addition to Nash equilibrium principle. Therefore let's discuss some of this kind of principles.

V. Orientation Principle On Guaranted Levels

The first player independently from the second player's action can get guaranted - maximin average payoff, that will be equal of the A matrix game's v ( A ) value. Likewise, the second player can get guaranted - maximin average payoff from the first player's action independently, that will be equal of B ^T matrix game's v ( B^T ) value. By considering B ^T matrix game we change places: The first player will become the second player, but the second player will be the first. The values v ( A ) and v ( B ^T ) represent some levels of satisfaction for the players.

Example 5.1. Define the players satisfaction levels in г ( A , B ) game, we consider as "Battle of the sexes" model

Hence, the players payoffs are reduced in mixed strategies than the payoffs in pure strategies. The players maximin and equilibrium situations in mixed strategies are different, bat payoffs are the same in the process of using the both principls.

Let's find out which of the following mixed strategies are more reliable in terms of average payoff's. That the Nash equilibrium is stable, is finally certain. Therefore let's consider I Principle - Orientation on quaranted levels.

Let's say, the 2nd player predicts his partner the 1st player in  г (A, B) game will use the maximin у о (1 2 j strategy. In this case, if the 2nd player will X       I ,

13  3 J use the first pure strategy (the first column), i.e. if the situation (X 0 ,1) will be chosen, then the 1st and the 2nd player will respectively win

v . ( X ⁰,1) = 2 ■- + 0 ■- = -

1    33

v , ( X 0 ,1) = 1 ■-+ 0 ■- =

2     ₃₃

2 ,             (19)

.

But in ( X ⁰ ,2) situation the 1st and the 2nd player will respectively win

( A , B ) = 1

(2,1)   (0,0) ^.

(0,0)   (1,2)

v, (X °,2) = 0 •1 + 1 • 2 = 2,

1        333

v2 (X ^2) = 0 ■-+ 2 ■-=

2       333

According to this it is preferred for the 2nd player to use the second pure strategy against maximin X ⁰

strategy, he will win 4 much more than it was in the 3, equilibrium situation 2

We can  repeat the same by using maximin

Y о = f 2 1)  strategy by the 2nd player. At this time, in к3,3J the case of using first pure strategy by the 1st player, the players win respectively

• v. (1, Y °) = 2 ■- + 0 •   = -,

• 1       333

v ₂ (1, Y °) = 1 •- + 0 •- = -.

• 2               3       33

If the 1st player will choose the second pure strategy, then they will win respectively

• v, (2, Y °) = 0 • 2 + 1 •1 = 1,

• 1        333

v ₂ (2, Y °) = 0 ■-+ 2 •-= -.

2        333

Therefore, for the 1st player it is preferred to use its first pure strategy against Y ⁰ strategy.

If both players discuss the same in the process of using I principle, they will lead to (1,2) situation, where the players payoffs are 0 and 0. Besides, the situation (1,2) is not equilibrium in Nash's opinion.

Let's note that one of the players, who plays by equilibrium mixed strategy, fails to predict the intention of his partner, who will use maximin mixed strategy. Specifically, let's assume that the 2nd player plays by

T equilibrium mixed y * = | 1 2 | strategy, but the 1 st к 3,3 J player uses maximin mixed v = f 12) strategy. Than к 3,3 J we have the situation (X 0 , Y * ), where the players' payoff are

• v , ( X °, Y ') = 2, v ₂( X °, Y *) = 1.      (23)

• ^{1                     3}

Now let's say, the 1st player uses an equilibrium mixed

T

X * = | 2 11 strategy, but the 2nd player - maximin к 3,3 J mixed       Y - = f 2 1)         strategy.        Than к 3,3 J

• v , ( X *, Y °) = 1, v ₂ ( X Y °) = ². We get the similar

situation of the previous case - the 1st player cannot predict the 2nd player's intention and uses the equilibrium mixed strategy, but the 2nd player uses maximin mixed strategy. The 1st player remains the winner by using an equilibrium strategy.

• VI. Conclusion

Beside an equilibrium principle for solution bimatrix Г ( A , B ) games in pure strategies two other principles are studied. One of them is the dominance principle of comparing pure strategies - in strictly dominance case the line of dominance has no meaning in order to maintain an equilibrium situation in pure strategies. By weakly dominance procedure we may not be able to get an equilibrium situation. The second principle is the usage the preferred pure strategies that is based on making a prediction by the player about his partner’s behavior. Such preferred strategies are defined in concrete situations based on guaranteed levels. As a guaranteed level the player can get maximum average payoff, that is gained from the matrix of his payoffs by using maximin mixed strategy. If in a bimatrix game we do not have an equilibrium situation in pure strategies and by one player’s prediction his partner will use maximin mixed strategy, then it is preferable for him to use a concrete pure strategy against mixed pure strategy because of it he will gain much more, than in an equilibrium situation. In the case if both players argue then they will come to nonequilibrium situation in pure strategies and will gain less. If one player plays by an equilibrium mixed strategy, he cannot make prediction on his partner’s decision and if this partner will use maximin mixed strategy, then the player by using an equlibrium mixed strategy will be the winner. The principles of analisys are not sufficient to find preferred pure strategies. We think that, it will be more interesting for the future to study the task of finding the most preferred mixed strategies.