Hi. I don't have a straight answer to your question, but maybe you could attack the problem by ranking your data points according to the probability P(x < x_k) for a each data index k, which can be estimated as the sum over j of I(x_j < x_k) divided by n, where I(p) = 1 if p is true and 0 otherwise. If n is large enough, you may be able to sort the data by their rank.

Can you be a bit more precise with your problem formulation. Just a bit more would be needed to answer this better and point you in the right direction. You say that the partial ordering can be allowed but other times it is not. What makes this different than just the classic sorting problem? Can't you just number the values from the fuzzy source with pseudo-values (that reflect the inequalities you are given), then just sort that or use ranking techniques like Alfonzo suggests? How bad can it be sorted (i.e., if I were to count n elements in the set where |X|=n, how many can I have wrong at worst)? Any type of clarification or an example would be useful for researchers or myself for answering your question.

Are you interested in randomized sorting algorithms? Or approximation algorithms? Exact algorithms? How is the data brought in for the ideal algorithm. You mention X, but what about the actual array of elements as input?

I'm not sure if this will help, but in Introduction to Algorithms by Cormen et al., they ask about a Fuzzy Sorting Algorithm (p.163 (ish) if I recall off the top of my head). This blog looks at giving a solution to that exercise, http://mypathtothe4.blogspot.ca/2013/02/quicksort-continued-fuzzy-sorting.html

Hope this helps!

As I understand, you have less than nxn pairwise orderings, but - because there can be contradictions - you don't have a partial ordering. I'd suggest "u-statistics". For each variable, you count how many of the other variables are "less" and subtract the number that are "more". This gives you an u-score for this variable, see http://www.ncbi.nlm.nih.gov/pubmed/15122738. This approach is intended to work with different people "voting" for subsets of pairs, creating "loops".

Thanks Alfonso, Daniel and Knut for your helpful comments. Here is more information about the context:

In an experiment, I show participants one query image on the left and two test images (x_i) and (x_j) on the right and ask them to "vote" which one of test images is more similar to the query image, hence (x_i>x_j) or the other way around. Collecting data for many test images from many subjects, the goal is to now sort the test images based on their similarity to the query image. So, contradictions come from variations in judgements even for one particular subjects. The number of inequalities are normally very large but there is no guarantee that all the possible combinations (actually, nchoosek(n,2), not nxn ) of pairs of images exist in the set of judgements.

Thank you so much for taking the time to reply. Any further comments would be much appreciated as well.

From your explanation u-statistics should work, but if you don't have judgments for all n(n-1)/2 pairs you may have a bias.

Thanks, I will check that out.

I've seen a similar experiment setup. The purpose is image distortion analysis. I guess they stick to the mean observer (i.e. opinion) score (MOS).

Simply, for an image I and a reference image R,they compute the average score similarity to the reference image provided. http://link.springer.com/chapter/10.1007%2F978-3-319-02895-8_36

I guess MOS should work perfectly in case of bias-free data to obtain the sorting of a series of images to a reference image. [I am not sure if it fits to the u-statistics class where you are taking the sample mean or not]

There is at least two questions unsolved to me.

1) If it is the matter of similarity to a query, why did not use a similarity score? For instance, you can show one image and ask people to assess its similarity on the score of 0~10 (or something like that)? Why a pair of test images? What constraint/purpose makes you to present two images? (e.g. in the case of the example above, a paired comparison was needed because identifying the more influential distortion is kind of important to the authors) Can't this constraint be utilized later or implemented another way? [I guess this helps if you are in the feasibility study of data gathering]

2) Is the sort with respect to the reference image enough for you, or do you want to establish a relation between all of the images doing such a comparison to several control images? (this question came to me based on your former formulation)