Multi
Objective Optimization and Decisions Based on Ratings Methods of Preference
Ranking
Alexey L. Sadovski
Texas A&M University-Corpus Christi
E-mail: Alexey.Sadovski@tamucc.edu
Keywords: Multi objective decisions, preference ranking, ratings, and expert evaluation.
Abstract. The problem consists of finding such x from the set of feasible decisions X that gives, in some sense, the best value to objective functions v1(x), ... , vn(x). If the set X is finite set, then we have a selection problem of decision-making. If X belongs to some continuous space, then we deal with a problem of multi objective programming. There are many approaches to the solution of such problems under consideration. The most effective method of the solution is to find some utility function G( v1(x), ... , vn(x)) of given criteria and then to solve problems of the mathematical programming:
Usually function G(·) depends on preferences of decision-makers or it is based upon expert information. Let us consider some linear-weighted aggregative objective function as an integrated objective function (utility function):
The question is how to determine the weight coefficients. Using rating methods of preference ranking, we can ask decision-makers (expert, advisers etc.) to present their preferences of objective functions v1(x), ... , vn (x) in the form of ranking, or binary, or multi-comparisons, and find coefficients ak based on final consensus ranking [1].
The preference ranking is one of the methods to solve so-called selection problems. Selection problems are very important for decision making in unique systems such as medical, environmental or ecological ones. Very often the right decision is based upon expert information. In this paper we deal with some approaches to the choice of the best variants, and its application to the multi-criteria optimization and decisions. This paper presents axiomatic systems of rating methods of preference ranking. Results include the convergence of consensus ranking to the real ranking almost everywhere, and the inclusion of the consensus ranking into the Kemeny Median set [2]. Also we will show, that all contemporary rating systems, (for instance those used in sports classifications, Sadovski [3]), are congruent in the sense of producing the same final preference ranking.
Preference Ranking. Let us consider a finite set of objects A = {a1, ... , an } and a set of m experts E. Each expert presents binary matrix Qk = (qij), k=1, ..., m, and ij=1, ... n. The problem is to find consensus ranking of objects based upon information provided by experts.
There are a few ways to solve the problem under consideration. The first one is to determine Pareto set P = {P½ Ç Qk Í P Í Qk }, but set P is too wide. The second method of the solution presented by Arrow [4] was based on a contradictory system of five axioms. The most useful result obtained by Kemeny, is the so-called Kemeny Median H= {K½ S d(K, Qk) = minSd(P,Qk)}, which can be determined by methods of integer programming. It is necessary to outline, that the Kemeny Median satisfies four of five Arrow’s axioms. Also, there is inclusion H Í P , the set H is still quite wide.
The methods presented in this paper have three advantages. First, there is a very simple numerical procedure. The second improvement is the possibility of using different forms of expert information such as preference ranking, binary and multi-comparison at the same time; this significantly differs from previous methods based on uniform types of expert information. The third advantage is that the result of this rating procedure is a unique preference ranking and not just some set of suitable alternatives such as a Pareto Set or a Kemeny Median.
Axioms of Rating Systems. Suppose there is some order of objects a1, ..., an under consideration, which is unknown to the decision-maker. Let us assume, that we have chosen some scale, and each object has its own yet unknown value r0(ai) in this chosen scale; inspire that these values are unknown we have some real, but unknown, ranking and this statement is a content of the first axiom.
Axiom 1. There is some order of given objects in any chosen scale.
Let us denote by 
the difference between real
rating values. We believe that here is
Axiom 2. Fraction
where function 
is
nonnegative increasing function and f(0)=1.
This assumption shows the odds of preferences by experts asked to ranking or compares objects.
Let ri0 i = 1,
..., n are some arbitrary initial ratings, rik
is rating of an i-th object after k-th recalculation and 
. The
following statement gives the simple way to calculate ratings of objects
according the results of expert estimations.
Axiom 3.
where 
and is nonnegative decreasing function.
It is reasonable that for large 
increasing of
rik should be small, if 
, but decreasing should be large if 
.
This idea is very useful, for instance, in sports methods of classifications:
it means that if strong team or player outs the weak one there is almost no
increasing in the rating for the winner, however in the case of losing the game
the higher rated team wastes many points. So we have two following assumptions
for function F:
Axiom 4. 
Axiom 5. 
Example. The most well known rating system has been suggested by Elo [3], and it is used for the ranking of chess players. Elo supposed that 200 points are difference between neighbor grades of players, and that probability of winning of the more qualified player is equal to 0.75. So he had chosen some scale and calculated ratings for all more or less well known players since the beginning of the century. Using the most simple function satisfied axiom 2, which is an exponent, we can determine base of this function:
and a = 1.0055
The new rating in Elo system is equal to old rating plus ten folded difference between an actual result of the match and expected outcome of the game.
Main Result. The following theorem establishes equivalency for all rating systems of preference ranking.
Theorem 1. For any initial ratings any
method based on axioms 1-5 presents some preference ranking which is the same
as a real unknown ranking with probability one in the space of realization,
when 
.
A sketch of the proof is following. Let us consider ranking of the two
objects ai and aj
as rating procedure. Hence we deal with the space of sequences 
, where 
, if and
otherwise. Each 
is realization of Berrnully trials
and there is some measure 
in the space W (2) which is generated by
probability
Suppose that 
i.e. p > ½. On the one hand
according the weak law of large numbers almost everywhere
On the other hand 
.
So with probability one in the space of realization
where qij is a
random variable. In such a way we can obtain the following equation with
respect of :
.
Because of continuity and decreasing of function F and because of p > ½
there is some positive which is solution of last
equation. So, if > 0, then
as a result of rating procedure 
with
probability one.
Now we can consider comparison of many objects. Here we deal with matrix 
.
And with more complicated ergodic
process (2). The measure in this case is constructed as the
measure of Cartesian product of one dimensional sequences.
And if for some ai and aj 
.
Remark. This theorem shows that all rating
systems are equal. Indeed, we have just discussed so called additive rating
systems of preference ranking, but the same statements and ideas are correct
for multiplicative rating methods in which 
.
Ratings and Kemeny Median. Presume that experts present information about preferences in matrix form: Qk = (qij (k)), i,j = 1, . . ., n, k = 1, . . . , m. For any two matrices of binary relations Qk and Ql distance between them may be defined in the following way:
If matrices Qk present preference ranking by experts then Kemeny median (4) is such matrix K that
The Kemeny median is really set of such matrices K, and at a present moment is the most useful consensus ranking, but determination of this median is the problem of integer programming with all difficulties of calculations. The following result establishes connection between Kemeny median and rating rankings:
Theorem 2. The consensus preference ranking obtained as a result of rating procedure belongs with probability one to the Kemeny Median set in the space of realization W.
It is easily seen that rating methods are iterative procedures for determining Kemeny Median. The proof of this theorem based on facts that Kemeny Median as well as a rating preference ranking are satisfied four of five Arrow axioms.
Applications. As a result of such procedure of preference ranking we can obtain ratings r1, ... , rn for given objectives. Suppose that we have got r1³ r2 ³ ... rn. Let the value of coefficient a1 to be equal to one, in this case using the structure of the rating procedure we can find other weight coefficients from the following relationship:
where f and are
defined by just described system of axioms preference ranking. Just defined
weight coefficients give us an opportunity to use additive integrated utility
function:
Now we are able to transform an optimization problem with many objectives to the problem of mathematical programming with only one objective function, and apply one of the developed algorithms to determine optimal solution.
In the conclusion we would like to stress out that rating systems of
preference ranking are very flexible. They provide an opportunity to work with
different types of expert information such as binary and multi-comparison,
ranking, etc. Moreover, there is a possibility to work with fuzzy information
[5]. If, for instance, 
is measure of belonging that 
then it is enough to replace qij
by in axiom 3 to use fuzzy
relationship offered by experts. The last remark concerns theorem 1, which
holds also under conditions of fuzziness.
REFERENCES
[1]. Sadovski A.L, Choice of Variants Based on Ratings Methods of Preference Ranking and Its Applications, Proceedings of the IX Annual Meeting on Applied Mathematics, Oklahoma, 1993.
[2]. Kemeny, J., Snell J., Mathematical Models in Social Sciences, The MIT Press, 1972.
[3]. Sadovski L.E., Sadovski A.L., Mathematics and Sports, American Mathematical Society, RI, 1993.
[4]. Arrow K.J., Social Choice and Individual Values, Wiley&Sons, NY, 1963.
[5]. Sadovski A.L., Application of Expert Methods in the Decision Making Problems in Conditions of Fuzzy Information, Voprosy Kibernetiky v.151 (Russian), Academic Press, Moscow, 1989.