A note on values for Markovian coalition processes

Authors: Ulrich Faigle Michel Grabisch

Publish Date: 2013/03/27

Volume: 1, Issue: 2, Pages: 111-122

PDF Link

Abstract

The Shapley value is defined as the average marginal contribution of a player taken over all possible ways to form the grand coalition N when one starts from the empty coalition and adds players one by one The authors have proposed in a previous paper an allocation scheme for a general model of coalition formation where the evolution of the coalition of active players is ruled by a Markov chain and need not finish at the grand coalition The aim of this note is to develop some explanations in the general context of time discrete stochastic processes exhibit new properties of the model correct some inaccuracies in the original paper and give a new version of the axiomatizationThe Shapley value is a wellknown allocation scheme for both TU and NTUgames with numerous applications It is defined as the average marginal contribution of a player taken over all possible ways to form the grand coalition N when one starts from the empty coalition and adds players one by oneIn real situations however there is no a priori reason for a process of cooperation to end with the grand coalition nor are all ways of forming the grand coalition necessarily feasible This explains why the Shapley value can produce counterintuitive results in some cases as pointed out by eg Roth 1980 Shafer 1980 Scafuri and Yannelis 1984Guided by these considerations the authors have proposed an allocation scheme for a general model of coalition formation Faigle and Grabisch 2012 where the evolution of the coalition of active players is ruled by a Markov chain The classical Shapley value appears then as the particular case where the only transitions possible consist of the addition of a single player to the present coalition and all these transitions are equiprobableThe aim of this note is to develop some explanations in the even more general context of time discrete stochastic processes that are not necessarily Markovian exhibit new properties of the model and correct some inaccuracies in the original paper Faigle and Grabisch 2012 In particular we give a new version of the axiomatization We restrict our exposition to the minimum and refer the reader to the original paper for examples and further details on the Markovian modelWe consider a finite set of players N with N=n By a scenario fancyscriptS= S 0S 1S 2ldots we mean a sequence of coalitions S tsubseteq N starting with the empty set S 0 =emptyset No particular property is assumed on the sequence there could be repetitions for example In this note however we will restrict ourselves to scenarios of finite length We call any twoelement subsequence S tS t+1 in fancyscriptS a transition in fancyscriptS and denote it by S trightarrow S t+1A scenario fancyscriptS arises from the observation of the status of cooperation along discrete time t=012ldots We assume that a process of cooperation among players in N starts formally from the empty coalition S 0=emptyset no player is active then coalition S 1 is observed then S 2 etc Coalition S t is the set of active players those engaged in cooperation or ready to cooperate at time t A finite scenario fancyscriptS= S 0S 1ldots S tau is said to be of length tau with S tau being the final state of cooperation Note that we do not necessarily assume S tau =N

Keywords: