Filling in pattern designs for incomplete pairwise comparison matrices: (quasi-)regular graphs with minimal diameter

Pairwise comparisons have become popular in the theory and practice of preference modelling and quantification. In case of incomplete data, the arrangements of known comparisons are crucial for the quality of results. We focus on decision problems where the set of pairwise comparisons can be chosen and it is designed completely before the decision making process, without any further prior information. The objective of this paper is to provide recommendations for filling patterns of incomplete pairwise comparison matrices based on their graph representation. The proposed graphs are regular and quasi-regular ones with minimal diameter (longest shortest path). Regularity means that each item is compared to others for the same number of times, resulting in a kind of symmetry. A graph on an odd number of vertices is called quasi-regular, if the degree of every vertex is the same odd number, except for one vertex whose degree is larger by one. We draw attention to the diameter, which is missing from the relevant literature, in order to remain the closest to direct comparisons. If the diameter of the graph of comparisons is as low as possible (among the graphs of the same number of edges), we can decrease the cumulated errors that are caused by the intermediate comparisons of a long path between two items. Contributions of this paper include a list containing (quasi-)regular graphs with diameter 2 and 3 up until 24 vertices. Extensive numerical tests show that the recommended graphs indeed lead to better weight vectors compared to various other graphs with the same number of edges. It is also revealed by examples that neither regularity nor small diameter is sufficient on its own, both properties are needed. Both theorists and practitioners can utilize the results, given in several formats in the appendix: plotted graph, adjacency matrix, list of edges, Graph6’ code.