11 Competition Model
with Free Resource Prices,
Walras Equilibrium

1 Walras Model

In the model called by the Nash name, the cost of a service capacity unit is supposed to be fixed. Each individual server $i$ controls the capacity $x_i$ and the price $y_i$ charged for services. Therefore, the Nash model illustrates the formation of competitive service prices, if the resource prices are fixed by some large external market.

More complicated models, called by the Walras name, describe the formation of the competitive resource prices, too. In the Walras model, the capacity $w_i$ of servers $i=1,...,m$ depends on the resource vector $x_i=(x_{ij},\ i,j=1,...,m)$ defining the consumption of different resources. Each server $i$ owns a single resource $b_i$ and charges a price $p_i$ for a unit of this resource to partner-servers.

A server $i$ controls the resource vector $x_i=x_{ij},\ j=1,...,m$. The component $x_{ij}$ denotes the amount of resource $b_j$ used by the server $i$. The resource balance condition means that

$$\begin{eqnarray}b_i=\sum_{j = 1,...,m} x_{ij},\ i=1,...,m \end{eqnarray}$$

A server $i$ also controls the price $y_i$ that is charged for services, as in the Nash model. Therefore we shall describe the Walras model in the terms similar to those of the Nash model (see expression (10.1)).

Assume that the server capacity $w_i$ is an increasing function of the resource vector $x_i =(x_{ij},j=1,..., m)$.

$$\begin{eqnarray}w_i = \phi_i (x_i). \end{eqnarray}$$

A simple example of this function

$$\begin{eqnarray}w_i =k_{i} \prod_{j=1}^m (1-\exp(- k_{ij} x_{ij})). \end{eqnarray}$$

The resource component $x_{ij}$ denotes the amount of resource $b_j$ used by server $i$. The coefficient $k_{ij}$ shows how useful is the resource $b_j$ for the server $i$. The coefficient $k_i$ defines the capacity limit when $x_{ij} \rightarrow \infty$. Then the profit of the $i$-th server:

$$\begin{eqnarray}u_i= u_i(x_j, y_j,p_j, \ j=1, ... ,m) = \nonumber \\ a_i y_i +p_i \sum_{j \ne i} x_{ij} - \sum_{j \ne i} p_j x_{ij}. \end{eqnarray}$$

Here $i$ is the server index. $a_i$ is the rate of customers. $y_i$ is the service price. $x_j=(x_{jk},\ k=1,...,m)$ is the resource vector determining the capacity $w_j$ of server $j$.
From the balance condition follows $x_{ii}=b_i-\sum_{j \ne i} x_{ji}$. Note, the profit $u_i$ of each individual server $i$ depends on the parameters $x_j,y_j,p_j$ of all $m$ servers $j=1,...,m$.

Here the first component $a_i y_i$ defines the income of a server $i$ collected from customers of for its services. The second component $p_i \sum_{j \ne i} x_{ij}$ defines the sum payed by other servers using the resource $b_i$. The third component $\sum_{j \ne i} p_j x_{ij}$ shows the expenses for resources obtained from other servers.
In two-server cases

$$\begin{eqnarray}u_1= u_1( x_{12}, y_1, p_1, x_{21}, y_2, p_2) = \nonumber \\ a_1 y_1 + p_1x_{21} - p_2 x_{12}. \end{eqnarray}$$

and

$$\begin{eqnarray}u_2= u_2( x_{21}, y_2, p_2, x_{12}, y_1, p_1) = \nonumber \\ a_2 y_2 + p_2 x_{12} - p_1 x_{21}. \end{eqnarray}$$

Here $x_{11}$ and $x_{22}$ are not included explicitly because they are defined by the balance conditions

$$\begin{eqnarray}x_{11}=b_1-x_{21},\ x_{22}=b_2-x_{12}. \end{eqnarray}$$

By fixing the lower and upper limits
$a_{p_i}, a _{x_{ij}}, a_{y_i}, b_{p_i}, b_{x_{ij}}, b_{y_i}\ i,j=1,...m$ we obtain the inequalities

$$\begin{eqnarray}a_{p_i} \le p_i \le b_{p_i},\ a_{x_{ij}} \le x_{ij} \le b_{x_{ij}},\\ \nonumber a_{y_i} \le y_i \le b_{y_i},\ i,j=1,...,m \end{eqnarray}$$

In the Walras model the service cost, the waiting cost, and the customer behavior are similar to those of the Nash model. Namely, the service cost

$$\begin{eqnarray}c_i = y_i + \gamma_i, \end{eqnarray}$$

where $\gamma_i$ is waiting cost at the server $i$ (see expression (10.5)) . A customer goes to the server $i$, if

$$\begin{eqnarray}c_i < c_j,\ j=1,...,m,\ j \not= i,\ c_i \le c_0. \end{eqnarray}$$

A customer goes away, if

$$\begin{eqnarray}\min_i c_i > c_0, \end{eqnarray}$$

where $c_0$ is the critical cost. The rate $a$ of incoming consumers flow is fixed:

$$\begin{eqnarray}a= \sum_{i=0}^m a_i, \end{eqnarray}$$

where $a_0$ is the rate of lost customers.

2 Search for Nash Equilibrium

First fix a contract-vector $(x_i^0, y_i^0, p_i^0, \ i=1, ... ,m)$. Then the fraud-vector $(x_i^1,y_i^1, p_i^1, \ i=1, ... ,m)$ is obtained by maximizing the profits of each server $i$ assuming that all other partners $j \not= i$ will respect the contract $(x_i^0, y_i^0, p_i^0, \ i=1, ... ,m)$

$$\begin{eqnarray}(x_i^1, y_i^1,p_i^1, ) =\nonumber \\ arg \ \max_{x_i,y_i,p_i} u_i(x_i, y_i,p_i,\ x_j^0,y_j^0,p_j^0, \ j=1, ... ,m, \ j \not=i ). \end{eqnarray}$$

Here the profit function $u_i(x_i, y_i,p_i,\ x_j^0,y_j^0,p_j^0, \ j=1, ... ,m, \ j \not=i )$ is defined by expression (11.4). There are rectangular constraints (11.8). A server $i$ optimizes only components $x_{ij},\ i \ne j$ because $x_{ii}$ is defined by the balance condition $x_{ii}=b_i-\sum_{j \ne i} x_{ji}$.

In the two-server case

$$\begin{eqnarray}( x_{12}^1, y_1^1, p_1^1, ) =\nonumber \\ arg \max_{ x_{12}, y_1, p_1} u_1( x_{12}, y_1, p_1, x_{21}^0, y_2^0, p_2^0), \end{eqnarray}$$

and

$$\begin{eqnarray}( x_{21}^1, y_2^1,p_2^1, ) =\nonumber \\ arg \max_{x_{21},y_2, p_2} u_2(x_{21}, y_2, p_2, x_{12}^0, y_1^0, p_1^0). \end{eqnarray}$$

Condition (11.13) transforms vectors $z^n,\ n=0,1,2,...$ into vectors $z^{n+1}$, where $z^n=(x^n,y^n,p^n)$, $x^n=(x_1^n,...,x_m^n)$, $y^n=(y_1^n,...,y_m^n)$, and $p^n=(p_1^n,...,p_m^n)$. Denote this transformation by $T$

$$\begin{eqnarray}z^{n+1} = T(z^n),\ n=0,1,2,... \end{eqnarray}$$

Here the vector $z=(x_i,y_i,p_i, v_i\ i=1,...,m) \in B \subset R^{m^2+2m}$ . We reach the equilibrium at the fixed point $z^n$, where

$$\begin{eqnarray}z^{n} = T(z^n). \end{eqnarray}$$

We may obtain the Nash equilibrium directly by simple iterations (11.16), if the transformation $T$ is contracting [Neuman and Morgenstern, 1953]. There are more sophisticated and efficient iterative procedures [Herings, 1994].

If the equilibrium exists but the transformation $T$ is not contracting then one minimizes the square deviation

$$\begin{eqnarray}\min_{z \in B} \parallel z - T(z) \parallel^2. \end{eqnarray}$$

The equilibrium is achieved, if the minimum (11.18) is zero.

The alternative way to achieve equilibrium is by minimizing the fraud profit

$$\begin{eqnarray}\min_{z \in B} \sum_i (u_i(T(z))-u_i(z)). \end{eqnarray}$$

Here the difference $u_i(T(z))-u_i(z)$ shows the profit obtained by $i$-th server by breaking the contract $z$. The advantage of (11.19) is clear economic meaning.

The constraints (11.8) limits the Walras model. Therefore, setting these constraints one should resolve the following contradiction. Wider limits means more computing for optimization but less restriction for the Walras model, and vice versa. A way to get around this contradiction is to start with narrow bounds (11.8). One widens them if some of these bounds obviously restrict the profit maximum.

If the equilibrium test (11.18) fails additional testing of the sufficient existence conditions is needed. It is well known, that the equilibrium exists, if the profit $u$ is strictly convex function of parameters $(y,x,p)$ [Michael, 1976]. Therefore, the "non-strict-convexity" of this function could be a reason of the failure to obtain the equilibrium.

Expressions (11.4) and (11.6) show that profits $u_i$ are linear functions of resource prices $p_i$. Linear functions are not strictly convex. In economic terms this deviation from the sufficient conditions means the server obligation to buy some fixed amount of resource $x_j$ independently of the price $p_j$. In this case the owner of resource $x_j$ maximizes the profit by increse the price $p_j$ to infinity. Then nobody will buy it e.tc.. Thus the Nash equilibrium may not exist in this case. Besides this model is not practical because the obligation to buy certain amount of resources regardless of the price in obviosly not the realistic one.

To avoid this difficulty two versions of the "Look-Ahead" (LA) equilibrium models are considered in the following sections. In the LA models the control parameters $p,y,x$ are devided into two groups: contract and free. For example in the model (11.13)- (11.19) all the parameters were included into the contract. The parameters that are not included into the contract are called as free. The natural example of the free parameter is resource consumptions $x$.

The important problem of models with free parametrs is than one must anticipate the free parameters of all competitors.

We consider estimations of free parameters based on two different assumptions: Nash (NLA) and Greedy (GLA). In the Nash ( NLA) case we assume that all the servers select the free parameters at given contract parameters by conditions Nash equilibrium. In the Greedy (GLA) case servers select such free parameters that maximize their profits at fixed contract parameters. The NLA models may provide genuine Nash equilibrium if servers esimate competitors profit functuions well enough. However GLA models seems to be more realistic.

Look Ahead LA versions differs by the number of parameters to be set free. Denote by LA(p,y) the case when only the vector of resource demand $x$ is free. Denote by LA(p) the case when both vectors $x$ and $y$ are free.

3 "Nash-Look-Ahead" (NLA) Equilibrium

Definition of NLA equilibrium is similar to that of Nash equilibrium. The difference is that competitors responces. are anticipated while searching for the equilibrium prices. We consider two versions of NLA.

In the first version, NLA(p) for short, both the resource consumption $x_j$ and the service charge $y_j$ are predicted for all servers at given resource price $p$. It is assumed that competing servers $j \not= i$ define parameters $(x_j,y_j)$ by the usual Nash equilibrium conditions such as (10.14) at fixed resource prices $p=(p_i,\ i=1,...,m)$ . For example, they increase consumption if the prices fall.

In the second version that is denoted as NLA(p,y), only the resource consumptions $x_j$ are predicted for all servers. That means all servers $j$ define resource demand $x_j$ by the usual Nash equilibrium conditions at fixed both the service charges $p=(p_j,\ i=1,...,m)$ and service prices $y=(y_j,\ i=1,...,m)$ . For example, they not only increase resource consumption $x_j$ if the prices $p_j$ fall but adapt the service charges $y_j$ to changed resource prices as well.

Using both versions NLA while determining resource prices $p$ one transforms linear profit functions of $p_j$into nonlinear ones. This way one may satisfy the necessary equilibrium conditions. That is true in both the cases: NLA(p) and NLA(p,y). It seems that NLA(py) better describes the actual economical behavior of participants and demands less calculations.

1 First Version: NLA(p)

1 Search for NLA(p) Equilibrium

1 Defining Nash Profit

Using NLA(p) the Nash profit is defined as the profit function $U(p)$ satisfying Nash conditions at fixed resource prices $p$. Then the profit of the $i$-th server:

$$\begin{eqnarray}U_i(p)= u_i(x_j^* y_j^*,p_j, \ j=1, ... ,m) = \nonumber \\ a_i y_i^* +p_i \sum_{j \ne i} x_{ij}^* - \sum_{j \ne i} p_j x_{ij}^*. \end{eqnarray}$$

Here $i$ is the server index. $a_i$ is the rate of customers. $y_i^*=y_i(p)$ is the equilibrium price of services. $x_j^*=(x_{jk}^*,\ k=1,...,m),\ x_{jk}^*=x_{jk}(p)$ is the equilibrium resource vector that defines the capacity $w_j$ of server $j$. All depend on resource prices $p$.
From the balance condition follows $x_{ii}^*=b_i-\sum_{j \ne i} x_{ji}^*$.
The vector $(x^*,y^*)$ is defined by Nash conditions (11.19) for fixed resource prices $p$ by this condition

$$\begin{eqnarray}\min_{z \in B} \sum_i (u_i(T(z))-u_i(z)), \end{eqnarray}$$

where $z=(x,y)$. Denote Nash equilibrium at fixed $p$ as $z^*=z(p)$, then

$$\begin{eqnarray}x^*=x(p), y^*=y(p). \end{eqnarray}$$

In two-server cases

$$\begin{eqnarray}U_1(p_1,p_2)= u_1( x_{12}^*, y_1^*, p_1, x_{21}^*, y_2^*, p_2) = \nonumber \\ a_1 y_1^* + p_1x_{21}^* - p_2 x_{12}^*. \end{eqnarray}$$

and

$$\begin{eqnarray}U_2(p_1,p_2)= u_2( x_{21}^*, y_2^*, p_2, x_{12}^*, y_1^*, p_1) = \nonumber \\ a_2 y_2^* + p_2 x_{12}^* - p_1 x_{21}^*. \end{eqnarray}$$

Here $x_{11}^*$ and $x_{22}^*$ are not included explicitly because they are defined by the balance conditions

$$\begin{eqnarray}x_{11}^*=b_1-x+{21}^*,\ x_{22}^*=b_2-x_{12}^*. \end{eqnarray}$$

One solves (11.21) many times for each fixed resource price $p$ before the equilibrium value $p=p^*$ is reached.

2 Defining NLA(p) Profit

First a contract-vector $( p_i^0, \ i=1, ... ,m)$ is fixed. Then the fraud-vector $( p_i^1, \ i=1, ... ,m)$ is obtained by maximizing the profits of each server $i$ assuming that other partners $j \not= i$ keep the contract resource prices.

$$\begin{eqnarray}p_i^1 = arg \ \max_{p_i} U_i(p_i,\ p_j^{0}, \ j=1, ... ,m, \ j \not=i ), \ i=1,...,m. \end{eqnarray}$$

Here $p_j^{0},\ j \not=i$ are contact resource prices of competing servers $j \not= i$.

In the two-server case

$$\begin{eqnarray}p_1^1 = arg \max_{ p_1} U_1( p_1, p_2^{0}), \end{eqnarray}$$

and

$$\begin{eqnarray}p_2^1 = arg \max_{ p_2} U_2( p_2, p_1^{0}). \end{eqnarray}$$

Condition (11.26) transforms vectors $p^n,\ n=0,1,2,...$ into vectors $p^{n+1}$, where $p^n=(p_i^n,\ i=1,...,m)$, Denote this transformation by $T$

$$\begin{eqnarray}p^{n+1} = T(p^n),\ n=0,1,2,... \end{eqnarray}$$

We reach the equilibrium at the fixed point $p^n$, where

$$\begin{eqnarray}p^{n} = T(p^n). \end{eqnarray}$$

If the equilibrium exists but the transformation $T$ is not contracting then we minimize the square deviation

$$\begin{eqnarray}\min_{p \in B} \parallel p - T(p) \parallel^2. \end{eqnarray}$$

The equilibrium is achieved, if the minimum (11.31) is zero.

The alternative way to achieve equilibrium is by minimizing the fraud profit

$$\begin{eqnarray}\min_{p \in B} \sum_i (U_i(T(p))-U_i(p)). \end{eqnarray}$$

Here the difference $U_i(T(p))-u_i(p)$ shows the profit obtained by $i$-th server by deviating from the NLA equilibrium $p^*$.
The final equilibrium values of $(x,y)$ are defined substituting $p^*$ into expression (11.22)

2 Second Version: NLA(p,y)

1 Search for NLA(p,y) Equilibrium

1 Defining Nash Profit

Using NLA(p,y) the profit of the $i$-th server:

$$\begin{eqnarray}U_i(p,y)= u_i(x_j^* y_j,p_j, \ j=1, ... ,m) = \nonumber \\ a_i y_i^* +p_i \sum_{j \ne i} x_{ij}^* - \sum_{j \ne i} p_j x_{ij}^*. \end{eqnarray}$$

Here $i$ is the server index. $a_i$ is the rate of customers. $x_j^*=(x_{jk}^*,\ k=1,...,m),\ x_{jk}^*=x_{jk}(p,y)$ is the equilibrium resource vector that defines the capacity $w_j$ of server $j$. All depend on prices $p$ and $y$.
From the balance condition follows $x_{ii}^*=b_i-\sum_{j \ne i} x_{ji}^*$.
The vector $x^*$ is defined at fixed prices $(p,y)$ by this condition

$$\begin{eqnarray}\min_{x \in B} \sum_i (u_i(T(x))-u_i(x)). \end{eqnarray}$$

Denote Nash equilibrium at fixed price vector $(p,y)$ as

$$\begin{eqnarray}x^*=x(p,y). \end{eqnarray}$$

In two-server cases

$$\begin{eqnarray}U_1(p_1,y_1,p_2,y_2)= u_1( x_{12}^*, y_1, p_1, x_{21}^*, y_2, p_2) = \nonumber \\ a_1 y_1 + p_1x_{21}^* - p_2 x_{12}^*. \end{eqnarray}$$

and

$$\begin{eqnarray}U_2(p_1,y_1,p_2,y_2)= u_2( x_{21}^*, y_2, p_2, x_{12}^*, y_1, p_1) = \nonumber \\ a_2 y_2 + p_2 x_{12}^* - p_1 x_{21}^*. \end{eqnarray}$$

Here $x_{11}^*$ and $x_{22}^*$ are not included explicitly because they are defined by the balance conditions

$$\begin{eqnarray}x_{11}^*=b_1-x+{21}^*,\ x_{22}^*=b_2-x_{12}^*. \end{eqnarray}$$

One solves (11.21) many times for each fixed price vector $(p,y)$ before the equilibrium values $(p=p^*,y^*)$ are reached.

2 Defining NLA(p,y) Profit

First a contract-vector $( p_i^0, y_i^0\ i=1, ... ,m)$ is fixed. Then the fraud-vector $( p_i^1, y_i^1\ i=1, ... ,m)$ is obtained by maximizing the profits of each server $i$ assuming that other partners $j \not= i$ keep the contract resource prices.

$$\begin{eqnarray}(p_i^1,y_i^1) = arg \ \max_{p_i,y_i} U_i(p_i,y_i\ p_j^{0},y_j^{0} \ j=1, ... ,m, \ j \not=i ), \ i=1,...,m. \end{eqnarray}$$

Here $p_j^{0},y_j^{0}\ j \not=i$ are contact prices of competing servers $j \not= i$.

In the two-server case

$$\begin{eqnarray}(p_1^1,y_1^1) = arg \max_{ p_1,y_1} U_1( p_1,y_1, p_2^{0},y_2^0), \end{eqnarray}$$

and

$$\begin{eqnarray}(p_2^1,y_2^1) = arg \max_{ p_2,y_2} U_2( p_2,y_2 p_2^{0},y_2^0). \end{eqnarray}$$

Condition (11.26) transforms vectors $p^n,y^n\ n=0,1,2,...$ into vectors $p^{n+1},y^{n+1}$, where $p^n=(p_i^n,\ i=1,...,m)$, and $y^n=(y_i^n, \ i=1,...m)$. Denote this transformation by $T$

$$\begin{eqnarray}z^{n+1} = T(z^n),\ n=0,1,2,... \end{eqnarray}$$

where $z=(p,y)$. We reach the equilibrium at the fixed point $p^n$, where

$$\begin{eqnarray}z^{n} = T(z^n). \end{eqnarray}$$

If the equilibrium exists but the transformation $T$ is not contracting then we minimize the square deviation

$$\begin{eqnarray}\min_{z \in B} \parallel z - T(z) \parallel^2. \end{eqnarray}$$

The equilibrium is achieved, if the minimum (11.44) is zero.

The alternative way to achieve equilibrium is by minimizing the fraud profit

$$\begin{eqnarray}\min_{z \in B} \sum_i (U_i(T(z))-U_i(z)). \end{eqnarray}$$

Here the difference $U_i(T(z))-u_i(z)$ shows the profit obtained by $i$-th server by deviating from the NLA equilibrium $z^*$.
The final equilibrium values of $x^*)$ are defined substituting $(p^*,y^*)$ into expression (11.35)

4 "Greedy-Look-Ahead" (GLA) Equilibrium

Definition of GLA equilibrium is similar to that of NLA because in both the cases competitors responces. are anticipated while searching for the equilibrium prices. The difference is that the 'greedy' servers select the free parameters not by equilibrium conditions but by maximal profit. We consider only one version GLA(py) where the free parameter is a vector of resource consumption $x$. The resource vector $x$ is predicted for all servers assuming that each server defines resource demand by maximizing profit at fixed both the resource and service price vectors $p$ and $y$ .

Using GLA(py) one transforms linear profit functions of $p_j$into nonlinear ones. This way one may satisfy the necessary equilibrium conditions if the profit functions are convex. That is true in both the cases: NLA and GLA. In this sense both versions are equivalent. Thus one may select a version that better describes the actual economical behavior of participants.

Both the NLA and the GLA approaches is based on the important tacit assumption that servers know profit functions of their competitors. This is not true as usuall. However, that is a price one pays for making profit functions strictly convex. This is needed to satisfy necessary equilibrium conditions. The price is not so great when servers know at least some approximation of competitor profit functions and behavior

1 Search for GLA(p,y) Equilibrium

1 Defining Nash Profit

Using GLA(p,y) the profit of the $i$-th server:

$$\begin{eqnarray}U_i(p,y)= u_i(x_j^* y_j,p_j, \ j=1, ... ,m) = \nonumber \\ a_i y_i^* +p_i \sum_{j \ne i} x_{ij}^* - \sum_{j \ne i} p_j x_{ij}^*. \end{eqnarray}$$

Here $i$ is the server index. $a_i$ is the rate of customers. $x_j^*=(x_{jk}^*,\ k=1,...,m),\ x_{jk}^*=x_{jk}(p,y)$ is the greedy resource vector that defines the capacity $w_j$ of server $j$ and is obtained by maximizing the profit function $U_i$ at given contract prices $p$ and $y$.
From the balance condition follows $x_{ii}^*=b_i-\sum_{j \ne i} x_{ji}^*$.
At fixed prices $(p,y)$ the vector $x^*$ is defined by these conditions

$$\begin{eqnarray}\max_{x_{ij} \in B} U_i(p,y),\ i=1,...,m,\ i \ne j. \end{eqnarray}$$

Denote the Greedy resource consumption vector at fixed price vectors $(p,y)$ as

$$\begin{eqnarray}x^*=x(p,y). \end{eqnarray}$$

In two-server cases

$$\begin{eqnarray}U_1(p_1,y_1,p_2,y_2)= u_1( x_{12}^*, y_1, p_1, x_{21}^*, y_2, p_2) = \nonumber \\ a_1 y_1 + p_1x_{21}^* - p_2 x_{12}^*. \end{eqnarray}$$

and

$$\begin{eqnarray}U_2(p_1,y_1,p_2,y_2)= u_2( x_{21}^*, y_2, p_2, x_{12}^*, y_1, p_1) = \nonumber \\ a_2 y_2 + p_2 x_{12}^* - p_1 x_{21}^*. \end{eqnarray}$$

Here $x_{11}^*$ and $x_{22}^*$ are not included explicitly because they are defined by the balance conditions

$$\begin{eqnarray}x_{11}^*=b_1-x+{21}^*,\ x_{22}^*=b_2-x_{12}^*. \end{eqnarray}$$

One solves (11.21) many times for each fixed price vector $(p,y)$ before the equilibrium values $(p=p^*,y^*)$ are reached.

2 Defining GLA(p,y) Profit

First a contract-vector $( p_i^0, y_i^0\ i=1, ... ,m)$ is fixed. Then the fraud-vector $( p_i^1, y_i^1\ i=1, ... ,m)$ is obtained by maximizing the profits of each server $i$ assuming that other partners $j \not= i$ keep the contract resource prices.

$$\begin{eqnarray}(p_i^1,y_i^1) = arg \ \max_{p_i,y_i} U_i(p_i,y_i\ p_j^{0},y_j^{0} \ j=1, ... ,m, \ j \not=i ), \ i=1,...,m. \end{eqnarray}$$

Here $p_j^{0},y_j^{0}\ j \not=i$ are contact prices of competing servers $j \not= i$.

In the two-server case

$$\begin{eqnarray}(p_1^1,y_1^1) = arg \max_{ p_1,y_1} U_1( p_1,y_1, p_2^{0},y_2^0), \end{eqnarray}$$

and

$$\begin{eqnarray}(p_2^1,y_2^1) = arg \max_{ p_2,y_2} U_2( p_2,y_2 p_2^{0},y_2^0). \end{eqnarray}$$

Condition (11.26) transforms vectors $p^n,y^n\ n=0,1,2,...$ into vectors $p^{n+1},y^{n+1}$, where $p^n=(p_i^n,\ i=1,...,m)$, and $y^n=(y_i^n, \ i=1,...m)$. Denote this transformation by $T$

$$\begin{eqnarray}z^{n+1} = T(z^n),\ n=0,1,2,... \end{eqnarray}$$

where $z=(p,y)$. We reach the equilibrium at the fixed point $p^n$, where

$$\begin{eqnarray}z^{n} = T(z^n). \end{eqnarray}$$

If the equilibrium exists but the transformation $T$ is not contracting then we minimize the square deviation

$$\begin{eqnarray}\min_{z \in B} \parallel z - T(z) \parallel^2. \end{eqnarray}$$

The equilibrium is achieved, if the minimum (11.44) is zero.

The alternative way to achieve equilibrium is by minimizing the fraud profit

$$\begin{eqnarray}\min_{z \in B} \sum_i (U_i(T(z))-U_i(z)). \end{eqnarray}$$

Here the difference $U_i(T(z))-u_i(z)$ shows the profit obtained by $i$-th server by deviating from the NLA equilibrium $z^*$.
The final equilibrium values of $x^*)$ are defined substituting $(p^*,y^*)$ into expression (11.35)

5 Monte-Carlo Simulation

1 Search for Equilibrium

The analytical solution of both the described market models is not practical. Therefore, we briefly consider the basic steps of an algorithm of the statistical simulation using Monte-Carlo techniques. The algorithm implements two basic tasks:

• generates the next event time $t$,
• updates the state of queuing system defined by the vector of waiting customers $n(t)=(n_i(t),\ i=1,...,m)$,
• updates the vector $h(t)=(h_i(t),\ i=1,...,m)$ of the service cost including the money charged and the time lost.

There are $2m+2$ types of event times $t$:

• the time $t$ when a customer arrives into the system,
• the time $t$ when a customer arrives into the $i$-th server, $i=1,...,m$,
• the time $t$ when a customer departs from the $i$-th server,
• the time $t$ when a customer abandons the service (departs from the system without being served).

Here $i=1,...,m$. The system state is updated at each event time $t$. Two vectors define the system state:

• a vector $n=n(t)$ with $m$ components $n=(n_1,...,n_m)$, where $n_i =n_i(t)$ shows the number of customers waiting for the service of the $i$-th server,
• a vector $h=h(t)$ with $m$ components $h=(h_1,...,h_m)$, where $h_i(t) =y_i+\gamma_i,\ \gamma_i=n_i(t)/w_i$ shows the total customer expenses, $y_i$ is money charged for the service, and $\gamma_i$ is the time lost waiting for the service of the $i$-th server.

There are no state changes between events. The basic steps of the Monte Carlo algorithm:

1. fix the zero event time $t=t^0=0$ when the first customer arrives,
2. define the zero state vector $n^0$ by the condition: $n_{i}^0=0,\ i=1,...,m$
   and the zero state vector $h^0$ by the condition : $h_{i}^0=y_i=0,\ i=1,...,m$
   because there are no customers waiting for service yet,
3. define the next arrival into the system by the expression
   $$\begin{eqnarray}\tau_a=-1/a\ ln (1-\eta) \end{eqnarray}$$
   
   
   
   
   where $\eta$ is a random number uniformly distributed in the interval [0,1],
4. chose the best server $i^0$ for the first customer by the condition $i^0=arg \min_{i=0,...,m}\ h_i$ where $h_i=y_i$, because $\gamma_i=0,\ i=1,...,m$ since there are no customers waiting yet, $i^0=0$ means that the customer abandons the service,
5. define the time of event when the first customer will be served by the server $i^0$ using the expression
   $$\begin{eqnarray}\tau_{i^0}=-1/x_{i^0}\ ln (1-\eta), \end{eqnarray}$$
   
   
   
   

6. define the next event $t^1$ by comparing the arrival time $\tau_a$ and the service time $\tau_{i^0}$ :
   if $\tau_a < \tau_{i^0}$ then $t^1=\tau_a$,
   if $\tau_a > \tau_{i^0}$ then $t^1=\tau_{i^0}$,
7. define the system state at the next event $t^1$:
   if $t^1=\tau_a$ then $n_{i^0}=1$ and $n_i=0, \ i=1,...,m,\ i \ne i^0$,
   consequently $h_{i^0}=y_{i^0}+1/w_{i^0}$ and $h_i=y_i, \ i=1,...,m,\ i \ne i^0$,
   if $t^1=\tau_{i^0}$ then $n_i=0, \ i=1,...,m,$ and $h_i=y_i, \ i=1,...,m,\ i \ne i^0$.

Definition of later events and system states is longer but the main idea remains the same. For illustration, we update the fourth step for the $n$th customer:

• chose the best server $i^0$ for the $n$th customer by the condition
  $i^0=arg \min_{i=0,...,m}\ h_i$,
  where $h_i=y_i +\gamma_i$, $\gamma_{i^0}=n_i/\omega_{i^0}$, and $n_i$ is the number of customers waiting for server $i$.

The algorithm can be directly adapted to the Monte-Carlo simulation of the Nash model with two servers, too. For example, that can be done this way:
- set to unit both the resource charges $p_i=1,\ i=1,2$,
- set to zero resources exchanges $x_{21}=x_{12}=0$,
- assume that $x_{11}=x_1,\ x_{22}=x_2$, where variables $x_1, \ x_2$ are from expression (10.1).
If the number of severs $m>2$ then some modification of the described algorithm is needed.

2 Modeling Customers of Different Taste

If the customers value their time differently (see Section 2.1) then the fourth step of the algorithms should be changed accordingly. For illustration, here is the fourth step for the second customer :

• if a random number $\eta < p_b$,
  regard the $n$th customer as very busy one,
  chose the best server $i^0$ for this customer by the condition
  $i^0=arg \min_{i=0,...,m}\ h_i^b$,
  where $h_i^b=y_i +k_b\gamma_i$, $\gamma_{i^0}=n_i/\omega_{i^0}$, and $n_i$ is the number of customers waiting for server $i$,
  if a random number $\eta < p_b$,
  regard the customer as busy one,
  and chose the best server $i^0$ by the condition
  $i^0=arg \min_{i=0,...,m}\ h_i$,
  where $h_i^b=y_i +\gamma_i$, $\gamma_{i^0}=n_i/\omega_{i^0}$.
  

3 Testing Equilibrium Conditions

In the Monte-Carlo simulation, equilibrium tests (11.18) should be relaxed by accepting some simulation error $\epsilon$:

$$\begin{eqnarray}\min_{z \in B} \parallel z - T(z) \parallel^2 \le \epsilon, \end{eqnarray}$$

The alternative way to achieve equilibrium is by minimizing the fraud profit (11.19). Then the test is

$$\begin{eqnarray}\min_{z \in B} \sum_i (u_i(T(z))-u_i(z)) \le \epsilon \end{eqnarray}$$

To test the convexity of profit functions, some smoothing is desirable. The smoothing eliminates the random deviations due to Monte-Carlo simulation. Both the convolution and the Wiener filters are applied for smoothing the profit functions (possibly multi-modal). The convolution filter defines the function at some fixed point as an average of values in the neighborhood of this point. The more sophisticated Wiener filter is implemented, too.

4 Wiener Filter

If the objective function $f(x)$ is defined by Monte Carlo simulation, some noise is present. That means that one observes the sum

$$\begin{eqnarray}\phi(x)=f(x)+\xi, \end{eqnarray}$$

where $\xi$ is a random number called the noise.

If finding the optimum of a convex function $f(x)$ is the only goal, we can apply some stochastic optimization algorithms [Ermoljev and Wets, 1988]. These algorithms converge to the optimum of $f(x)$ by filtering the noise during the optimization process.

To test properties of $f(x)$, such as convexity, unimodality e.t.c., we need specific smoothing algorithms that eliminate false local optima. In one-dimensional cases, a convenient smoothing function is the conditional expectation of the Wiener process with noise [Kushner, 1964b,Senkiene, 1980]. It is assumed that the optimization parameter $x \in [0,1]$, the Wiener parameter is a unit, and the noise $\xi$ is Gaussian with zero mean and variance $S_i$ at the points $x^i \in [0,1],\ i=1,...,n$. Then the conditional expectation $\mu_k=\mu_n(x^k)$ of the objective function $y_k=f(x^k)$ at some fixed point $x^k$ with respect to the observations results $y_i=\phi(x^i),\ i=1,...,n,$ can be expressed this way

$$\begin{eqnarray}\mu_k=\protect\frac{\sum_{i=1}^k b_i y_i +\frac{ b_k}{c_k} \sum_... ... c_i y_i} {\sum_{i=1}^k b_i +\frac{b_k}{c_k} \sum_{i=k+1}^n c_i}. \end{eqnarray}$$

Here

$$\begin{eqnarray}b_1=1,\ B_1=1,\\ b_2=\frac{S_1^2+r_{1,2}}{S_2^2},\ B_2=B_1+b_2,\... ...S_k^2}, C_{k+1}=\sum_{i=k+1}^n c_i,\\ r_{i,j}=\vert x^i-x^j\vert. \end{eqnarray}$$

It is convenient to assume that

$$\begin{eqnarray}S_i=S,\ i=1,...,n, \end{eqnarray}$$

where $S$ can be considered as a smoothing parameter.

If $S=0$ then no smoothing occurs. The smoothing function (the conditional expectation) is the piece-wise line connecting the observed points (see Figure 1.1).
If $S$ is large then one obtains a horizontal line corresponding to the average value of observed values $y_i$. That means a sort of "total smoothing." In modeling the yield of differential amplifiers, the best smoothing was achieved at $S=10$ [Mockus et al., 1997].

Figure 11.1 shows how the first server profit $u_1$ depends on the price $p_1$ charged for its resources. There are two samples of the same relation. They show the differences between two samples of random arrival times of fifty customers.

Figure 11.1: The relation of the profit $u_1$ on the resource price $p_1$ (top), the "refreshed" relation of the profit $u_1$ on the resource price $p_1$ (bottom).

The buttons 'smooth' and 'wiener' on the right side are for switching on these filters. The button 'smooth' is for the convolution filter. The button 'wiener' is for the Wiener filter.
The field denoted by 'S' at the top right corner, defines the smoothing parameter $S$ of the Wiener filter (see expression (11.71).
One can increase the level of smoothing by pressing the 'smooth' or 'wiener' buttons repeatedly.
The 'refresh' button repeats the Monte-Carlo simulation of the same profit function.

Figures 11.2 show the third sample of the 'refreshed' unsmoothed graph and the same sample smoothed by the convolution filter.

Figure 11.2: The third sample of the relation of the profit $u_1$ on the resource price $p_1$ (top), the relation of the profit $u_1$ on the price $p_1$, smoothed by the convolution filter (bottom).

The underlying profit function is the same in all the Figures, from 11.1 up to 11.2. The repeated simulation defines different graphs because of the simulation errors. After smoothing, the level of these errors is lower.

6 Software Example

Java j2sdk implementation [Treigys, 2003] and [Sviderskaite, 2003] of the Walras model is on web-sites (see section 4).

Figure 11.3 shows the input page. The method 'Bayes1' is set. The parameters:
the number of initial iterations$lt$ is 5,
the number of iterations$it$ is 10,
the stocks of server resources $b_1$ and $b_2$ is 0.7
the "run-away" threshold $C0$ is 20
the customer rate $A$ is 20,
the number of time units $M$ is 5
the efficiency of all servers $z_{ij}$ is 1.0
the accuracy is 20 %
the lower bounds $min$ are 0.0,
the upper limits $max$ are 30.0,
t

Figure 11.3: The table of initial parameters.

Figure 11.4 shows the results of optimization.
In this figure:
$iteration$ denotes the "best' iteration
$F(x)$ means the minimal deviation from the equilibrium point,
$y_1,p_1,y_2,p_2$ are the optimal values of the parameters.

Figure 11.4: Optimization results using the method Bayes1.

Figure 11.5 shows how the profits of the first server depends on the service charge $y_1$.

Figure 11.5: Relation of the profit $u_1$ on the service charge $y_1$.

The figure 11.6 shows how the profits of the first server depends on the resource price $p_1$.

Figure 11.6: Relation of the profit $u_1$ on the resource price $p_1$.

The result is difficult to explain so the additional investigation is needed. That could be made easy by performing profit analysis by separate program at fixed esimates of equilibrium vectors $p,y$.