Some probabilistic properties of the nearest adjoining order method and its extensions

Abstract

In this paper, some probabilistic properties of the nearest adjoining order (NAO) method are presented. They have been obtained under weaker assumptions than those commonly used, i.e. it is not assumed that comparisons are not independent and that probability of comparison errors are known. The results presented comprise the evaluation of the probability of obtaining an errorless solution with the use of the NAO method; asymptotic properties of this solution derived under the assumption that comparisons of different pairs (i.e. pairsx _i ,x _j andx _r ,x _r fori ≠r,s andj ≠r,s) are not correlated — for the case of one expert. An extension of results for the case ofN > 1 independent experts is also presented. This extension is accomplished by including an additional step — the aggregation of comparisons made by all experts for each pair of objects. Two ways of such an aggregation are analyzed: the averaging of experts' opinions and the majority principle. In the latter case, the result of the comparison is the same as the opinion of the majority of experts. The results obtained indicate an exponential convergence of the probability of the NAO solution to an errorless one in both cases. However, an application of the majority principle leads to a minimization problem, which is the same as in the case ofN = 1 and is much simpler than that corresponding to averaging of comparisons.