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

Szádoczki, Zsombor, Bozóki, Sándor ORCID: and Tekile, Hailemariam Abebe (2021) Filling in pattern designs for incomplete pairwise comparison matrices: (quasi-)regular graphs with minimal diameter. Omega . DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:

A nyílt hozzáférést az EISZ és a kiadó között létrejött "Read and Publish" szerződés biztosította. Open access was provided "Read and Publish" contract between EIS and the publisher.


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.

Item Type:Article
Uncontrolled Keywords:pairwise comparison, incomplete pairwise comparison matrix, graph, diameter, regular graph
Subjects:Mathematics, Econometrics
ID Code:6983
Deposited By: Veronika Vitéz
Deposited On:22 Oct 2021 08:50
Last Modified:22 Oct 2021 08:50

Repository Staff Only: item control page


Downloads per month over past year

View more statistics