Incomplete pairwise comparison matrices based on graphs with average degree approximately 3
研究了基于平均度约3的图的不完全成对比较矩阵，分析了多种图结构下权重向量的准确性，发现两个边不相交生成树的并集在多数情况下表现最佳。
Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>5</mml:mn> <mml:mo>,</mml:mo> <mml:mn>6</mml:mn> <mml:mo>,</mml:mo> <mml:mn>7</mml:mn> <mml:mo>,</mml:mo> <mml:mn>8</mml:mn> <mml:mo>,</mml:mo> <mml:mn>9</mml:mn> <mml:mo>,</mml:mo> <mml:mn>10</mml:mn> </mml:mrow> </mml:math> , this requires from 1.4 n to 1.8 n edges, resulting in completion ratios between 33% ( $$n=10$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>10</mml:mn> </mml:mrow> </mml:math> ) and 80% ( $$n=5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> ). 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.