Py amidal alues1
Ram´on Flo es
Depa men o S a is ics, Uni e sidad Ca los III de Mad id, Spain
e-mail: lo es@es -econ.uc3m.es
Elisenda Molina
Depa men o S a is ics, Uni e sidad Ca los III de Mad id, Spain
e-mail: [email p o ec ed]
Juan Tejada
Depa men o S a is ics and Ope a ions Resea ch and IMI (In e disciplina y Ma hema ical Ins i u e),
Uni e sidad Complu ense de Mad id, Spain
e-mail: [email p o ec ed]
Abs ac
We p opose and analyze a new ype o alues o coope a i e TU-games, which we call
py amidal alues. Assuming ha he g and coali ion is sequen ially o med, and all o de ings
a e equally likely, we de ine a py amidal alue o be any expec ed payo in which he en an
playe ecei es a sala y, and he es o his ma ginal con ibu ion o he jus o med coali ion
is dis ibu ed among he incumben playe s. We ela e he py amidal- ype sha ing scheme we
p opose wi h o he sha ing schemes, and we also ob ain some known alues by means o his
kind o py amidal p ocedu es. In pa icula , we show ha he Shapley alue can be ob ained
by means o an in e es ing py amidal p ocedu e ha dis ibu es nonze o di idends among he
incumben s. As a esul , we ob ain an al e na i e o mula ion o he Shapley alue based on a
measu e o complemen a i y be ween wo playe s. Finally, we in oduce he amily o p opo -
ional py amidal alues, in which an incumben ecei es a di idend in p opo ion o his ini ial
in es men , measu ed by means o his ma ginal con ibu ion.
Keywo ds: Game heo y, TU games, py amidal alues, p ocedu al alues, Shapley alue,
co- alues, consensus alues, egali a ian Shapley alues.
1 In oduc ion
In his pape we p opose a gene al p ocedu e o ob aining a b oad class o solu ion concep s
based on a py amidal dis ibu ion o he bene i s, ha a e sequen ially ob ained h ough a dy-
namic p ocess o coali ion o ma ion, in which playe s successi ely come in o play and join he
cu en coali ion un il he g and coali ion is o med. The well-known Shapley alue (Shapley
[15]) has been cha ac e ized in Webe [17] as he a e age o e all pe mu a ions o a e y ex eme
py amidal dis ibu ion o he bene i s, in which he en an playe ecei es all he jus gene a ed
bene i s (join ly c ea ed by he exis ing coali ion o playe s and he en an ), when he g and coali-
ion is sequen ially o med, and all o de ings a e equally likely. Howe e , such ex eme sha es
1This esea ch has been suppo ed by I+D+i esea ch p ojec MTM2011-27892 om he Go e nmen o Spain.
1
immedia ely lead us o poin ou wo ques ions: Why he incumben s a e going o accep he deal?
Why he en an is going o s ay in he coali ion a e ecei ing all his con ibu ion?
Assuming also ha all o de ings a e equally likely, we p opose o compose alues using a
mo e gene al py amidal sha ing scheme in which he en an playe ecei es a sala y and he
igh o ge pa o he bene i s de i ed om subsequen inco po a ions o he jus o med coali-
ion, whe eas he emaining bene i is dis ibu ed among he incumben playe s. In Sec ion 2, we
i s in oduce some s anda d concep s and no a ion on Game Theo y ha will be used h ough-
ou his pape , we p o ide a o mal de ini ion o a py amidal sha ing scheme, and we es ablish
some gene al p ope ies o he class o alues de i ed om hose schemes. We also analyze he
ela ion be ween he no ion o py amidal sha ing schemes and he idea o “p ocedu al” alues
as de ined by Malawski in [10]. In Sec ion 3 we ob ain some known alues by means o py ami-
dal sha ing schemes. On he one hand, we show ha he Shapley alue can also be ob ained as a
non-ex eme py amidal alue which is based on he second-o de di e ence ope a o o a pai o
playe s conside ed by Segal [14]; and on he o he hand, we de i e he amily o consensus alues
in oduced by Ju, Bo m and Ruys [8], and also he amily o egali a ian Shapley alues in oduced
by Joos en [7], also desc ibed by an den B ink, Funaki and Ju [16], and mo e ecen ly by Casajus
and Hue ne [2], as py amidal alues. Bo h amilies, which in end o econcile ma ginalism wi h
egali a ianism, a ise ollowing a egali a ian app oach o de e mine he igh o ge pa o he
bene i s de i ed om subsequen inco po a ions o he jus o med coali ion, and a ma ginalis ic
one when de e mining en an ’s sala y. In Sec ion 4, we de ine a p opo ional amily o py ami-
dal alues in which he en an playe ecei es as sala y his own alue plus a ixed p opo ion o
his added alue (i.e., he join ly c ea ed bene i less his sala y), whe eas he emaining bene i is
dis ibu ed among he incumben playe s acco ding o each playe ’s con ibu ion o he coali ion
p e iously o med. Sec ion 5 concludes he pape .
Acknowledgemen s
We would like o wa mly hank he e e ees o hei ca e ul epo s, ha de ini ely imp o ed he
quali y o ou pape and made i much mo e eadable and in e es ing.
2 Py amidal alues
An n-pe son coope a i e game in cha ac e is ic unc ion o m wi h ans e able u ili y (TU game)
is an o de ed pai (N, ), whe e Nis a ini e se o nplaye s and : 2N→IR is a map assigning
a eal numbe (S), called he alue o S, o each coali ion S⊆N, and whe e (∅) = 0. The
eal numbe (S) ep esen s he ewa d ha coali ion Scan achie e by i sel i all i s membe s ac
oge he . Le Gnbe he space o all TU games wi h ixed playe se N, whe e n=|N|, and iden i y
(N, )∈Gnwi h i s cha ac e is ic unc ion when no ambigui y appea s. One o he main opics
deal wi h in Coope a i e Game Theo y is, gi en a game (N, )∈Gn, o di ide he amoun (N)
be ween playe s i he g and coali ion Nis o med. A payo ec o , o alloca ion, is any x∈Rn,
which gi es playe i∈Na payo xi. A payo ec o is said o be e icien i ∑i∈Nxi= (N).
2
A alue ϕ o TU games is an assigna ion which associa es o each n-pe son game (N, )∈Gn
a payo ec o ϕ(N, )∈Rn. The Shapley alue, which we will deno e by φ, is one o he
mos in e es ing alues in Coope a i e Game Theo y. I can be cha ac e ized as he a e age o
he ma ginal con ibu ion ec o s o e all pe mu a ions (Webe [17]). Fo mally, le (N, )∈Gn,
and le Π(N)deno e he se o all pe mu a ions on he playe se N, which we will ep esen as
bijec ions π:N→N. Fo a pe mu a ion π∈Π(N),π(i)∈N={1, . . . , n} ep esen s agen i’s
posi ion in o de π. De ine he se o all p edecesso s o iin π o be Pπ(i) = {j∈N|π(j)<π(i)},
and he se o all his successo s o be Sπ(i) = {j∈N|π(j)>π(i)}. Mo eo e , he di ec successo
o iin he o de πwill be deno ed by dsπ(i). Now, he ma ginal con ibu ion ec o mπ( )∈Rno
game and pe mu a ion πis gi en by
mπ
i( ) = (Pπ(i)∪ {i})− (Pπ(i)),i∈N,
which assigns o each playe i∈Ni s ma ginal con ibu ion o he wo h o he coali ion con-
sis ing o all his p edecesso s in π.2In ha case, when playe jjoins coali ion Pπ(j), he gene a es
he su plus mπ
j( ), which, acco ding o Webe [17] cha ac e iza ion o he Shapley alue, is dis-
ibu ed among he cu en coali ion as ollows:
•En an j’s sala y: sπ
j( ) = mπ
j( )
•Incumben s Pπ(j)’s sha es: aπ
ij ( ) = 0, o all i∈Pπ(j)
In his se ing, we de ine a class o alues, which we call py amidal alues, ha is based on a mo e
gene al sha ing scheme in which he en an playe ecei es a sala y and he igh o ge pa
o he bene i s de i ed om subsequen inco po a ions o he jus o med coali ion, whe eas he
emaining bene i is dis ibu ed among he incumben playe s. Fo mally:
De ini ion 1. Le Pbe a alue o TU games. Then, Pis called a py amidal alue, i o all o de s
π∈Π(N)wi h n≥1, and o e e y n-pe son TU game (N, )∈Gn, he e exis s a py amidal
sha ing scheme S( ) = {(sπ
j( ),(aπ
ij ( ))i∈Pπ(j))j∈N|π∈Π(N)}such ha
sπ
j( ) + ∑
i∈Pπ(j)
aπ
ij ( ) = mπ
j( ),∀j∈N. (1)
and e i ying:
Pi( ) = ∑
π∈Π(N)
1
n!pπ
i( ),∀i∈N, (2)
whe e pπ
i( ) = sπ
i( )i π(i) = n, and
pπ
i( ) = sπ
i( ) + ∑
j∈Sπ(i)
aπ
ij ( ), o all i∈Nwi h π(i)<n. (3)
2In he sequel, o con enience, we will w i e single on {i}jus as i.
3
No e ha nega i e sala ies o sha es a e allowed in he p e ious de ini ion. As usual, nega i e
quan i ies mus be in e p e ed as cos s, penal ies o in es men s in a b oad sense. No e also
ha condi ion (1) assu es ha e e y alue gene a ed by means o a py amidal sha ing scheme
is e icien . Howe e , since we do no impose any o he condi ion o e he sha ing scheme, i
could be he case ha he sha es o he incumben s, i.e., he di idends3, depend on he u u e,
o ha he sala ies a e non a ional. Thus, De ini ion 1 may be oo gene al. We will p o ide
some condi ions o e a py amidal sha ing scheme in o de o es ic ou sel es o deal wi h non-
an icipa i e sha ing schemes which in addi ion espec common sense bounds in o de o a oid
sala ies oo low and oo high.
De ini ion 2. Le Sbe a py amidal sha ing scheme. Then, Swill be a P- a ional sha ing scheme
i i sa is ies he ollowing p ope ies. Le (N, )∈Gnbe any n-pe son game:
(i)Sala ies Ra ionali y. I (N, )is supe addi i e, hen (i)≤sπ
i( )≤mπ
i( ), o all o de s
π∈Π(N).
(ii)Di idends Ra ionali y (Non an icipa i e sha es). I π,π0∈Π(N)a e wo o de s which coincide
up o momen k∈ {2, . . . , n}(i.e., π−1(`) = π0−1(`), o all `=1, 2, . . . , k), hen aπ
ij ( ) =
aπ0
ij ( ), o all j∈Nwi h 1 <π(j) = π0(j)≤k, and o all i∈Pπ(j) = Pπ0(j).
Ob iously, he p ope ies o he sha ing scheme de e mine he py amidal alue p ope ies, so
le us o malize some o he in e es ing p ope ies o a py amidal sha ing scheme. We will ans-
la e o he py amidal sha ing scheme he usual p ope ies o addi i i y, dummy and symme y,
and besides hem we will also ansla e he usual mono onici y condi ions in o de o p o ide
app op ia e incen i es o he agen s.
De ini ion 3. Le (N, )∈Gnbe any n-pe son TU game, and le S( ) = {(sπ
j( ),(aπ
ij ( ))i∈Pπ(j))j∈N|π∈
Π(N)}be a py amidal sha ing scheme. Then, S e i ies,
(i)Cons an Sala y. I o all j∈N he e exis s a eal cons an kj( )∈Rsuch ha sπ
j( ) = kj( ),
o all π∈Π(N).
(ii)P-Addi i i y. I o all o de s π∈Π(N), and o all j∈Ni holds:
•sπ
j( +w) = sπ
j( ) + sπ
j(w), and
•aπ
ij ( +w) = aπ
ij ( ) + aπ
ij (w), o each i∈Pπ(j),
o all (N, ),(N,w)∈Gn, whe e +wis gi en by ( +w)(S) = (S) + w(S), o all S⊆N.
(iii)P-Dummy playe . I
•sπ
i( ) = (i), and
•aπ
ij ( ) = 0, o e e y j∈Sπ(i), and all o de s π∈Π(N),
o all i∈Nbeing a dummy playe (i.e., (S∪i) = (S) + (i) o e e y coali ion S).
3No e ha hese di idends a e no he same as he well-known Ha sanyi di idends, which a e associa ed o coali ions,
no only o agen s.
4
(i )P-Symme y. I , o all symme ic playe s i,j∈N(i.e., (S∪i) = (S∪j), o all S⊆
N {i,j}),
•sπ
i( ) = sπij
j( ), and
• o all k∈N {i,j},aπ
ik( ) = aπij
jk ( ), o all k∈Sπ(i),
whe e he o de πij is de ined as πij(k) = π(k),πij(i) = π(j)and πij(j) = π(i).
( )P-S ong mono onici y. I i sa is ies s ong mono onic sala ies and di idends, de ined as ollows.
Le i∈Nbe any playe , and le (N, ),(N,w)be wo n-pe son games o which (S∪i)−
(S)≤w(S∪i)−w(S), o all S⊆N i, and being (T∪i)− (T)<w(T∪i)−w(T) o
some T⊆N i, hen
•S ong mono onic sala ies:sπ
i( )≤sπ
i(w), o all o de s π∈Π(N)and (sπ
i( ))π∈Π(N)6=
(sπ
i(w))π∈Π(N).
•S ong mono onic di idends:aπ
ij ( )≤aπ
ij (w), o all j∈Sπ( ), o all o de s π∈Π(N),
wi h aπ0
ij ( )<aπ0
ij (w), o some o de π0
No e ha he cons an sala y p ope y implies ha he sala y is an inhe en a ibu e o each
playe , and i can be ela ed, o ins ance, o his pe sonal aining. Mo eo e , since Pπ(i) = ∅
o all o de s πsuch ha π(i) = 1, hen each playe ’s cons an sala y equals his own alue
(i).P-Addi i i y, P-dummy playe and P-symme y i ially lead o he same p ope ies o
he co esponding py amidal alue. Le us ecall hose well-known p ope ies o alues o TU
games, as well as o he p ope ies which we will use la e . Fo mally, a alue ϕ:Gn→Rn:
(i)is e icien i ∑i∈Nϕi( ) = (N), o all (N, )∈Gn;
(ii)is addi i e i ϕ( +w) = ϕ( ) + ϕ(w), o all (N, ),(N,w)∈Gn;
(iii)is ela i e in a ian wi h espec o s a egic equi alence i ϕ(N,w) = aϕ(N, ) + b, o e e y
(N, )∈Gn,a>0 and b∈Rn, whe e wis gi en by w(S) = a (S) + ∑i∈Sbi, o all S⊆N;
(i )is symme ic i ϕi( ) = ϕj( ), o all (N, )∈Gn, and o all symme ic playe s i,j∈N;
( )p ese es desi abili y [11] i ϕi( )≤ϕj( ), o all playe s i,j∈Nsuch ha (S∪i)≤ (S∪j),
o all S⊆N {i,j}, o all (N,n)∈Gn;
( i)is s ong mono onic [18] i ϕi( )≤ϕi(w), o e e y playe i∈N, and o all games (N, ),(N,w)∈
Gn o which (S∪i)− (S)≤w(S∪i)−w(S), o all S⊆N i;
( ii)is coali ionally mono onic [18] i o e e y coali ion T⊆Nand e e y wo games (N, ),(N,w)∈
Gnsuch ha (T)>w(T)and (S) = w(S), o all S6=T, i ollows ϕi( )≥ϕi(w), o
e e y playe i∈T;
( iii) e i ies posi i i y [9] i ϕi( )≥0, o all i∈N, whene e he game (N, )is mono onic (i.e.,
(T)≥ (S), o each Tand Ssuch ha T⊇S);
(ix) e i ies he dummy p ope y i ϕi( ) = (i), o all (N, )∈Gn, and o e e y dummy playe
i∈N;
5

(x) e i ies he null playe p ope y i ϕi( ) = 0, o all (N, )∈Gn, and o e e y null playe
i∈N(i.e., (S∪i) = (S), o all S⊆N i);
(xi) e i ies he null playe ou p ope y [4] i ϕj(N, ) = ϕj(N i, |N i), o all j6=i∈N, o all
(N, )∈Gnsuch ha iis a null playe in . He e, (N i, |N i)is he es ic ed game gi en
by |N i(S) = (S), o all S⊆N i;
(xii)is s anda d o wo-pe son games i ϕi( ) = (i) + 1
2 ({i,j})− (i)− (j), o all i6=j, o
e e y wo-pe son game ({i,j}, )∈G2.
P oposi ion 1. Any addi i e and e icien alue ϕcan be ob ained as a P-addi i e py amidal alue. Mo e-
o e , i ϕ e i ies he null playe ou p ope y, hen he co esponding py amidal sha ing scheme Sϕ e i ies
di idends a ionali y.
P oo . Le ϕbe any addi i e and e icien alue. Le us i s ecall he unanimi y basis o Gn,
{(N,uT)}T⊆N, wi h T6=∅, whe e
uT(S) = 


1, i T⊆S,
0, o he wise.
We will show ha he alue o any mul iple o a unanimi y game ϕ(kuT),k∈R, can be ob ained
by means o a py amidal sha ing p ocedu e. Le π∈Π(N)be any gi en o de . Le us conside
he ollowing edis ibu ion, whe e π∈Tis he las membe o Tacco ding o he o de π.
•Fo e e y playe j∈Pπ( π), his sala y is sπ
j(kuT) = 0, and he dis ibu es aπ
ij (kuT) = 0
among his p edecesso s i∈Pπ(j).
•When he las membe o Ta i es, he dis ibu es kas ollows:
sπ
π(kuT) = ϕ π(kuT) + ∑
j∈Sπ( π)
ϕj(kuT), (4)
aπ
i π(kuT) = ϕi(kuT), o all i∈Pπ( π). (5)
•Fo all j∈Sπ( π), his sala y is sπ
j(kuT) = ϕj(kuT), which is paid by π. Tha is, aπ
ij (kuT) = 0,
o all i∈Pπ(j) { π}, and aπ
πj(kuT) = −ϕj(kuT).4
Clea ly, he p oposed sha ing scheme gi es ϕ(kuT). Now, le (N, )∈Gnbe a gi en TU game.
Then i can be exp essed as (see Shapley [15]) =∑T⊆N
T6=∅
∆(T)uT, whe e ∆(T)is he Ha sanyi
di idend o Tin (N, ), gi en by ∆(T) = ∑S⊆T
S6=∅
(−1) −s (S),sand being he ca dinali ies o Sand
4Those nega i e sha es can be in e p e ed as in es men s on human capi al.
6
T, espec i ely. Thus, he P-addi i e sha ing scheme Sde ined by
sπ
j( ) = ∑
T⊆N
sπ
j(∆(T)uT),
aπ
ij ( ) = ∑
T⊆N
aπ
ij (∆(T)uT), o all i∈Pπ(j),
o all j∈N, and o all π∈Π(N), eco e s ϕ( ). No e ha S e i ies condi ion (1). Now, we
will check ha i ϕ e i ies he null playe ou p ope y, hen he py amidal sha ing scheme is
di idends a ional:
•Fo e e y playe j∈Pπ( π),sπ
j(∆(T)uT) = 0, and aπ
ij (∆(T)uT) = 0 o all i∈Pπ(j), which
clea ly do no depend on Sπ(j).
•Fo all j∈Sπ( π), no e ha j/∈Tand he e o e i is a null playe in he game (N,∆(T)uT).
Then, since ϕ e i ies he null playe ou p ope y and i is e icien , i also e i ies he null
playe p ope y, and he e o e sπ
j(∆(T)uT) = ϕj(∆(T)uT) = 0, which is paid by π. Thus,
sπ
j(∆(T)uT) = 0 and aπ
ij (∆(T)uT) = 0 o all i∈Pπ(j), which clea ly do no depend on
Sπ(j).
•Fo he las incoming membe o T, and aking in o accoun ha ϕ e i ies null playe ou
and null playe p ope ies, i ollows:
sπ
π(N,∆(T)uT) = ϕ π(N,∆(T)uT) + ∑
Sπ( π)
ϕj(N,∆(T)uT) = ϕ π(T,∆(T)uT) + 0, (6)
aπ
i π(N,∆(T)uT) = ϕi(N,∆(T)uT) = ϕi(T,∆(T)uT), o all i∈Pπ( π), (7)
which depend only on T⊆Pπ( π)
The e o e, he py amidal sha ing scheme is di idends a ional.
I is also ema kable ha wo di e en py amidal sha ing schemes S1and S2may lead o he
same alue; a om being a d awback, his ac is an ad an age. Ha ing wo di e en imple-
men a ions o he same alue enla ges he oppo uni ies o apply i as an e ec i e solu ion o
a gi en game in a speci ic si ua ion. Le us hink abou he ex eme py amidal sha ing scheme
which de e mines he Shapley alue, in which he en an playe ecei es he whole bene i s, and
no di idends a e dis ibu ed. Such ex eme sha es immedia ely lead us o poin ou wo ques-
ions: Why he incumben s a e going o accep he deal? Why he en an is going o s ay in he
coali ion a e ecei ing all his con ibu ion? We can a oid hose ques ions by ob aining he Shap-
ley alue also as a non-ex eme py amidal alue. Fo ins ance, P oposi ion 1 p o ides us wi h
an al e na i e and non-ex eme py amidal sha ing scheme o ob aining he Shapley alue as a
py amidal one. Le (N,uT)be he unanimi y game wi h espec o coali ion T⊆N, and le us
conside he ollowing py amidal sha es:
(i)En an j’s sala y: sπ
j(∆(T)uT) = ∆(T)
, i j= π∈Tis he las membe o Tacco ding o he
o de π; and sπ
j(∆(T)uT) = 0, o he wise;
7
(ii)Incumben s Pπ(j)’s sha es: aπ
ij (∆(T)uT) = ∆(T)
, i j= π∈Tis he las membe o T
acco ding o he o de πand i∈Pπ(j)∩T; and being aπ
ij (∆(T)uT) = 0 o he wise,
o all j∈N, and o all o de s π∈Π(N). The inal payo ha playe i∈N ecei es acco ding o
he o de π∈Π(N)is hen gi en by ∆(T)
i i∈T, and 0 i i/∈T. Thus, acco ding o P oposi ion 1
he addi i e py amidal alue we ob ain is gi en by ∑T⊆N
i∈T
∆(T)
, o all i∈T, which is p ecisely he
exp ession o he Shapley alue in e ms o he Ha sanyi di idends o he game. The py amidal
sha ing scheme o he o iginal game (N, )is:
(i)En an j’s sala y: sπ
j( ) = ∑T⊆Pπ(j)
∆(T∪j)
+1
(ii)Incumben s Pπ(j)’s sha es: aπ
ij ( ) = ∑T⊆Pπ(j)
i∈T
∆(T∪j)
+1
Since he e a e a leas wo di e en py amidal sha ing schemes which esul in he Shapley alue,
i ollows ha he e a e a con inuum o hem wi h he same p ope y (all hei linea con ex com-
bina ions). Howe e , he ob ained py amidal sha ing scheme is no sala ies a ional in gene al.
The ques ion is whe he he Shapley alue migh be ob ained by means o a a ional non-ex eme
py amidal sha ing scheme. Unexpec edly, we gi e a posi i e answe in Sec ion 3.
Rela ion wi h p ocedu al alues
Py amidal sha ing schemes a e closely ela ed o he idea o p ocedu al alues, in oduced by
Malawski [10]. P ocedu al alues a e py amidal alues o which he ma ginal con ibu ion o
he en e ing playe is di ided among he playe s p opo ionally o a weigh sys em which does
no depend on he playe s’ names no on hei con ibu ions. To be speci ic (see Malawski [10]),
le sbe a p ocedu e on Gn, ha is, a amily o nonnega i e coe icien s ((sk,j)k
j=1)n
k=1such ha
∑k
j=1sk,j=1, o all k. Then, he p ocedu al alue ψsde e mined by he p ocedu e sis he py a-
midal alue ob ained by means o he ollowing sala ies and di idends:
•En an j’s sala y: sπ
j( ) = sπ(j),π(j)mπ
j( ),
•Incumben s Pπ(j)’s sha es: aπ
ij ( ) = sπ(j),π(i)mπ
j( ), o all i∈Pπ(j).
(8)
The class o py amidal sha ing schemes is ob iously la ge han he class o p ocedu al sha ing
schemes. Fo ins ance, he py amidal sha ing scheme desc ibed abo e o de i e he Shapley alue
is no p ocedu al. La e , in Sec ions 3 and 4, we will show ha also he class o py amidal alues
is la ge han he class o p ocedu al alues. To be speci ic, he class o py amidal alues con ains
linea alues which a e no p ocedu al, such as he consensus amily o alues (Ju e al. [8]), and
also he e exis non-linea py amidal alues ha canno be ob ained h ough a p ocedu al scheme,
such as he p opo ional amily in oduced in Sec ion 4. In ac , when es ic ing o he sub-class
o p ocedu al alues Malawski p o es in [10] ha e iciency, linea i y, symme y, posi i i y and
coali ional mono onici y cha ac e ize he class o p ocedu al alues. In ou con ex , his can be
ead as a s onge e sion o ou P oposi ion 1. He also es ablishes ha symme y and coali ional
mono onici y can be eplaced by desi abili y p ese a ion.
8
3 Rela ion wi h o he alues
In his sec ion, we ob ain some known amilies o alues by means o py amidal sha ing schemes.
Such cons uc ions show some in e es ing ea u es o he analyzed alues. We i s p o e ha
he Shapley alue can also be ob ained as a non-ex eme py amidal alue in which he en an
playe ecei es only his own alue as sala y whe eas he emaining bene i is dis ibu ed among
he incumben playe s. As a consequence, we es ablish a new o mula ion o he Shapley alue
which es s on he second-o de di e ence ope a o used in Segal [14], which is in u n closely
ela ed o he no ions o inc easing di e ences and supe modula i y (see Ichiisi [6]) and has a
meaning ul economic in e p e a ion. Then, we de i e he amily o consensus alues (Ju, Bo m and
Ruys [8]), and also he amily o egali a ian Shapley alues (Joos en [7], an den B ink, Funaki and
Ju [16], Casajus and Hue ne [2]), as py amidal alues. Bo h amilies a ise ollowing a egali a ian
app oach o de e mine he igh o ge pa o he bene i s de i ed om subsequen inco po a ions
o he jus o med coali ion, and a ma ginalis ic one when de e mining en an ’s sala y.
Fo he in e es ed eade , and o he sake o comple eness, we collec he o mal de ini ions
o all he known alues we will analyze in his Sec ion in a inal Appendix. We also eco e he
cha ac e iza ions esul s we use.
The Shapley alue as a a ional non-ex eme py amidal alue
Fo a gi en o de π∈Π(N), and playe s i,j∈Nsuch ha π(i)≤π(j), le us de ine he ma ginal
con ibu ion o playe j wi h espec o playe i, acco ding o o de π, o be
mπ
ij ( ) = ({k∈N|π(i)≤π(k)≤π(j)})− ({k∈N|π(i)≤π(k)<π(j)}).
No e ha mπ
ij ( )can be in e p e ed as he ma ginal con ibu ion o agen j o he g oup leaded by
agen iacco ding o o de π. I we deno e he coali ion o all playe s who ha e a i ed be ween
playe s iand jby Sπ(i,j) = {k∈N|π(i)<k<π(j)}, hen mπ
ij ( ) = (Sπ(i,j)∪ {i,j})−
(Sπ(i,j)∪i), i i6=j, and mπ
jj ( ) = (j).
Now, we de ine in P oposi ion 2 a a ional non-ex eme py amidal p ocedu e which is based
on hese ma ginal con ibu ions and which u ns ou o gi e he Shapley alue as a inal payo .
In his py amidal sha ing scheme, playe i∈Pπ(j) ecei es he ma ginal con ibu ion o playe j
wi h espec o i, acco ding o o de π, a he cos o paying o his di ec successo he ma ginal
con ibu ion o playe jwi h espec o his di ec successo .
P oposi ion 2. The Shapley alue can be ob ained h ough he py amidal sha ing scheme S ha dis-
ibu es he ma ginal con ibu ion o playe j ∈N among he agen s in Pπ(j)∪j as ollows:
(i)En an j’s sala y: sπ
j( ) = (j)
(ii)Incumben s Pπ(j)’s sha es: aπ
ij ( ) = mπ
ij ( )−mπ
dsπ(i),j( ),
o e e y o de π∈Π(N), e e y playe i ∈N, and e e y n-pe son TU game (N, ).
9
In pa icula , he py amidal de ini ion o α-consensus alues o e s an al e na i e cons uc-
i e app oach o he s anda dized emainde ec o s ha de e mine he α-consensus alues, which
p o ides solid g ound o i in e ms o he dynamics o economic ac i i y.
4α-P opo ional py amidal alues o mono onic games
In he α-egali a ian Shapley and consensus amilies, he emaining su plus, which ep esen s he
alue ha en an j’s pa icipa ion adds o he incumben s, is sha ed equally among all he in-
cumben s. In his sec ion we conside a non-egali a ian amewo k, in which a playe ’s igh o
ge pa o he o hcoming bene i s is de e mined acco ding o his ini ial in es men . We measu e
his ini ial in es men as he alue his inco po a ion ha e added o he incumben s, o in o he
wo ds, by means o his ma ginal con ibu ion, and de ine he amily o α-p opo ional py amidal
alues. Tha is, we also adop a ma ginalis ic app oach o de e mine he di idends.
Taking in o accoun ha a p opo ional alloca ion wi h espec o a gi en weigh sys em in
which some o he weigh s can be s ic ly nega i e mus be ca e ully used, we es ic he de ini-
ion o α-p opo ional py amidal alues o he subclass o mono onic TU games (i.e., (S)≤ (T),
o all S⊆T). In ha case, all ma ginal con ibu ions mπ
j( ),j∈N,π∈Π(N)a e nonnega i e.
De ini ion 5. Fo e e y mono onic TU game (N, )∈Gn, and e e y α∈[0, 1], he α-p opo ional
py amidal alue is he alue ob ained by means o he ollowing py amidal sha ing scheme:
(i)En an j’s sala y:
sπ,α
j( ) = 


mπ
j( ), i (Pπ(j)) = 0,
(j) + α(mπ
j( )− (j)), o he wise.
(ii)Incumben s Pπ(j)’s sha es:
aπ,α
ij ( ) = 


0, i (Pπ(j)) = 0,
(1−α)mπ
i( )
(Pπ(j)) (mπ
j( )− (j)), o he wise.
o all j∈N, and o all o de s π∈Π(N). Thus, he inal payo ha playe i∈N ecei es
acco ding o he o de π∈Π(N)is gi en by:
ppπ,α
i( ) = (i) + α(mπ
i( )− (i)) + (1−α)∑
j∈Sπ(i)
(Pπ(j))6=0
mπ
i( )
(Pπ(j))(mπ
j( )− (j)), (16)
i (Pπ(i)) 6=0, and
ppπ,α
i( ) = mπ
i( ) + (1−α)∑
j∈Sπ(i)
(Pπ(j))6=0
mπ
i( )
(Pπ(j))(mπ
j( )− (j)), (17)
16

i (Pπ(i)) = 0, o all i=1, . . . , n. The e o e, he α-p opo ional py amidal alue, which is he
expec ed alue unde he o me sha ing scheme when all o de s a e equally likely, is gi en by
PPα
i( ) = 1
n!∑
π∈Π(N)
(Pπ(i))6=0
 (i) + α(mπ
i( )− (i))+∑
π∈Π(N)
(Pπ(i))=0
mπ
i( )+
1−α
n!∑
π∈Π(N)
∑
j∈Sπ(i)
(Pπ(j))6=0
mπ
i( )
(Pπ(j))(mπ
j( )− (j)),i=1, . . . , n. (18)
P oposi ion 6. Fo e e y mono onic TU game (N, )∈Gn, and e e y α∈[0, 1], i holds
PPα( ) = αφ( ) + (1−α)PP0( ).
P oo . T i ially, i we exp ess (i)and mπ
i( )as α (i)+(1−α) (i)and αmπ
i( )+(1−α)mπ
i( )
in he i s summand o (18), i ollows ha e e y α-p opo ional py amidal alue is he linea
con ex combina ion o he wo ex eme alues o α=0 and α=1. Mo eo e , since he 1-
p opo ional py amidal alue is in ac he Shapley alue, hen he esul holds.
When we es ic ou sel es o he class o mono onic simple games, he whole amily educes
o he Shapley alue.
P oposi ion 7. Le (N,u)∈Gnbe a mono onic simple game such ha u(i) = 0 o e e y non e o playe
i∈N. Then PPα(u) = φ(u), o all α∈[0, 1].
P oo . Le (N,u)∈Gnbe a mono onic simple game, and le be π∈Π(N)be a gi en o de . Then,
he e exis s a unique iπ∈Nwi h nonze o ma ginal con ibu ion. Mo eo e :
•Since u(Pπ(j)) = 0 o all j∈Pπ(iπ), hen sπ,α
j(u) = mπ
j(u) = 0 and aπ,α
ij (u) = 0, o all
i∈Pπ(j),
•sπ,α
iπ(u) = mπ
iπ(u) = 1, aπ,α
iiπ(u) = 0, o all i∈Pπ(iπ),
•I j∈Sπ(iπ), hen jis a non e o playe . The e o e, sπ,α
j=u(j) + α(mπ
j(u)−u(j)) = 0 and
aπ,α
ij = (1−α)mπ
i(u)(mπ
j(u)−u(j)) = 0, o all i∈Pπ(j).
Le us analyze, by means o an example, he beha io o he ex eme ze o-p opo ional alue
and he α’s choice e ec o e he inal alloca ion o bene i s.
Example 3. Le us conside he ollowing 4-pe son game (N, ), wi h (1) = 1, (2) = (3) =
(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
(S)2 2 4 1 1 2 6 7 5 8 10
17
In his example, playe ’s 1 and 2 ma ginal con ibu ions lead o he same Shapley alue
φ1( ) = φ2( ) = 27
12 . The ma ginal con ibu ions o playe 4 a e always g ea e o equal han
hose o playe 2, and playe 3 is in he weakes posi ion:
φ( ) = (27
12, 2 7
12, 2 1
12, 23
4)
On he con a y, he oles o playe s 1 and 2 a e dis inguished by means o he p opo ional py a-
midal alues o all α∈[0, 1), which a e gi en by:
PPα( ) = α(2.5833, 2.5833, 2.0833, 2.75) + (1−α)(4.4266, 1.8060, 1.7622, 2.0052)
No e ha p opo ional alues ewa d a playe o his con ibu ion o he es ablishmen o he i m
as well as o his con ibu ion o he i m’s g ow h; mo eo e , he ma ginal con ibu ions o playe
1 a e g ea e o small size’s coali ions han hose o playe s 2, 3 and 4, which on he con a y a e
g ea e han he ma ginal con ibu ions o playe 1 o big size’s coali ions. Thus, since pa ame e
αcon ols o wha ex en a playe mus be compensa ed acco ding o his pa icipa ion a he
beginning o he p ojec a he han o his con ibu ion o i s e olu ion, he ewa ds ha playe 1
ecei e inc ease as αdec eases o ze o. The ela i e posi ion among he es o he playe s emains.
We end up by b ie ly discussing which p ope ies o he lis in Sec ion 2 hold o no o he
α-p opo ional py amidal alues, being ou a gumen s hea ily based on he p e ious desc ip-
ion o hese alues as a linea combina ion o he Shapley alue and he alue PP0( ). To be
speci ic, e e y p opo ional alue e i ies e iciency, symme y, posi i i y (when es ic ed o he
class o suppe addi i e games), s anda dness o wo pe son-games, null playe and null playe
ou . On he con a y, addi i i y, ela i e in a iance wi h espec o s a egic equi alence, s ong
mono onici y, and dummy p ope ies a e no (always) sa is ied by hese alues. No e also ha
α-p opo ional py amidal alues a e no p ocedu al in gene al.
5 Conclusions and u u e esea ch
In his pape we p opose a gene al p ocedu e o ob aining a b oad class o solu ion concep s
based on a py amidal dis ibu ion o he bene i s ha a e sequen ially ob ained h ough a dy-
namic p ocess o coali ion o ma ion, in which playe s successi ely come in o play and join he
cu en coali ion un il he g and coali ion is o med. In pa icula , we ob ain some known alues
by means o py amidal sha ing schemes and we in oduce a p opo ional amily o py amidal
alues, in which incumben s ecei e di idends in p opo ion o hei ini ial in es men .
Axioma ic cha ac e iza ions o he p opo ional amily, and also o some sub-classes o py a-
midal alues a e le o u u e esea ch, as well as a s a egic analysis o his kind o solu ions. I
may be also in e es ing o gene alize he no ion o p opo ional py amidal alues o a weigh ed
e sion in which he incumben s’ sha es depend on a gene al sys em o weigh s.
Wi h espec o po en ial ex ensions, he py amidal sha ing o he cu en bene i s idea allows
o deal wi h hose si ua ions in which he numbe o inal pa icipan s whe e no known in ad-
18
ance. Mo eo e , i should be in e es ing o in oduce he no ion o py amidal sha ing scheme in
he con ex o games wi h a communica ion g aph [12] and [1].
Finally, i mus be poin ed ou ha he complexi y o he calculus o a py amidal alue elies
c ucially on he calculus o he py amidal sha ing scheme and, ob iously, on he complexi y o
he cha ac e is ic unc ion o he game. In he case o he wo p oposed amilies, i he ma ginal
con ibu ions can be compu ed (o a leas app oxima ed) in polynomial ime, hen any py amidal
alue can also be es ima ed in polynomial ime. In ac , ollowing Cas o, Gomez and Tejada
[3], any alue ha can be exp essed as an expec a ion o a polynomial unc ion o he ma ginal
con ibu ion ec o s o e all pe mu a ions, when all o de ings a e equally likely, can be es ima ed
in polynomial ime, whene e he ma ginal con ibu ions a e compu able in polinomial ime.
Appendix
In his appendix we collec he o mal de ini ions o all he known alues analyzed in Sec ion 3,
as well as he cha ac e iza ion esul s we ha e used.
Theo em 1 (Shapley, 1953).The e exis s a unique alue sa is ying he e iciency, symme y, dummy, and
addi i i y axioms. I is he Shapley alue, which is de ined o e e y (N, )∈Gnas ollows:
φi(N, ) = ∑
S⊆N
i/∈S
s!(n−s−1)!
n! (S∪ {i})− (S),i=1, . . . , n, (19)
whe e s =|S|deno es he ca dinali y o coali ion S ⊆N.
The Consensus alue (Ju e al. [8]) is aimed o gene alize he s anda d solu ion o 2-pe son TU
games in o n-pe son cases. I is based on a wo-sided nego ia ion p ocess ha can be unde s ood
as a s anda dized emainde ule desc ibed by he ollowing ec o s. The eade is e e ed o Ju e
al. [8] o a de ailed exposi ion o his ule.
De ini ion 6 (Ju, Bo m and Ruys, 2007).Le (N, )∈Gn, and π∈Π(N)be a gi en pe mu a ion.
De ine Sπ
k={π−1(1), . . . , π−1(k)} ⊆ Nand Sπ
0=∅. Then, he s anda dized emainde o
coali ion Sπ
k, (Sπ
k), is ecu si ely de ined as ollows:
(Sπ
k) = 


(N), i k=n,
(Sπ
k) + 1
2 (Sπ
k+1)− (Sπ
k)− ({π−1(k+1)}), i k∈ {1, . . . , n−1}.
(Sπ
k)is he alue le o Sπ
ka e alloca ing su pluses o ea lie lea e s N Sπ
k. Then, he s an-
da dized emainde ec o , s π( ), which co esponds o he si ua ion whe e he playe s lea e
he game one by one in he o de (π−1(n), . . . , π−1(1)), is de ined ecu si ely by:
s π−1(k)=


({π−1(k)}) + 1
2 (Sπ
k)− (Sπ
k−1)− ({π−1(k)}), i k∈ {2, . . . , n},
(Sπ
1), i k=1.
19
De ini ion 7 (Ju, Bo m and Ruys, 2007).Fo e e y (N, )∈Gn, he consensus alue Ψ( )is de ined
as he a e age, o e he se o all pe mu a ion Π(N), o he indi idual s anda dized emainde
ec o s, i.e.,
Ψ( ) = 1
n!∑
π∈Π(N)
s π( ).
De ini ion 8 (Ju, Bo m and Ruys, 2007).Fo e e y (N, )∈Gnand α∈[0, 1], he α-consensus
alue Ψα( )is de ined as he a e age, o e he se o all pe mu a ion Π(N), o he indi idual
α- emainde ec o s, i.e.,
Ψα( ) = 1
n!∑
π∈Π(N)
(s π)α( ).
He e, he α- emainde α(Sπ
k)and he indi idual α- emainde ec o (s π)α( )a e de ined as
ollows:
α(Sπ
k) = 


(N), i k=n,
(Sπ
k) + (1−α) α(Sπ
k+1)− (Sπ
k)− ({π−1(k+1)}), i k∈ {1, . . . , n−1}.
and
(s π−1(k))α=


({π−1(k)}) + α α(Sπ
k)− (Sπ
k−1)− ({π−1(k)}), i k∈ {2, . . . , n},
α(Sπ
1), i k=1.
The au ho s in oduce he ollowing p ope y in o de o cha ac e ize he amily o consensus
alues. The nex heo em co esponds o Theo em 5 in Ju, Bo m and Ruys [8]. We make use o
(a)cha ac e iza ion.
De ini ion 9 (Ju, Bo m and Ruys, 2007).A alue ϕ:Gn→Rn e i ies he α-dummy p ope y i
ϕi( ) = α (i)+(1−α) (i) + (N)−∑j∈N (j)
n, o all (N, )∈Gn, and e e y dummy playe
i∈Nwi h espec o .
Theo em 2 (Ju, Bo m and Ruys, 2007).(a) The α-consensus alue Ψαis he unique one-poin solu ion
concep on Gn ha sa is ies e iciency, symme y, he α-dummy p ope y and addi i i y.
(b) The α-consensus alue Ψαis he unique unc ion ha sa is ies e iciency, symme y, he α-dummy
p ope y and he ans e p ope y o e he class o TU games.
(c) Fo any ∈Gn, i holds ha
Ψα( ) = ααφ( ) + (1−α)E( ),
whe e E( )is he equal su plus solu ion o , i.e., Ei( ) = (i) + (N)−∑j∈N (j)
n.
(d) The α-consensus alue Ψαis he unique unc ion ha sa is ies e iciency and he α-equal wel a e
loss p ope y o e he class o TU games.
20
The Egali a ian Shapley alues (Joos en [7]) make he ade-o be ween ma ginalism and egal-
i a ianism by means o con ex combina ions o he Shapley alue and he equal di ision solu ion.
De ini ion 10 (Joos en, 1996).Fo e e y (N, )∈Gnand α∈[0, 1], he α-egali a ian Shapley
alue ϕα( )is gi en by
ϕα( ) = αφ( ) + (1−α)ED( ),
whe e ED( )is he equal di ision alue which dis ibu es he wo h (N)equally among all
playe s: ED( ) = ( (N)
n, . . . , (N)
n).
Re e ences
[1] B´
eal S, R´
emila E, Solal P (2012) Compensa ions in he Shapley alue and he compensa ion
solu ions o g aph games. In e na ional Jou nal o Game Theo y 41, 157-178.
[2] Casajus A, Hue ne F (2013) Null playe s, solida i y, and he egali a ian Shapley alues.
Jou nal o Ma hema ical Economics 49, 58-61.
[3] Cas o J, Gomez D, Tejada J (2009) Polynomial calcula ion o he Shapley alue based on
sampling. Compu e s and Ope a ions Resea ch 36, 1726-1730.
[4] De ks JJM, Halle HH (1999) Null playe s ou ? Linea alues o games wi h a iable sup-
po s. In e na ional Game Theo y Re iew 1, 301-314.
[5] G abisch M, Roubens M (1999) An axioma ic app oach o he concep o in e ac ion among
playe s in coope a i e games. In e na ional Jou nal o Game Theo y 28, 547-565.
[6] Ichiisi T (1981) Supe -modula i y: applica ions o con ex games and o he g eedy algo i hm
o LP. Jou nal o Economic Theo y 25, 283-286.
[7] Joos en R (1996) Dynamics, equilib ia and alues. Disse a ion, Maas ich Uni e si y.
[8] Ju Y, Bo m P, Ruys P (2007) The consensus alue: a new solu ion concep o coope a i e
games. Social Choice and Wel a e 28, 685-703.
[9] Kalai E, Same D (1987) On weigh ed Shapley alues. In e na ional Jou nal o Game Theo y 16,
205-222.
[10] Malawski M (2013) ”P ocedu al” alues o coope a i e games. In e na ional Jou nal o Game
Theo y 42, 305-324.
[11] Maschle M, Peleg B (1966) A cha ac e iza ion, exis ence p oo and dimension bounds o
he ke nel o a game. Paci ic Jou nal o Ma hema ics 18, 289-328.
[12] Mye son RB (1977) G aphs and coope a ion in games. Ma hema ics o Ope a ions Resea ch 2,
225-229.
[13] Owen G (1972) Mul ilinea ex ensions o games. Managemen Sciences 18, 64-79.
21

[14] Segal I (2003) Collusion, exclusion and inclusion in andom-o de ba gaining. Re iew o Eco-
nomic S udies 70, 439-460.
[15] Shapley LS (1953) A alue o n-pe son games. Con ibu ions o he Theo y o Games II, 307-317.
[16] an den B ink R, Funaki Y, Ju Y (2013) Reconciling ma ginalism wi h egali a ianism: con-
sis ency, mono onici y, and implemen a ion o egali a ian Shapley alues. Social Choice and
Wel a e 40, 693-714.
[17] Webe RJ (1988) P obabilis ic alues o games. In A. Ro h (Ed.), The Shapley alue: Essays in
hono o Lloyd S. Shapley. Camb idge Uni e si y P ess, 101-119.
[18] Young HP (1985) Mono onic solu ions o coope a i e games. In e na ional Jou nal o Game
Theo y 14, 65-72.
22