- 1 Walras Model
- 2 Search for Nash Equilibrium
- 3 "Nash-Look-Ahead" (NLA) Equilibrium

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

- 5 Monte-Carlo Simulation
- 1 Search for Equilibrium
- 2 Modeling Customers of Different Taste
- 3 Testing Equilibrium Conditions
- 4 Wiener Filter

- 6 Software Example

11 Competition Model

with Free Resource Prices,

Walras Equilibrium

In the model called by the Nash name, the cost of a service capacity unit is supposed to be fixed. Each individual server controls the capacity and the price 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 of servers depends on the resource vector defining the consumption of different resources. Each server owns a single resource and charges a price for a unit of this resource to partner-servers.

A server controls the resource vector . The component denotes the amount of resource used by the server . The resource balance condition means that

A server also controls the price 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 is an increasing function of the resource vector .

A simple example of this function

The resource component denotes the amount of resource used by server . The coefficient shows how useful is the resource for the server . The coefficient defines the capacity limit when . Then the profit of the -th server:

Here is the server index. is the rate of customers. is the service price. is the resource vector determining the capacity of server .

From the balance condition follows . Note, the profit of each individual server depends on the parameters of all servers .

Here the first component defines the income of a
server collected from customers of for its services. The second component
defines the sum payed by other servers using the resource . The third
component
shows the expenses for
resources obtained from other servers.

In
two-server cases

and

Here and are not included explicitly because they are defined by the balance conditions

By fixing the lower and upper limits

we obtain the
inequalities

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

where is waiting cost

A customer goes away, if

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

where is the rate of lost customers.

First fix a contract-vector . Then the fraud-vector is obtained by maximizing the profits of each server assuming that all other partners will respect the contract

Here the profit function is defined by expression (11.4). There are rectangular constraints (11.8). A server optimizes only components because is defined by the balance condition .

In the two-server case

and

Condition (11.13) transforms vectors into vectors , where , , , and . Denote this transformation by

Here the vector . We reach the equilibrium

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

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

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

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

Here the difference shows the profit obtained by -th server by breaking the contract . 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 is strictly convex function of parameters [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 are linear functions of resource prices . 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 independently of the price . In this case the owner of resource maximizes the profit by increse the price 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 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 .

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 is free. Denote by LA(p) the case when both vectors and are free.

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 and
the service charge are predicted for all servers at given resource price .
It is assumed that competing servers define parameters
by the usual Nash equilibrium conditions such as (10.14)
at fixed resource prices
^{}.
For example, they increase consumption if the prices fall.

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

Using both versions NLA while determining resource prices
one transforms linear
profit functions of ^{}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.

Here is the server index. is the rate of customers. is the equilibrium price of services. is the equilibrium resource vector that defines the capacity of server . All depend on resource prices .

From the balance condition follows .

The vector is defined by Nash conditions (11.19) for fixed resource prices by this condition

where . Denote Nash equilibrium at fixed as , then

In two-server cases

and

Here and are not included explicitly because they are defined by the balance conditions

One solves (11.21) many times for each fixed resource price before the equilibrium value is reached.

First a contract-vector is fixed. Then the fraud-vector is obtained by maximizing the profits of each server assuming that other partners keep the contract resource prices.

Here are contact resource prices of competing servers .

In the two-server case

and

Condition (11.26) transforms vectors into vectors , where , Denote this transformation by

We reach the equilibrium

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

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

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

Here the difference shows the profit obtained by -th server by deviating from the NLA equilibrium .

The final equilibrium values of are defined substituting into expression (11.22)

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

Here is the server index. is the rate of customers. is the equilibrium resource vector that defines the capacity of server . All depend on prices and .

From the balance condition follows .

The vector is defined at fixed prices by this condition

Denote Nash equilibrium at fixed price vector as

In two-server cases

and

Here and are not included explicitly because they are defined by the balance conditions

One solves (11.21) many times for each fixed price vector before the equilibrium values are reached.

First a contract-vector is fixed. Then the fraud-vector is obtained by maximizing the profits of each server assuming that other partners keep the contract resource prices.

Here are contact prices of competing servers .

In the two-server case

and

Condition (11.26) transforms vectors into vectors , where , and . Denote this transformation by

where . We reach the equilibrium

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

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

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

Here the difference shows the profit obtained by -th server by deviating from the NLA equilibrium .

The final equilibrium values of are defined substituting into expression (11.35)

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 . The resource vector is predicted for all servers assuming that each server defines resource demand by maximizing profit at fixed both the resource and service price vectors and .

Using GLA(py)
one transforms linear
profit functions of ^{}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

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

Here is the server index. is the rate of customers. is the greedy resource vector that defines the capacity of server and is obtained by maximizing the profit function at given contract prices and .

From the balance condition follows .

At fixed prices the vector is defined by these conditions

Denote the Greedy resource consumption vector at fixed price vectors as

In two-server cases

and

Here and are not included explicitly because they are defined by the balance conditions

One solves (11.21) many times for each fixed price vector before the equilibrium values are reached.

First a contract-vector is fixed. Then the fraud-vector is obtained by maximizing the profits of each server assuming that other partners keep the contract resource prices.

Here are contact prices of competing servers .

In the two-server case

and

Condition (11.26) transforms vectors into vectors , where , and . Denote this transformation by

where . We reach the equilibrium

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

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

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

Here the difference shows the profit obtained by -th server by deviating from the NLA equilibrium .

The final equilibrium values of are defined substituting into expression (11.35)

5 Monte-Carlo Simulation

- generates the next event time ,
- updates the state of queuing system defined by the vector of waiting customers ,
- updates the vector of the service cost including the money charged and the time lost.

- the time when a customer arrives into the system,
- the time when a customer arrives into the -th server, ,
- the time when a customer departs from the -th server,
- the time when a customer abandons the service (departs from the system without being served).

- a vector with components , where shows the number of customers waiting for the service of the -th server,
- a vector with
components
, where
shows the total customer expenses,
is
money charged for the service, and is the time lost
waiting for the service of the -th server
^{}.

- fix the zero event time when the first customer arrives,
- define the zero state vector by the
condition:

and the zero state vector by the condition :

because there are no customers waiting for service yet, - define the next arrival
into the system by the expression

where is a random number uniformly distributed in the interval [0,1], - chose the best server for the first customer by the condition where , because since there are no customers waiting yet, means that the customer abandons the service,
- define the time of event when the first
customer
will be served by the server using the expression

- define the next event by comparing the arrival time
and the service time :

if then ,

if then , - define the system state at the next event
:

if then and ,

consequently and ,

if then and .

- chose the best server for the th
customer by the condition

,

where , , and is the number of customers waiting for server .

- set to unit both the resource charges ,

- set to zero resources exchanges ,

- assume that , where variables are from expression (10.1).

If the number of severs then some modification of the described algorithm is needed.

- if a random number ,

regard the th customer as very busy one,

chose the best server for this customer by the condition

,

where , , and is the number of customers waiting for server ,

if a random number ,

regard the customer as busy one,

and chose the best server by the condition

,

where , .

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

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

where is a random number called the noise.

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

To test properties of , 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 , the Wiener parameter is a unit, and the noise is Gaussian with zero mean and variance at the points . Then the conditional expectation of the objective function at some fixed point with respect to the observations results can be expressed this way

Here

It is convenient to assume that

where can be considered as a smoothing parameter.

If then no smoothing occurs. The smoothing function (the
conditional expectation) is the piece-wise line connecting the
observed points (see Figure 1.1).

If is large then one obtains a horizontal line
corresponding to the average value of observed values . That
means a sort of "total smoothing." In modeling the yield of
differential amplifiers, the best smoothing was achieved at
[Mockus et al., 1997].

Figure 11.1 shows how the first server profit
depends on the price 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.

The field denoted by 'S' at the top right corner, defines the smoothing parameter 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.

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.

Figure
11.3 shows the input page.
The
method 'Bayes1' is set. The parameters:

the number of initial iterations is
5,

the number of iterations is 10,

the stocks of server
resources and is 0.7

the "run-away" threshold is 20

the customer rate
is 20,

the number of time units is 5

the efficiency
of all servers is 1.0

the accuracy is 20 %

the lower bounds are
0.0,

the upper limits are 30.0,

t

Figure 11.4 shows the results of optimization.

In
this figure:

denotes the "best' iteration

means the
minimal deviation from the equilibrium point,

are the optimal
values of the parameters.

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

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 . jonas mockus 2004-03-20