# Is there a way to estimate the minimal number of pairwise comparisons required to place complete ordering over a set of items?

I have 200 items that I need users to compare. If there are 2 items, A and B, then the comparison is A before B or B before A. Since there 200 items, this is $\binom{200}{2} = 19,900$ possible combinations. These combinations are uniformly and independently drawn and shown to the users to evaluate. There is a very good chance that some combinations will not ever be shown, and hence, we will never know the comparison between those combinations.

My question is this: is there a way to estimate the minimum/required number of pairwise comparisons needed to place complete order over a set of items?

Example: We have 3 items {A, B, C}. If we compare {A,B} with B < A and {B,C} with B > C, then we can say the order is C, B, A.

• Who are "the users"? Are you interested in orderings for one specific user, or in some "population average ordering", whatever that means? Do you need an exact ordering of all the 200 items, or is some coarse ordering enough (say knowing the rank to within ~$\pm 10$, say)? – kjetil b halvorsen Jun 22 '18 at 15:49
• The users are essentially survey respondents; they are subject matter experts. Both individual and population ordering are of interest, as well as exact and fuzzy ordering. – Jane Wayne Jun 22 '18 at 15:52
• Can you please ad that new information as an edit to the post? And, how do you propose to define a population ordering? – kjetil b halvorsen Jun 22 '18 at 16:11
• If you do not get an answer here it might be worth trying a mathematics or computing site. – mdewey Jun 22 '18 at 16:32
• Why wouldn't this question be a variant of issues wrt stochastic dominance and/or exchangeability? McCullagh has a nice paper discussing the nuances of these topics, Exchangeability and regression models stat.uchicago.edu/~pmcc/reports/exchangeability.pdf or, alternatively, this paper Ranking Sets of Objects pareto.uab.es/sbarbera/SB-sets7-hut2.pdf – Mike Hunter Jun 23 '18 at 17:07

This is so far a very incomplete answer. I suppose 200 items, which we sample independently and uniformly. If there is any prior information on the ordering, one could maybe do better than that. I will represent the items as the integers $1,2,\dotsc, 200$ and suppose (in the simulations shown) that the true ordering (for one person) is the usual ordering of integers. Then I suppose that the response on the pairs given is without error. We will need later to pass by such strong assumptions. So the question is: "how many pairs do we have to sample to get to know the true ordering?"

I will answer a some what different question. We will represent the sampled pairs as a directed graph, calculate the connected components of that graph and find the length of the longest connected component. First I show a plot of a such graph, made with the R igraph package. This graph is simulated as above with 50 vertices and 50 pair comparisons, its largest component has 42 vertices and there is 8 isolated vertices. Looking closer at the largest component: From this graph we can see that, for instance, both 17 and 21 is between 6 and 39, but there is no comparison between 17 and 21 themselves. So from such a graph we can calculate some fuzzy ranking, but it should be clear that if you want a complete ranking, the number of pair comparisons required will be very large!

To advance more I guess we will need some probability model on rankings, I will try to come back with that.