A Dynamic Algorithm for Computing Multiweighted Shapley Values of Cooperative TU Games

In an earlier paper of the author, (Dragan, 1994), the Multiweighted Shapley Values have been introduced as linear operators on the space of TU games, which satisfy the efficiency and the dummy player axioms. This is the class of values, which for different systems of weights includes among others, the Shapley Value, the Weighted Shapley Value, the Random Order Values, the Harsanyi payoff vectors, the Owen coalition structure values, etc. An early dynamic algorithm for computing the Shapley Value is due to late M. Maschler (1982). This algorithm is building a sequence of allocations, corresponding to a sequence of games, ending with the Shapley Value, corresponding to the null game. In the present work, we show a similar algorithm for computing the Multiweighted Shapley Values. The algorithm is illustrated by applying it to a MWSV which is neither a Harsanyi payoff vector, nor a Random Order Value. As the algorithm is using results from our earlier paper, to make the paper self contained, the basic definitions and notations are given in the first section, while the characterizations of the MWSVs are further given in the second section and the algorithm is presented in the last section. Notice that in fact our algorithm contains a class of algorithms, in which by taking various systems of weights, the algorithm will compute different values. In this class, the well known weights of the Shapley Value will generate the Maschler algorithm for computing the value.