- 1 Bimatrix Game (BG)

- 2 Search for
Equilibrium
- 1 Direct Search Algorithm (DS)
- 2 Necessary and Sufficient Conditions of BG
- 3 Irrelevant Fraud Algorithm (IF)
- 4 Quadratic Strategy Elimination Algorithm (QSE)
- 5 Preventing Corruption

- 3 Matrix Game
- 4 Software Example
- 5 Future Developments

13 Inspection Model

The Nash and Walras models illustrate the competition in economics. Both models define such prices and other production parameters that satisfy the Nash equilibrium. However, the market competition represents only a part of economical and social activities. Another part is the inspection that one needs to provide tax collection, health and environment protection, e.t.c.. We consider a simple model that illustrates the competition between inspector and violator.

1 Bimatrix Game (BG)

and

Here and are probabilities (mixed strategies) of moves and .

In the Bimatrix Game (BG) . In the Quadratic Bimatrix Game (QBG) . We shall consider mainly QBM because they are simpler and represent many real games.

The QBG is Well-defined Quadratic Bimatrix Game (WBG) if it cannot be reduced to a "lesser" game by elimination of a raw or a column. Details are explained by examples.

This game is not well-defined

because it can be reduced to a lesser game by elimination of the third column. Here is the reduced BG:

The reduced game is equivalent to the original one because the third column of the matrix is dominated by the first two columns and will not be used by the second player.

However this reduced game can be reduced further by eliminating the third raw, too:

This QBG is equivalent to the previous BG because the third raw of the matrix is dominated by the first two. That is convenient because solution of QBG is simpler. Therefore we later call such games as Almost Quadratic Bimatrix Games (ABG)

Here is another example of not well-defined game

In this example the third column of is dominated by the first two but the third raw of is not. Thus the original quadratic game is reduced to non-quadratic one by eliminating the third column of .

We denote such games as NBG

Now we shall describe two simple game models.

Consider the ranger-poacher game. Denote by the inspection vector and by the violation vector. Here denotes the inspection probability of the area . means the violation probability in the area . Denote by the inspection payoff function when the object is inspected and the object is violated. Denote by the violation payoff function when the object is inspected and the object is violated. Functions and denote the inspection and violation utility functions using inspection and violation vectors . These vectors define probabilities of inspection and violation.

For example,

and

Here is the probability of detecting the violation if it happens in the area . A number is the probability of completing the violation

Expression (13.5) means that if the violation is completed and
detected^{} then
the inspector premium is equal to the payoff of
violation^{}. Expression
(13.6) shows that if the violation is completed and detected, the
violator payoff is negative. The payoff is positive, if it is
completed and not detected.

The utility functions at given inspection and violation vectors and

and

Here , so the inspection model is a bimatrix game [Forgo et al., 1999]. The matrices (13.3) were defined by (13.5)(13.6) when

, , and .

Consider a security system protecting some object. Denote by , the protection vector and by the violation vector. Here denotes the part of security funds designated to protect the area and means the violation probability of the area . Denote by the security payoff function when the area is protected and the area is violated. Denote by the violation payoff function when the area is protected and the area is violated. Utility functions and denote expected values of security and violation payoff functions using protection and violation vectors . These vectors define the distribution of protection funds and violation probabilities.

Consider examples of simplified payoff functions. We start by defining security payoff function

Here is the expected reward of security team which protects the area for preventing the violation and arresting the violators. Denote by the probability of this event. A number is the value of protected goods. Denote by the probability of completing the violation

The violation payoff function

Here is the penalty of attempted and detected violation where is a large number. The expected profit of successful violation of the protected area is defined as the product and the expected profit of successful violation of the unprotected area is .

Assume for simplicity that probability of protection is equal to the part of security funds . This is the linearizion of the non-linear security function .

Expression (13.9) means that if the violation is completed and
detected^{}
in the area then
the reward of security is equal to the value of the protected
goods . Expression
(13.10) shows that if the violation is detected, the
violator penalty is a large number .
The violetors payoff is equal to the value of stolen goods if the crime in the area is
successfully completed and not detected.

The utility functions at given inspection and violation vectors and

and

Here .

The matrices (13.4) were defined by (13.9)(13.10) when

,
, and

It is well known [Forgo et al., 1999] that, in randomly generated large bimatrix games, the proportion of games having pure strategy equilibriums is defined by the Poisson distribution

That means that roughly two-thirds of randomly generated bimatrix games have at least one equilibrium point in pure strategies. This result holds for general randomly generated bimatrix games

1 Direct Search Algorithm (DS)

Here is a set of maximal elements at each column of the matrix . is a set of maximal elements at each row of the matrix . If equilibrium exists and the intersection is empty, one needs mixed strategies to obtain the equilibrium [Owen, 1968].

For a pair to be an equilibrium point of the bimatrix game , it is necessary and sufficient [Forgo et al., 1999] that there exist real numbers such that satisfies the system

Here denotes the unit vector. The condition (13.18) represents the bilinear problem because it involves products of different variables. The solution of bilinear problems is difficult. Therefore, specific algorithms are developed to search for mixed strategies of the equilibrium. Complementary pivoting is most frequently used [Lemke, 1965] one. The Lemke-Howson algorithm finds a sample equilibrium point of bimatrix game.

Later we shall investigate a simple "Irrelevant Fraud" (IF) algorithm [Mockus, 2000] that follows directly from the Nash equilibrium conditions and is implemented using standard software of linear problems. The conditions when IF provides the Nash equilibrium will be defined. The software for QBG will be described.

3 Irrelevant Fraud Algorithm (IF)

It follows from definition that the mixed strategies and satisfy equilibrium if one cannot obtain greater profit by changing them. From conditions

it follows that

because

and

The idea is to define such mixed strategies that makes the partner fraud irrelevant

and

Expressions (13.19) - (13.23) include inequalities. Therefore, the linear programming (LP) is a convenient method of solution. In LP all the variables are supposed to be nonnegative. Thus, variables and should be expressed as differences of two nonnegative variables and . Then from expressions (13.19) (13.21 (13.23) one obtains this LP problem

Here .

Note, that in WBG the expressions (13.19) - (13.23) and (13.24) - (13.28) satisfy the equilibrium condition (13.18). That remains true in the almost well-defined quadratic bimatrix games (ABG), too.

The IF conditions shows some interesting aspects of Nash equilibrium of quadratic bimatrix games and can be implemented using standard software for linear equations or linear programming that is simple, efficient and widely available.

1 Example-1 ( explicit solution of poaching game)

and

From here and the Irrelevant Fraud expressions(13.19)(13.23)

From here and (13.47)(13.48) follows

In the case from (13.54)

From here

because .

From (13.55)

From here

If then, in the same way, one obtains

In the general case

where means a product of all except . Here the solutions are positive

That shows, that the inspector problem (13.5)(13.6) can be solved by the Irrelevant Fraud (IF) algorithm.

However, the solution of linear inequalities (13.19) - (13.23) and the corresponding LP (13.43) - (13.46) may not exist if the game is not WBG.

Then one searches for the equilibrium using the Direct Search (DS) algorithm (13.14). That complements the IF algorithm (13.44) - (13.46) and defines the equilibrium in pure strategies, if it exists.

4 Quadratic Strategy Elimination Algorithm (QSE)

- obtain a solution of linear equations (13.19) - (13.22), including
inequalities (13.23),

if a solution of the system is found, go to step 7 - search for equilibrium in pure strategies by the Direct Search algorithm (13.14)

if a solution is found, go to step 7 - obtain a solution of linear equations (13.19) - (13.37), ignoring inequalities (13.23)
- reduce the system of linear equations by eliminating the column and the raw if at least one of the corresponding variables is negative or/and , set to zero both the variables and
- if a solution of the reduced system is found, go to step 7
- if the reduced system is not empty, go to step 3
- estimate maximal wins
obtainable assuming
that partners keep solutions

- compare obtained wins
with the maximal ones
,

if and stop, and record the components as equilibrium strategies,

othervise print the note that the equilibrium tests (13.69) and (13.70) failed.

Often the equilibrium is found in NBG, too, but there is no guarantee. However QSE is fast and each solution is tested by conditions (13.69) and (13.70). Therefore one may safely use QSE for NBG as well.

2 Example-2 (numerical solution of poaching game)

and .

Then from (13.5 )(13.6)

There is no IF solution. Ignoring inequalities (13.53) one obtains

There is no DS solution, too. Therefore, following the fourth step of QSE algorithm, the game is reduced setting to zero variables . Then

Here the IF solution and the expected values satisfy the equilibrium conditions as expected because this is ABG.

3 Example-3 (numerical solution of security game)

and .

Then from (13.5 )(13.6)

There is no IF solution. Ignoring inequalities (13.53) one obtains

There is no DS solution, too. Therefore, following the fourth step of QSE algorithm, the game is reduced setting to zero variables . Then

Here the QSE solution

satisfy the equilibrium conditions. Note that this game is NBG so the solution is not guaranteed in general. Therefore the statistical investigation of QSE algorithm in the NBG games would be useful to estimate the expected failure numbers when QSE is applied in NBG.

5 Preventing Corruption

The game will not be played by rules if the players may win more by breaking them. Unauthorized deals (for example, bribes) are usual tools breaking the rules of non-zero-sum games where . An example of such deal is sharing the killed pray between the inspector and violator. Values of the optimal deal are defined by the Nash bargaining conditions [Owen, 1968]

The optimal deal
depends on the set of feasible deals ,

and on max-min values defining what the players will get if the deal fails

Here

is the maximal expected guarantee win of the first player,

is that of the second player.

In the deal the first player gets , the second one obtains .

The optimal deal is uniquely defined by the following assumptions.

- ,
- ,
- if and
,

then , - if and , then ,
- suppose that a set is obtained from by this transformation

, then from follows that , - if , and , then .

where

If the sum of expected wins of both players is restricted by then

and the optimal deal

An obvious way to prevent unauthorized deals is by introducing penalties that makes the deal unprofitable

From (13.85)

Assuming, that the deal is arranged before the game

Here is the maximal expected utility to be divided between the bargaining players.

1 Example-4 (corrupt inspector)

Assume the max-min values to be equal to nearly-equilibrium solution .

Then, from (13.85) the optimal deal

. From (13.87) expected penalties preventing the deal

3 Matrix Game

and

It follows form expressions (13.89) and (13.90) that . Here one obtains the equilibrium by solving two linear programming problems [Owen, 1968]

and

The important feature the zero-sum games is the mini-max condition

An interactive QBG model is implemented using Java JDK1.2 [Vaisnora, 2001].
To start the program , one goes to one of web-sites
(see Section 4) and selects
"Discrete Optimization

Bimatrix Game Problem

Bimatrix Game, an example of bimatrix game optimization using LP,
Java 1.3 and DS and QSE algorithms"

The applet starts by clicking 'index.html'. That is not secure mode thus
all the data is introduced just by screen writing.
Starting by the command line:

'appletviewer -J-Djava.security.policy=java.policy index.html'

one works in secure mode and the data can be introduced by files,
for example:

'environment.txt'

#Wed Feb 18 18:01:29 EET 2004 V_EQUTION=-Pi*10+(1-Pi)*Qj*Gj;i\=j;\nQj*Gj; U_EQUTION=Pi*Gi-(1-Pi)Gi*Qi;i\=j;\n0;\\ DATA_SAVE_URL=file\:/home/jonas/bimatrix/data1.txt DATA_LOAD_URL=file\:/home/jonas/bimatrix/data-1.txt VARIABLES=P G Q RESULTS_SAVE_URL=and

'data.txt'

P G Q 0.1 1.0 0.1 0.2 1.0 0.1 0.3 1.0 0.01

Figure 13.1 shows the input window i 2.4 and 2.4.

Figure 13.2 shows the input window defining the payoff functions of security game (13.9) (13.10)

Figure 13.3 shows the input window including data from the security game examples examples 2.4 and 2.4.

Figure 13.4 shows results obtained by solving IF equations (13.19 - (13.22) ignoring constrains (13.23

Figure 13.5 shows the input data for the reduced QBG obtained by eliminating the last raw and column.

Figure 13.6 shows the IF solution of the reduced QBG

Figure 13.7 shows the snapshot of the calculations^{}

Data is recorded by adding forests and by entering their parameters . To prevent unauthorized deals one enters 'Fine' and 'Fine's probability' defining the average penalties. The optimization starts by clicking the button .

The output window shows average wins in the form of
matrices u[i,j] and v[i,j].

The results of DSA are presented as pairs of
pure strategies, ignoring zero ones,
no DSA solution is found,

The results of IFA shows that there is no IFA solution,
since there are negative parameters, namely .

Following QSE the third raw and the third column are eliminated and the QSE
solution of the reduced QBG
is found.

The utility functions (13.5)(13.6) of both examples are selected to make models easy understandable without any special knowledge. That is important for studies. Most real life applications are described by more complicated utility functions. Therefore, the natural next step is to implement and to investigate these functions.

Statistical estimation of failures applying QSE algorithm for equilibrium search in the not well-defined cases could be useful because QSE is simple and the test by conditions (13.69) (13.70) is easy.

Optimization of resources preventing unauthorized deals (see section 2.5). is a challenging theoretical and practical problem,too.

jonas mockus 2004-03-20