2004 INFORMS

MATHEMATICSOFOPERATIONSRESEARCHVol.29,No.4,November2004,pp.739–775issn0364-765X
eissn1526-5471
04
2904
0739informs®doi10.1287/moor.1040.0118©2004INFORMSAsymptoticValuesofVectorMeasureGamesAbrahamNeymanInstituteofMathematicsandCenterfortheStudyofRationality,HebrewUniversity,91904Jerusalem,Israel,[e-mail],@ie.technion.ac.ilInhonorofL.S.Shapley’seightiethbirthdayTheasymptoticvalue,introducedbyKannaiin1966,isanasymptoticapproachtothenotionoftheShapleyvalueforgameswithinfinitelymanyplayers.AvectormeasuregameisagamevwheretheworthvSofacoalitionSisafunctionfofSwhereisavectormeasure.Specialclassesofvectormeasuregamesaretheweightedmajoritygamesandthetwo-houseweightedmajoritygames,whereatwo-houseweightedmajoritygameisagameinwhichacoalitioniswinningifandonlyifitiswinningintwogivenweightedmajoritygames.Allweightedmajoritygameshaveanasymptoticvalue.However,notalltwo-houseweightedmajoritygameshaveanasymptoticvalue.Inthispaper,weprovethattheexistenceofinfinitelymanyatomswithsufficientvarietysufficefortheexistenceoftheasymptoticvalueinageneralclassofnonsmoothvectormeasuregamesthatincludesinparticulartwo-houseweightedmajoritygames.Keywords:asymptoticvalue;weightedmajoritygame;two-houseweightedmajoritygame;vectormeasuregame;ShapleyvalueMSC2000subjectclassification:Primary:91A12,91A13,60G20,60G51OR/MSsubjectclassification:Primary:Games/groupdecision,cooperativeHistory:ReceivedNovember7,2003;revisedMay20,2004.1.Introduction.Oneofthebasicsolutionconceptsincooperativegametheory,theShapleyvalueassignsauniqueoutcometoeachfinitetransferableutilitygame.Thevalueofagamecanbethoughtofasasortofaverageorexpectedoutcome,oranapriorimeasureofpower.ItwasintroducedbyShapleyin1953astheuniquefunction(fromgamestooutcomes)satisfyingsomeplausibleaxioms(efficiency,linearity,symmetry,andthenullplayeraxiom).1.1.Asymptoticvalue.TheShapleyvaluewasinitiallydefinedforgameswithfinitelymanyplayers.Itismostrelevanttoimportantgamemodelsineconomicsandpoliticalsciencewithmanyplayers,wheremostoftheplayersare“insignificant”ontheirown,yetimportantaspartofacoalition(e.g.,shareholdersofalargepubliccompany,oralargeelectorate).Insuchgamestheremaybe,inaddition,asetofindividuallysignificantplayers.ThissuggeststheneedtoanalyzetheShapleyvalueofgameswithalargenumberofindividuallyinsignificantplayersaswellasagroupofindividuallysignificantplayers.Therehavebeentwostrandsintheliteraturepursuingthisissue.Oneanalyzestheasymp-toticsofvaluesoffinitegames(e.g.,ShapiroandShapley1978;Shapley1962a,1964b)whiletheotherdefinesavalueforlimitgames(e.g.,MilnorandShapley1978,AumannandShapley1974).Theasymptoticvalue,introducedbyKannaiin1966,bridgesthesetwoapproaches.TheasymptoticvalueofalimitinggamevisdefinedwheneverallthesequencesoftheShapleyvalueoffinitegamesthat“approximate”vhavethesamelimit.Itturnsoutthattheexistenceoftheasymptoticvalueisnotguaranteedandmanyauthorshavestudiedclassesofgamesforwhichthisvalueexists(e.g.,Kannai1966,AumannandShapley1974,Hart1977,FogelmanandQuinzii1980,Dubey1980,Neyman1981).1.2.Vectormeasuregames.Ascalarmeasuregameisagameinwhichtheworth,vS,ofacoalitionSisafunctionfofitsscalarmeasure.Inavarietyofpapers(e.g.,theabove-739NeymanandSmorodinsky:AsymptoticValuesofVectorMeasureGames740MathematicsofOperationsResearch29(4),pp.739–775,©2004INFORMSmentionedstudies)theexistenceresultsfortheasymptoticvalueturnouttobeparticularcasesofthemoregeneralresultwhichstatesthatallgamesthatcanbeapproximated(intheboundedvariationnorm)bylinearcombinationsofscalarmeasuregameshaveanasymptoticvalue.(Theothertoolsusedintheexistenceresultsareself-dualityanddiagonality.)Infact,theseresultsfollowfromthefactthatallmonotonicscalarmeasuregames(andthusalsoallscalarmeasuregamesofboundedvariation)haveanasymptoticvalue(Neyman1988).(“Continuity”ofthegameatandatthegrandcoalitionisassumed.)AvectormeasuregameisagamevinwhichtheworthvSofacoalitionSisafunctionfofavectorofmeasures,1SnS,namely,v=f1n.Therearemanygamesthatariseinapplicationsandhavearepresentationasvectormeasuregames.Someimportantexamplesofsuchgamesarecoalitionalmarketgamesofexchangeeconomieswithtransferableutilities,ormarketgamesforshort,withfinitelymanytypes(seeAumannandShapley(1974,ChapterVI)(i.e.,“marketswithmoney”or“marketswithsidepayments”;cf.ShapleyandShubik1966,1969;Shapley1964b).Marketgameswithsmoothutilitiescanbeapproximated(intheboundedvariationnorm)byvectormeasuregameswhere,inaddition,thefunctionfissmooth(seeAumannandShapley1974,ChapterVI).Anotherexampleofgamesthatareapproximatedbyvectormeasuregamesismodelsofeconomieswheresomeeconomicactivitiesneedpoliticalapproval,asintheAumannandKurz(1977a,b)modelsofpowerandtaxationandthepowerandpublicgoodsmodelsofAumannetal.(1983,1987).Inthesemodelsthefunctionfisdiscontinuous,andinfactisaproductoftwootherfunctions:a01-valuedfunctionhandasmoothfunctiong.TheworthgSdescribesthemaximaleconomicoutputthatthecoalitionScanproducewithoutanypoliticalco