Suppose there are x number of objects to be ranked. Then there are x[(x-1)/2] possible comparisons of these objects. Only subsets of x can be evaluated for comparisons and there is always one most and one least preferred object as defined by a user. These subsets have a constant number of y objects in them.
For example, suppose there are 7 numbered objects (1, 2, 3, 4, 5, 6, 7) for which a user has a ranking of (1>2>3>4>5>6>7). 4 objects are allowed to be shown at a time to the user to attempt to reveal their ranking of the objects. Note that there are 21 possible pairwise comparisons.
If 1, 2, 3, 4 are randomly shown to a user, and the user chooses 1 as most preferred and 4 as least preferred. 5 pairwise comparisons are generated: 1>2, 1>3, 1>4, 2>4, and 3>4 (the comparison between 2 and 3 is unresolved). What would be the next best 4 object set to show the user to maximize the number of comparisons by taking advantage of transitivity? Then, the next best 4 objects to show based on the users most and least preferred choices in the second iteration an so on. The aim is to minimize the number of sets to be shown that will reveal the maximum x[(x-1)/2] possible comparisons.
I envision a matrix could keep track of the comparisons by placing a 1 in the off diagonals of the matrix if a object was more desired. For example, if the hypothetical ranking for the user was revealed the matrix would look as follows:
M 1 2 3 4 5 6 7
1 X
2 1 X
3 1 1 X
4 1 1 1 X
5 1 1 1 1 X
6 1 1 1 1 1 X
7 1 1 1 1 1 1 X
T 6 5 4 3 2 1 0
Notice that the row with a T as the first element (indicating total) sums the elements in each column and reveals the users ranking of the objects (although now with the scale reversed i.e. 1 is the best with a score of 6 and so on).
Could the information in this matrix be used to choose the next best 4 object set to show?
It seems that solving the for the elements in the diagonals just off the main diagonal in the matrix would maximize the number of object comparisons produced from transitivity.
