Incomplete pairwise comparison matrices based on graphs with average degree approximately 3

A crucial, both from theoretical and practical points of view, problem in preference modelling is the number of questions to ask from the decision maker. We focus on incomplete pairwise comparison matrices based on graphs whose average degree is approximately 3 (or a bit more), i.e., each item is compared to three others in average. In the range of matrix sizes we considered, $$n=5,6,7,8,9,10$$ n = 5 , 6 , 7 , 8 , 9 , 10 , this requires from 1.4n to 1.8n edges, resulting in completion ratios between 33% ( $$n=10$$ n = 10 ) and 80% ( $$n=5$$ n = 5 ). We analyze several types of union of two spanning trees (three of them building on additional ordinal information on the ranking), 2-edge-connected random graphs and 3-(quasi-)regular graphs with minimal diameter (the length of the maximal shortest path between any two vertices). The weight vectors are calculated from the natural extensions, to the incomplete case, of the two most popular weighting methods, the eigenvector method and the logarithmic least squares. These weight vectors are compared to the ones calculated from the complete matrix, and their distances (Euclidean, Chebyshev and Manhattan), rank correlations (Kendall and Spearman) and similarity (Garuti, cosine and dice indices) are computed in order to have cardinal, ordinal and proximity views during the comparisons. Surprisingly enough, only the union of two star graphs centered at the best and the second best items perform well among the graphs using additional ordinal information on the ranking. The union of two edge-disjoint spanning trees is almost always the best among the analyzed graphs.