Compensations in the Shapley value and the compensation solutions for graph games

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

Compensations in the Shapley value and the compensation solutions for graph games? Sylvain Béal†, Eric Rémila‡, Philippe Solal February 24, 2010 Abstract We consider an alternative expression of the Shapley value that reveals a system of compensations: each player receives an equal share of the worth of each coalition he belongs to, and has to compensate an equal share of the worth of any coalition he does not belong to. We give an interpretation in terms of formation of the grand coalition according to an ordering of the players and define the corresponding compensation vector. Then, we generalize this idea to cooperative games with a communication graph. Firstly, we consider cooperative games with a forest (cycle-free graph). We extend the compensation vector by considering all rooted spanning trees of the forest (see Demange [3]) instead of orderings of the players. The associated allocation rule, called the compensation solution, is characterized by component efficiency and relative fairness. The latter axiom takes into account the relative position of a player with respect to his component. Secondly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees by using the classical algorithms DFS and BFS. If the graph is complete, we show that the compensation solutions associated with DFS and BFS coincide with the Shapley value and the equal surplus division respectively. Keywords: Shapley value, compensations, relative fairness, compensation solution, DFS, BFS, equal surplus division.

communication graph

over all

all rooted

games can

rooted spanning

such algorithms

graph games

coalition

component should

compensation solution

Voir

Publié par

pefav

Nombre de lectures

Langue

English

CompensationsintheShapleyvalueandthecompensationsolutionsforgraphgames∗SylvainBéal†,EricRémila‡,PhilippeSolal§February24,2010AbstractWeconsideranalternativeexpressionoftheShapleyvaluethatrevealsasystemofcompensations:eachplayerreceivesanequalshareoftheworthofeachcoalitionhebelongsto,andhastocompensateanequalshareoftheworthofanycoalitionhedoesnotbelongto.Wegiveaninterpretationintermsofformationofthegrandcoalitionaccordingtoanorderingoftheplayersanddeﬁnethecorrespondingcompensationvector.Then,wegeneralizethisideatocooperativegameswithacommunicationgraph.Firstly,weconsidercooperativegameswithaforest(cycle-freegraph).Weextendthecompensationvectorbyconsideringallrootedspanningtreesoftheforest(seeDemange[3])insteadoforderingsoftheplayers.Theassociatedallocationrule,calledthecompensationsolution,ischaracterizedbycomponenteﬃciencyandrelativefairness.Thelatteraxiomtakesintoaccounttherelativepositionofaplayerwithrespecttohiscomponent.Secondly,weconsidercooperativegameswitharbitrarygraphsandconstructrootedspanningtreesbyusingtheclassicalalgorithmsDFSandBFS.Ifthegraphiscomplete,weshowthatthecompensationsolutionsassociatedwithDFSandBFScoincidewiththeShapleyvalueandtheequalsurplusdivisionrespectively.Keywords:Shapleyvalue,compensations,relativefairness,compensationsolution,DFS,BFS,equalsurplusdivision.JELClassiﬁcationnumber:C71.1IntroductionTheShapleyvalue(Shapley[17])isthemoststudiedallocationruleforcooperativegameswithtransferableutility(TU-gameshenceforth).OnewaytointerprettheShapleyvalueconsistsinconsideringequallylikelyorderingsofplayers.Foreachsuchordering,theplayersenterabargainingroomonebyone,anduponenteringeachplayerispaidhismarginalcontribution.Thisprocedureyieldstheso-calledmarginalvector,andtheShapleyvalueistheaverageoverallorderingsoftheplayersofthemarginalvectors.∗TheauthorsaregratefultoTheoDriessen,AmandineGhintran,AnnaKhmelnitskayaandAymericLardonforstimulatingdiscussions.WehavealsobeneﬁtedfromcommentsofseminarparticipantsatCaenUniversityandattheﬁrstMINTworkshop.FinancialsupportbytheComplexSystemsInstituteofLyon(IXXI)andtheNationalAgencyforResearch(ANR)–researchprogram“ModelsofInﬂuenceandNetworkTheory”ANR.09.BLANC-0321.03–isgratefullyacknowledged.†Correspondingauthor.UniversitédeSaint-Etienne,CNRSUMR5824GATELyonSaint-Etienne,France.E-mail:sylvain.beal@univ-st-etienne.fr.Tel:(+33)(0)4.77.42.19.68.Fax:(+33)(0)4.77.42.19.50.‡UniversitédeLyon,LIP,UMR5668CNRS-ENSLyon-UniversitéLyon1,France.E-mail:eric.remila@ens-lyon.fr.Tél:(+33)(0)4.26.23.38.14.Fax:(+33)(0)4.72.72.80.80§UniversitédeSaint-Etienne,CNRSUMR5824GATELyonSaint-Etienne,France.E-mail:philippe.solal@univ-st-etienne.fr.Tel:(+33)(0)4.77.42.19.61.Fax:(+33)(0)4.77.42.19.50.1

Voir