31 augustus 2011

De Shapley-waarde voor waardefuncties op tweeledige verzamelingen

De Shapley-waarde is een bekend verdelingsconcept in de coöperatieve speltheorie. Deze waarde geeft aan iedere speler een deel van de totale waarde die wordt gegenereerd als alle spelers samenwerken. De Shapley-waarde is eerlijk in de zin dat die aan een aantal gewenste eigenschappen voldoet.

We beschouwen een coöperatief spel met een tweeledige verzameling die bepaalt welke spelers aan het spel deelnemen. Deze paper presenteert een analytische oplossing voor de Shapley-waarde wanneer de totale waarde van een spelerscoalitie uitsluitend afhangt van het aantal deelnemende coalitiespelers. De rekencomplexiteit is slechts lineair in het aantal spelers, terwijl de gebruikelijke rekencomplexiteit van de Shapley-waarde exponentieel is. Dit efficiënte resultaat geldt ook bij een willekeurige trekking van (i) tweeledige verzamelingen, en (ii) geschikte waardefuncties.

We illustreren ons resultaat met een voorbeeld dat is gerelateerd aan het probleem van de toekenning van systeemrisico bij banken.