Evaluation of the ranking probabilities for partial orders based on random linear extensions

Partial order theory and Hasse diagrams appears to be a promising tool for decision-making in environmental issues. Alternatives or objects are said to be partial ordered when it is impossible to find a mutual relationship (< or >) for all criteria. This is often the case in complicated real life situations. However, sometimes it is attractive to apply a total order, i.e. linear rank, and not just the partial order. Based on ranking probabilities and linear extensions it is possible to derive a total order. A linear extension is a projection of the partial order into a total order that comply with all the relations in the partial order. When all linear extensions are known the ranking probabilities can be found as the probability for an object to occupy a specific rank. However, the total number of linear extensions is proportional with the faculty of the number of objects in the partial order. Therefore it is practically impossible to identify all possible linear extensions for partial orders with more than around 20 objects. This study reviews and evaluates a method which estimates the ranking probability based on sampling of a minor random fraction of the linear extensions. Using standard statistics the necessary number of random linear extensions is described as a function of the ranking probability estimate and the restrictions on the confidence interval around the ranking probability. The analysis reveals a smaller systematic uncertainty, which occurs due to the random selection of ranking between two incomparable objects. The discrepancy appears to be dependent on the structure of the partial order. The method using random linear extensions thus appears as a valuable tool for analysing larger partially ordered sets, which are practically impossible to handle using the total set of linear extensions. (C) 2003 Elsevier Ltd. All rights reserved.