Sorting with stochastic comparisions

Question

Given a list where for every pair of elements (A, B) the probabilities P(A > B), P(A < B), and P(A = B) is known, how do you determine the most probable sorted permutation?

Answer 1

Let's ignore P(A=B) (we can say it splits evenly among <,> and change them to <=,>=).

Now, let's look at a similar, yet intuitively easier problem:

• let's find the best assignment such that P(arr[0]<arr[1])*...*P(arr[i]<arr[i+1])*...*P(arr[n-2]<arr[n-1]) is maximal.
• This is easier problem since we now take into account only adjacent elements, (and not for example P(arr[0]<arr[n-1]) - we use 'less' information. [proof is missing atm].

Now, we are looking to maximize the probability, which is equivalent to maximizing:

log{P(arr[0]<arr[1])} + ... + log{P(arr[n-2]<arr[n-1])}

Which in its turn is equivalent to minimizing:

-log{P(arr[0]<arr[1])} - ... - log{P(arr[n-2]<arr[n-1])}

This is a TSP with weights on edges:

w(v,u) = -log(P(v<u))

However, TSP is NP-Complete, and unless the missing proof hypothesis is wrong (still thinking on it...) - it means that there is no known polynomial solution to this problem, or at the very least to the adjacent elements only variation.