Counting All Common Subsequences to Order Alternatives

摘要

Many real world tasks involve the need to order alternatives based on specifications of preference over subsets of the alternatives, the problem of preference based alternative ordering. Examples include dancing championship adjudication, Eurovision Song Contest decision-making, collaborative filtering and meta-search engines. One usual solution to this problem consists in allocating scores to the alternatives and aggregating the scores to generate ranks for all alternatives. Examples of this solution include competition adjudication. Another solution involves generating ranks from different sources for all the alternatives and then adding the rank values of each alternative to give the Borda scores for this alternative. The Borda scores are then used to order the alternatives. Examples include elections and meta-search engines. The problem with these two approaches is, the scores or ranks are sometimes hard to determine (e.g., collaborative filtering). In this paper we take the view that relative preferences over alternatives (e.g., one alternative is preferred to another) are easier to obtain than absolute scores or ranks. We consider an alternative approach to this problem where, instead of using absolute scores or ranks, we use relative preferences over subsets of the alternatives to generate a total ordering that is maximally agreeable with the given preferences. We consider a set of preference specifications over all or part of the alternatives. For every pair of alternatives we calculate the probability that the two alternatives should be placed in an order. Then the Order-By-Preference algorithm is used to construct a total ordering for all the alternatives, which is guaranteed to be approximately optimal.