We consider two models of the theory of games and markets [Rosenmuller, 1981]. The Nash equilibrium [Nash, 1950] is applied. The "market" is represented by a collection of
independent servers. Each server tries to maximize its profit by
setting optimal service prices and optimal server rates. The
server rate is the average number of customers that would be
served in nonstop operation. Thus, we can consider this rate as
the server capacity.
10 Competition Model
with Fixed Resource Prices,
The profits of individual servers are maximized assuming that
their partners respect some agreement about the service prices
and rates. We call this the "Contract-Vector." Service prices
and rates obtained by maximizing individual profits of the
servers transform the Contract-Vector into the "Fraud-Vector."
The optimization problem is to search for such Contract-Vector
that reduces the deviation of the Fraud-Vector from the
Contract-Vector. That makes the fraud less relevant. The fraud is
irrelevant and the Nash equilibrium is achieved, if this deviation is
zero. Then servers cannot increase their profits by
changing service prices and server rates agreed by the
The quality of service is defined by the average time lost by
customers while waiting for services. Formal expressions of
other quality measures are difficult. A customer prefers the
server with lesser total service cost. The total cost includes
the service price plus waiting losses. A customer goes away, if
the total cost exceeds a certain critical level. A flow of
customers is stochastic. Service times are stochastic, too.
There is no known analytical solution for this model. The
results are obtained by Monte-Carlo simulation.
The first market model considers a simple case. Here the server rate
depends on a single resource that is freely obtainable at some market
price. This model is the "Nash model," for short.
In the second model, it is supposed that the server rates depend
on several resources. Each server owns a fixed amount of single
resource. Thus, the number of different resources is assumed to
be equal to the number of servers. The resource limits are
controlled using resource prices that are expressed as Lagrange
multipliers. This model is the "Walras model,"
for short. It is similar, but not identical, to the traditional
Walras model [Walras, 1874].
In the Nash model, the servers rent their equipment at fixed
price per unit of the server capacity. Therefore, in the Nash
model we are looking for the equilibrium of server capacities
and service prices.
In the Walras model, the servers share each other resources.
Therefore, here we are looking for the optimal prices charged for the
shared resources. That is in addition to the search of equilibrium of server
capacities and service prices.
Here the market models are to illustrate the possibilities and
limitations of the optimization theory and numerical techniques
in competitive environments. Both the models are developed as test
functions for the Bayesian algorithms. However, these simple
models may help to design more realistic ones describing the
processes of competition better. Besides, the simplified competitive models are convenient tools for teaching the Operations Research and the
Theory of Games and Markets.
Let us consider servers providing the same service
where is the profit, is the service price, is
the rate of customers, is the running cost, and is the
server index. Assume that a server capacity is an
increasing function of the running cost :
A simple example of this function
Here defines the maximal server rate and shows
the efficiency of resource . Then the total service cost
where is the average waiting cost. To simplify the
expressions assume that the waiting cost is equal to an average
waiting time. Suppose that arriving customers estimate the
average waiting time as the relation of the number of waiting
customers to the server capacity
A customer goes to the server , if
A customer goes away, if
where is the critical cost. The rate of incoming
consumers is fixed
where is the rate of lost customers. Conditions
(10.6) and (10.7) separate the flow of incoming
customers into flows. This makes the problem very difficult
for analytical solution. The separated flow is not simple one, even
in the case when the incoming flow is Poisson
[Gnedenko and Kovalenko, 1987]. Thus, we need the Monte Carlo simulation, to
define average rates of customers
conditions (10.6) (10.7), and average profits
by expression (10.1).
In reality, different customers value their time differently. In the simple case, one divides these customers into two categories:
busy and very busy. The time coefficient of the busy customers is set to one. The time of very busy customers is denoted by .
Therefore, parameters are different.
1 Customers of Different Taste
For busy customers
For very busy customers
Assume that the probability of very busy customer is , then the probability of busy customer is .
First we fix the initial values, the "Contract-Vector"
. The transformed values, the
, is obtained by
maximizing the profits of each server . The maximization is
performed under the assumption that all partners
will honor the contract
3 Search for Nash Equilibrium
Formally, condition (10.11) transforms the vector
into the vector . To make expressions
shorter denote this transformation by
One may obtain the equilibrium at the fixed point , where
The fixed point exists, if the feasible set is convex
and all the profit functions are convex
[Michael, 1976]. We obtain the equilibrium directly by
iterations (10.12), if the transformation is contracting
[Neuman and Morgenstern, 1953]. If not, then we minimize the square deviation
The equilibrium is achieved, if the minimum (10.14)
is zero. If the minimum (10.14) is positive then the equilibrium does not exist. That is a theoretical conclusion.
In statistical modeling, some deviations are inevitable. Therefore,
we assume that the equilibrium exists, if the minimum is
not greater then modeling errors.
One can minimize deviation (10.14) by the usual
stochastic approximation techniques [Ermoljev and Wets, 1988], if
square deviation (10.14) is an unimodal function of
. If not, then the Bayesian techniques of global stochastic
optimization [Mockus, 1989a] should be used. The global
stochastic optimization may outperform the local one in the
unimodal case, too. That happens, if the noise level is great because the
Bayesian global stochastic optimization methods are less
sensitive to large noise levels.
The Equilibrium is stable, if transformation (10.12) is locally
contracting near a fixed point (10.13). If not, then some
stabilizing conditions should be introduced. The transformation
is referred to as locally contracting, if there exists a
. Here is a
-vicinity defined by the "natural" deviations from the
The same result one obtains by the following condition.
Here the difference
shows the profit obtained by -th server
by breaking the contract . We call the sum (10.16)
as a fraud profit. Minimization of the fraud profit seems natural in economical terms
and is convenient for computations. In these terms equilibrium means a contract
where fraud is not profitable.
The first existence theorem is due to Nash [Nash, 1951] and
dates back to 1951. Many generalizations appeared since then.
Finding less and less restrictive sufficient conditions have been
an active field of research [Forgo et al., 1999]. The proofs of
these conditions are based on the various fixed point theorems
[Brouwer, 1912,Kakutani, 1941,Browder, 1968]. Considering the
examples of this book, we prefer simple existence conditions to
the general ones. Testing the existence conditions, we express
them in terms of the profit functions instead of the
For example, the stable equilibrium exists, if the profit is
strictly convex function of all the components of its parameters
, and is a convex set [Michael, 1976]. In such
cases, small changes of components will not change the
maximum points considerably.
The situation would be different in the non-strictly-convex
cases. Here even very small change of some parameters , may
change the maximum point of considerably. For
example, in linear cases this point may jump from minimal to
maximal limits. In multi-modal cases the point can jump
from one local minimum to another one.
These sharp changes violate the continuity of the
transformation . The continuity of is needed in the
Brouwer's fixed point theorem [Brouwer, 1912]. In other
theorems, such as Kakutani's [Kakutani, 1941] or Browder's
[Browder, 1968], the fixed-point conditions are less
restrictive. However, testing these conditions is not a trivial
If , the formation and stability of a coalition are important issues.
4 Stable Coalition, Core of Games
Denote by a coalition of an
individual server .
Denote by a coalition of
two servers and .
coalition of all servers.
Assume that service prices
, service rates , and shares of profit
are determined by the coalition agreement for all
the coalition members .
Denote by the number
of servers in the coalition and by
Suppose that all the remaining servers form the opposite
coalition . Assume that the profits
corresponds to equilibrium service prices and rates
This way we consider the -server system as a set of two-server
systems, where the first server is coalition and the second
one is coalition . A coalition is
stable if there is no dominant coalition such that
The definition of the stable coalition is related to the
definition of a game core [Rosenmuller, 1981].
It is well known that if
then the game core is empty
and there is no
stable coalition .
Inequality 10.18 means that a game is essential. Equality
10.19 defines a constant-sum game [Owen, 1968].
The server system is clearly not a constant-sum game. Thus one of
two "non-existence" conditions (10.19) is not satisfied
meaning that a stable coalition may exist. If a stable
coalition exists, one may determine it by testing
10.17 for all pairs of coalitions. The game core is
empty, if for any there is a dominant coalition
Consider a case of three servers .
1 Example of Server Coalition
the coalition of an individual server .
the coalition of two servers and .
the monopolistic coalition of all
Subscripts denote numbers of
servers in the coalition .
Consider for simplicity the
symmetric case. Here profit functions and control
parameters depend only on the number of servers in the
coalition but not on their "names."
The symmetric case implicitly assumes equality of the control
parameters and equal sharing of the coalition profit, meaning
that in the case of
In the case of
In the case of individual servers
The monopolistic coalition is stable if
The coalition is
The coalition is stable if
There is no stable coalition if no
of these condition are satisfied.