Sort array based on binary comparisons while minimizing intransitive trials

Question

I have a list of 15 cities. I randomly draw 70 pairs out of the possible 15*14/2=105 pairs of cities. For each of the 70 pairs, I ask my participants to decide whether city A is bigger than city B. The important thing is, sometimes participants make 'mistakes' and give an answer that's incompatible with their previous answers. (i.e., it violates transitivity).

I need a way to sort my cities based on each participant's response, in a way that minimizes the number of trials that violate transitivity.

I don't need the actual order of cities, as there might not be a unique solution. I just need to calculate the (minimum) number of intransitive answers given by each participant.

How could I do this other than using exhaustive search?

EDIT: To give an example, take cities A,B,C,D and E. Participant Jon Doe thinks that the correct order of the cities (from smallest to biggest) is ABCDE. I don't care whether he's actually right or not, I just care about how well his responses -listed below- match his belief.

In three independent trials, Jon replied the following:

trial 1: A < B

trial 2: B < C (+)

trial 3: C < D

trial 4: D < E (+)

trial 5: E > B (*)

So, the answer in trial 5 (*) is incompatible with those in trials 2 and 4 together. Either one trial (nr. 5) did not correspond to Jon's belief, or 2 trials (2 and 4) didn't. I don't care to figure out which was Jon's belief (ABCDE), I just need to know that the "minimum number of intransitive answers" for Jon Doe is 1.

Answer 1

So... the problem might be interesting, but it's not clear what you want. You need to sort your cities but you don't need their order?

Minimize the number of trials that violate transitivity... how do you do that? The intransitivity is in the answers you get, not in whatever you do with them.

Calculate the number of intransitive answers given by each participant... if you have all the answers of each of the subjects, then an inconsistency is a cycle in the direct graph where nodes are cities and a node points to another iff the participant said its city is bigger than the other's. There are algorithms for that, see this question.

Of course an edge might be part of more than one cycle, and in this case we could try to find the minimum number of edges we have to remove to make it acyclical. Unfortunately, the problem is NP complete; so you won't find a fast answer. However, since your numbers are fairly low, you might manage to find a passably fast solution.

Hope this helps.