Pyramidal values

Pyramidal values1 Ram´on Flores Department of Statistics, Universidad Carlos III de Madrid, Spain e-mail: [email protected] Elisenda Molina Department of Statistics, Universidad Carlos III de Madrid, Spain e-mail: [email protected] Juan Tejada Department of Statistics and Operations Research and IMI (Interdisciplinary Mathematical Institute), Universidad Complutense de Madrid, Spain e-mail: [email protected] Abstract We propose and analyze a new type of values for cooperative TU-games, which we call pyramidal values. Assuming that the grand coalition is sequentially formed, and all orderings are equally likely, we define a pyramidal value to be any expected payoff in which the entrant player receives a salary, and the rest of his marginal contribution to the just formed coalition is distributed among the incumbent players. We relate the pyramidal-type sharing scheme we propose with other sharing schemes, and we also obtain some known values by means of this kind of pyramidal procedures. In particular, we show that the Shapley value can be obtained by means of an interesting pyramidal procedure that distributes nonzero dividends among the incumbents. As a result, we obtain an alternative formulation of the Shapley value based on a measure of complementarity between two players. Finally, we introduce the family of proportional pyramidal values, in which an incumbent receives a dividend in proportion to his initial investment, measured by means of his marginal contribution. Keywords: Game theory, TU games, pyramidal values, procedural values, Shapley value, co-values, consensus values, egalitarian Shapley values. 1 Introduction In this paper we propose a general procedure for obtaining a broad class of solution concepts based on a pyramidal distribution of the benefits, that are sequentially obtained through a dynamic process of coalition formation, in which players successively come into play and join the current coalition until the grand coalition is formed. The well-known Shapley value (Shapley [15]) has been characterized in Weber [17] as the average over all permutations of a very extreme pyramidal distribution of the benefits, in which the entrant player receives all the just generated benefits (jointly created by the existing coalition of players and the entrant), when the grand coalition is sequentially formed, and all orderings are equally likely. However, such extreme shares 1This research has been supported by I+D+i research project MTM2011-27892 from the Government of Spain. 1 immediately lead us to point out two questions: Why the incumbents are going to accept the deal? Why the entrant is going to stay in the coalition after receiving all his contribution? Assuming also that all orderings are equally likely, we propose to compose values using a more general pyramidal sharing scheme in which the entrant player receives a salary and the right to get part of the benefits derived from subsequent incorporations to the just formed coalition, whereas the remaining benefit is distributed among the incumbent players. In Section 2, we first introduce some standard concepts and notation on Game Theory that will be used throughout this paper, we provide a formal definition of a pyramidal sharing scheme, and we establish some general properties of the class of values derived from those schemes. We also analyze the relation between the notion of pyramidal sharing schemes and the idea of “procedural” values as defined by Malawski in [10]. In Section 3 we obtain some known values by means of pyramidal sharing schemes. On the one hand, we show that the Shapley value can also be obtained as a non-extreme pyramidal value which is based on the second-order difference operator for a pair of players considered by Segal [14]; and on the other hand, we derive the family of consensus values introduced by Ju, Borm and Ruys [8], and also the family of egalitarian Shapley values introduced by Joosten [7], also described by van den Brink, Funaki and Ju [16], and more recently by Casajus and Huettner [2], as pyramidal values. Both families, which intend to reconcile marginalism with egalitarianism, arise following a egalitarian approach to determine the right to get part of the benefits derived from subsequent incorporations to the just formed coalition, and a marginalistic one when determining entrant’s salary. In Section 4, we define a proportional family of pyramidal values in which the entrant player receives as salary his own value plus a fixed proportion of his added value (i.e., the jointly created benefit less his salary), whereas the remaining benefit is distributed among the incumbent players according to each player’s contribution to the coalition previously formed. Section 5 concludes the paper. Acknowledgements We would like to warmly thank the referees for their careful reports, that definitely improved the quality of our paper and made it much more readable and interesting. 2 Pyramidal values An n-person cooperative game in characteristic function form with transferable utility (TU game) is an ordered pair (N,v), where Nis a finite set of nplayers and v: 2N→IR is a map assigning a real number v(S), called the value of S, to each coalition S⊆N, and where v(∅) = 0. The real number v(S)represents the reward that coalition Scan achieve by itself if all its members act together. Let Gnbe the space of all TU games with fixed player set N, where n=|N|, and identify (N,v)∈Gnwith its characteristic function vwhen no ambiguity appears. One of the main topics dealt with in Cooperative Game Theory is, given a game (N,v)∈Gn, to divide the amount v(N) between players if the grand coalition Nis formed. A payoff vector, or allocation, is any x∈Rn, which gives player i∈Na payoff xi. A payoff vector is said to be efficient if ∑i∈Nxi=v(N). 2 Avalue ϕfor TU games is an assignation which associates to each n-person game (N,v)∈Gn a payoff vector ϕ(N,v)∈Rn. The Shapley value, which we will denote by φ, is one of the most interesting values in Cooperative Game Theory. It can be characterized as the average of the marginal contribution vectors over all permutations (Weber [17]). Formally, let (N,v)∈Gn, and let Π(N)denote the set of all permutations on the player set N, which we will represent as bijections π:N→N. For a permutation π∈Π(N),π(i)∈N={1, . . . , n}represents agent i’s position in order π. Define the set of all predecessors of iin πto be Pπ(i) = {j∈N|π(j)<π(i)}, and the set of all his successors to be Sπ(i) = {j∈N|π(j)>π(i)}. Moreover, the direct successor of iin the order πwill be denoted by dsπ(i). Now, the marginal contribution vector mπ(v)∈Rnof game vand permutation πis given by mπ i(v) = v(Pπ(i)∪ {i})−v(Pπ(i)),i∈N, which assigns to each player i∈Nits marginal contribution to the worth of the coalition consisting of all his predecessors in π.2In that case, when player jjoins coalition Pπ(j), he generates the surplus mπ j(v), which, according to Weber [17] characterization of the Shapley value, is distributed among the current coalition as follows: •Entrant j’s salary: sπ j(v) = mπ j(v) •Incumbents Pπ(j)’s shares: aπ ij (v) = 0, for all i∈Pπ(j) In this setting, we define a class of values, which we call pyramidal values, that is based on a more general sharing scheme in which the entrant player receives a salary and the right to get part of the benefits derived from subsequent incorporations to the just formed coalition, whereas the remaining benefit is distributed among the incumbent players. Formally: Definition 1. Let Pbe a value for TU games. Then, Pis called a pyramidal value, if for all orders π∈Π(N)with n≥1, and for every n-person TU game (N,v)∈Gn, there exists a pyramidal sharing scheme S(v) = {(sπ j(v),(aπ ij (v))i∈Pπ(j))j∈N|π∈Π(N)}such that sπ j(v) + ∑ i∈Pπ(j) aπ ij (v) = mπ j(v),∀j∈N. (1) and verifying: Pi(v) = ∑ π∈Π(N) 1 n!pπ i(v),∀i∈N, (2) where pπ i(v) = sπ i(v)if π(i) = n, and pπ i(v) = sπ i(v) + ∑ j∈Sπ(i) aπ ij (v), for all i∈Nwith π(i)<n. (3) 2In the sequel, for convenience, we will write singleton {i}just as i. 3 Note that negative salaries or shares are allowed in the previous definition. As usual, negative quantities must be interpreted as costs, penalties or investments in a broad sense. Note also that condition (1) assures that every value generated by means of a pyramidal sharing scheme is efficient. However, since we do not impose any other condition over the sharing scheme, it could be the case that the shares of the incumbents, i.e., the dividends3, depend on the future, or that the salaries are non rational. Thus, Definition 1 may be too general. We will provide some conditions over a pyramidal sharing scheme in order to restrict ourselves to deal with nonanticipative sharing schemes which in addition respect common sense bounds in order to avoid salaries too low and too high. Definition 2. Let Sbe a pyramidal sharing scheme. Then, Swill be a P-rational sharing scheme if it satisfies the following properties. Let (N,v)∈Gnbe any n-person game: (i)Salaries Rationality. If (N,v)is superadditive, then v(i)≤sπ i(v)≤mπ i(v), for all orders π∈Π(N). (ii)Dividends Rationality (Non anticipative shares). If π,π0∈Π(N)are two orders which coincide up to moment k∈ {2, . . . , n}(i.e., π−1(`) = π0−1(`), for all `=1, 2, . . . , k), then aπ ij (v) = aπ0 ij (v), for all j∈Nwith 1 <π(j) = π0(j)≤k, and for all i∈Pπ(j) = Pπ0(j). Obviously, the properties of the sharing scheme determine the pyramidal value properties, so let us formalize some other interesting properties of a pyramidal sharing scheme. We will translate to the pyramidal sharing scheme the usual properties of additivity, dummy and symmetry, and besides them we will also translate the usual monotonicity conditions in order to provide appropriate incentives to the agents. Definition 3. Let (N,v)∈Gnbe any n-person TU game, and let S(v) = {(sπ j(v),(aπ ij (v))i∈Pπ(j))j∈N|π∈ Π(N)}be a pyramidal sharing scheme. Then, Sverifies, (i)Constant Salary. If for all j∈Nthere exists a real constant kj(v)∈Rsuch that sπ j(v) = kj(v), for all π∈Π(N). (ii)P-Additivity. If for all orders π∈Π(N), and for all j∈Nit holds: •sπ j(v+w) = sπ j(v) + sπ j(w), and •aπ ij (v+w) = aπ ij (v) + aπ ij (w), for each i∈Pπ(j), for all (N,v),(N,w)∈Gn, where v+wis given by (v+w)(S) = v(S) + w(S), for all S⊆N. (iii)P-Dummy player. If •sπ i(v) = v(i), and •aπ ij (v) = 0, for every j∈Sπ(i), and all orders π∈Π(N), for all i∈Nbeing a dummy player (i.e., v(S∪i) = v(S) + v(i)for every coalition S). 3Note that these dividends are not the same as the well-known Harsanyi dividends, which are associated to coalitions, not only to agents. 4 (iv)P-Symmetry. If, for all symmetric players i,j∈N(i.e., v(S∪i) = v(S∪j), for all S⊆ N\ {i,j}), •sπ i(v) = sπij j(v), and •for all k∈N\ {i,j},aπ ik(v) = aπij jk (v), for all k∈Sπ(i), where the order πij is defined as πij(k) = π(k),πij(i) = π(j)and πij(j) = π(i). (v)P-Strong monotonicity. If it satisfies strong monotonic salaries and dividends, defined as follows. Let i∈Nbe any player, and let (N,v),(N,w)be two n-person games for which v(S∪i)− v(S)≤w(S∪i)−w(S), for all S⊆N\i, and being v(T∪i)−v(T)<w(T∪i)−w(T)for some T⊆N\i, then •Strong monotonic salaries:sπ i(v)≤sπ i(w), for all orders π∈Π(N)and (sπ i(v))π∈Π(N)6= (sπ i(w))π∈Π(N). •Strong monotonic dividends:aπ ij (v)≤aπ ij (w), for all j∈Sπ(v), for all orders π∈Π(N), with aπ0 ij (v)<aπ0 ij (w), for some order π0 Note that the constant salary property implies that the salary is an inherent attribute of each player, and it can be related, for instance, to his personal training. Moreover, since Pπ(i) = ∅ for all orders πsuch that π(i) = 1, then each player’s constant salary equals his own value v(i).P-Additivity, P-dummy player and P-symmetry trivially lead to the same properties for the corresponding pyramidal value. Let us recall those well-known properties of values for TU games, as well as other properties which we will use later. Formally, a value ϕ:Gn→Rn: (i)is efficient if ∑i∈Nϕi(v) = v(N), for all (N,v)∈Gn; (ii)is additive if ϕ(v+w) = ϕ(v) + ϕ(w), for all (N,v),(N,w)∈Gn; (iii)is relative invariant with respect to strategic equivalence if ϕ(N,w) = aϕ(N,v) + b, for every (N,v)∈Gn,a>0 and b∈Rn, where wis given by w(S) = av(S) + ∑i∈Sbi, for all S⊆N; (iv)is symmetric if ϕi(v) = ϕj(v), for all (N,v)∈Gn, and for all symmetric players i,j∈N; (v)preserves desirability [11] if ϕi(v)≤ϕj(v), for all players i,j∈Nsuch that v(S∪i)≤v(S∪j), for all S⊆N\ {i,j}, for all (N,n)∈Gn; (vi)is strong monotonic [18] if ϕi(v)≤ϕi(w), for every player i∈N, and for all games (N,v),(N,w)∈ Gnfor which v(S∪i)−v(S)≤w(S∪i)−w(S), for all S⊆N\i; (vii)is coalitionally monotonic [18] if for every coalition T⊆Nand every two games (N,v),(N,w)∈ Gnsuch that v(T)>w(T)and v(S) = w(S), for all S6=T, it follows ϕi(v)≥ϕi(w), for every player i∈T; (viii)verifies positivity [9] if ϕi(v)≥0, for all i∈N, whenever the game (N,v)is monotonic (i.e., v(T)≥v(S), for each Tand Ssuch that T⊇S); (ix)verifies the dummy property if ϕi(v) = v(i), for all (N,v)∈Gn, and for every dummy player i∈N; 5 (x)verifies the null player property if ϕi(v) = 0, for all (N,v)∈Gn, and for every null player i∈N(i.e., v(S∪i) = v(S), for all S⊆N\i); (xi)verifies the null player out property [4] if ϕj(N,v) = ϕj(N\i,v|N\i), for all j6=i∈N, for all (N,v)∈Gnsuch that iis a null player in v. Here, (N\i,v|N\i)is the restricted game given by v|N\i(S) = v(S), for all S⊆N\i; (xii)is standard for two-person games if ϕi(v) = v(i) + 1 2v({i,j})−v(i)−v(j), for all i6=j, for every two-person game ({i,j},v)∈G2. Proposition 1. Any additive and efficient value ϕcan be obtained as a P-additive pyramidal value. Moreover, if ϕverifies the null player out property, then the corresponding pyramidal sharing scheme Sϕverifies dividends rationality. Proof. Let ϕbe any additive and efficient value. Let us first recall the unanimity basis for Gn, {(N,uT)}T⊆N, with T6=∅, where uT(S) =    1, if T⊆S, 0, otherwise. We will show that the value of any multiple of a unanimity game ϕ(kuT),k∈R, can be obtained by means of a pyramidal sharing procedure. Let π∈Π(N)be any given order. Let us consider the following redistribution, where tπ∈Tis the last member of Taccording to the order π. •For every player j∈Pπ(tπ), his salary is sπ j(kuT) = 0, and he distributes aπ ij (kuT) = 0 among his predecessors i∈Pπ(j). •When the last member of Tarrives, he distributes kas follows: sπ tπ(kuT) = ϕtπ(kuT) + ∑ j∈Sπ(tπ) ϕj(kuT), (4) aπ itπ(kuT) = ϕi(kuT), for all i∈Pπ(tπ). (5) •For all j∈Sπ(tπ), his salary is sπ j(kuT) = ϕj(kuT), which is paid by tπ. That is, aπ ij (kuT) = 0, for all i∈Pπ(j)\ {tπ}, and aπ tπj(kuT) = −ϕj(kuT).4 Clearly, the proposed sharing scheme gives ϕ(kuT). Now, let (N,v)∈Gnbe a given TU game. Then it can be expressed as (see Shapley [15]) v=∑T⊆N T6=∅ ∆(T)uT, where ∆(T)is the Harsanyi dividend of Tin (N,v), given by ∆(T) = ∑S⊆T S6=∅ (−1)t−sv(S),sand tbeing the cardinalities of Sand 4Those negative shares can be interpreted as investments on human capital. 6 T, respectively. Thus, the P-additive sharing scheme Sdefined by sπ j(v) = ∑ T⊆N sπ j(∆(T)uT), aπ ij (v) = ∑ T⊆N aπ ij (∆(T)uT), for all i∈Pπ(j), for all j∈N, and for all π∈Π(N), recovers ϕ(v). Note that Sverifies condition (1). Now, we will check that if ϕverifies the null player out property, then the pyramidal sharing scheme is dividends rational: •For every player j∈Pπ(tπ),sπ j(∆(T)uT) = 0, and aπ ij (∆(T)uT) = 0 for all i∈Pπ(j), which clearly do not depend on Sπ(j). •For all j∈Sπ(tπ), note that j/∈Tand therefore it is a null player in the game (N,∆(T)uT). Then, since ϕverifies the null player out property and it is efficient, it also verifies the null player property, and therefore sπ j(∆(T)uT) = ϕj(∆(T)uT) = 0, which is paid by tπ. Thus, sπ j(∆(T)uT) = 0 and aπ ij (∆(T)uT) = 0 for all i∈Pπ(j), which clearly do not depend on Sπ(j). •For the last incoming member of T, and taking into account that ϕverifies null player out and null player properties, it follows: sπ tπ(N,∆(T)uT) = ϕtπ(N,∆(T)uT) + ∑ Sπ(tπ) ϕj(N,∆(T)uT) = ϕtπ(T,∆(T)uT) + 0, (6) aπ itπ(N,∆(T)uT) = ϕi(N,∆(T)uT) = ϕi(T,∆(T)uT), for all i∈Pπ(tπ), (7) which depend only on T⊆Pπ(tπ) Therefore, the pyramidal sharing scheme is dividends rational. It is also remarkable that two different pyramidal sharing schemes S1and S2may lead to the same value; far from being a drawback, this fact is an advantage. Having two different implementations of the same value enlarges the opportunities to apply it as an effective solution to a given game in a specific situation. Let us think about the extreme pyramidal sharing scheme which determines the Shapley value, in which the entrant player receives the whole benefits, and no dividends are distributed. Such extreme shares immediately lead us to point out two questions: Why the incumbents are going to accept the deal? Why the entrant is going to stay in the coalition after receiving all his contribution? We can avoid those questions by obtaining the Shapley value also as a non-extreme pyramidal value. For instance, Proposition 1 provides us with an alternative and non-extreme pyramidal sharing scheme for obtaining the Shapley value as a pyramidal one. Let (N,uT)be the unanimity game with respect to coalition T⊆N, and let us consider the following pyramidal shares: (i)Entrant j’s salary: sπ j(∆(T)uT) = ∆(T) t, if j=tπ∈Tis the last member of Taccording to the order π; and sπ j(∆(T)uT) = 0, otherwise; 7 (ii)Incumbents Pπ(j)’s shares: aπ ij (∆(T)uT) = ∆(T) t, if j=tπ∈Tis the last member of T according to the order πand i∈Pπ(j)∩T; and being aπ ij (∆(T)uT) = 0 otherwise, for all j∈N, and for all orders π∈Π(N). The final payoff that player i∈Nreceives according to the order π∈Π(N)is then given by ∆(T) tif i∈T, and 0 if i/∈T. Thus, according to Proposition 1 the additive pyramidal value we obtain is given by ∑T⊆N i∈T ∆(T) t, for all i∈T, which is precisely the expression of the Shapley value in terms of the Harsanyi dividends of the game. The pyramidal sharing scheme for the original game (N,v)is: (i)Entrant j’s salary: sπ j(v) = ∑T⊆Pπ(j) ∆(T∪j) t+1 (ii)Incumbents Pπ(j)’s shares: aπ ij (v) = ∑T⊆Pπ(j) i∈T ∆(T∪j) t+1 Since there are at least two different pyramidal sharing schemes which result in the Shapley value, it follows that there are a continuum of them with the same property (all their linear convex combinations). However, the obtained pyramidal sharing scheme is not salaries rational in general. The question is whether the Shapley value might be obtained by means of a rational non-extreme pyramidal sharing scheme. Unexpectedly, we give a positive answer in Section 3. Relation with procedural values Pyramidal sharing schemes are closely related to the idea of procedural values, introduced by Malawski [10]. Procedural values are pyramidal values for which the marginal contribution of the entering player is divided among the players proportionally to a weight system which does not depend on the players’ names nor on their contributions. To be specific (see Malawski [10]), let sbe a procedure on Gn, that is, a family of nonnegative coefficients ((sk,j)k j=1)n k=1such that ∑k j=1sk,j=1, for all k. Then, the procedural value ψsdetermined by the procedure sis the pyramidal value obtained by means of the following salaries and dividends: •Entrant j’s salary: sπ j(v) = sπ(j),π(j)mπ j(v), •Incumbents Pπ(j)’s shares: aπ ij (v) = sπ(j),π(i)mπ j(v), for all i∈Pπ(j). (8) The class of pyramidal sharing schemes is obviously larger than the class of procedural sharing schemes. For instance, the pyramidal sharing scheme described above to derive the Shapley value is not procedural. Later, in Sections 3 and 4, we will show that also the class of pyramidal values is larger than the class of procedural values. To be specific, the class of pyramidal values contains linear values which are not procedural, such as the consensus family of values (Ju et al. [8]), and also there exist non-linear pyramidal values that cannot be obtained through a procedural scheme, such as the proportional family introduced in Section 4. In fact, when restricting to the sub-class of procedural values Malawski proves in [10] that efficiency, linearity, symmetry, positivity and coalitional monotonicity characterize the class of procedural values. In our context, this can be read as a stronger version of our Proposition 1. He also establishes that symmetry and coalitional monotonicity can be replaced by desirability preservation. 8 3 Relation with other values In this section, we obtain some known families of values by means of pyramidal sharing schemes. Such constructions show some interesting features of the analyzed values. We first prove that the Shapley value can also be obtained as a non-extreme pyramidal value in which the entrant player receives only his own value as salary whereas the remaining benefit is distributed among the incumbent players. As a consequence, we establish a new formulation of the Shapley value which rests on the second-order difference operator used in Segal [14], which is in turn closely related to the notions of increasing differences and supermodularity (see Ichiisi [6]) and has a meaningful economic interpretation. Then, we derive the family of consensus values (Ju, Borm and Ruys [8]), and also the family of egalitarian Shapley values (Joosten [7], van den Brink, Funaki and Ju [16], Casajus and Huettner [2]), as pyramidal values. Both families arise following a egalitarian approach to determine the right to get part of the benefits derived from subsequent incorporations to the just formed coalition, and a marginalistic one when determining entrant’s salary. For the interested reader, and for the sake of completeness, we collect the formal definitions of all the known values we will analyze in this Section in a final Appendix. We also recover the characterizations results we use. The Shapley value as a rational non-extreme pyramidal value For a given order π∈Π(N), and players i,j∈Nsuch that π(i)≤π(j), let us define the marginal contribution of player j with respect to player i, according to order π, to be mπ ij (v) = v({k∈N|π(i)≤π(k)≤π(j)})−v({k∈N|π(i)≤π(k)<π(j)}). Note that mπ ij (v)can be interpreted as the marginal contribution of agent jto the group leaded by agent iaccording to order π. If we denote the coalition of all players who have arrived between players iand jby Sπ(i,j) = {k∈N|π(i)<k<π(j)}, then mπ ij (v) = v(Sπ(i,j)∪ {i,j})− v(Sπ(i,j)∪i), if i6=j, and mπ jj (v) = v(j). Now, we define in Proposition 2 a rational non-extreme pyramidal procedure which is based on these marginal contributions and which turns out to give the Shapley value as a final payoff. In this pyramidal sharing scheme, player i∈Pπ(j)receives the marginal contribution of player j with respect to i, according to order π, at the cost of paying to his direct successor the marginal contribution of player jwith respect to this direct successor. Proposition 2. The Shapley value can be obtained through the pyramidal sharing scheme Sthat distributes the marginal contribution of player j ∈N among the agents in Pπ(j)∪j as follows: (i)Entrant j’s salary: sπ j(v) = v(j) (ii)Incumbents Pπ(j)’s shares: aπ ij (v) = mπ ij (v)−mπ dsπ(i),j(v), for every order π∈Π(N), every player i ∈N, and every n-person TU game (N,v). 9 In particular, the pyramidal definition of α-consensus values offers an alternative constructive approach to the standardized remainder vectors that determine the α-consensus values, which provides solid ground for it in terms of the dynamics of economic activity. 4α-Proportional pyramidal values for monotonic games In the α-egalitarian Shapley and consensus families, the remaining surplus, which represents the value that entrant j’s participation adds to the incumbents, is shared equally among all the incumbents. In this section we consider a non-egalitarian framework, in which a player’s right to get part of the forthcoming benefits is determined according to his initial investment. We measure this initial investment as the value his incorporation have added to the incumbents, or in other words, by means of his marginal contribution, and define the family of α-proportional pyramidal values. That is, we also adopt a marginalistic approach to determine the dividends. Taking into account that a proportional allocation with respect to a given weight system in which some of the weights can be strictly negative must be carefully used, we restrict the definition of α-proportional pyramidal values to the subclass of monotonic TU games (i.e., v(S)≤v(T), for all S⊆T). In that case, all marginal contributions mπ j(v),j∈N,π∈Π(N)are nonnegative. Definition 5. For every monotonic TU game (N,v)∈Gn, and every α∈[0, 1], the α-proportional pyramidal value is the value obtained by means of the following pyramidal sharing scheme: (i)Entrant j’s salary: sπ,α j(v) =    mπ j(v), if v(Pπ(j)) = 0, v(j) + α(mπ j(v)−v(j)), otherwise. (ii)Incumbents Pπ(j)’s shares: aπ,α ij (v) =    0, if v(Pπ(j)) = 0, (1−α)mπ i(v) v(Pπ(j)) (mπ j(v)−v(j)), otherwise. for all j∈N, and for all orders π∈Π(N). Thus, the final payoff that player i∈Nreceives according to the order π∈Π(N)is given by: ppπ,α i(v) = v(i) + α(mπ i(v)−v(i)) + (1−α)∑ j∈Sπ(i) v(Pπ(j))6=0 mπ i(v) v(Pπ(j))(mπ j(v)−v(j)), (16) if v(Pπ(i)) 6=0, and ppπ,α i(v) = mπ i(v) + (1−α)∑ j∈Sπ(i) v(Pπ(j))6=0 mπ i(v) v(Pπ(j))(mπ j(v)−v(j)), (17) 16 if v(Pπ(i)) = 0, for all i=1, . . . , n. Therefore, the α-proportional pyramidal value, which is the expected value under the former sharing scheme when all orders are equally likely, is given by PPα i(v) = 1 n!∑ π∈Π(N) v(Pπ(i))6=0 v(i) + α(mπ i(v)−v(i))+∑ π∈Π(N) v(Pπ(i))=0 mπ i(v)+ 1−α n!∑ π∈Π(N) ∑ j∈Sπ(i) v(Pπ(j))6=0 mπ i(v) v(Pπ(j))(mπ j(v)−v(j)),i=1, . . . , n. (18) Proposition 6. For every monotonic TU game (N,v)∈Gn, and every α∈[0, 1], it holds PPα(v) = αφ(v) + (1−α)PP0(v). Proof. Trivially, if we express v(i)and mπ i(v)as αv(i)+(1−α)v(i)and αmπ i(v)+(1−α)mπ i(v) in the first summand of (18), it follows that every α-proportional pyramidal value is the linear convex combination of the two extreme values for α=0 and α=1. Moreover, since the 1proportional pyramidal value is in fact the Shapley value, then the result holds. When we restrict ourselves to the class of monotonic simple games, the whole family reduces to the Shapley value. Proposition 7. Let (N,u)∈Gnbe a monotonic simple game such that u(i) = 0for every non veto player i∈N. Then PPα(u) = φ(u), for all α∈[0, 1]. Proof. Let (N,u)∈Gnbe a monotonic simple game, and let be π∈Π(N)be a given order. Then, there exists a unique iπ∈Nwith nonzero marginal contribution. Moreover: •Since u(Pπ(j)) = 0 for all j∈Pπ(iπ), then sπ,α j(u) = mπ j(u) = 0 and aπ,α ij (u) = 0, for all i∈Pπ(j), •sπ,α iπ(u) = mπ iπ(u) = 1, aπ,α iiπ(u) = 0, for all i∈Pπ(iπ), •If j∈Sπ(iπ), then jis a non veto player. Therefore, sπ,α j=u(j) + α(mπ j(u)−u(j)) = 0 and aπ,α ij = (1−α)mπ i(u)(mπ j(u)−u(j)) = 0, for all i∈Pπ(j). Let us analyze, by means of an example, the behavior of the extreme zero-proportional value and the α’s choice effect over the final allocation of benefits. Example 3. Let us consider the following 4-person game (N,v), with v(1) = 1, v(2) = v(3) = v(4) = 0, and: S{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4}N v(S)2 2 4 1 1 2 6 7 5 8 10 17 In this example, player’s 1 and 2 marginal contributions lead to the same Shapley value φ1(v) = φ2(v) = 27 12 . The marginal contributions of player 4 are always greater or equal than those of player 2, and player 3 is in the weakest position: φ(v) = (27 12, 2 7 12, 2 1 12, 23 4) On the contrary, the roles of players 1 and 2 are distinguished by means of the proportional pyramidal values for all α∈[0, 1), which are given by: PPα(v) = α(2.5833, 2.5833, 2.0833, 2.75) + (1−α)(4.4266, 1.8060, 1.7622, 2.0052) Note that proportional values reward a player for his contribution to the establishment of the firm as well as for his contribution to the firm’s growth; moreover, the marginal contributions of player 1 are greater for small size’s coalitions than those of players 2, 3 and 4, which on the contrary are greater than the marginal contributions of player 1 for big size’s coalitions. Thus, since parameter αcontrols to what extent a player must be compensated according to his participation at the beginning of the project rather than to his contribution to its evolution, the rewards that player 1 receive increase as αdecreases to zero. The relative position among the rest of the players remains. We end up by briefly discussing which properties of the list in Section 2 hold or not for the α-proportional pyramidal values, being our arguments heavily based on the previous description of these values as a linear combination of the Shapley value and the value PP0(v). To be specific, every proportional value verifies efficiency, symmetry, positivity (when restricted to the class of supperadditive games), standardness for two person-games, null player and null player out. On the contrary, additivity, relative invariance with respect to strategic equivalence, strong monotonicity, and dummy properties are not (always) satisfied by these values. Note also that α-proportional pyramidal values are not procedural in general. 5 Conclusions and future research In this paper we propose a general procedure for obtaining a broad class of solution concepts based on a pyramidal distribution of the benefits that are sequentially obtained through a dynamic process of coalition formation, in which players successively come into play and join the current coalition until the grand coalition is formed. In particular, we obtain some known values by means of pyramidal sharing schemes and we introduce a proportional family of pyramidal values, in which incumbents receive dividends in proportion to their initial investment. Axiomatic characterizations for the proportional family, and also for some sub-classes of pyramidal values are left for future research, as well as a strategic analysis of this kind of solutions. It may be also interesting to generalize the notion of proportional pyramidal values to a weighted version in which the incumbents’ shares depend on a general system of weights. With respect to potential extensions, the pyramidal sharing of the current benefits idea allows to deal with those situations in which the number of final participants where not known in ad18 vance. Moreover, it should be interesting to introduce the notion of pyramidal sharing scheme in the context of games with a communication graph [12] and [1]. Finally, it must be pointed out that the complexity of the calculus of a pyramidal value relies crucially on the calculus of the pyramidal sharing scheme and, obviously, on the complexity of the characteristic function of the game. In the case of the two proposed families, if the marginal contributions can be computed (or at least approximated) in polynomial time, then any pyramidal value can also be estimated in polynomial time. In fact, following Castro, Gomez and Tejada [3], any value that can be expressed as an expectation of a polynomial function of the marginal contribution vectors over all permutations, when all orderings are equally likely, can be estimated in polynomial time, whenever the marginal contributions are computable in polinomial time. Appendix In this appendix we collect the formal definitions of all the known values analyzed in Section 3, as well as the characterization results we have used. Theorem 1 (Shapley, 1953).There exists a unique value satisfying the efficiency, symmetry, dummy, and additivity axioms. It is the Shapley value, which is defined for every (N,v)∈Gnas follows: φi(N,v) = ∑ S⊆N i/∈S s!(n−s−1)! n!v(S∪ {i})−v(S),i=1, . . . , n, (19) where s =|S|denotes the cardinality of coalition S ⊆N. The Consensus value (Ju et al. [8]) is aimed to generalize the standard solution for 2-person TU games into n-person cases. It is based on a two-sided negotiation process that can be understood as a standardized remainder rule described by the following vectors. The reader is referred to Ju et al. [8] for a detailed exposition of this rule. Definition 6 (Ju, Borm and Ruys, 2007).Let (N,v)∈Gn, and π∈Π(N)be a given permutation. Define Sπ k={π−1(1), . . . , π−1(k)} ⊆ Nand Sπ 0=∅. Then, the standardized remainder for coalition Sπ k,r(Sπ k), is recursively defined as follows: r(Sπ k) =    v(N), if k=n, v(Sπ k) + 1 2r(Sπ k+1)−v(Sπ k)−v({π−1(k+1)}), if k∈ {1, . . . , n−1}. r(Sπ k)is the value left for Sπ kafter allocating surpluses to earlier leavers N\Sπ k. Then, the standardized remainder vector, srπ(v), which corresponds to the situation where the players leave the game one by one in the order (π−1(n), . . . , π−1(1)), is defined recursively by: srπ−1(k)=   v({π−1(k)}) + 1 2r(Sπ k)−v(Sπ k−1)−v({π−1(k)}), if k∈ {2, . . . , n}, r(Sπ 1), if k=1. 19 Definition 7 (Ju, Borm and Ruys, 2007).For every (N,v)∈Gn, the consensus value Ψ(v)is defined as the average, over the set of all permutation Π(N), of the individual standardized remainder vectors, i.e., Ψ(v) = 1 n!∑ π∈Π(N) srπ(v). Definition 8 (Ju, Borm and Ruys, 2007).For every (N,v)∈Gnand α∈[0, 1], the α-consensus value Ψα(v)is defined as the average, over the set of all permutation Π(N), of the individual α-remainder vectors, i.e., Ψα(v) = 1 n!∑ π∈Π(N) (srπ)α(v). Here, the α-remainder rα(Sπ k)and the individual α-remainder vector (srπ)α(v)are defined as follows: rα(Sπ k) =    v(N), if k=n, v(Sπ k) + (1−α)rα(Sπ k+1)−v(Sπ k)−v({π−1(k+1)}), if k∈ {1, . . . , n−1}. and (srπ−1(k))α=   v({π−1(k)}) + αrα(Sπ k)−v(Sπ k−1)−v({π−1(k)}), if k∈ {2, . . . , n}, rα(Sπ 1), if k=1. The authors introduce the following property in order to characterize the family of consensus values. The next theorem corresponds to Theorem 5 in Ju, Borm and Ruys [8]. We make use of (a)characterization. Definition 9 (Ju, Borm and Ruys, 2007).Avalue ϕ:Gn→Rnverifies the α-dummy property if ϕi(v) = αv(i)+(1−α)v(i) + v(N)−∑j∈Nv(j) n, for all (N,v)∈Gn, and every dummy player i∈Nwith respect to v. Theorem 2 (Ju, Borm and Ruys, 2007).(a) The α-consensus value Ψαis the unique one-point solution concept on Gnthat satisfies efficiency, symmetry, the α-dummy property and additivity. (b) The α-consensus value Ψαis the unique function that satisfies efficiency, symmetry, the α-dummy property and the transfer property over the class of TU games. (c) For any v ∈Gn, it holds that Ψα(v) = ααφ(v) + (1−α)E(v), where E(v)is the equal surplus solution of v, i.e., Ei(v) = v(i) + v(N)−∑j∈Nv(j) n. (d) The α-consensus value Ψαis the unique function that satisfies efficiency and the α-equal welfare loss property over the class of TU games. 20 The Egalitarian Shapley values (Joosten [7]) make the trade-off between marginalism and egalitarianism by means of convex combinations of the Shapley value and the equal division solution. Definition 10 (Joosten, 1996).For every (N,v)∈Gnand α∈[0, 1], the α-egalitarian Shapley value ϕα(v)is given by ϕα(v) = αφ(v) + (1−α)ED(v), where ED(v)is the equal division value which distributes the worth v(N)equally among all players: ED(v) = (v(N) n, . . . , v(N) n). References [1] B´ eal S, R´ emila E, Solal P (2012) Compensations in the Shapley value and the compensation solutions for graph games. International Journal of Game Theory 41, 157-178. [2] Casajus A, Huettner F (2013) Null players, solidarity, and the egalitarian Shapley values. Journal of Mathematical Economics 49, 58-61. [3] Castro J, Gomez D, Tejada J (2009) Polynomial calculation of the Shapley value based on sampling. Computers and Operations Research 36, 1726-1730. [4] Derks JJM, Haller HH (1999) Null players out? Linear values for games with variable supports. International Game Theory Review 1, 301-314. [5] Grabisch M, Roubens M (1999) An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory 28, 547-565. [6] Ichiisi T (1981) Super-modularity: applications to convex games and to the greedy algorithm for LP. Journal of Economic Theory 25, 283-286. [7] Joosten R (1996) Dynamics, equilibria and values. Dissertation, Maastricht University. [8] Ju Y, Borm P, Ruys P (2007) The consensus value: a new solution concept for cooperative games. Social Choice and Welfare 28, 685-703. [9] Kalai E, Samet D (1987) On weighted Shapley values. International Journal of Game Theory 16, 205-222. [10] Malawski M (2013) ”Procedural” values for cooperative games. International Journal of Game Theory 42, 305-324. [11] Maschler M, Peleg B (1966) A characterization, existence proof and dimension bounds for the kernel of a game. Pacific Journal of Mathematics 18, 289-328. [12] Myerson RB (1977) Graphs and cooperation in games. Mathematics of Operations Research 2, 225-229. [13] Owen G (1972) Multilinear extensions of games. Management Sciences 18, 64-79. 21 [14] Segal I (2003) Collusion, exclusion and inclusion in random-order bargaining. Review of Economic Studies 70, 439-460. [15] Shapley LS (1953) A value for n-person games. Contributions to the Theory of Games II, 307-317. [16] van den Brink R, Funaki Y, Ju Y (2013) Reconciling marginalism with egalitarianism: consistency, monotonicity, and implementation of egalitarian Shapley values. Social Choice and Welfare 40, 693-714. [17] Weber RJ (1988) Probabilistic values for games. In A. Roth (Ed.), The Shapley value: Essays in honor of Lloyd S. Shapley. Cambridge University Press, 101-119. [18] Young HP (1985) Monotonic solutions of cooperative games. International Journal of Game Theory 14, 65-72. 22