AN AVERAGE PER CAPITA FORITI.]LA FOR THE SHAPLEY VALTIE

A new formula. the storage of the computer, a,nd a,voids for 2n the the Shapley va,lue is given which does not require-1 values of the characteristic function in the search in the memorv for such data. (s-i)!(n-s)!----;r-1. In computing the ShapJ.ey value of a cooperative TU game, the 2n-I values of the characteristic function should be introduced in the cornputing tool anytl'ay. Therefore, if these data should be kept and retrieved, the conputation may become inpossible for large n. Ve give a formula for the Shapley value which is allowing the computation of the value by manipulating two n*1-dimensional vectors; each value of the characteristic function is given as an n*l-dimensional vector which is irnmediately used and deleted. In this w&yr the difficutty of computing the Shapley value reduces to the correct typing of data. Ve give a simple combinatorial proof in the next section, then a more elegant one using the Hart/Mas-Colell potentials and an example. The list of references contains pa,pers devoted to the applications ([1] and t5]) and papers in which the interpretations of the Shapley value as a, sound fair allocation are emphasized (t4] and [Z]); the computational aspect is discussed main]y in two paper " ([2] and [6]). 2. The Shapley value introduced in [8], for a cooperative TU gane with the set of pla.yers N and the characteristic function u, is given by the well-known formula (1) where s = l.9f O;(o) =!SlieS [r(s)-t(s- {t})], vi € N, Some notations are needed: for /c 1.....