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)

1 Quadratic Bimatrix Game (QBG)

There are two players. The payoff function of the first player is expressed by a matrix $u(i,j)$ where $i=1,...,m$ denote moves (pure strategies) of the first player and $j=1,...,n$ represent moves of the second one. The payoff of the second player is $v(i,j)$. The utility functions $U$ and $V$ of the first and second players are defined as expected values of the payoffs $u(i,j)$ and $v(i,j)$.

$$\begin{eqnarray}U(x,y)= \sum_{i,j} x_i u(i,j) y_j, \end{eqnarray}$$

and

$$\begin{eqnarray}V(x,y)=\sum_{i,j} x_i v(i,j) y_j. \end{eqnarray}$$

Here $x=(x_i,\ i=1,...,m)$ and $y=(y_j,\ j=1,...,n)$ are probabilities (mixed strategies) of moves $i$ and $j$.

In the Bimatrix Game (BG) $u(i,j) \ne v(i,j)$. In the Quadratic Bimatrix Game (QBG) $m=n$. 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

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{ccc} 0.1 & 0.0 & 0.0\\ 0.0 ... ...\\ 1.0 & 0.6 & 0.1 \\ 1.0 & 1.0 & 0.04 \end{array}\Bigg \vert \end{eqnarray}$$

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

$$\begin{eqnarray}u_1(i,j)=\Bigg \vert \begin{array}{ccc} 0.1 & 0.0 \\ 0.0 & 0... ...0 \\ 1.0 & 0.6 \\ 1.0 & 1.0 \end{array}\Bigg \vert \nonumber \end{eqnarray}$$

The reduced game is equivalent to the original one because the third column of the matrix $v(i,j)$ 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:

$$\begin{eqnarray}u_2(i,j)=\Bigg \vert \begin{array}{cc} 0.1 & 0.0 \\ 0.0 & 0.... ...{cc} 0.8 & 1.0 \\ 1.0 & 0.6 \end{array}\Bigg \vert \nonumber \end{eqnarray}$$

This QBG is equivalent to the previous BG because the third raw of the matrix $u_1(i,j)$ 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

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{ccc} 0.1 & 0.0 & 0.0\\ 0.0 ... ... 0.1 & 0.08 & 0.01 \\ 0.1 & 0.1 & 0.007 \end{array}\Bigg \vert \end{eqnarray}$$

In this example the third column of $v(i,j)$ is dominated by the first two but the third raw of $u(i,j)$ is not. Thus the original quadratic game is reduced to non-quadratic one by eliminating the third column of $v(i,j)$.

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{ccc} 0.1 & 0.0 & 0.0\\ 0.0 ... ... \\ 0.1 & 0.08 \\ 0.1 & 0.1 \end{array}\Bigg \vert \nonumber \end{eqnarray}$$

We denote such games as NBG

Now we shall describe two simple game models.

2 Poaching Game

Consider the ranger-poacher game. Denote by $x=(x_1,...,x_m),\ x_i \ge 0,\ \sum_i x_i=1$ the inspection vector and by $y=(y_1,..,y_m),\ y_j \ge 0,\ \sum_j y_j =1$ the violation vector. Here $x_i$ denotes the inspection probability of the area $i$. $y_j$ means the violation probability in the area $j$. Denote by $u(i,j)$ the inspection payoff function when the object $i$ is inspected and the object $j$ is violated. Denote by $v(i,j)$ the violation payoff function when the object $i$ is inspected and the object $j$ is violated. Functions $U(x,y)$ and $V(x,y)$ denote the inspection and violation utility functions using inspection and violation vectors $x,y$. These vectors define probabilities of inspection and violation.

For example,

$$\begin{eqnarray}u(i,j)&=&\cases {p_i g_i q_i, &if $i=j$\ \cr 0, &otherwise,\cr} \end{eqnarray}$$

and

$$\begin{eqnarray}v(i,j)&=&\cases {-q_j p_i g_j + (1-p_i) q_j g_j, &if $i=j$\ \cr q_j g_j, &otherwise.\cr} \end{eqnarray}$$

Here $p_i$ is the probability of detecting the violation if it happens in the area $i$. A number $q_i$ is the probability of completing the violation if violation occurs in the area $i$ and $g_i$ is the payoff of the completed violation in the area $i$.

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 $x$ and $y$

$$\begin{eqnarray}U(x,y)= \sum_{i,j} x_i u(i,j) y_j, \end{eqnarray}$$

and

$$\begin{eqnarray}V(x,y)=\sum_{i,j} x_i v(i,j) y_j. \end{eqnarray}$$

Here $u(x,y) \ne v(x,y)$, so the inspection model is a bimatrix game [Forgo et al., 1999]. The matrices (13.3) were defined by (13.5)(13.6) when
$p_1=0.1,\ p_2=0.2,\ p_3=0.3$, $g_i=1,\ i=1,,,.3$, and $q_1=q_2=1.0,\ q_3=0.1$.

3 Security Game

Consider a security system protecting some object. Denote by $x=(x_1,...,x_m)$, $x_i \ge 0,\ \sum_i x_i=1$ the protection vector and by $y=(y_1,..,y_m),\ y_j \ge 0,\ \sum_j y_j =1$ the violation vector. Here $x_i$ denotes the part of security funds designated to protect the area $i$ and $y_j$ means the violation probability of the area $j$. Denote by $u(i,j)$ the security payoff function when the area $i$ is protected and the area $j$ is violated. Denote by $v(i,j)$ the violation payoff function when the area $i$ is protected and the area $j$ is violated. Utility functions $U(x,y)$ and $V(x,y)$ denote expected values of security and violation payoff functions using protection and violation vectors $x,y$. These vectors define the distribution of protection funds and violation probabilities.

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

$$\begin{eqnarray}u(i,j)&=&\cases {p_i g_i - (1-p_i)g_i q_i, &if $j=i$\ \cr 0, &if $j \ne i$,\cr} \end{eqnarray}$$

Here $p_i g_i$ is the expected reward of security team which protects the area $i$ for preventing the violation and arresting the violators. Denote by $p_i$ the probability of this event. A number $g_i$ is the value of protected goods. Denote by $q_i$ the probability of completing the violation in the area $i$. Suppose that the expected penalty for bad protection is defined as the product $(1-p_i)g_i q_i$. The payoff function of security team protecting area $i$ is zero, is no violation happens in this area $i \ne j$.

The violation payoff function

$$\begin{eqnarray}v(i,j)&=&\cases {- p_i b + (1-p_i) q_i g_i, &if $j=i$\ \cr q_j g_j, &if $j \ne i$.\cr} \end{eqnarray}$$

Here $-p_i b$ is the penalty of attempted and detected violation where $b$ is a large number. The expected profit of successful violation of the protected area $i$ is defined as the product $(1-p_i) q_j g_j$ and the expected profit of successful violation of the unprotected area $j$ is $q_j g_j$.

Assume for simplicity that probability of protection $p_i$ is equal to the part of security funds $x_i$. This is the linearizion of the non-linear security function $p_i=p_i(x_i)$.

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

The utility functions at given inspection and violation vectors $x$ and $y$

$$\begin{eqnarray}U(x,y)= \sum_{i,j} x_i u(i,j) y_j, \end{eqnarray}$$

and

$$\begin{eqnarray}V(x,y)=\sum_{i,j} x_i v(i,j) y_j. \end{eqnarray}$$

Here $u(x,y) \ne v(x,y)$.

The matrices (13.4) were defined by (13.9)(13.10) when
$p_1=0.1,\ p_2=0.2,\ p_3=0.3$, $g_i=1,\ i=1,,,.3$, and $q_1=q_2=0.1,\ q_3=0.01$

2 Search for Equilibrium

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

$$\begin{eqnarray}e^{-1}/( k!) \end{eqnarray}$$

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)

A simple way to obtain equilibrium in pure strategies is the Direct Search Algorithm (DS). The set $IJ$ of equilibrium points in pure strategies is the intersection of two sets $I$ and $J$ defined by the following conditions

$$\begin{eqnarray}IJ=I \cap J, \\ I=\cup_j I(j),\ J= \cup_i J(i)\\ I(j), \subseteq arg\ max_i\ u(i,j)\\ J(i), \subseteq arg\ max_j\ v(i,j). \end{eqnarray}$$

Here $I(j)$ is a set of maximal elements at each column of the matrix $u(i,j)$. $J(i)$ is a set of maximal elements at each row of the matrix $v(i,j)$. If equilibrium exists and the intersection $IJ$ is empty, one needs mixed strategies to obtain the equilibrium [Owen, 1968].

2 Necessary and Sufficient Conditions of BG

For a pair $(x^0,y^0)$ to be an equilibrium point of the bimatrix game $(A,B)$, it is necessary and sufficient [Forgo et al., 1999] that there exist real numbers $\alpha^0,\beta^0$ such that $(x^0,y^0,\alpha^0,\beta^0)$ satisfies the system

$$\begin{eqnarray}xAy-\alpha=0, \\ xBy-\beta=0, \nonumber\\ Ay-\alpha I \le 0, \no... ... I \le 0, \nonumber\\ x \ge 0,\ y \ge 0, \ Ix=1, Iy=1. \nonumber \end{eqnarray}$$

Here $I$ 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 $x$ and $y$ satisfy equilibrium if one cannot obtain greater profit by changing them. From conditions

$$\begin{eqnarray}\sum_{j=1}^m u(i,j) y_j = U,\ i=1,...,m ,\\ \sum_{i=1}^m v(i,j)... ... \\ \sum_{i=1}^m x_i = 1, \\ x_i \ge 0,\ y_j \ge 0,\ i,j=1,...,m. \end{eqnarray}$$

it follows that

$$\begin{eqnarray}\sum_{i=1}^m \sum_{j=1}^m x_i u(i,j) y_j = U,\ i=1,...,m ,\\ \s... ...\ \sum_{i=1}^m x_i ^0= 1, \\ x_i \ge 0,\ y_j \ge 0,\ i,j=1,...,m. \end{eqnarray}$$

because

$$\begin{eqnarray}\sum_{i=1}^m x_i \sum_{j=1}^m u(i,j) y_j = U,\ i=1,...,m ,\\ \s... ... \\ \sum_{i=1}^m x_i = 1, \\ x_i \ge 0,\ y_j \ge 0,\ i,j=1,...,m. \end{eqnarray}$$

and

$$\begin{eqnarray}\sum_{i=1}^m x_i U= U,\ i=1,...,m ,\\ \sum_{j=1}^m y_j V= V,\ j... ... \\ \sum_{i=1}^m x_i = 1, \\ x_i \ge 0,\ y_j \ge 0,\ i,j=1,...,m. \end{eqnarray}$$

The idea is to define such mixed strategies that makes the partner fraud irrelevant. Therefore, if the solution $x,y$ of (13.19), (13.21, (13.23) exists one obtains the equilibrium just by setting

$$\begin{eqnarray}x^0 = x, \end{eqnarray}$$

and

$$\begin{eqnarray}y^0 = y. \end{eqnarray}$$

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 $U$ and $V$ should be expressed as differences of two nonnegative variables $U=u_1-u_2$ and $V=v_1-v_2$. Then from expressions (13.19) (13.21 (13.23) one obtains this LP problem

$$\begin{eqnarray}\max_{x,y,u,v} (u_1-u_2+v_1-v_2),\\ \sum_{j=1}^m u(i,j) y_j = u_... ...\ge 0,\ i,j=1,...,m, u_1 \ge 0,\ u_2 \ge 0, v_1 \ge 0, v_2 \ge 0. \end{eqnarray}$$

Here $x=(x_1,...,x_m),\ y=(y_1,...,y_m),\ u=(u_1,u_2),\ v=(v_1,v_2)$.

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)

Suppose that $q_i=g_i=1$. Then from (13.5 )(13.6)

$$\begin{eqnarray}u(i,j)&=&\cases {p_j, &if $i=j$\ \cr 0, &otherwise,\cr} \end{eqnarray}$$

and

$$\begin{eqnarray}v(i,j)&=&\cases {- p_i + (1-p_i), &if $i=j$\ \cr 1, &otherwise.\cr} \end{eqnarray}$$

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

$$\begin{eqnarray}\sum_{j=1}^m u(i,j) y_j= U,\ i=1,...,m ,\\ \sum_{i=1}^m v(i,j) ... ... \\ \sum_{i=1}^m x_i = 1, \\ x_i \ge 0,\ y_j \ge 0,\ i,j=1,...,m. \end{eqnarray}$$

From here and (13.47)(13.48) follows

$$\begin{eqnarray}p_j y_j = U,\ j=1,...,m \\ \sum_{i \ne j} x_i +(1-2p_j) x_j =V,... ...\\ \sum_j y_j=1,\ \sum_i x_i=1,\ y_j \ge 0,\ x_i \ge 0 \nonumber \end{eqnarray}$$

In the case $m=2$ from (13.54)

$$\begin{eqnarray}p_1 y_1=U, \\ p_2 y_2=U. \end{eqnarray}$$

From here

$$\begin{eqnarray}y_1=p_2/(p_1+p_2), \\ y_2=p_1/(p_1+p_2), \end{eqnarray}$$

because $p_1+p_2=1$.
From (13.55)

$$\begin{eqnarray}(1-2p_1)x_1+x_2=V , \\ x_1+(1-2p_2)x_2=V. \end{eqnarray}$$

From here

$$\begin{eqnarray}x_1=p_2/(p_1+p_2) , \\ x_2=p_1/(p_1+p_2). \end{eqnarray}$$

If $m=3$ then, in the same way, one obtains

$$\begin{eqnarray}y_1=x_1=p_2 p_3/(p_1p_2+p_1p_3+p_2p_3), \\ y_2=x_2=p_1 p_3/(p_1p_2+p_1p_3+p_2p_3),\\ y_3=x_3=p_1 p_2/(p_1p_2+p_1p_3+p_2p_3). \end{eqnarray}$$

In the general case

$$\begin{eqnarray}y_i=x_i= \prod_{k \ne i}p_k /(\sum_i \prod_{k \ne i} p_k) , \end{eqnarray}$$

where $\prod_{k \ne i} p_k$ means a product of all $p_k$ except $p_i$. Here the solutions are positive

$$\begin{eqnarray}x_i > 0,\ y_j >0,\ i,j=1,...,m. \end{eqnarray}$$

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)

The quadratic strategy elimination algorithm includes both IF and DS algorithms. In addition it eliminates irrelevant raws and columns:

1. obtain a solution $(x^*,y^*)$ of linear equations (13.19) - (13.22), including inequalities (13.23),
   if a solution of the system is found, go to step 7
2. search for equilibrium in pure strategies by the Direct Search algorithm (13.14)
   if a solution is found, go to step 7
3. obtain a solution $(x^*,y^*)$ of linear equations (13.19) - (13.37), ignoring inequalities (13.23)
4. reduce the system of linear equations by eliminating the column $j=k$ and the raw $i=k$ if at least one of the corresponding variables is negative $y_k \le 0$ or/and $x_k \le 0$, set to zero both the variables $y_k=0$ and $x_k=0$
5. if a solution of the reduced system is found, go to step 7
6. if the reduced system is not empty, go to step 3
7. estimate maximal wins $U_{max},V_{max}$ obtainable assuming that partners keep solutions $(x^*,y^*)$
   $$\begin{eqnarray}U_{max}=\max_x \sum_{i,j} x_i u(i,j) y_j^* , \\ V_{max}=\max_y \sum_{i,j} x_i^* v(i,j) y_j . \end{eqnarray}$$
   
   
   
   

8. compare obtained wins $U^*, V^*$ with the maximal ones $U_{max},V_{max}$ ,
   if $U^* \ge U_{max}$ and $V^* \ge V_{max}$ stop, and record the components $x_i^* >0,\ y_j^**>0$ as equilibrium strategies,
   othervise print the note that the equilibrium tests (13.69) and (13.70) failed.

1 QSE and Equilibrium conditions

QSE algorithm stops if DS or IF solution is obtained. In the DS case an equilibrium is found by definition. The same is true for IF solution of WBG. That remains true for IF solutions of ABG because here original QBG are reduced to lesser QBG.

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)

Suppose that $g_1=g_2= g_3=1$,
$q_1=q_2=1,\ q_3=0.1$ and $p_1=0.1,\ p_2=0.2,\ p_3=0.3$.
Then from (13.5 )(13.6)

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{ccc} 0.1 & 0.0 & 0.0\\ 0.0 ... ... 1.0 & 0.6 & 0.1 \\ 1.0 & 1.0 & 0.04 \end{array}\Bigg \vert. \end{eqnarray}$$

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

$$\begin{eqnarray}x_1=3.31 x_2=1.66 x_3 =-3.97 \\ y_1=0.21 y_2=0.10 y_3=0.69 \end{eqnarray}$$

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

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{cc} 0.1 & 0.0 \\ 0.0 & 0.2 \... ...egin{array}{cc} 0.8 & 1.0 \\ 1.0 & 0.6 \end{array}\Bigg \vert. \end{eqnarray}$$

Here the IF solution $x_1= 2/3,\ x_2=1/3,\ y_1= 2/3,\ y_2= 1/3$ and the expected values $U=0.067,\ V=0.867$ satisfy the equilibrium conditions as expected because this is ABG.

3 Example-3 (numerical solution of security game)

Suppose that $g_1=g_2= g_3=1$,
$q_1=q_2=0.1,\ q_3=0.01$ and $p_1=0.1,\ p_2=0.2,\ p_3=0.3$.
Then from (13.5 )(13.6)

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{ccc} 0.0 & 0.0 & 0.0\\ 0.0 ... ... 0.1 & 0.08 & 0.01 \\ 0.1 & 0.1 & 0.07 \end{array}\Bigg \vert. \end{eqnarray}$$

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

$$\begin{eqnarray}x_1=6.414 x_2=3.207 x_3 =-8.621 \\ y_1=1.0 y_2=0.0 y_3=0.0 \end{eqnarray}$$

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

$$\begin{eqnarray}u(i,j)=\Bigg \vert \begin{array}{cc} 0.0 & 0.0 \\ 0.0 & 0.1 \... ...in{array}{cc} 0.09 & 0.1 \\ 0.1 & 0.08 \end{array}\Bigg \vert. \end{eqnarray}$$

Here the QSE solution

$$\begin{eqnarray}x_1=1/3\ x_2=2/3\ x_3 =0 \\ y_1=1.0\ y_2=0.0\ y_3=0.0 \end{eqnarray}$$

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 $v(i,j) \neq -u(i,j)$. An example of such deal is sharing the killed pray between the inspector and violator. Values of the optimal deal $(\bar{u},\bar{v})$ are defined by the Nash bargaining conditions [Owen, 1968]

The optimal deal $(\bar{u},\bar{v})$ depends on the set of feasible deals $D$,
and on max-min values defining what the players will get if the deal fails

$$\begin{eqnarray}u^*=max_x\ min_y U(x,y), \nonumber \\ v^*=max_x\ min_y V(x,y). \end{eqnarray}$$

Here
$u^*$ is the maximal expected guarantee win of the first player,
$v^*$ is that of the second player.
In the deal the first player gets $\bar{u}$, the second one obtains $\bar{v}$.
The optimal deal $(\bar{u},\bar{v}) =\phi(D,u^*,v^*)$ is uniquely defined by the following assumptions.

1. $(\bar{u},\bar{v}) \ge (u^*,v^*)$,
2. $(\bar{u},\bar{v}) \in D$,
3. if $(u,v) \in D$ and $(u,v) \ge (\bar{u},\bar{v})$,
   then $(u,v)= (\bar{u},\bar{v})$,
4. if $(\bar{u},\bar{v}) \in T \subset D$ and $(\bar{u},\bar{v}) =\phi(D,u^*,v^*)$, then $(\bar{u},\bar{v})=\phi(T,u^*,v^*)$,
5. suppose that a set $D'$ is obtained from $D$ by this transformation
   $u'=a_1 u+ b_1,\ v'=a_2 v + b_2$, then from $\phi(D,u^*,v^*)=(\bar{u},\bar{v})$ follows that $\phi(D',a_1 u+ b_1,\ a_2 v + b_2)=(a_1 u+ b,\ a_2 v + b_2)$,
6. if $(u,v) \in D \Leftrightarrow (v,u) \in D$, $u^*=v^*$ and $\phi(D,u^*,v^*)=(\bar{u},\bar{v})$, then $\bar{u}=\bar{v}$.

If there is a pair $(u,v) \in D$, such that $u > u^*,\ v> v^*$, then the optimal deal

$$\begin{eqnarray}(\bar{u},\bar{v})= arg\ max_{u,v} (u-u^*)(v-v^*), \end{eqnarray}$$

where

$$\begin{eqnarray}(u,v) \in D,\ u \ge u^*, \ v \ge v^* \end{eqnarray}$$

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

$$\begin{eqnarray}D=\{(u,v): u+v \le c\}, \end{eqnarray}$$

and the optimal deal

$$\begin{eqnarray}(\bar{u},\bar{v})=\nonumber \\ ((c+u^*-v^*)/2,\ (c+v^*-u^*)/2) \end{eqnarray}$$

An obvious way to prevent unauthorized deals is by introducing penalties $(w_1,w_2)$ that makes the deal unprofitable

$$\begin{eqnarray}(w_1,w_2) \ge (\bar{u} - u^*, \bar{v}-v^*) \end{eqnarray}$$

From (13.85)

$$\begin{eqnarray}w_i \ge c-u^*-v^*,\ i=1,2. \end{eqnarray}$$

Assuming, that the deal is arranged before the game

$$\begin{eqnarray}c=\max_i\ g_i q_i \end{eqnarray}$$

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

1 Example-4 (corrupt inspector)

Suppose that in the case of inspector game (2.4) the sum of expected wins is restricted by $c=\max_i\ g_i q_i=1$.
Assume the max-min values to be equal to nearly-equilibrium solution $u^8=U=0.067, v^*=V=0.867$.
Then, from (13.85) the optimal deal
$(\bar{u}, \bar{v})=(0.1,0.9)$. From (13.87) expected penalties preventing the deal
$w_i \ge 0.0467,\ i=1,2$

3 Matrix Game

In some special cases, the Inspector problem is reduced to the Matrix Game. It is well known [Owen, 1968] that equilibrium is defined as two linear programming problems, if $v_{ij}=-u_{ij}$. One reduces utilities (13.5) and (13.6) to the zero-sum case by subtracting the penalty terms $(1-p_i) q_j g_j$ and $q_i g_i$ from the inspectors utilities. In such a case

$$\begin{eqnarray}u(i,j)&=&\cases {p_i g_i q_i -(1-p_i) q_j g_j, &if $i=j$\ \cr - q_i g_i, &otherwise,\cr} \end{eqnarray}$$

and

$$\begin{eqnarray}v(i,j)&=&\cases {-q_j p_i g_j + (1-p_i) q_j g_j, &if $i=j$\ \cr q_j g_j, &otherwise.\cr} \end{eqnarray}$$

It follows form expressions (13.89) and (13.90) that $v_{ij}= -u_{Ij}$. Here one obtains the equilibrium by solving two linear programming problems [Owen, 1968]

$$\begin{eqnarray}\max_x \ U, \\ \sum_{i=1}^m x_i u_{ij} \ge U,\ j=1,...,m, \nonu... ... \ge 0, \nonumber \\ U=u_1-u_2,\ u_1 \ge 0,\ u_2 \ge 0, \nonumber \end{eqnarray}$$

and

$$\begin{eqnarray}\min_y\ V, \\ -\sum_{j=1}^m y_j u_{ij} \le V, \ i=1,...,m, \non... ... \ge 0, \nonumber\\ V=v_1-v_2,\ v_1 \ge 0,\ v_2 \ge 0. \nonumber \end{eqnarray}$$

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

$$\begin{eqnarray}\min_y\ V = \max_x \ U. \end{eqnarray}$$

4 Software Example

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.1: The input window.

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

Figure 13.2: Specification of payoff functions.

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

Figure 13.3: The input data of the original QBG.

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

Figure 13.4: The IF results of the original QBG ignoring constrains.

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

Figure 13.5: The input data for the reduced QBG.

Figure 13.6 shows the IF solution of the reduced QBG

Figure 13.6: The IF solution of the reduced QBG.

Figure 13.7 shows the snapshot of the calculations

Figure 13.7: A snapshot of IF calculations.

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

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 $x_3=-8.621\lq$.
Following QSE the third raw and the third column are eliminated and the QSE solution of the reduced QBG $x_1=0.667,\ x_2=0.333,\ y_1=1.0,\ y_2=0$ is found.

5 Future Developments

The first task is to update the experimental software providing the exact implementation of the QSE algorithm.

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.