- 1 Optimization Problems in Market Models
- 2 Nash Model

- 3 Search for Nash Equilibrium

- 4 Stable Coalition, Core of Games

10 Competition Model

with Fixed Resource Prices,

Nash Equilibrium

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 contract.

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 , by conditions (10.6) (10.7), and average profits by expression (10.1).

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 .

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 constant such that

for all . Here is a -vicinity defined by the "natural" deviations from the equilibrium.

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.

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 task.

4 Stable Coalition, Core of Games

Denote by a coalition of an individual server .

Denote by a coalition of two servers and .

Denote by a 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 .

1 Example of Server Coalition

Denote by the coalition of an individual server .

Denote by the coalition of two servers and .

Denote by the monopolistic coalition of all three servers.

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 and .

The coalition is stable if and .

The coalition is stable if and .

There is no stable coalition if no of these condition are satisfied. jonas mockus 2004-03-20