A new decision making model based on Rank Centrality for GDM with fuzzy preference relations

ContentslistsavailableatScienceDirect

European Journal of Operational Research

journalhomepage:www.elsevier.com/locate/ejor

Decision Support

A new decision making model based on Rank Centrality for GDM with fuzzy preference relations

Anis Yazidi

^{a,b,c,g,h,∗}

, Magdalena Ivanovska

^d

, Fabio M. Zennaro

^e

, Pedro G. Lind

^a,b,c

, Enrique Herrera Viedma

^f

aDepartment of Computer Science, OsloMet – Oslo Metropolitan University, P.O. Box 4 St. Olavs plass, Oslo N-0130, Norway

bORCA – OsloMet Research Center for AI, Pilestredet 52, Oslo N-0166, Norway

cNordSTAR – Nordic Center for Sustainable and Trustworthy AI Research, Pilestredet 52, Oslo N-0166, Norway

dDepartment of Data Science and Analytics, BI Norwegian Business School, Nydalsveien 37, Oslo N-0484, Norway

eDepartment of Informatics, University of Oslo, P.O. Box 1080 Blindern, Oslo N-0316, Norway

fAndalusian Research Institute in Data Science and Computational Intelligence, University of Granada, Granada 18071, Spain

gDepartment of Computer Science, Norwegian University of Science and Technology, Trondheim, Norway

hDepartment of Plastic and Reconstructive Surgery, Oslo University Hospital, Oslo, Norway

a rt i c l e i nf o

Article history:

Received 2 June 2020 Accepted 19 May 2021 Available online 1 June 2021 Keywords:

Decision support systems Group decision making Fuzzy preference relations Rank Centrality Markov chains

a b s t r a c t

Preference aggregation inGroupDecision Making (GDM)is asubstantialproblem thathas receiveda lotofresearchattention.Decisionproblemsinvolvingfuzzypreferencerelationsconstituteanimportant classwithinGDM.Legacyapproachesdealingwiththelattertypeofproblemscanbeclassifiedintoin- directapproaches,whichinvolvederivingagrouppreferencematrixasanintermediatestep,anddirect approaches,whichdeduceagrouppreferencerankingbasedonindividualpreferencerankings.Although theworkonindirectapproacheshasbeenextensiveintheliterature,thereisstillascarcityofresearch dealingwiththedirectapproaches.Inthispaperwepresentadirectapproachtowardsaggregatingsev- eralfuzzypreferencerelationsonasetofalternativesintoasingleweightedrankingofthealternatives.

By mappingthepairwisepreferencesintotransitions probabilities,weareabletoderive apreference rankingfrom thestationary distributionofastochastic matrix.Interestingly,the rankingofthe alter- nativesobtainedwithourmethodcorrespondstotheoptimizeroftheMaximumLikelihoodEstimation ofaparticularBradley-Terry-Lucemodel.Furthermore,weperformatheoretical sensitivityanalysisof theproposedmethodsupportedbyexperimentalresultsandillustrateourapproachtowardsGDMwith aconcretenumerical example.Thiswork opensavenues forsolving GDMproblemsusingelements of probabilitytheory,andthus,providesasoundtheoreticalfundamentaswellasplausiblestatisticalinter- pretationfortheaggregationofexpertopinionsinGDM.

© 2021 The Authors. Published by Elsevier B.V.

ThisisanopenaccessarticleundertheCCBYlicense(http://creativecommons.org/licenses/by/4.0/)

1. Introduction

Groupdecisionmaking(GDM)settingsinvolveagroupofindi- viduals (experts),whereeach memberofthegroup expressesher preferences over a set of alternatives. Illustrative examples range fromparliamentarygroupsworkingtoconvergeonapoliticaldeci- sion,togroupsoffriendsdecidingonthebestchoiceofrestaurant foradinner.TheaimofGDMistoidentifythemostpreferredal- ternativeforthewholegroupofindividuals,ortoderivearanking ofthealternativesthatreflectsthepreferencesofthegroup.

∗Corresponding author.

E-mail addresses: [email protected] (A. Yazidi), [email protected] (E.H.

Viedma).

Theliteratureproposesmanydifferentformsofexpressingpref- erences of experts (Capuano, Chiclana, Fujita, Herrera-Viedma, &

Loia,2017).Someofthemostpopularonesarethefollowing:

• Rankings, which are ranked lists of the alternatives from the mostpreferredtotheleastpreferredone(Seo&Sakawa,1985).

• Utility vectors,where each componentof the vector describes theutilityofthecorrespondingalternative,whichcanbe seen as its ordinal strength (Tanino, 1990). These are sometimes calledpriority vectors or weighted rankings. We use the latter expressionthroughoutthispaper.

• Preferencerelations, wherepreferenceis expressedas abinary relationonthesetofalternatives(Kitainik,2012).

• FuzzyPreference Relations (FPRs), which relax the binary pref- erencerelations with the possibility of expressing degrees of https://doi.org/10.1016/j.ejor.2021.05.030

0377-2217/© 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )

preference among the alternatives (Pedrycz, Ekel, & Parreiras, 2010).Preferencedegreescanbeassessedusinglinguisticterm setswhichcanbemorenaturalforhumanexperttoarticulate (Ureña,Kou,Wu,Chiclana,&Herrera-Viedma,2019).

FPR is themostcommonlyused representationforexpressing preferences ina setof alternatives,in whichan expertexpresses her preferences asdegreesofpreferenceassignedto eachpair of alternatives. The mostcommon wayto store thesepairwisepref- erences is in the form of a preference matrix. The main reason behind the popularity of the preference relations comes from a knownfactfrompsychologystudiesthathumanbeingsarebetter atcomparingpairsofalternativesthanatcomingupwithacom- pletepreferenceorderingofasetofalternatives(Ureña,Chiclana, Morente-Molinera,&Herrera-Viedma,2015).

WithinGDMinvolvingFPR,therearetwo mainfamiliesofap- proaches:directapproachesandindirectapproaches.The indirect approachesfirstcompute thegroupopinionintheformofanFPR (wewillcallita grouporacollectiveFPR),usually expressedasa preferencematrix,andthen findasolutionwhichisa(weighted) ranking ofthe differentalternatives based on the collective FPR.

The collective preference matrix is generally derived by apply- ing an aggregationoperator to the individual ones. On the other hand, thedirect approachesdonot involveconstructing a collec- tive preference matrix describing the group opinion as an inter- mediate step. They first compute an individual ranking for each expertbasedon her FPR,andthenthe groupranking isobtained from the individual rankings ofthe experts usingan aggregation operator. Forexcellent surveyson consensus processes andpref- erenceaggregationwereferthereadertothecomprehensivesur- veys (Cabrerizo, Moreno,Pérez,&Herrera-Viedma,2010;Herrera- Viedma,Cabrerizo,Kacprzyk,&Pedrycz,2014)andtothebookby Herrera-Viedmaetal.(2011).

While studies on indirectapproachesfor aggregatingpairwise preferences abound, thedirectapproaches arenot aspopular, al- thoughthereareafewexceptions(Dong,Xu,&Yu,2009;Fan,Ma, Jiang, Sun, & Ma, 2006). Herrera and his collaborators (Herrera, Herrera-Viedma, & Verdegay,1996) pioneered the firstdirect ap- proachtowardsGDMbasedonFPR.However,theworkinthisdi- rectionisveryscarce,althoughitisknownthatdirectapproaches usually possesstwo desirableproperties,internalconsistency and Paretoprincipleofthesocialchoicetheory(Dong&Zhang,2014).

Oneofthefewavailabledirectapproachesintheliteraturewas recentlypresentedbyDongetal.in(Dong&Zhang,2014).There, the authors extended the original direct approach presented in (Herreraetal., 1996) inorder tosupport(i) differentpreferences representations,and(ii)aconsensusprocessintheformofrounds whereexpertsarerequiredtoadjusttheirpairwisepreferences.In- terestingly, inorder toachieve consensus, Dong etal.resort toa formofafeedbackbasedonmeasuringconsensususingtheindi- vidual weightedrankings oftheexperts.Thisis distinctfromthe main streamofresearch inFPRsince consensus degreecomputa- tion is not based onweighted rankings ofindividual experts but rather based on elements from the preferencematrices. The ap- proach by Dong etal. allows the experts to update their prefer- ence matricesin orderto reach a consensus, defining two quan- tities, namely the cardinal consensus degree, based on the vec- tor representationinspired by(Chiclana,Herrera,Herrera-Viedma,

& Martínez, 2003; Dong, Xu, Li, & Feng, 2010) and the ordinal consensusdegreeinspiredby(Herrera-Viedma,Alonso,Chiclana,&

Herrera,2007;Herrera-Viedma,Herrera,&Chiclana,2002).

In this article, we take a direct approach towards group de- cision making given fuzzy preferences over a set of alternatives.

We propose a method for aggregating the opinions of several experts, which are expressed as FPRs, into a single weighted ranking of the alternatives. Similarly to the work in (Dopazo &

Martínez-Céspedes, 2017), we transform the preference matrices intostochasticmatrices,andthenusethetheoryofMarkovchains andrandom walks to compute rankings over the alternatives, as implementedinthePageRankalgorithm (Gleich,2015). Onemain difference in this paper compared to the method in (Dopazo &

Martínez-Céspedes, 2017) lays in the definition of the stochastic matrix.In(Dopazo&Martínez-Céspedes,2017)thestochasticma- trixissimplya column-normalizationofthepreferencematrixso that its entriesare proportional tothe corresponding preferences and representthe probabilities (relative strengths) ofdominance betweenthealternatives.Inourframeworkwe determinetheen- triesofthestochasticmatrixsimilarlyasin(Negahban,Oh,&Shah, 2012;2016)andthey representtheprobabilities oftransiting be- tween the corresponding alternatives in the way that the prob- ability oftransition fromalternative x to alternative y is propor- tionaltothedegreeofpreferenceofytox.Thestationaryvectors, however,havesimilarinterpretationinbothourapproachandthe approach in(Dopazo & Martínez-Céspedes,2017) as their entries representpreferencestrengthsofthecorrespondingalternativesin both the cases. The difference is that the normalization we use leadstoa stationaryvectorthat satisfies theglobalbalanceprop- ertywithrespecttothepreferencematrix:thepreferencestrength of an alternative depends on whether the alternative dominates weakorstrongalternatives.ThisisthecoreideaoftheRankCen- tralitymethod(Negahban etal.,2012;2016) andwe discussitin moredetailinSection3.1.

Noticethatassigningandinterpretingadegreeofpreferenceis not straightforward. Using a probability value to quantifyan FPR gives an intuitive interpretation of FPR itself and, moreover, en- ablestoestablishalinkbetweenprobabilitytheoryandpreference aggregation.Furthermore,weprovethattheweightedrankingob- tained as a resultof the method presented in thispaper corre- spondsto theresultof MaximumLikelihood Estimation (MLE)of thePlackett-Lucemodel(Plackett,1975).

Thereisabodyofliteratureonmethodsthatcomputeweighted ranking from preference matrices based on optimization tech- niques such asleastsquare method(Gong,2008), leastdeviation method (Xu & Da, 2005), multiobjective optimization(Fernandez

& Leyva, 2004), new fuzzy linear programming method (FLPM) (Zhu & Xu, 2014), goal programming (Fan et al., 2006), etc. Al- thoughthesemethodsareshowntoprovidegoodresults,theyre- layonhuman-engineeredtechniquesorheuristicsanddonotpro- vide plausibletheoretical interpretation oftheir computationand modellingsteps.Ourworkisdistinctfromthelatterworksasthe waywe derivea rankingvector can beexplained usingprobabil- itytheoryandthusweprovidea theoreticalinterpretationofour framework.

Indeed,asmentionedabove,ourworkisdirectlyinspiredby a recentworkon RankCentralityalgorithm (Negahbanetal., 2012;

2016), whichaggregatesa setofpairwisecomparisonsofalterna- tivesintoaglobalweightedranking.Inrankingbasedonpairwise comparisons,thegoalistorank,forexample,footballteamsbased onresultsofplayedmatchesbetweenthem.Thisproblemhasan obviousanalogywithrankingofalternativesbasedonpairwiseex- pressedpreferences,butdespitethevastamountofworkonrank- ing alternatives based on preferences, to the best of our knowl- edge,theideasofRankCentralityhavenotyetbeenadoptedinthe contextoffuzzypreferenceaggregation.Wearguethatbyproperly transformingthe fuzzypreferencesintoprobabilities oftransition betweenalternatives,probabilitytheorycannaturallybeappliedin preferenceaggregationand,consequently,wehopethatourframe- workcaninspirefurtherresearchinthatdirection.

The remainder of this paper is structured as follows. In Section 2 we introduce the relevant background and the fun- damental concepts of the state of the art in fuzzy preferences.

Section3presentsourapproachforaggregatingpreferencesbased

ontheconceptofMarkovchainsanddiscussestheconditionsun- derwhichsomedesirablepropertiesfortheaggregationprocesses hold. In Section 4 we provide a theoretical sensitivity analysis oftheproposed aggregationmethod.Concrete numericalexample showingthe consistencyofour frameworkfollowed byan exper- imental sensitivityanalysisisgiveninSection5.Finaldiscussions andconclusionsareprovidedinSection6.

2. Backgroundandpreliminaryconcepts

In the following we assume that E=

{

^e1,...,em

}

^{is a set of}

experts and X=

{

^x1,...,xn

}

^{is a set of} alternatives. We use the following definition ofa fuzzypreference relationas provided in (Herrera-Viedma,Herrera,Chiclana,&Luque,2004).

AFuzzyPreferenceRelation(FPR)P onasetofalternativesX is afuzzysetontheproductsetX×X,i.e.arelationonX character- izedbyamembershipfunction

μ

^{P:X×X→[0,1]. (1)}

p_{i j}=

μ

P(^xi,x_j)^isinterpreted asthepreference degreeofthealter- nativex_ioverthealternativex_j.Ausualnaturalassumptionisthat p_{i j}+p_ji=1,for every i,j∈

{

¹,...,n

}

^{,i.e. thatP isadditive recip-}

rocal.Ifp_{i j}>0.5,we saythatx_i ispreferredtox_j;if p_{i j}=0.5,we saythatweareindifferentbetweenx_iandx_j;andp_{i j}=1indicates that x_iisabsolutelypreferredtox_j.Theadditivereciprocity prop- ertyensuresthat p_ii=0.5andp_{i j}>0.5iffp_ji<0.5.

When the set X is not too big, it is convenient to represent P asan n×n matrixof preferencevalues,wheren=

|

^X

|

^,i.e.P= [p_{i j}]n×n.We callthisapreference matrix.Forconvenience,we use the samenotationforboth the fuzzypreferencerelationandthe correspondingpreferencematrix.

We assume that each of the m experts expresses her prefer- encesindependentlyofeachotherandintheformofafuzzypref- erence relation.Letus denoteby P^(k) theFPR of thek-thexpert andletP^(k)=[p⁽_{i j}^k)]_n×nbethecorrespondingpreferencematrix.

AnindirectapproachtoGDMaimsatreachingacollectiveopin- ionbyfirstaggregatingalltheindividualpreferencematricesintoa collectiveFPR.Adirectapproachwouldpredictthecollectiveopin- ionoraGDM-”target”,ingeneral,byturningexperts’FPRmatrices intovectorswhoseentriesmeasuretherankingofthealternatives.

More formally,a weightedranking can be defined as a function r:X→R,whichmapseachalternativeinX intoits absolutepref- erencestrength.¹ Aggregatingtheindividualrankingvectorsyields apossibleconsensustargetforthesetofindividuals.

Whatever approach one chooses, direct or indirect, there are two mainphasesinGDMbasedonFPR, anaggregationphase and anexploitationphase.

In the aggregationphase, the corresponding individual prefer- encevalues(correspondingentriesinFPRmatricesorrankingvec- tors)areaggregatedintoacollectivepreferencevalueusinganag- gregationoperator.

There are manyaggregationoperators, such asweightedaver- age (WA),fuzzymajority, etc.One popularexample istheopera- tor calledOrdered WeightedAveraging(OWA)dueto(Yager,1988).

TheWAandtheOWAoperatorspresumewehavealistofweights w=(^w1,...,wm)^,wk∈[0,1],k=1,...,m,suchthat

w_k=1.Let p₁,...,pm be a listof preferencevalues to be aggregated. While the WA operator is definedas a simpleweighted average ofthe preferences:

WA

(

^p1,. . ., pm

)

= m

k=1

w_kp_k, (2)

1The ordering of the alternatives is implicit in each weighted ranking and follows from the linear order of the real numbers: Alternatives assigned a higher number rank higher, and alternatives assigned the same number rank the same.

theOWAoperatorisdefinedas OWA

(

^p1,..., pm

)

=

m

k=1

w_kp_{σ (k)}, (3)

where

σ

^isapermutationoftheset

{

¹,...,m

}

^{suchthat p}_{σ (}k+1)≥ p_{σ (k)}fork∈

{

⁰,...,m−1

}

^.

In the case of WA, the weights w=(^w1,...,wm) ^{can be as-} sumed to be corresponding to the importance of the experts in thegroupwithrespecttotheparticulardecisionmakingproblem, orto theconfidence ofthe expertsintheir opinions.In thecase ofOWA,assigningweights wenablesweightingdifferentlyprefer- ences ofdifferent strength,giving morevalue to strongerprefer- ences,forexample.BychoosingdifferentwinWAandOWA,one canimplementdifferentaggregationoperators.

The exploitation phase is the phase of deducinga (weighted) rankingvectorbasedonafuzzypreferencerelation(matrix).

Tworelevant approachestowards defining the rankingin this phase are (Herrera etal., 1996): Quantifier-Guided DominanceDe- gree (QGDD), where the rank of each alternative represents the dominanceorimportanceofthealternativeovertherestoftheal- ternatives;andQuantifier-GuidedNon-DominanceDegree(QGNDD), wheretherankofeachalternativerepresentsthedegreetowhich thealternativeisnotdominatedbytherestofthealternatives.An alternativetoQGDDandQGNDDistheNetflowmethod(Bouyssou, 1992)which isalsobasedon dominanceofan alternative.² More precisely, this method defines the rank of an alternative as the difference betweentheinflowandthe outflowofpreferencefrom it,which,undertheadditivereciprocityassumption(p_{i j}+p_ji=1), reducestothefollowingexpression:

NF

(

^xi

)

= n

j=1,j=i

pi j− n

j=1,j=i

pji

= n

j=1,j=i

2p_{i j}−n+1

=2

_n

j=1,j=i

p_{i j}−n−1 2

. (4)

Notice that the Netflow method is related to the Copeland vot- ingrulein(Marchant,1996). Anaxiomaticcharacterizationofthe Copelandrulecanbefoundin(Henriet,1985).

TheindirectandthedirectapproachestowardsGDMwithFPR differ in the waythe phases of aggregation andexploitation are combined:Intheindirectapproaches, onefirstapplies theaggre- gationphase tothe setof individual FPRsinorderto obtain one collective FPR. Then the exploitation phase isapplied to the col- lectiveFPR to give thefinal (weighted) ranking.In thedirect ap- proaches,theexploitationphaseisappliedfirstateachindividual FPRtogivetheindividualrankings.Thentheaggregationphaseis appliedattheindividualrankingstofindthefinalcollectiverank- ing (Herrera et al., 1996). Fig. 1 highlights these differences be- tweenthetwoapproaches.

Note that aggregating opinions of experts into a group opin- ionby anyofthe above approachesdoesnot necessarilyamount toreachingaconsensus.Toguaranteeagreementbetweentheex- perts,one could consider a third phaseafter thetwo phases de- scribedabove, inwhichone forcesthe individual opinionsofthe expertstogetclosetoeachother (Palomares,Estrella,Martínez,&

Herrera,2014). Thisnarrowingphase can be implementedin two different ways: (i) through automatic approaches without expert feedback,or(ii)throughapproacheswithfeedbackonpreferences

2Note that the Netflow method has also been defined in ( García-Lapresta, Martínez-Panero, & Meneses, 2009 ) as the broad Borda count.

Fig. 1. Tensor representation of methods for GDM. Indirect method (above); direct method (below).

wherethereisamoderatorthatwilltrytoreduce thedivergence ofopinionsbetweentheexperts.Inbothoftheseapproachescon- sensus isconsidered to bea stage whereall the individual opin- ions are sufficiently closeto each other.Quantitatively, the close- ness canbe measuredasadistanceinthe“spaceofopinions” ei- therbetweeneachopinionandthecollective(aggregated)opinion, orbetweenpairsofindividualopinions.

Havingdescribedbrieflythedecisionframeworkandthemain approaches for quantitative analysis in GDM, in the next section we propose a new method to address the aggregation and ex- ploitationprocessesandweanalyseitsproperties.

3. Arankcentrality-basedpreferenceaggregationmethod

In this section we introduce a method for aggregating the fuzzypreferencerelationsoftheexpertse₁,. . .,emintoacollective weightedrankingofthealternativesx₁,...,xn.Westartbyprovid- ing a way of transforming a preference matrix over the alterna- tivesintoaweightedrankingvectorofthealternatives,whichwill beusedintheexploitationphaseofthegeneralmethod.Thenwe provide the full GDM procedure. At the end we prove that, un- der the assumption that detailed balancerelation is satisfied,the proposed method satisfies some desirable properties of aggrega- tionprocesses.

3.1. Frompreferencematricestorankingvectors

Weconsiderann×npreferencematrixPoverthealternatives x₁,...,xn (n≥2) whichis additivereciprocal, i.e.amatrix whose elementsp_{i j} areintheunitintervalandobeythecondition

p_{i j}=1−p_ji. (5)

Avaluep_{i j}>0.5meansthatthealternativex_iispreferredoverx_j, while p_{i j}=0.5meansthatnopreferencebetweenx_iandx_jexists.

Inspiredbyrecentworkonrankingbasedonadatasetofpair- wise comparisons (Negahban et al., 2012;2016), our approach is basedonatransformationofthegivenpreferencematrixPintoa stochasticmatrixSdefinedinthefollowingway:

si j= 1

n−1pji, (6a)

sii=1− 1 n−1

n

j=1,j=i

pji. (6b)

Thedivisionbyn−1isintroducedfornormalizationpurposes,

js_{i j}=1,andto guaranteethat each elements_{i j} is proportional tothecorresponding p_ji andfulfillsthecondition0≤s_{i j}≤1.Each rowcanthen beseenasaprobability distributionandthematrix SasthematrixoftransitionprobabilitiesofaMarkovchainwithn states.³Theelements_{i j} correspondstotheprobabilityoftransiting froma statex_itoastate x_j and,asdefinedinEq.(6a),thisprob- abilityequalstheproductoftheprobabilityofchoosingrandomly thestatex_jamongthen−1statesdifferentfromx_jandadopting thatstatewithprobability p_ji.Thisensuresthattheprobabilityof transitionfromalternativex_itoalternativex_jisproportionaltothe preferenceof x_j over x_i. Notice that itis always possible tocon- struct such a stochastic matrix, even ifthere are missing entries inthe preferencematrixP,i.e.ifthereis incompleteinformation (Herrera-Viedmaetal.,2007).

WeimposethatthepreferencematrixP fulfillsthecondition

pi j=0, (7)

foreveryi,j∈

{

¹,...,n

}

^{,andthereforealsop}i j=1,foreveryi,j∈

{

¹,. . .,n

}

^{, which means that an} alternative is never completely

“excluded” against another one and also never “fully dominates”

another one. (This may be achieved by replacing a zero prefer- encewithan arbitrarily small

>0 preference).It iseasy to see thatunderthisparticularconditionthematrixSisirreducibleand aperiodic (see Appendix A). Then, according to Perron-Frobenius theorem (Horn & Johnson, 1990; MacCluer, 2000), S beingan ir- reducibleaperiodicstochastic matrix,thereisa uniquestationary solution

π

satisfying:

π

⁼

π

^{S. (8)}

The stationary distribution

π

^{can be computed} iteratively via arandomwalkontheMarkovchaindefinedbythestochasticma- trixS,oranalyticallyviathecomputationoftheeigenvectorassoci-

3In the remainder of the paper we will use the terms alternative and state inter- changeably.

atedwiththehighesteigenvalueofthematrixS.Wewillinterpret the stationary distribution

π

^{as a weightedranking, where each}

componentofthevector

π

^{(each“weight”)representstheimpor-}

tance ofthe corresponding alternative withrespect to thewhole setofalternatives,andwewillrefertothismethodforcomputing rankingsasaRankCentrality(RC)method(Negahban,Oh,&Shah, 2016).WecallthecorrespondingmatrixSacentralitymatrix.

To justifythe above interpretation of the stationaryvector

π

^,

weanalyseitsrelationwiththeinitiallygivenpreferencematrixP. AccordingtoEq.(8),thecomponentsofthevector

π

^read:

π

ⁱ⁼ⁿ

j=1

π

^{jsji. (9)}

The product

π

js_ji in theabove sum representsthe probability of transitioningfromx_jtox_iadjustedby theweightofx_j and,simi- larlyasin(Dopazo&Martínez-Céspedes,2017),canbeinterpreted asthe relative importanceofalternative x_iwithrespect tothe al- ternative x_j.Then,since

π

i,accordingtoEq.(9),isa sumofsuch products, it can be interpreted asthe (absolute) importance ofx_i. Now,accordingtoEq.(6a),thetransitionprobabilitiess_ji arepro- portional topreferences p_{i j}, hencewe caninterpret

π

js_ji asrela- tivepreferencestrengthofx_iwithrespecttox_j,and

π

ias(absolute) preferencestrengthofx_i.

TherearetwoimportantpropertiesoftheRCmethod.Thefirst property is that the ranking dynamicsfollows a continuoustime Markovchain inglobalbalance,andtherespective balanceequa- tion canbe easily derived fromEq.(6)andEq.(8).Namely, from Eq.(9)weobtain:

π

i=

π

is_ii+ n

j=1,j=i

π

js_ji, (10)

whichisequivalentto

(

^1−sii

) π

i= n

j=1,j=i

π

js_ji. (11)

FromEq.(6)wehave 1−s_ii=

n

j=1,j=i

s_{i j}, (12)

which together withEq.(11) andEq.(6a) leads to thefollowing equations

n

j=1,j=i

si j

π

i= n

j=1,j=i

sji

π

j

n

j=1,j=i

p_ji

π

i= n

j=1,j=i

p_{i j}

π

j, (13)

whichwecalltheglobalbalanceequations.Noticethatthestronger condition which assumes a term-by-term equality between the sumsinEq.(13),foreveryi∈

{

¹,...,n

}

^{,iscalledadetailedbalance.}

Wediscussthecaseofadetailedbalanceinasubsequentsection.

Thesecondpropertyisgivenbytherelationbetweenthecom- ponents ofthestationarysolution(ranking)andtheinitialprefer- encedegreesthatfollowsdirectlyfromthesecond globalbalance equation:

π

i= 1 n

j=1,j=ipji

n

j=1,j=i

p_{i j}

π

j. (14)

Note thatifwe didnot havethe terms

π

j onthe righthand- side oftheEq.(14),thenthemethodwouldhavebeenequivalent totheNetflowmethodsince

π

iwouldbeproportionalton

j=ip_{i j}

whichisthecaseforNF(^xi)^{tooasseen inEq.(4).However, hav-} ing

π

j ontheright-hand sideofEq.(14)reflectsthe ideaofcen- tralityranking.Namely,the importanceofeach alternativex_j=x_i quantifiedby

π

jistakenintoaccountwhendetermining

π

i.Thus, weak alternatives that have low

π

j due to being dominated by manyother alternatives will not contribute muchto theincrease of

π

ievenif p_{i j} islarge,becauseoneneeds toconsidertheprod- uct p_{i j}

π

j andnot only p_{i j} asintheclassicalNetflowmethod.In- formally,thismeansthatbeatingweakalternatives,i.e.alternatives withlow

π

j,doesnotincreasemuchtheranking.Thisisoneofthe coreideasoftheRankCentralitymethod(Negahbanetal.,2016).

3.2. TheGDMmethod

Ourframework forpreference aggregationconsists of the fol- lowingsubsequentsteps:

1. Consider a set of m experts E=

{

^e1,. . .,em

}

^{. Each expert e}k, 1≤k≤m, has a pairwise preferencematrix P^(k) over the set ofalternativesX=

{

^x1,...,xn

}

^.

2. UsingEq.(6),foreachmatrixP^(k)wecomputethecorrespond- ingstochasticmatrixS^(k).

3. WesolveEq.(8)foreachexperte_k,i.e.wesolve

π

=

π

^S(k),for

k=1,...,m,anddenotetheuniquesolutionby

π

^{(k).Thevector}

π

^(k)=[

π

1^(k),. . .,

π

n^(k)] definesaweightedrankingofthealter- nativescorresponding tothepreferencesofthe experte_k over theset of nalternatives. As observed in theprevious section,

π

i^(k)canbeinterpretedasthepreferencestrengthofthealter- nativex_iaccordingtoexperte_k.Then,since

π

^(k)isaprobability distributionover X,it can be seen asrepresenting theexpert e_k’sdistributionofpreferencestrengthsoverX.

4. Wedefinethecollectiverankingvectorasthearithmeticaver- ageof the individual ranking vectors, determining its compo- nentsasfollows:

π

i^(c)= 1 m

m

k=1

π

i^(k). (15)

Notice that,by takingthearithmetic average oftheindividual rankingvectorsastheaggregatedstate

π

^{(c),onenaturallydefines}

theconsensualstagewithrespecttothataggregatedstate:perfect consensusoccurswhenalltheexpertsarriveatthesameopinion givenby

π

^{(c).Moreover,suchdefinitionofperfectconsensusstate}

reflects the assumption that the perfect consensus state should notbeneartosome specificexpertandinprejudicetotheother.

From a more physicalperspective, one can take

π

^{(c) asthe cen-}

ter ofmassoftheset ofopinionsofthem experts(expressedas weightedrankings),inthespaceofallthepossibleopinions,i.e.it istheunique pointfromwhichallthe experts’opinionsare seen equallydistributed,m

k=1(

π

i^(k)−

π

i^(c))=0,foreveryi=1,...,n.In otherwords,usingthearithmeticaverageintheaggregationphase oftheGDMprocessprovidesa safealternative toreachingacon- sensus,intheabsenceofaspecialthirdphaseforthat purposein theprocess.

An extension to WAor OWA is straightforward and does not compromisethebulkofourframework:Foranychoiceofweights, whichshoulddependonthespecificsetofexpertsand/orthespe- cificdecisionmakingcontext,rankingsandpreferenceswillstillbe treatablewithinourframework.

3.3. Thedetailedbalancecase

Recall that thestationary vector satisfies the detailed balance (timereversibility)propertyifthefollowingequationholds:

π

is_{i j}=

π

js_ji, (16) foreveryi,j∈

{

¹,...,n

}

^.

Inthissectionwe assumethat Eq.(16)holdsfortheelements ofthestochasticmatrixSandthecomponentsofthecorrespond- ing stationaryvector obtainedin steps 2. and3. in the previous section. Then, combiningEq.(5), Eq.(6) andEq.(16),one arrives tothefollowingequationequivalenttoEq.(16):

p_{i j}=

π

i

π

i+

π

j . (17)

Eq.(17)highlightsthecorrespondencebetweenpairwiseexpressed preferences in the form of a preference matrix and the prefer- ence strengths assigned to the alternatives in the corresponding weighted ranking vector. Note that Eq. (17) implies transitivity of the preference matrix P (from p_{i j}>0.5 and p_jk>0.5 follows p_ik>0.5).

Notice thatEq.(17)meansthatthepreferencerelationP satis- fiestheBradley-Terry-Luce(BTL)model(vanBerkum,1997).Itwas demonstratedalsobyRajkumarandShivani(Rajkumar&Agarwal, 2014)thatthetime-reversibilityofSisequivalenttotheexistence ofanunderlyingBTLmodelthatdescribesthepreferencesinP ac- cordingtotheirpreferencestrengths

π

^.

At this juncture, we shall present a theorem that provides a mathematical interpretation of the stationary distribution of the centralitymatrix Scorresponding to thepreferencematrix P, namely thatthe stationarydistributionof Sisa maximumlikeli- hoodestimateoftheBTLmodelunderlyingP.

Theorem 1. Let the BTL pairwise comparison model be defined by a parameter vector

π

=[

π

1,...,

π

^n],

π

i∈(⁰,1)^{,i.e. p}i j=_πi^π₊ⁱ_πj,for i,j∈

{

¹,...,n

}

^{,where p}i j=P(^xi>x_j)^{.4 LetP}=[p_{i j}]beapreference matrixandletS beitscorrespondingcentralitymatrixdefinedbyEq.

(6a) and Eq.(6b). ThentheMaximum Likelihood Estimate (MLE)of theBTLmodelsatisfiestheglobalbalanceequationwithP.

The proof of the above theoremcan be found in AppendixB. ThetheoremstatesthattheMLEoftheparametervector

π

^ofthe

BTLmodelforpairwisecomparisonsofnalternatives,

π

^{∗,satisfies}

theglobalbalancepropertygiveninEq.(13)withthegroundtruth probabilities P ofthe model.This means that

π

^{∗ is a stationary}

distributionofthecentralitymatrixScorrespondingtoP,sincethe globalbalanceequationsinEq.(13)arederivedfromthestationary distributioninEq.(9)throughaseriesofequivalencesteps.Finally, sincethestationarydistributionofSisuniqueontheunitinterval, we canconcludethatitisequalto

π

^{∗,theMLEoftheBTLmodel}

inwhichPdescribestheprobabilitiesofthepairwisecomparisons.

In Section 3.1 we discussed two generalproperties of the RC method.Here,weobservethatinthespecialcasewhentherank- ingvectorsdeterminedinstep3.oftheGDMproceduresatisfyde- tailedbalance,i.e.theequations(16)and(17),twodesirableprop- erties of the aggregation processes are satisfied: internal consis- tencyandtheParetoprinciple.Weinterpretthesepropertiessimi- larlyasin(Dong&Zhang,2014)and(Chiclana,Herrera,&Herrera- Viedma,2002).

Internal Consistency. In our setting, internal consistency can be understood asthe consistency ofthe process that transforms each expert’sopinionfromitsinitial formofapreferencematrix, throughastochasticmatrix,toitsendformofaweightedranking vector. Inotherwords,thepropertyofinternal consistencyissat- isfiedifthefollowingholds:Thederivedindividualrankingofthe k-thexpertbytheproceduredescribedinSection3.1,reflectsher initialpreferencerelation,rankinghigher(assigninghigherweights to) the alternatives she prefers more: p⁽_{i j}^k)≥p⁽_ji^k) if and only if

4x i> x jcan be interpreted as “x iwins over x j”, “x iis preferred to x j”, etc., and P(x i> x j)is the probability of this event that is to be estimated from a number of pairwise comparisons in the set of alternatives X = {^x 1, . . . , x n}^.

π

_i^(k)≥

π

_j^{(k),foreveryi},j∈

{

¹,...,n

}

^{.Thispropertyfollowsimme-}

diatelyfromEq.(17).

Paretoprinciple.ThegeneralinterpretationoftheParetoprinci- ple(unanimity)inthesocial-choice theoryisasfollows:Ifallthe expertsagreeuponacertainissue,thenthisagreementisreflected inthederivedcollectiveopinion.Inourframework,itcanbeinter- pretedasthe following requirement:Ifall the expertsprefer the alternativex_ioverthealternative x_jintheir individualpreference relations, then x_i ranks higher than x_j in the collective ranking.

Moreformally,if p⁽_{i j}^k)≥p⁽_ji^k),forevery k=1,...,m,then

π

i^c≥

π

^cj. This is a consequence of Eq.(17) andEq. (15): If p⁽_{i j}^k)≥p⁽_ji^k),for every k=1,...,m,then,fromEq.(17)itfollowsthat

π

i^(k)≥

π

j^(k), forevery k=1,...,m.From the last and Eq.(15),it follows that

π

_i^(c)≥

π

⁽_j^c).

Note that the above two properties are based on qualitative comparisons between preferences where neither the magnitude of preferences and preference strengths nor the information on whetherthe dominated alternatives are weak or strong,is taken intoaccount.SincethesearecrucialelementsintheRankCentral- itymethodthat enablederiving meaningfulrankings,they justify the violationofthe properties ofinternal consistency andPareto optimalityinthegeneralcase.Thisisclearlydemonstratedbyour exampleinSection5.1.Itwouldbeinteresting,however,toexam- inethesensitivityofthelatterpropertiestochangesintheinitial matrices.

4. SensitivityAnalysis(SA)

Inthis section weperform a theoretical sensitivityanalysisof theRankCentralitymethod.Morespecifically,weanalysethesen- sitivityoftheoutputofthe proceduredescribedinSection3.1in faceofsmallvariationsoftheinput,i.e.smallvariationsintheval- uesofthematrixparameters.Theaimofthisanalysisistounder- stand how the centrality-basedranking of the alternatives is af- fectedbysmallchangesintheexperts’opinions.Asabasisforour analysisweusethederivativesoftheoutput,andwelargelyapply resultsfromGolubandMeyer(Golub&Meyer,1986).

RecallthattheinputoftheRCrankingmethodisann×npref- erence matrix P (n≥2) that is additive reciprocal, i.e. a matrix whose elements p_{i j} are in theunit interval andobey the condi- tion

p_{i j}=1−p_ji. (18)

We consider an

-perturbation ofthe matrix P resulting in a newmatrixP˜(

)^,wherethepreferencesassociatedwithonepar- ticularpairofalternatives(^xk,x_l)^{changeasfollows:5}

˜

p_kl=p_kl+

⁽¹⁹⁾

with0<

^1,andconsequently,fromEq.(5),

˜

p_lk=1−p˜_kl=p_lk−

^{. (20)}

LetSandS˜(

)^{bethecentralitymatricesofPandP˜}(

)^respec- tively.NotethatP˜(⁰)=P andS˜(⁰)=S.Wheneverthereisnocon- fusion,we willomitthe dependencyon

^{fromthenotation. Ac-}

cordingtoEq.(6),thecorrespondingentriesofS˜(

)^arethengiven by:

˜ skl = 1

n−1p˜lk=skl−

n−1,

˜

s_lk =s_lk+

n−1.

5For simplicity, but also for clarity of the observations we make, we restrict to the case of varying the preferences related to only one pair of alternatives.

As forthediagonal terms,theonlytermsaffected by theper- turbationinthepreferencematrixares˜_kkands˜_ll:

˜

s_kk=s_kk+

n−1,

˜

s_ll =s_ll−

n−1.

All thesevariationscan be written ina compact formforthe centralitymatrixas

S˜

( )

=S+S where

S=

k l

⎛

⎜ ⎜

⎜ ⎜

⎜ ⎜

⎜ ⎜

⎜ ⎝

⎞

⎟ ⎟

⎟ ⎟

⎟ ⎟

⎟ ⎟

⎟ ⎠

0 ... 0 ... 0 ... 0 ..

. ... ... ... ... ... ... 0 ... _n−1 ... −_n−1 ... 0 k

..

. ... ... ... ... ... ... 0 ... _n−1 ... −_n−1 ... 0 l

..

. ... ... ... ... ... ... 0 ... 0 ... 0 ... 0

(23)

Theorem2. Let

π

˜(

)^{bethestationary}distributionofS˜(

)^.Then

∂ π

^˜i

( )

∂

⁼

π

^˜k+

π

˜l

n−1

(

^tli−tki

) π

i, (24) where t_ji denotes themean first passagetimefrom x_i to x_j, i.e.the expected numberofstepsto reachstatex_jforthefirsttimestarting fromstatex_i,intheunperturbedcentralitymatrixS˜(⁰)=S.

The proof ofTheorem 2isgiven inAppendixC.Notethat Eq.

(24) implies ^∂π˜_∂^k()=^π˜_n^k+₋₁^π˜lt_lk

π

k>0 and ^∂π˜_∂^l()=−^π˜_n^k+₋₁^π˜lt_kl

π

l<0 whichisexpected.

The perturbation of the preference associated with the pair (^xk,x_l) ^{affects every component}

π

^˜i in the stationarydistribution

π

˜(

)^{of the centrality matrixS˜}(

)^{. Forsufficiently small}

^these

componentscanbewrittenas⁶

π

˜i

π

i+

∂ π

^˜i

∂

=0

=

π

i

1+

π

^˜k+

π

˜l

n−1

(

^tli−t_ki

)

. (25)

Equation (25)canbe interpreted asfollows: Forsimilarfirst pas- sagetimesbetweenalternatives,theperturbationofpreferencesin asinglealternative-pairhasaneffectinthestationarydistribution thatisproportionaltotheamplitudeofitscomponents:dominant alternatives(higherrank)aremoreaffectedthanotheralternatives.

OneimportantconsequenceofEq.(25)isthatonecanestimate firstpassagetimesforallpossibletransitionsbetweenalternatives.

Indeed, fork=i and l=i, sincet_kk=t_ll=0 by definitionof first passagetime,Eq.(25)yieldsrespectively

t_lk=

π

˜k

π

k−1

n−1

π

^˜k¹+

π

˜l, (26a)

t_kl=

1−

π

˜l

π

l

n−1

1

π

˜k+

π

˜l

. (26b)

Equation (25)can be used toestimate theglobaldeviation of

π

˜(

)^fromthe”unperturbed” stationarydistribution

π

˜(⁰)^:

|| π

^˜

( )

−

π

˜

(

⁰

) ||

²

²

⁽ π

^˜k+

π

˜l

)

²

n−1

(

^tli−tki

)

²

π

i²

i, (27)

6It is worth mentioning that those two equations can be obtained too by apply- ing Proposition 2.1 due to Cho and Meyer ( Cho & Meyer, 20 0 0 )

where

(

^tli−t_ki

)

²

π

i²

i≡ 1 n−1

n

i=1

(

^tli−t_ki

)

²

π

i². (28)

Thisequationcanbeinterpretedasfollows.Theglobaldeviationof

π

˜(

)^fromtheunperturbedstationarydistribution

π

˜(⁰)^increases witha”weighted” second momentofthe componentsoftheun- perturbed stationarydistribution.The weights forthecomponent

π

iaregivenbythedifferencebetweenthefirstpassagetimesfrom thecorrespondingalternative x_itothe”perturbedaltrenatives”x_k andx_l.

This observationhas two main consequences. First, the result in Eq. (27) uncovers another intuitive consequence: the compo- nents of the stationary distribution which remain unchangedby perturbing the preference for a pair of alternatives (^xk,x_l) ^are those for which the mean first passage times from the corre- sponding alternative x_i to each alternative in the perturbed pair is equal, i.e. t_ki=t_li. In particular, perturbing the preference for pairs of alternatives (^xk,x_l)^{, which are evenly chosen in front of} all other alternatives x_i, i.e. t_ki=t_li for all i=k and i=l, will have no impact on the global preference strengths of the al- ternatives. Their impact is reduced to local changes of the am- plitudes of each alternative in the perturbed pair, namely

π

˜k

and

π

˜l.

Second, since deviations between perturbed and unperturbed stationarydistributionareeasytomeasureinpractice,Eq.(25)and (27) provide new insight for establishing a framework to assess, atleastataqualitative level,theimpactoflocalperturbations in theglobaldynamicstowardsconsensus.Namely,theresultsofthis sectionhavesomeimplicationswhenitcomestoreachingconsen- susworth pursuing asfuturework. Infact, wecan formalize the consensus problemasa gradient descent optimizationwhereex- perts need to do small adjustment to their preference matrices.

The sensitivity of Markov chains to their transition probabilities canbe usedforcomputingthegradient inorderto makethein- dividualstationarydistribution ofeach expertmove towards col- lectivestationarydistribution,byonlyadjustingthecorresponding preferencematrices.

5. TestingGDMwithFPR:numericalexperiments

Inthissection we providea concreteexampleofa GDMwith FPR usingourmethod.We firstcompare theresults ofusingour methodagainst theresults ofusingthe popularNetflowmethod.

Then, we perform an experimental sensitivity analyses to ex- plore what happens to the resulting ranking vector if we vary the entries ofthe initial preference matrices1.by severalvalues of

>0 applied to the same pair of alternatives; and 2. by a small fixed

>0 applied to differentpairs of alternatives in the matrix.

We start by a numerical examplehighlighting the similarities anddifferencesbetweenouralgorithmandanalgorithmthatuses thestandardNetflow(NF)method.

5.1. Anumericalexample

Weconsiderafirstscenariowithtwoexperts(m=2)andfour alternatives(n=4)⁷Theexperts’opinionsareexpressedinthefol-

7The code for performing the computations involved in the examples of this sec- tion is available at https://github.com/FMZennaro/GDM . The code can be straightfor- wardly changed for another number of experts. We have also tested for m = 3 and m = 4 , observing the same qualitative results.