A Markov Chain Model in Decision Making

Michael G. Voskoglou *

Abstract

An absorbing Markov chain is introduced in order to give a mathematical formulation of the decision making process. Examples are also given to illustrate our results .

1. The decision making process

Decision making (d-m) is the process of choosing a solution between two or more alternatives , aiming to achieve the best possible result for a given problem.

It is obvious that this process has sense if, and only if , there exist more than one feasible solutions , together with the suitable criterion (-ia) that helps the decision maker to choose the best among these solutions .

A proposed solution is characterized as a feasible one if it satisfies all the natural restrictions imposed (onto the problem) by the real system that we study (e.g. if x denotes

the desired quantity of stock of a product, it must be x0).

From the other hand, the adoption of the suitable criterion , especially when , as it frequently happens, the results of a decision are affected by random events , depends upon the decision maker's way of thinking (e.g. optimistic or conserva tive criterion etc).

It is well known that the complexity of the problems of the everyday life led , from the beginning of the 1950's, to the development of a systematic methodology for d-m, based onProbability Theory, Statistics, Economics, Psychology etc and called **Statistical** **Decision** **Theory** (e.g. see [1]).

The d-m process involves the following steps :

d_{1} = Analysis of the decision-problem (i.e. the problem on which one has to make a decision): Understanding, simplifying and reformulating the problem ,

d_{2 }= Collection and interpretation of all the necessary information ,

d_{3} = Determination of all the alternative feasible solutions, and

d_{4} = Choice of the best solution (using the suitable criterion).

One could add one more step to the process: The verification of the chosen solution according to the results obtained by applying it in practice . But this step is extended to areas which, because of their depth and their importance for the administrative rationalism, have been autonomous and are examined separately .

Notice that the three first steps above are continuous . This means that the completion of each step does not happen very quickly, but it needs some time, during which the decision maker's reasoning is characterized by transitions between hierarchically neighbouring steps. The "flow-diagram" of the d-m process is represented in figure 1 below:

d_{1 }d_{2 }d_{3} d_{4} Fig. 1

2. The Markov chain model .

A Markov chain is a mathematical model for describing a certain type of stochastic process that moves in a sequence of phases through a set of states .

In earlier papers we have used Markov chains in problem solving ([3] and [5]), in order to describe the processes of modelling [4] and learning [6] etc .

We consider the reader familiar with the basic theory of finite Markov chains (for a good exposition see [2]) and especially of the absorbing chains ([2] , Chapt. III) .

Here, in order to give a mathematical formulation of the d-m process, we introduce a finite absorbing Markov chain having as states the steps of this process described in the previous section .

It is supposed that d_{1 }is always the starting state , while d_{4} is the unique absorbing state , because , when the chain reaches d_{4} , it is impossible to leave it .

Let us denote by p_{ij} the transition probability from state d_{i} to d_{j }, i,j = 1,2,3,4 . Then the

**transition** **matrix** of the chain is

d_{1 }d_{2} d_{3} d_{4}

A=

with p_{21}+p_{23} = p_{32}+p_{34} = 1 (1)

Let us also denote by ö_{0}, ö_{1} ,_{ }ö_{2} , ........ the several phases of the chain and let

P_{i}= [p_{1}^{( i )} p_{2}^{( i )} p_{3}^{(} ^{i ) }p_{4}^{( i )}] be the row - matrix giving the probabilities for the chain to be in each one of the states in the phase ö _{i} , i = 0,1,2,.... .

Then , since d_{1} is always the starting state, we have that P_{0} = [1 0 0 0]

Further it is well known that P_{i+1} = P_{i }A and therefore

P_{1} = P_{0}A = [0 1 0 0] , P_{2} = P_{1} A = [p_{21} 0 p_{23} 0] , P_{3} = P_{2} A = [0 p_{21}+ p_{23}p_{32} 0 p_{23}p_{34}] ,

P_{4} = P_{3}A = [p_{21}^{2}+p_{21}p_{23}p_{32} 0 p_{21}p_{23}+ p_{23}^{2}_{ }p_{32 }p_{23}p_{34 }] (2) and so on .

In general an inductive argument shows that P_{n} = P_{0}A^{n} , n = 1,2,3,... .

We shall now bring A to its **standard** **form** A* by listing the absorbing state first and then partition A* as follows

d_{4 }d_{1 }d_{2} d_{3}

A= .

Let Q = be the matrix of non absorbing states and denote by I_{3} the 3x3 unitary matrix , then it is well known that I_{3}-Q is always an invertible matrix (e.g. see [3], section 2).

The **fundamental** **matrix** N of the chain is defined to be

N = (I_{3}-Q)^{-1} = adj(I_{3}-Q) ,

where D(I_{3}-Q) denotes the determinant and adj(I_{3}-Q) denotes the adjoint matrix of I_{3}-Q .

Thus a straightforward calculation and the use of relation (1) give that

N = = [n_{ij}] , i,j = 1,2,3 (3)

We recall that the ij-th entry of N gives the mean number of times in state d_{j} before the absorption, when the chain is started in d_{i} . Therefore , since d_{1} is always the starting state, the mean number of steps taken before absorption is given by

t = = (4) .

It is clear that the bigger the value of t , the more the difficulties that the decision maker faces during the decision making process; in other words we have obtained a measure for the difficulty of the decision making process .

3. Examples

I) The management of a wine - production company A has hired a group of specialists in order to decide about the suitable place for building up a new factory and has agreed to pay them for 6 working hours (w.h.) each time where an analysis of the decision - problem is required , for 54 w.h. each time where collection and interpretation of necessary information is needed , for 28 w.h. whenever a determination of the feasible solutions is needed and for 9 w.h. for the final choice of the best solution .

We shall describe the d-m process in terms of the model presented in the previous section and we shall calculate the expected total sum of w.h. to be paid , the mean number of steps needed before taking the decision and the probability for the d-m process to be terminated in 4 steps .

d_{1} : Analysis of the decision problem

It turns out that the profitability of the decision depends upon the types of wine , say

W_{1} ,W_{2} ,....,W_{n} , which are going to be produced by the antagonist companies, say

B_{1} , B_{2} ,......, B_{m}

d_{2} : Collection and interpretation of the necessary information

Suppose that the market's research has shown that there is only an antagonist company, say B_{1},_{ }which has the potential to produce three different types of wine , say W_{1}, W_{2}, and W_{3} d_{3} : Determination of the feasible solutions

Assume that the general situation of the area where the company A acts (communications, traffic, the already existing factories and storehouses of the companies A and B_{1} etc), combined with the funds available for the construction of the new factory, suggest that there are four favorable places , say P_{1} , P_{2} , P_{3} and P_{4} for the construction of the new factory .

d_{3 }d_{2 }: Going back from d_{3} to d_{2}

Assume that the market's research shows that the expected net profits of the company A with respect to the possible places for the construction of the new factory and the types of the wine which could be produced by the antagonist company are given in table 1 below :

P_{1 }P_{2 }P_{3} P_{4}

Table 1

d_{2 }d_{3} : New transition from d_{2 }to d_{3}

From table 1 becomes evident that the feasible solution P_{4 }is worse than P_{3} and therefore P_{4 }is rejected .

d_{4}: Choice of the best solution

Assume that the management of the company has no margin to risk for low profits from the new factory and therefore wants to adopt a conservative criterion for the choice of the best place for building it up.

Such a very common criterion, due to Wald and called the maximin of payoffs (profits), suggests to maximize the minimal, for each case, possible profits. According to this criterion , since the minimal expected profit from the choice of P_{1} is 2 monetary units, while the corresponding profit from the choice of P_{2} or P_{3} is 1 monetary unit, the place P_{1} must be chosen for building up the new factory .

From the description of the d-m process above it becomes evident that p_{21 }= 0, p_{23 }= 1. Also we have that p_{32 }= p_{34 }= 0.5 . In fact , when the chain reaches state d_{3} for the first time , the probability to go back to d_{2} in the next phase is 1 (since collection and interpretation of new information becomes necessary) , while , the second time that the chain reaches d_{3} , the probability to reach d_{2} in the next phase is 0. Thus the transition probability p_{32} is equal to the average and therefore p_{34} = 1- p_{32} = 0.5. Thus, relation (3) gives that

N = and therefore n_{11} = 1 , n_{12} = n_{13} = 2 . Thus the mean number

of steps before taking the decision is t = 5 steps , while the expected total sum of w.h. to be paid is 1.6+2.54+2.28+1.9 = 179 w.h.. Further , relation (2) gives that P_{3} = [0 0.5 0 0.5] , i.e p_{4}^{(3)} = 0.5 and therefore the probability for the d-m process to be terminated in 4 steps is 50% . This could happen if there was no feasible solution worse than one of the others and therefore we didn't reject any of them (as we did for P_{4} ).

II) Consider the previous problem and assume that the market's research has shown that there is a 30% probability that a new antagonist company B_{2} will appear in the near future, offering better prices for its wines. It is nevertheless expected that the possible appearence of B_{2} will not cause dramatical changes to the general situation of the area where A acts and therefore the feasible solutions for the construction of the new factory of A will remain the same .

Under these conditions the management of the company A ,after the initial analysis of the decision-problem , the collection and interpretation of the necessary information and the determination of the feasible solutions, reach to the conclusion that it is better to postpone its decision about the new factory for one year, in order to see what will happen meanwhile. The "flow-diagram" of the d-m process up to this point is represented in figure 2 below :

d_{1} d_{2} d_{3} Figure 2

Then, if B_{2} appears, a new analysis of the decision-problem will be needed , where, apart from the antagonist companies B_{1} , B_{2} and the types of the wines that they can produce, the prices of the wines must be also be taken into consideration.

Thus, the continuation of the "flow-diagram" of figure 2 is represented in figure 3 below :

d_{3 }d_{2 }d_{1} Figure 3

d_{4}

From figures 2 and 3 becomes evident that the transition probability p_{21} is equal to the average = 0.1 and therefore p_{23} = 0.9. It becomes also evident that p_{32} = and therefore p_{34} = 0.5 .

Then relation (3) gives that N = and therefore n_{11} = 1.222 ,n_{12 }= 2.222 and n_{13} = 2 , i.e t = 5.444 steps.

Also the total sum of the expected w.h. to be paid is approximately equal to (1.222).6+(2.222).54+2.28+1.9 = 190.32 w.h. (all calculations were made with accuracy up to the third decimal point) .

Finally, from relations (2) we get that P_{3} =[0 0.55 0 0.45], therefore the probability for the d-m process to be termina ted in 4 steps is 45%

REFERENCES

[1] BERGER J. O. , Statistical Decision Theory : Foundations, Concepts and Methods, Springer-Verlag, New York, 1980 .

[2] KEMENY J. and SNELL J. , Finite Markov Chains , Springer- Verlag , New York , 1976 .

[3] VOSKOGLOU M. G. and PERDIKARIS S. C., A Markov Chain model in Problem-Solving, Int.J. Math. Educ. Sci. Technol., 22, 909-914, 1991 .

[4] VOSKOGLOU M. G., An application of Markov Chain to the process of modelling, Int. J. Math. Educ. Sci. Technol., 25, 475-480, 1994 .

[5] VOSKOGLOU M. G., An application of ergodic Markov Chains to Analogical Problem-Solving, The Mathematics Education (India), 30, 96-108, 1996 .

[6] VOSKOGLOU M. G., Use of Markov Chains to describe the process of Learning, Theta (U.K.), 10, 36-40, 1996 .

_______________

* Tecnological Educational Institute (T.E.I.) - Messolonghi - Greece