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

Zsombor Szádoczki, Sándor Bozóki, Patrik Juhász, Sergii V. Kadenko and Vitaliy Tsyganok
Additional contact information
Sándor Bozóki: Research Group of Operations Research and Decision Systems, Research Laboratory on Engineering & Management Intelligence, Institute for Computer Science and Control (SZTAKI), Eötvös Loránd Research Network (ELKH)
Patrik Juhász: Corvinus University of Budapest
Sergii V. Kadenko: Institute for Information Recording of the National Academy of Sciences of Ukraine
Vitaliy Tsyganok: Institute for Information Recording of the National Academy of Sciences of Ukraine

Annals of Operations Research, 2023, vol. 326, issue 2, No 7, 783-807

Abstract: 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$$ 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.

Keywords: Pairwise comparison; Incomplete pairwise comparison matrix; Graph of comparisons; Filling in pattern (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04819-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:326:y:2023:i:2:d:10.1007_s10479-022-04819-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04819-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().