Metodolosˇki zvezki, Vol. 2, No. 1, 2005, 125-134 Stochastic Preference and Group Decision Lavoslav Caklovic´1 Abstract In this article a notion of stochastic flow associated to stochastic preference is introduced. It is proved that stochastic flow is a consistent flow if and only if stochastic preference is consistent. If both of them are consistent, the flow and the stochastic preference, then, the normal integral of the flow is the logarithm of value function associated to stochastic preference flow. This means that normal integral of stochastic preference flow, which always exists, can be considered as a generalization of ordinal value function in that context. It is also proved that if flow preference is a weak preference order, then, normal integral of unimodular stochastic flow is a value function. This approach is applied to the data obtained from a web questionnaire when students were asked to give preference flows for certain criteria over the set of their lecturers. In that case the stochastic flow and the group flow generate equivalent ranking. Finally, we calculated the Condorcet’s flow and Savage’s value function associated to its unimodular flow. The ranking obtained from Condorcet’s flow is not equivalent to ranking obtained from stochastic flow. In this article we show that stochastic flow and group flow from Caklovic´ (2003b) generate equivalent ranking (see Tables 2 and 3). That means that in situations when only rating is the aim of the experiment one can organize a questionnaire to collect data only for stochastic flow, i.e. using the scale -1, 0,1. This is less time consuming than giving strength of a preference for each pair of alternatives. 1 Introduction Let us denote by S = {a, b, c,...} a finite set of alternatives. The classical approach to stochastic preference can be found in French (1986). The problem is as follows: To each pair of alternatives (a, b), a decision maker assigns probability pab of choosing a when the choice between a and b is offered. We assume that pab +pba = 1, with convention paa = -|. We say that a is stochastically more preferable than b ifpab ? \. A binary relation obtained in such a way we call stochastic preference, let us denote it by P. The question is which condition should satisfy numbers pab to generate a value function V on the set of alternatives, i.e. so that pab ? - ? V(a) ? V(b). (1.1) 1PMF Matematicˇki odjel, Bijenicˇka 30, 10000 Zagreb, Croatia; caklovic@math.hr 126 Lavoslav Caklovic´ Theorem 1 (French, 1986, p.101) Let us suppose that pab = 0, \/a,b. If stochastic preference satisfies srsbc =s: (1.2) for alla,b,c E S then P is necessarily a weak preference order. Sketch of the proof Choose any a E S and for b E S define f(b) := —-. (1.3) Then, (1.2) implies pbc = f(b)+f(c) and bPc & f(b) > f(c) which means that f is a value function for P. Transitivity of P is now evident. D Let us consider the following weighted directed graph (S, A) over the set of alternatives as vertices. For each pair {c, b} of alternatives an arc ? = (c, b) E A is defined if pbc > 12 with the weight p bc F?:=log — , (1.4) where the logarithm is taken with respect to some base m > 1. Evidently F? > 0, for each arc ? E A. Flow F : A —> R defined by (1.4) is called stochastic flow. If F is a complete flow (defined for all pairs) then, matrix F defined by Fbc:=F(c,b), if (c,b) E A, b=c Fbc:=-F(b,c), if (b,c) EA,b=c Fcc := 0, Vc E S is antisymmetric matrix called flow matrix. Lemma 2 Stochastic flow F : A —> R defined by (1.4) is potential difference if and only if stochastic preference P satisfies (1.2). Proof Let us suppose relation (1.2) and denote ? = (c, b) an arc. Because of (1.2) and (1.3) pbc = pba/pab = f(b) pcb pca/pac f(c) which implies that F? is a potential difference of the form F? = logf(b)-logf(c). (1.5) Presuming now that F is potential difference F? := X(b) - X(c) for each arc ? = (c, b) for some potential X : S —> R, then, evidently F? + Fß = F? (1.6) Stochastic Preference and Group Decision 127 for each ß = (c, a) and ? = (a, b) such that ß + ? = ?. If we define f by X(c) =: logf(c), yc E S then, (1.6) is equivalent to f(b) f(a) = f(b) f(a) ' f(c) f(c) , which is, on the other hand, equivalent to (1.2). This proves the lemma. D Because of equation (1.6) we can now define a consistent flow if it is a potential difference i.e. if there exists a potential X such that BX = F. (1.7) This means that potential X is defined for consistent flow. The following definition extends a notion of potential for any flow. Definition 3 A solution X of normal equation associated to (1.7) B?BX = B?F, J]Xi = 0 (1.8) ieS we call normal integral of F. If F is stochastic flow then, we call X stochastic normal integral of F. 2 Complete stochastic flow Now we are going to calculate normal integral of a complete stochastic flow, i.e. all pairs of alternatives are being compared. Let us rewrite the formula for weight function w, formula (15) from Caklovic´ (2003a), where m is the base of logarithmic function in (1.4) wa = mXa, VaeS. (2.1) We can normalize it to obtain 1-sum ranks if necessary. Using equation (2) in Caklovic´ (2003a) we can simply calculate Xa = -^ Fab (2.2) = - J](logpab - logpba) b ^ a and the weight of the node a is, by formula (2.1), 1 wa = I II —— . (2.3) The expression will be used later on. 128 Lavoslav Caklovic´ 3 The main result A consistency condition (1.2) is a sufficient condition for a value function existence associated to stochastic preference. If this is not the case, the stochastic flow still makes sense and its normal integral induces a group ranking given by formula (2.3). Normal integral of a given flow is not a value function in general. Even the question if it is doesn’t makes sense. A correct question is whether normal integral of the unimodular flow of a given flow is a value function or not, where by unimodular flow of a flow F we mean the flow with values sign F. This unimodular flow can be considered as an binary relation on the set of vertices, we call it flow preference of F, which in general, is not transitive. Next theorem, which seems not to be known in the literature, gives the answer. Theorem 4 Let F be a complete unimodular flow and y its flow preference defined by ayb^ F(b,a) > 0, a = b with convention a y a, Va G S. If relation y is transitive then, the normal integral X of F is a value function, i.e. consistent with y in the sense ayb^X(a)-X(b)>0. (3.1) Proof. Let us denote by y the strict preference relation defined by a y b & a y b and b ^ a, and by ~ equivalence relation defined by a ~ b & a y b and b y a. From the formula (2.2) it is easy to see that n ¦ X(x) = #{yeS|xyy}-#{yeS|yyx} (3.2) and n ¦ X(x) = 2V(x) - #[x] - #S where [x] denotes equivalence class of x i.e. [x] := {y E S | y ~ x}. If y ~ x then [x] = [y] and V(x) = V(y) which implies X(x) = X(y). Let us suppose now that x >- y, i.e. x ^ y i x ^ y. Then, n ¦ (X(x) - X(y)) = V(x) - V(y) + V(x) - #[x] - (V(y) - #[y]) > V(x) - #[x] - (V(y) - #[y]) = #{z e S | x y z} - #{z e S | y y z}, using transitivity of y and the fact that x y y we obtain X(x)-X(y)>0. Stochastic Preference and Group Decision 129 This proves x ^ y => X(x) > X(y). (3.3) To complete the proof we have to prove the implication X(x) > X(y) => x ^ y. Let us suppose that X(x) > X(y) and y >- x for some x,y E S. Because of (3.3) we conclude that X(y) > X(x), and y ^ x implies X(y) > X(x) which contradicts the supposition. This proves the implication and the theorem. D Corollary 5 If stochastic preference is a weak preference then, normal integral of associated unimodular stochastic flow is a value function, i.e. satisfies (3.1). If instead of unimodular flow we consider (weighted) stochastic flow it may happen that normal integral will not be consistent with underlying weak stochastic preference. It would be interesting to find a necessary condition, in terms of pab, so that normal integral of stochastic flow is a value function. 4 A test example In the sequel G denotes a group of decision makers, n := #G, and S denotes the set of alternatives, candidates in election process. Let us assume that each decision maker has three possibilities when faced with opportunity to select a or b from pair {a, b} of alternatives: • select a, • select b, • express his indifference. After the process of election had finished we had the following numbers: gba(a) = #{geG\g selected a} gba(b) = #{geG\g selected b} iba = #{geG\gis indifferent between a and b}. Furthermore, we define fba(a) = gba(a) + -iba fba(b) = gba(b) + -iba Obviously pba + pab = 1 and we can define a stochastic flow F by formula (1.4). In this example a group of 48 students were asked to give preference flows over the set S of their lecturers. The experiment was organized at the Department of Psychology of University of Zagreb. First, the students made pairwise comparisons of criteria (teaching 130 Lavoslav Caklovic´ Table 1: Stochastic flow from the example. ---------------------------------------------------------------- ;File:stochast.txt [General_section] Project=Ranking [Levels_section] level1=group,1 level3=Morgan::Charm::Jones:: Flint::Mohamad::Kekonnen::Moore::Beaute [Flow_section] [level1>group?level3] Morgan::Charm = -1.40148452661387 Morgan::Jones = -0.0180185055026783 Morgan::Mohamad = 1.28093384546206 Morgan::Kekonnen = 0.269476107955208 Morgan::Moore = -0.856050651496798 Morgan::Beaute = -1.37020822336827 Morgan::Flint = -1.3066767331552 Charm::Jones = 1.14770189886463 Charm::Mohamad = 3.41538201665411 Charm::Kekonnen = 1.31463837221346 Charm::Moore = 0.322773392263051 Charm::Beaute= -0.184192464729766 Charm::Flint= -0.314493329902438 Jones::Mohamad = 1.16074406977512 Jones::Kekonnen = 0.296265816143172 Jones::Moore = -0.76432345902784 Jones::Beaute = -1.22644566017799 Jones::Flint = -0.828692672556169 Mohamad::Kekonnen = -0.782274960455953 Mohamad::Moore = -1.88454120267902 Mohamad::Beaute = -2.73002910782099 Mohamad::Flint = -1.62113395219729 Kekonnen::Moore = -1.09861228866811 Kekonnen::Beaute = -1.59685913022724 Kekonnen::Flint = -0.896746135801185 Moore::Beaute = -0.677398823591806 Moore::Flint = -0.668249628938218 Beaute::Flint = 0.184192464729766 ---------------------------------------------------------------- Stochastic Preference and Group Decision 131 Table 2: Ranking from original data. NAME GROUP WEIGHT UNIM. WEIGHT V. Mohamad 0.243 0.168 L. Kekonnen 0.171 0.141 A. Morgan 0.149 0.138 G. Jones 0.142 0.132 A. V. Moore 0.092 0.114 N. Flint 0.072 0.104 D. Charm 0.069 0.102 P. Beaute 0.062 0.100 Inconsistency (deg) 10.17 12.17 Table 3: Ranking from stochastic flow. NAME STOCH. WEIGHT SAVAGE V. Mohamad 0.319 8 L. Kekonnen 0.157 7 A. Morgan 0.140 6 G. Jones 0.130 5 A. V. Moore 0.081 4 N. Flint 0.065 2 I D. Charm 0.056 3 1 P. Beaute 0.052 1 Inconsistency (deg) 12.41 qualities, professional competence, lecturers’ attitude towards students) on the scale 0-1-2-3-4. Second, they gave their preferences, on the set of alternatives, for each criteria using the same scale. Potential method was used to calculate the group flow (or consensus ˇ flow) and appropriate ranks. The results are given in Table C (Caklovic´, 2003b) and the column GROUP WEIGHT in Table 2 bellow is reprinted from that table. Stochastic flow is obtained using the same data simply by forgetting the strength in individual preferences given by each group member and calculated using above formulas. The question is whether the stochastic normal integral and the normal integral of weighted consensus flow gives different ranking. The answer is no and the result is shown in column STOCH. WEIGHT in Table 3. This column and the column GROUP WEIGHT in Table 2 gives the same ranking. As we have already said, the original data (for each student) is as follows: 132 Lavoslav Caklovic´ 1. preference flow on the set of criteria, 2. preference flow on the set of alternatives for each criteria. Stochastic flow construction, as we have pointed out, takes only priority, not its strength. It is also interesting to compare rankings obtained from the unimodular flow of the group flow and stochastic preference flow; generally they are different. When taking unimodular flow of the group preference flow we first take consensus and then forget its weight whereas with stochastic preference flow we consider the preference without its strength first, of each decision maker, and only after that we calculate consensus flow. It is interesting to compare the rankings obtained at the end of each process. Ranking obtained from unimodular consensus flow is given in Table 2 (UNIM. weight) and the ranking obtained from stochastic flow is given in Table 3 (STOCH. weight). They are equivalent (in our example) and they are equivalent to group ranking obtained from normal integral of group preference flow. In general, they are not equivalent and it is easy to find a counterexample. Let us explain the numbers in the column SAVAGE of Table 3. The unimodular flow of the stochastic preference flow represents a weak preference relation ^ on the set of alternatives. This can be seen from data given in Table 1. Savage’s value function is then defined by V(a) = #{beS\a^b}. (4.1) The arrows f or J,, in the table, denote that an alternative got a better or worse position when compared with stochastic rank. Generally speaking it is not true that a given flow generates a weak preference, as it is the situation with a stochastic flow in our example, see Theorem 4. The stochastic flow is given on page 130. It can be downloaded from internet address http://www.math.hr/~caklovic/Decision/Download/stochastic.txt and saved on your local disc. After doing that, you can start the program http: //dec i s ion. ma th.hr/dec i s ion/remote .pl and upload, now local, file stochastic . txt from your local disk, using the above interface, the second column in Table 3 can be checked too. 4.1 Condorcet’s flow The value of Condorcet’s flow, on the arc ? = (b, a), is defined as Jrc(?) = v(b,a)-v(a,b) where v(b, a) denotes the number of voters that prefer a against b. The Condorcet’s flow is given on page 134 and it’s normal integral is given in Table 4, column C. potential. In column savage we also calculated the value function V generated by unimodular flow of Savage’s flow. It can be noticed, that it is equivalent to ranking R generated by C. weight, i.e. R o V-1 is a strictly increasing function. The arrows f or J, have the same meaning as in Table 3. Unimodular flow of the Condorcet’s flow generates a weak preference relation and values of Savage’s value function V associated to that weak preference are given in column savage, Table 4. Theorem 4 claims that Condorcet’s ranks, obtained by PM, and Stochastic Preference and Group Decision 133 Savage’s value function are equivalent that can be seen from the table, columns C. RANKS and SAVAGE. Table 5: Ranking from Condorcet’s flow. NAME ST. RANKS C. RANKS C. POT. C. WEIGHT (R) SAVAGE (V) V. Mohamad 1 2 18.18 0.235 ˇ 7 I L. Kekonnen 2 1 22.13 0.276 ^ 8 1 A. Morgan 3 4 -0.13 0.093 ˇ 4 I G. Jones 4 3 13.63 0.182 ^ 6 1 A. V. Moore 5 5 -0.63 0.091 5 N. Flint 6 8 -26.75 0.025 ˇ 1 J, D. Charm 7 6 -12.75 0.050 ^ 3 1 P. Beaute 8 7 -14.38 0.046 ^ 2 1 In the column ST. RANKS of Table 4 ranking according to stochastic flow is given. In column C. POT. normal integral of Condorcet’s flow is given according to equation (2.1). Evidently, Condorcet’s ranks (C. RANKS) and stochastic ranks (ST. RANKS) are not equivalent. 5 Conclusion In the test example the original group weight and stochastic weight are equivalent (see Tables 2 and 3). This means that instead of asking each group member for his preference flow it is sufficient to ask him about the alternative he gives preference to, without specifying the weight of the preference. A fine analysis of group decision, such as group ˇ clustering is not possible in that case, see Caklovic´ (2003) for details. References [1] Barthe´le´my, J.-P. (1989): Social welfare and aggregation procedures: Combinatorial and Algorithmic Aspects. In Applications of combinatorics and graph theory to the biological and social sciences, IMA Vol. Math. Appl., 17, Springer, 39–73. ˇ [2] Caklovic´, L. (2005): Decision Making by Potential Method. Int. J. of Pure and Appl. Math., to appear. ˇ [3] Caklovic´, L. (2003): Graph distance in multicriteria decision making context. Metodolosˇki zvezki, 19, 25-34. [4] French, S. (1986): Decision theory, An Introdiction to the Mathematics of Rational-ity. Chichester: Ellis Horwood Limited. 134 Lavoslav Caklovic´ Table 5: Stochastic flow from the example. ------------------------------------------------------------------------------------------------------------------ ;File: Condorcet.txt [General_section] Proj ect=Ranking [Levels_section] level1=group,1 level3=Morgan::Charm::Jones::Flint::Mohamad::Kekonnen:: Moore::Beaute [Flow_section] [level1>group?level3] Morgan::Charm=-19 Morgan::Jones=19 Morgan::Mohamad=2 6 Morgan::Kekonnen=31 Morgan::Moore=1 Morgan::Beaute=-22 Morgan::Flint=-35 Charm::Jones=31 Charm::Mohamad=35 Charm::Kekonnen=35 Charm::Moore=11 Charm::Beaute=-2 Charm::Flint=-27 Jones::Mohamad=11 Jones::Kekonnen=12 Jones::Moore=-16 Jones::Beaute=-32 Jones::Flint=-34 Mohamad::Kekonnen=5 Mohamad::Moore =-21 Mohamad::Beaute=-30 Mohamad::Flint=-33 Kekonnen::Moore=-25 Kekonnen::Beaute=-33 Kekonnen::Flint=-36 Moore::Beaute=-13 Moore::Flint=-32 Beaute::Flint=-17 ----------------------------------------------------------------------------