Essays on competition and cooperation in game theoretical models

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
Depa amen o de Es a ís ica e In es igación Ope a i a
ESSAYS ON COMPETITION AND COOPERATION
IN GAME THEORETICAL MODELS
Julio González Díaz
San iago de Compos ela, Ap il 2005
Suppo ed by he Minis e io de Educación y Ciencia and FEDER, unde p ojec s BEC2001-0535 and BEC2002-
04102-C02-02
UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
Depa amen o de Es a ís ica e In es igación Ope a i a
Essays on Compe i ion and Coope a ion in Game
Theo e ical Models
PhD candida e
Julio González Díaz
Ad iso s:
Ignacio Ga cía Ju ado Es ela Sánchez Rod íguez
San iago de Compos ela, Ap il 22, 2005
A mi amilia, po hace lo odo más ácil...
Un pelda˜no m´as

P e ace
This hesis is he esul o my i s ou yea s as a esea che in game heo y. None heless, my
de o ion o games, specially he ze o-sum ones, is much olde han ha . I would say ha i
eally began when I i s saw my eldes b o he playing chess wi h my a he ; by ha ime I was
six yea s old. Bo h o hem passed me he lo e o his game, which I s ill p ac ice. Apa om
chess, I ha e also was ed pa o my leisu e ime o e he las ew yea s playing compu e games,
ca ds, and many o he boa d and able games wi h my amily and iends. I was no be o e
he i h yea o my unde g adua e s udies in Ma hema ics ha I ealized ha he scope o he
heo y o games goes a beyond simple (and no so simple) di e sions.
My i s o mal app oach o game heo y was du ing a cou se augh by Ignacio Ga cía Ju ado.
A e Ignacio’s cou se, games we e no jus a hobby anymo e. Hence, a e inishing he deg ee, I
joined he PhD p og am o he Depa men o S a is ics and Ope a ions Resea ch wi h he idea
o w i ing my hesis in game heo y. Soon a e ha , Ignacio became my ad iso . He is he one
who has helped me mos du ing hese ou yea s, no only because o his academic guidance, bu
also o being he main esponsible o he ui ul yea s I ha e spen as a game heo is so a .
Many hanks, Ignacio, o he ime you ha e spen on me.
Many hanks, oo, o my o he ad iso , Es ela, o all he ime she has de o ed o his hesis;
mainly h ough he co-au ho ship in Chap e s 5, 6, and 7. Thanks o all he discussions, so
cen al o he co e o his hesis.
Join esea ch wi h di e en people has helped me o deepen in o game heo y and o un-
de s and many o he aspec s o a esea che ’s li e. Hence, I am g a e ul o all my co-au ho s:
Ignacio, Es ela, Pe e , Henk, Ruud, Ma ieke, and An onio. Besides, special hanks o my ad-
anced ma hema ics consul an s: Roi and Ca li os o hei help ul discussions ha con ibu ed
o mos o he Chap e s o his hesis, mainly h ough Chap e s 5 and 6.
I ha e also had he possibili y o isi ing some p es igious uni e si ies du ing hese yea s.
These s ays ha e subs an ially in luenced my o ma ion no only as a esea che , bu also in
many o he aspec s o li e. Because o his, I am indeb ed o Pe e , Henk, Ruud, A an za,. . . and
all he people a Cen ER o he pleasan a mosphe e I had du ing my h ee-mon h isi o
Tilbu g Uni e si y. I am also indeb ed o Inés and Jo di o ha ing in i ed me o isi he Uni
o Economic Analysis o he Uni e si a Au ònoma de Ba celona, and o he o he membe s o
he Depa men o hei ecep ion; I am specially g a e ul o he PhD s uden s a IDEA o hei
iii
i P e ace
wa m welcome, whe e Se gio and Joan dese e a special men ion. Finally, I am deeply indeb ed
o William o in i ing me o isi he Depa men o Economics o Roches e Uni e si y. My
g a i ude o all he membe s o he Depa men , o he PhD s uden s, o Diego, Paula, Rica do,
Caga ay, and many o he s.
Mo eo e , William’s in luence on his hesis goes u he han jus he in i a ion o isi
Roches e Uni e si y. He has augh o me some o he sec e s o co ec (scien i ic) w i ing, and
I ha e ied o ollow his c edo h oughou his hesis. Un o una ely, i was al eady oo la e o
implemen his p inciples in some o he chap e s o his hesis (in he o he s jus blame me o
my inap i ude).
I deeply app ecia e he kind suppo om he g oup o Galician game heo is s and om he
people in he Depa men o S a is ics and Ope a ions Resea ch.
I am also g a e ul o my wo o icema es, Rosa and Manuel. Because o hem I ha e de eloped
my esea ch in a e y com o able en i onmen . Also, hanks Manuel o you coun less LaTeX
ecommenda ions.
Finally, I wan o men ion all he o he PhD s uden s a he Facul y o Ma hema ics o
he enjoyable con e sa ions and discussions du ing he daily co ee b eaks. Thanks o Ma co,
Ca li os, Te e, Bea,. . . .
Las , bu no leas , I ha e o ende many hanks o my amily and o my iends. They ha e
p o ided me wi h a e y pleasan and elaxed a mosphe e du ing all hese yea s.
Julio González Díaz
Ap il 2005, San iago de Compos ela
Con en s
P e ace iii
Con en s
No a ions ii
I Noncoope a i e Game Theo y 1
In oduc ion 3
Sho Bibliog aphy ...................................... 4
1 A Silen Ba le o e a Cake 5
1.1 In oduc ion........................................ 6
1.2 TheModel ........................................ 7
1.3 TwoPlaye s........................................ 9
1.4 Mo ePlaye s ....................................... 14
1.5 ConcludingRema ks................................... 19
Bibliog aphy ......................................... 20
2 Fini ely Repea ed Games: A Gene alized Nash Folk Theo em 21
2.1 In oduc ion........................................ 22
2.2 Basic No a ion, De ini ions and an Example . . . . . . . . . . . . . . . . . . . . . . 23
2.3 TheTheo em....................................... 26
2.4 Unobse able Mixed Ac ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 ConcludingRema ks................................... 31
Bibliog aphy ......................................... 32
3 Unila e al Commi men s in Repea ed Games 33
3.1 In oduc ion........................................ 34
3.2 No a ion.......................................... 35
3.3 TheFolkTheo ems.................................... 39
3.4 ConcludingRema ks................................... 44
Bibliog aphy ......................................... 46
4 A Noncoope a i e App oach o Bank up cy P oblems 47
4.1 In oduc ion........................................ 48
4.2 The Model and he Main Resul s . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Bank upc y Games and Bank up cy Rules . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 ConcludingRema ks................................... 55
Bibliog aphy ......................................... 56
4 In oduc ion o Noncoope a i e Game Theo y
Sho Bibliog aphy
Benoî , J.-P. and V. K ishna (1987): “Nash Equilib ia o Fini ely Repea ed Games,” In e -
na ional Jou nal o Game Theo y, 16, 197–204. (Quo ed in pp. 3)
Ga cía-Ju ado, I. and J. González-Díaz (2005): “Unila e al Commi men s in Repea ed
Games,” P ep in . (Quo ed in pp. 3)
Ga cía-Ju ado, I., J. González-Díaz, and A. Villa (2004): “A Noncoope a i e App oach
o Bank up cy P oblems,” P ep in . (Quo ed in pp. 3)
Ga cía-Ju ado, I., L. Méndez-Naya, and F. Pa one (2000): “Unila e al Commi men s in
Fini ely Repea ed Games,” In e na ional Game Theo y Re iew, 2, 129–139. (Quo ed in pp. 3)
González-Díaz, J. (2003): “Fini ely Repea ed Games: A Gene alized Nash Folk Theo em,”
Tech. Rep. 03-08, Depa men o S a is ics and OR, Uni e si y o San iago de Compos ela, o
appea in Games and Economic Beha io . (Quo ed in pp. 3)
González-Díaz, J., P. Bo m, and H. No de (2004): “A Silen Ba le o e a Cake,” Tech.
ep., Cen ER discussion pape se ies. (Quo ed in pp. 3)
Hame s, H. (1993): “A Silen Duel o e a Cake,” Me hods and Models o Ope a ions Resea ch,
37, 119–127. (Quo ed in pp. 3)
Smi h, L. (1995): “Necessa y and Su icien Condi ions o he Pe ec Fini e Ho izon Folk
Theo em,” Econome ica, 63, 425–430. (Quo ed in pp. 3)

Chap e 1
A Silen Ba le o e a Cake
Con en s
1.1 In oduc ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Two Playe s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Mo e Playe s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Concluding Rema ks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Bibliog aphy ................................... 20
5
6 Chap e 1. A Silen Ba le o e a Cake
1.1 In oduc ion
The e a e many s a egic si ua ions in which some agen s ace a decision p oblem in which iming
is impo an . The li e a u e on iming games has been de o ed o analyze hese si ua ions and
p o ide heo e ical models o s udy he unde lying s a egic p oblem. A i s app oach o iming
games appea s in Ka lin (1959) in he ze o sum con ex . Mo e ecen con ibu ions a e Bas on
and Ga nae (2000) and La aki e al. (2003). A classic example o iming game is he wa o
a i ion, in oduced in Smi h (1974) and widely s udied, o ins ance, in Hend icks e al. (1988).
Mo e speci ically, conside he ollowing wa o a i ion game. Two i al i ms a e engaged in
a ace o make a pa en able disco e y, and hence, as soon as one i m makes he disco e y, all
he p e ious e o made by he o he i m u ns ou o be useless. This pa en ace model has
been widely s udied in li e a u e (see, o ins ance, Fudenbe g e al. (1983)). In his model i is
assumed ha , as soon as one o he i ms lea es he ace, he game ends. The mo i a ion o
his assump ion is ha , once he e is only one i m in he ace, he game educes o a decision
p oblem in which he emaining i m has o op imize i s esou ces. Hence, he s a egy o each
i m consis s o deciding, o each ime , whe he o lea e he ace o no . Mos o he li e a u e
in iming games models wha we call non-silen iming games, ha is, as soon as one playe
ac s, he o he s a e in o med and he game ends.1In his Chap e , on he con a y, we p o ide
a o mal model o he silen si ua ion. We use again he pa en ace o mo i a e ou app oach.
Conside a si ua ion in which wo i ms a e engaged in a pa en ace and also in an ad e ising
campaign. Suppose ha one o he wo i al i ms, say i m 1, decides o lea e he pa en ace.
Then, i will p obably be he case ha i m 1 does no wan i m 2 o ealize ha 1 is no in
he ace anymo e; and he e o e, i m 1 can ge a mo e ad an ageous posi ion o he ad e ising
campaign. Mo eo e , i i m 2 does no ealize abou he ac ha i m 1 has al eady le he
ace, i can also be he case ha , ha ing al eady i m 1 le he ace, i m 2 lea es he ace be o e
making he disco e y, bene i ing again i m 1.
Nex , we in oduce ou silen iming game. We conside he si ua ion ha nplaye s ha e o
di ide a cake o size S. A ime 0 playe ihas he ini ial igh o ecei e he amoun αi, whe e
i is assumed ha Pi∈Nαi< S. I playe iclaims his pa a ime > 0 hen he ecei es he
discoun ed pa δ αio he cake, unless he is he las claiman in which case he ecei es he
discoun ed emaining pa o he cake δ (S−Pj6=iαj). We e e o his game as a cake sha ing
game.
Hame s (1993) showed ha 2-playe cake sha ing games always admi a unique Nash equilib-
ium. In his Chap e we conside cake sha ing games ha a e sligh ly di e en om he games
in oduced in Hame s (1993). We i s p o ide an al e na i e, bu mo e di ec , exis ence and
uniqueness esul o 2-playe cake sha ing games and we gene alize his esul o cake sha ing
games wi h mo e playe s.
I is wo h o men ion he simila i ies be ween ou esul s and some well known esul s in all-
1An excep ion is Reinganum (1981), al hough he model is e y di e en om ou s.
1.2. The Model 7
pay auc ions (Webe , 1985). A i s glance, ou model seems qui e di e en om ha o all-pay
auc ions, bu i u ns ou o be he case ha hey ha e many simila i ies. Indeed, in his Chap e
we show ha he same kind o esul s ob ained o he all-pay auc ion (Hilman and Riley, 1989;
Baye e al., 1996) can be ob ained o ou iming game. Anyhow, e en when bo h he esul s and
also he a gumen s unde lying some o he p oo s a e e y simila , he wo models a e di e en
enough so ha ou esul s can no be de i ed om hose in he all-pay auc ions li e a u e.
This Chap e is o ganized as ollows. In Sec ion 1.2 we in oduce he cake sha ing games.
In Sec ions 1.3 and 1.4 we deal wi h 2-playe cake sha ing games and mo e playe cake sha ing
games, espec i ely.
1.2 The Model
In his Sec ion we o mally in oduce he cake sha ing games.
Le N={1,...,n}be a se o playe s wi h n≥2, le S > 0, le α= (α1,...,αn)∈RN
+
be such ha α1+···+αn< S, and le δ∈(0,1). Th oughou his Chap e we assume ha
0< α1< α2<···< αn. The numbe Sis called he size o he cake, he ec o α he ini ial
igh ec o and δ he discoun ac o .
The cake sha ing game wi h pu e s a egies associa ed wi h S,α, and δ, is he iple Γpu e
S,α,δ :=
(N, {Ai}i∈N,{πi}i∈N), whe e
Ai:= [0,∞)is he se o pu e s a egies o playe i∈N,
πiis he payo unc ion o playe i∈N, de ined by:
πi( 1,..., n) := 


(S−X
j6=i
αj)δ i i>max
j6=i j
αiδ io he wise.
Hence, i he e is a unique las claiman , hen he ecei es he discoun ed alue o he cake ha
emains a e ha o he playe s ha e aken hei ini ial igh s. I he e is no a unique las
claiman , hen all playe s ecei e he discoun ed alue o hei ini ial igh s. No e ha he payo
unc ions de ined abo e di e sligh ly om he payo unc ions in oduced in Hame s (1993),
whe e, in case he e is no a unique las claiman , he discoun ed alue o he emaining cake is
sha ed equally be ween he las claiman s. This change in he model does no a ec he esul s,
bu i helps o ha e cleane p oo s. 2
One easily e i ies ha Γpu e
S,α,δ has no Nash equilib ia. I he e is a unique las claiman ,
hen his playe can imp o e his payo by claiming a li le bi ea lie (and emaining he las
2Le us make some commen s conce ning he ela ion be ween he cake sha ing game (CS) and he all-pay
auc ions model (AP). Fo simplici y, we hink o he wo playe case. Se ing aside he issue o iming, no e he
ollowing di e ences: (i) Ini ial igh s: in CS hey depend on he playe (αi), in AP hey a e 0; (ii) in CS each
playe wan s o ge 1−(α1+α2), in AP he alua ion o he objec depends on he playe ; and (iii) In CS wai ing
ill ime , each playe is “paying” αi−(αi)δ ,i.e., i depends on he playe , in AP bidding , each playe is
“paying” . All he o he s a egic elemen s a e analogous in he wo models.
8 Chap e 1. A Silen Ba le o e a Cake
claiman ). I he e is no unique las claiman , hen one o he las claiman s can imp o e his
payo by claiming a li le bi la e (becoming he unique las claiman in his way). Hence, o
an app op ia e analysis o cake sha ing games we need o conside mixed s a egies.
Fo mally, a mixed s a egy is a unc ion G: [0,∞)→[0,1] sa is ying:
G(0) = 0,
Gis a nondec easing unc ion,
Gis le -con inuous,
limx→∞ G(x) = 1.
Fo a mixed s a egy Gwe can always ind a p obabili y measu e Pon [0,∞)such ha :3
o each x∈[0,∞), G(x) = P[0, x).(1.1)
On he o he hand, e e y p obabili y measu e Pon [0,∞)de ines by o mula (1.1) a mixed
s a egy G. Hence, he se o mixed s a egies coincides wi h he se o p obabili y measu es on
[0,∞).4Le Gdeno e he se o all mixed s a egies. We in oduce now some o he no a ions
ela ed o mixed s a egy G:
o each x∈[0,∞), we deno e limy↓xG(y), he p obabili y o choosing an elemen in he
closed in e al [0, x], by G(x+).
i he e is x > 0such ha o each pai a, b ∈[0,∞), wi h a < x < b, we ha e G(b)> G(a+)
(i.e., he p obabili y o choosing an elemen in (a, b)is posi i e), hen xis an elemen o
he suppo o G. I o each b > 0,G(b)>0(i.e., he p obabili y o choosing an elemen
in [0, b)is posi i e), hen 0is an elemen o he suppo o G. Le S(G)be he suppo o
he dis ibu ion unc ion G. One easily e i ies ha S(G)is a closed se .
he se o jumps (discon inui ies) o Gis J(G) := {x∈[0,∞) : G(x+)> G(x)},i.e., he
se o pu e s a egies which a e chosen wi h posi i e p obabili y.
I playe ichooses pu e s a egy and all o he playe s choose mixed s a egies {Gj}j6=i hen he
expec ed payo o playe iis
πi(G1,...,Gi−1, , Gi+1,...,Gn) = Y
j6=i
Gj( )δ (S−X
j6=i
αj) + (1 −Y
j6=i
Gj( )) δ αi
=δ (αi+ (S−X
j∈N
αj)Y
j6=i
Gj( )).
3See Roha gi (1976) o mo e de ails.
4An al e na i e way o de ining mixed s a egies Gis as a nondec easing, igh -con inuous unc ion om [0,∞)
o [0,1] wi h limx→∞ G(x) = 1. Fo such a unc ion we can always ind a p obabili y measu e Pon [0,∞)such
ha o each x∈[0,∞),G(x) = P

[0, x]

,i.e.,Gis he (cumula i e) dis ibu ion unc ion co esponding o
P. Al hough his equi alen app oach seems mo e na u al, i would lead o echnical p oblems when compu ing
Lebesgue-S iel jes in eg als la e on.
1.3. Two Playe s 9
I playe ialso chooses a mixed s a egy Gi, whe eas all o he playe s s ick o mixed s a egies
{Gj}j6=i, hen he expec ed payo o playe ican be compu ed by use o he Lebesgue-S iel jes
in eg al:
πi(G1, . . . , Gn) = Zπi(G1,...,Gi−1, , Gi+1,...,Gn)dGi( ).(1.2)
No e ha , wi h a sligh abuse o no a ion, he unc ions πido no only deno e payo s o playe s
when pu e s a egies a e played, bu also when mixed s a egies a e used.
The cake sha ing game associa ed wi h S,α, and δ, is de ined by he iple ΓS,α,δ :=
(N, {Xi}i∈N,{πi}i∈N), whe e
Xi:= Gis he se o mixed s a egies o playe i∈N,
πi, de ined by (1.2), is he (expec ed) payo unc ion o playe i∈N.
Gi en a s a egy p o ile G= (G1, G2,...,Gn)∈ Gn, le πG
i( )be he co esponding payo
πi(G1,...,Gi−1, , Gi+1, . . . , Gn). Hence, πG
i( )is he expec ed payo o playe iwhen he plays
he pu e s a egy and all he o he playe s ac in acco dance wi h G.
1.3 Two Playe s
In his Sec ion we p o ide an al e na i e p oo o he esul o Hame s (1993) o 2-playe cake
sha ing games. Ou incen i es o doing his job a e h ee old. Fi s o all we wan o ecall
ha ou model is sligh ly di e en om he model o Hame s (1993), and hence, a new p oo is
equi ed. Secondly, ou p oo is mo e di ec han Hame s’ p oo . Finally, ou p oo o ms he
basis o he esul s in Sec ion 1.4 o cake sha ing games wi h h ee o mo e playe s.
Fi s , we de i e a numbe o p ope ies o Nash equilib ia o n-playe cake sha ing games.
The ollowing Lemma shows ha in a Nash equilib ium playe s do no pu posi i e p obabili y
on a pu e s a egy > 0.
Lemma 1.1. Le ΓS,α,δ be an n-playe cake sha ing game and le he p o ile G= (Gi)i∈N∈ GN
be a Nash equilib ium o ΓS,α,δ. Then, o each i∈N,J(Gi)∩(0,∞) = ∅.
P oo . Le i∈N. We show ha J(Gi)∩(0,∞) = ∅. Assume, wi hou loss o gene ali y, ha
i= 1. Suppose ha u∈J(G1)∩(0,∞). I he e is i6= 1 such ha Gi(u+) = 0, hen, o each
∈[0, u],πG
1( ) = δ α1. Since he unc ion πG
1(·)is s ic ly dec easing on [0, u], playe 1 would
be be e o mo ing he p obabili y in u o 0. Hence, o each i∈N,Gi(u+)>0. Now, o each
i∈N {1}, conside he unc ions
πG
i( ) = δ (αi+ (S−X
j∈N
αj)Y
j6=i
Gj( )).
Since G1is discon inuous a u,i.e.,G1(u+)> G1(u), he e a e u1< u,u2> u, and ε > 0such

10 Chap e 1. A Silen Ba le o e a Cake
ha o each i6= 1 and each ∈[u1, u],
πG
i(u2)−πG
i( )≥ε.
I playe i∈N {1}pu s posi i e p obabili y on [u1, u],i.e., i Gi(u+)> Gi(u1), hen he can
inc ease his payo by a leas ε(Gi(u+)−Gi(u1)) by mo ing all his p obabili y o u2. Hence,
o each i∈N {1}, we ha e Gi(u+) = Gi(u1)and, o each ∈[u1, u],Gi( ) = Gi(u). Hence,
he unc ion
πG
1( ) = δ (α1+ (S−X
j∈N
αj)Y
j6=1
Gj( ))
is s ic ly dec easing on [u1, u]. Now, playe 1 can imp o e his payo by mo ing some p obabili y
om u o u1.
Lemma 1.1 implies ha , in a Nash equilib ium G, he playe s use mixed s a egies which a e
con inuous on (0,∞). Hence, o each i∈Nand each > 0, we can w i e Gi( +) = Gi( ).
Mo eo e , he unc ions πG
i(·)a e con inuous on (0,∞).
Lemma 1.2. Le ΓS,α,δ be an n-playe cake sha ing game and le he p o ile G= (Gi)i∈N∈ GN
be a Nash equilib ium o ΓS,α,δ. Le i∈Nand ∈S(Gi). Then, he e is j∈N {i}such ha
∈S(Gj).
P oo . Suppose ha /∈ ∪j6=iS(Gj). We dis inguish be ween wo cases:
Case 1: > 0.
The e a e 1, 2>0, wi h 1< < 2, such ha o each j6=i,Gj( 2) = Gj( 1).5Hence, o
each u∈[ 1, 2]and each j6=i,Gj(u) = Gj( 2). Hence, he unc ion
πG
i(u) = δu(αi+ (S−X
j∈N
αj)Y
j6=i
Gj(u))
is s ic ly dec easing on [ 1, 2]. Since ∈S(Gi), we ha e Gi( 2)> Gi( +
1),i.e., playe ipu s
posi i e p obabili y on ( 1, 2). Now, playe ican s ic ly imp o e his payo by mo ing all his
p obabili y o 1.
Case 2: = 0.
Le b > 0be he smalles elemen in ∪j6=iS(Gj)( ecall ha all he S(Gj)a e closed). Clea ly,
o each j6=i,Gj(b) = 0. Again, i Gi(b)> Gi(0+),i.e., i playe ipu s posi i e p obabili y on
(0, b), hen simila a gumen s as in Case 1 can be used o show ha playe ican s ic ly imp o e
his payo by mo ing his p obabili y o 0. Hence, Gi(b) = Gi(0+)and hence, since 0∈S(Gi),
we ha e Gi(0+)>0. Mo eo e , o each ∈(0, b],Gi( ) = Gi(b)( his is ele an only o he
5Fo each j∈N {i} he e a e j
1, j
2>0, wi h j
1< < j
2, such ha Gj( j
2) = Gj( j
1). Hence, we ake
1= maxj∈N {i} j
1and 2= minj∈N {i} j
2.
1.3. Two Playe s 11
case n= 2). Hence, o each j∈N {i}, he unc ion
πG
j( ) = δ (αj+ (S−X
k∈N
αk)Y
k6=j
Gk( ))
is s ic ly dec easing on (0, b].
Le a∈(0, b)and le j∈N {i}be a playe such ha b∈S(Gj). Le ε:= πG
j(a)−πG
j(b)>0.
Since he unc ion πG
j(·)is con inuous on (0,∞), we ha e ha , o δ > 0su icien ly small,
o each ∈[b, b +δ], πG
j(a)−πG
j( )>1
2ε.
Since b∈S(Gj),Gj(b+δ)>0 = Gj(b). Hence, playe jcan imp o e his payo by mo ing he
p obabili y he assigns o [b, b +δ) o a. Con adic ion.
The ollowing Lemma shows ha i some pu e s a egy does no belong o he suppo o
any o he equilib ium s a egies, hen no pu e s a egy ′> belongs o he suppo o any o
he equilib ium s a egies ei he .
Lemma 1.3. Le G= (Gi)i∈Nbe a Nash equilib ium o he n-playe cake sha ing game ΓS,α,δ.
Le ∈[0,∞)be such ha o each j∈N, /∈S(Gj). Then, o each j∈N,( , ∞)∩S(Gj) = ∅.
P oo . Le K:= ∪j∈NS(Gj). Clea ly, Kis closed and /∈K. We ha e o show ha K∩( , ∞) =
∅. Suppose ha K∩( , ∞)6=∅. Le ∗:= min{u∈K:u > }. Le j∗∈Nbe such ha
∗∈S(Gj∗). Since o each j∈N,[ , ∗)∩S(Gj) = ∅, hen we ha e ha , o each j∈N,
Gj( ) = Gj( ∗). Hence, he unc ions Gja e cons an on [ , ∗]. Now, since o each u∈[0,∞),
πG
j∗(u) = δu(αj∗+ (S−X
j∈N
αj)Y
j6=j∗
Gj(u)),
hen, he unc ion πG
j∗(·)is s ic ly dec easing on [ , ∗]. By he con inui y o πG
j∗(·)a ∗, o each
u∈[ ∗, ∗+ε], wi h ε > 0su icien ly small, we ha e πG
j∗( )> πG
j∗(u). Hence, Gj∗is cons an on
[ ∗, ∗+ε]as well, con adic ing he ac ha ∗∈S(Gj∗).
Now, we p o ide speci ic esul s o 2-playe cake sha ing games. The ollowing Lemma shows
ha , in a Nash equilib ium, he playe s use mixed s a egies o which he suppo s coincide.
Lemma 1.4. Le ΓS,α,δ be a 2-playe cake sha ing game and le (G1, G2)∈ G × G be a Nash
equilib ium o ΓS,α,δ. Then, S(G1) = S(G2).
P oo . This esul is jus a consequence o Lemma 1.2.
In he ollowing Lemma we show ha he suppo s o he s a egies in a Nash equilib ium a e
compac in e als.
Lemma 1.5. Le ΓS,α,δ be a 2-playe cake sha ing game and le G= (G1, G2)∈ G×G be a Nash
equilib ium o ΓS,α,δ. Le k:= logδα2
S−α1. Then, S(G1) = S(G2) = [0, k].
12 Chap e 1. A Silen Ba le o e a Cake
P oo . Fi s , we show ha S(G1) = S(G2)⊆[0, k]. Fo each ∈(k, ∞), we ha e
πG
2( ) = δ (α2+ (S−α1−α2)G1( ))
≤δ (α2+ (S−α1−α2))
=δ (S−α1)
< δk(S−α1)
=α2
=πG
2(0).
I G2(k) = G2(k+)<1,i.e., i playe 2 pu s posi i e p obabili y on (k, ∞), hen he can imp o e his
payo s ic ly by mo ing all his p obabili y o 0. Hence G2(k) = 1 and S(G1) = S(G2)⊆[0, k].
Le k∗be he la ges elemen in he closed se S(G1). Clea ly, k∗≤k. I k∗= 0, hen (G1, G2)
would be an equilib ium in pu e s a egies, a con adic ion. Hence, k∗>0. Now, by Lemma 1.3,
S(G1) = S(G2) = [0, k∗].
The only hing which emains o be shown is ha k∗=k. Suppose ha k∗< k. Now, o
each τ∈(0, k −k∗),
πG
1(k∗+τ) = δk∗+τ(α1+ (S−α1−α2)G2(k∗+τ))
=δk∗+τ(α1+ (S−α1−α2))
=δk∗+τ(S−α2)
> δk(S−α2)
=α2(S−α2)
S−α1
≥α1
=πG
1(0),
whe e a he weak inequali y we used ha α2(S−α2)≥α1(S−α1). Hence, i G1(0+)>0,i.e., i
playe 1 plays pu e s a egy 0 wi h posi i e p obabili y, hen he can imp o e his payo by mo ing
some p obabili y om 0 o pu e s a egy k∗+τ. Hence, G1(0+) = 0. Now, he e is ∈(k∗, k)
such ha
πG
2( ) = δ (α2+ (S−α1−α2)G1( ))
=δ (α2+ (S−α1−α2))
=δ (S−α1)
> δk(S−α1)
=α2
=πG
2(0).
Since 0∈S(G1)and πG
2(·)is con inuous a 0 (because G1(0+) = 0), playe 2 can s ic ly imp o e
his payo by mo ing some p obabili y om he neighbo hood o 0 o . Con adic ion. Hence,
k∗=k.
Now, we a e eady o p o e he main heo em o his Sec ion.
1.3. Two Playe s 13
Theo em 1.1. Le ΓS,α,δ be a 2-playe cake sha ing game and k:= logδα2
S−α1. De ine G∗=
(G∗
1, G∗
2)∈ G ×G by
G∗
1( ) := 


α2−α2δ
δ (S−α1−α2)0≤ ≤k
1 > k,
G∗
2( ) := 








0 = 0
α2(S−α2)−α1(S−α1)δ
δ (S−α1)(S−α1−α2)0< ≤k
1 > k.
Then, G∗is he unique Nash equilib ium o ΓS,α,δ. Mo eo e , he equilib ium payo s a e
π1(G∗
1, G∗
2) = α2(S−α2)
S−α1
,
π2(G∗
1, G∗
2) = α2.
P oo . One easily e i ies ha
πG∗
1( ) = 






α1 = 0
α2(S−α2)
S−α1
0< ≤k
δ (S−α2) > k,
and
πG∗
2( ) = (α20≤ ≤k
δ (S−α1) > k.
Hence,
π1(G∗
1, G∗
2) = α2(S−α2)
S−α1
and π2(G∗
1, G∗
2) = α2.
Since o each ∈[0,∞),
π1( , G∗
2)≤α2(S−α2)
S−α1
and π2(G∗
1, )≤α2,
we ha e ha G∗is a Nash equilib ium o ΓS,α,δ.
In o de o show ha he e a e no o he Nash equilib ia, le (G1, G2)be a Nash equilib ium o
ΓS,α,δ. By Lemma 1.1, he s a egies G1and G2a e con inuous on (0,∞). In he same way as in
he p oo o Lemma 1.5, we can show ha G1(0+) = 0. Hence, he unc ion πG
1(·)is con inuous
on (0,∞)and he unc ion πG
2(·)is con inuous on [0,∞). By Lemma 1.5, S(G1) = S(G2) = [0, k].
Hence, he e a e cons an s cand dsuch ha
o each ∈(0, k], c =πG
1( ) = δ (α1+ (S−α1−α2)G2( )),
o each ∈[0, k], d =πG
2( ) = δ (α2+ (S−α1−α2)G1( )).
20 Chap e 1. A Silen Ba le o e a Cake
Bibliog aphy
Bas on, V. J. and A. Y. Ga nae (2000): “On a Game in Manu ac u ing,” Ma hema ical
Me hods o Ope a ions Resea ch, 52, 237–249. (Quo ed in pp. 6)
Baye, M. R., D. Ko enock, and C. G. de V ies (1996): “The All-Pay Auc ion wi h Comple e
In o ma ion,” Economic Theo y, 8, 291–395. (Quo ed in pp. 7)
Fudenbe g, D., R. Gilbe , J. S igli z, and J. Ti ole (1983): “P eemp ion, Leap ogging
and Compe i ion in Pa en Races,” Eu opean Economic Re iew, 22, 3–31. (Quo ed in pp. 6)
Hame s, H. (1993): “A Silen Duel o e a Cake,” Me hods and Models o Ope a ions Resea ch,
37, 119–127. (Quo ed in pp. 6, 7, 9)
Hend icks, K., A. Weiss, and C. Wilson (1988): “The Wa o A i ion in Con inuous Time
wi h Comple e In o ma ion,” In e na ional Economic Re iew, 29, 663–680. (Quo ed in pp. 6)
Hilman, A. L. and J. G. Riley (1989): “Poli ically Con es able Ren s and T ans e s,” Eco-
nomics and Poli ics, 1, 17–39. (Quo ed in pp. 7)
Ka lin, S. (1959): Ma hema ical Me hods and Theo y in games. P og amming and Economics,
Addison-Wesley. (Quo ed in pp. 6)
La aki, R., E. Solan, and N. Vieille (2003): “Con inuous- ime Games o Timing,” Discussion
Pape 1363, Kellogg School o Managemen , No hwes e n Uni e si y. (Quo ed in pp. 6)
Reinganum, J. (1981): “On he Di usion o a New Technology: A Game Theo e ic App oach,”
The Re iew o Economic S udies, 48, 395–405. (Quo ed in pp. 6)
Roha gi, V. K. (1976): An In oduc ion o P obabili y Theo y and Ma hema ical S a is ics,
Wiley se ies in p obabili y and ma hema ical s a is ics. (Quo ed in pp. 8)
Smi h, J. M. (1974): “The Theo y o Games and E olu ion in Animal Con lic s,” Jou nal o
Theo e ical Biology, 47, 209–221. (Quo ed in pp. 6)
Webe , R. J. (1985): “Auc ions and Compe i i e Bidding,” in Fai Alloca ion, ed. by H. P.
Young, Ame ican Ma hema ical Socie y, P oceedings o symposia in applied ma hema ics, 143–
170. (Quo ed in pp. 7)

Chap e 2
Fini ely Repea ed Games: A
Gene alized Nash Folk Theo em
Con en s
2.1 In oduc ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Basic No a ion, De ini ions and an Example . . . . . . . . . . . . . . 23
2.2.1 The S age Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 The Repea ed Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Minimax-Be e ing Ladde s . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.4 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.5 Fu he P elimina ies . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 The Theo em . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Unobse able Mixed Ac ions . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Concluding Rema ks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Bibliog aphy ................................... 32
21
22 Chap e 2. Fini ely Repea ed Games: A Gene alized Nash Folk Theo em
2.1 In oduc ion
O e he pas hi y yea s, necessa y and su icien condi ions ha e been published o nume ous
“ olk heo ems”, asse ing ha he indi idually a ional easible payo s o ini ely o in ini ely e-
pea ed games wi h comple e in o ma ion can be achie ed by Nash o subgame pe ec equilib ia.1
The o iginal olk heo em was conce ned abou he Nash Equilib ia o in ini ely epea ed games.
This olk heo em s a ed ha e e y indi idually a ional easible payo o he o iginal game can
be ob ained as a Nash Equilib ium o he epea ed game; no assump ion was needed o his esul
(a s a emen and p oo o his esul can be ound in Fudenbe g and Maskin (1986)). Then, he
heo is s u ned o s udy subgame pe ec ion in in ini e ho izon models and hey ound a coun e -
pa o he p e ious esul o undiscoun ed epea ed games; again, no assump ions we e needed
(Aumann and Shapley, 1976; Rubins ein, 1979). A ew yea s la e , discoun pa ame e s we e
inco po a ed again in o he model; in his case, some condi ions we e needed o ge he pe ec
olk heo em (Fudenbe g and Maskin, 1986). These condi ions we e e ined in he mid-nine ies
(Ab eu e al., 1994; Wen, 1994).
Toge he wi h he p e ious esul s, also he li e a u e on ini ely epea ed games g ew. The
main esul s o ini e ho izon models ob ained condi ions o he Nash olk heo em (Benoî
and K ishna, 1987), and also o he pe ec one (Benoî and K ishna, 1985). This pe ec olk
heo em elied on he ac ha mixed s a egies we e obse able; he same esul bu wi hou ha
assump ion was ob ained in he mid-nine ies (Gossne , 1995). Assuming again obse able mixed
s a egies, Smi h (1995) ob ained a necessa y and su icien condi ion o he a bi a ily close
app oxima ion o s ic ly a ional easible payo s by subgame pe ec equilib ia wi h ini e ho izon:
ha he game ha e “ ecu si ely dis inc Nash payo s”, a p emise ha elaxes he assump ion in
Benoî and K ishna (1985) ha each playe ha e mul iple Nash payo s in he s age game.
Smi h claimed ha his condi ion was also necessa y o app oxima ion o he indi idually
a ional easible payo s o ini ely epea ed games by Nash equilib ia. In his Chap e we show
ha his is no so by es ablishing a simila bu dis inc su icien condi ion ha is weake han
bo h Smi h’s condi ion and he assump ions made by Benoî and K ishna (1987). Mo eo e , ou
condi ion is also necessa y. Essen ially, he di e ence be ween he subgame pe ec and Nash
cases hinges on he weakness o he Nash solu ion concep : in he Nash case i is no necessa y
o h ea s o puni i e ac ion agains playe s who de ia e om he equilib ium no o in ol e loss
o he punishing playe s hemsel es, i.e., h ea s need no be c edible. The kind o equilib ium
we de ine in his Chap e equi es o i s co esponding pa h ρ, o inish, o each playe i, wi h
a se ies Qio ounds in which icanno unila e ally imp o e his s age payo by de ia ion om
ρi, and o his e minal phase o s a wi h a se ies Q0
io ounds in which he o he playe s,
ega dless o he cos o hemsel es, can punish him e ec i ely o any p io de ia ion by imposing
a loss ha wipes ou any gains he may ha e made in de ia ing.
Many o he esul s men ioned abo e conce n he app oximabili y o he en i e se o indi id-
1The su ey by Benoî and K ishna (1996) includes many o hese esul s.
2.2. Basic No a ion, De ini ions and an Example 23
ually a ional easible payo s. The main heo em in his Chap e is mo e gene al in ha , o any
game, i cha ac e izes he se o easible payo s ha a e app oximable.
Al hough subgame pe ec equilib ium is a desi able e inemen o Nash equilib ium, esul s
o he la e a e s ill needed o games in which he pe ec olk heo em does no apply. Game G
in Figu e 2.1 shows ha , indeed, his is he case o a gene ic class o games. The assump ions o
he pe ec olk heo em do no hold o game G. Mo eo e , Theo em 2 in Smi h (1995) implies
ha (3,3) is he unique payo achie able ia subgame pe ec equilib ium in any epea ed game
such ha Gis i s s age game. Howe e , e e y easible and indi idually a ional payo , (e.g.,
(4,4)) can be app oxima ed in Nash equilib ium in many o hose epea ed games ( o small
enough discoun and big enough numbe o epe i ions).
L R
T 3,3 6,2
B 2,6 0,0
Figu e 2.1: A game o which he Nash olk heo em is needed.
We ha e s uc u ed his Chap e as ollows. We in oduce no a ion and concep s in Sec ion 2.2.
In Sec ion 2.3 we s a e and p o e he main esul . Nex , in Sec ion 2.4 we a e conce ned abou
unobse able mixed s a egies. Finally, we conclude in Sec ion 2.5.
2.2 Basic No a ion, De ini ions and an Example
2.2.1 The S age Game
As a egic game Gis a iple (N, A, ϕ), whe e:
N:= {1,...,n}is he se o playe s,
A:= Qi∈NAiand Aiis he se o playe i’s s a egies,
ϕ:= (ϕ1,...,ϕn)and ϕi:A→Ris he payo unc ion o playe i.
Le GNbe he se o games wi h se o playe s N.
We assume ha , o each i∈N, he se s Aia e compac and he unc ions ϕia e con inuous.
Le a−ibe a s a egy p o ile o playe s in N {i}and A−i he se o such p o iles. Fo each
i∈Nand each a−i∈A−i, le µi(a−i) := maxai∈Ai{ϕi(a−i, ai)}. Also, o each i∈N, le
i:= mina−i∈A−i{µi(a−i)}. The ec o := { 1,..., n}is he minimax payo ec o . Le Fbe
he se o easible payo s: F:= co{ϕ(a) : a∈A}. Le ¯
Fbe he se o all easible and indi idually
a ional payo s:
¯
F:= F∩ {u∈Rn:u≥ }.
To a oid con usion wi h he s a egies o he epea ed game, in wha ollows we e e o he
s a egies ai∈Aiand he s a egy p o iles a∈Ao he s age game as ac ions and ac ion p o iles,
espec i ely.
24 Chap e 2. Fini ely Repea ed Games: A Gene alized Nash Folk Theo em
2.2.2 The Repea ed Game
Le G(δ, T)be he game consis ing in he T- old epe i ion o Gwi h payo discoun pa ame e
δ∈(0,1]. In his game we assume pe ec moni o ing,i.e., each playe can choose his ac ion in
he cu en s age in he ligh o all ac ions aken by all playe s in all p e ious s ages. Le σbe
a s a egy p o ile o G(δ, T), and he ac ion p o ile sequence ρ={ρ1, . . . , ρT}i s co esponding
pa h. Le ϕ
i(ρ)be he s age payo o playe ia s age when all playe s play in acco dance
wi h ρ. Then, playe i’s payo in G(δ, T)when σis played is his a e age discoun ed s age payo :
ψi(σ)≡ψi(ρ) := ((1 −δ)/(1 −δT)) PT
=1 δ −1ϕ
i(ρ).2
2.2.3 Minimax-Be e ing Ladde s
Le Mbe an m-playe subse o N. Le AM:= Qi∈MAiand le G(aM)be he game induced
o he n−mplaye s in N Mwhen he ac ions o he playe s in Ma e ixed a aM∈AM.
By abuse o language, i i∈N M,aM∈AM, and σ∈AN Mwe w i e ϕi(σ) o i’s payo
a σin G(aM). A minimax-be e ing ladde o a game Gis a iple {N,A,Σ}, whe e Nis
a s ic ly inc easing chain {∅ =N0(N1(··· (Nh}o h+ 1 subse s o N(h≥1), Ais
a chain o ac ion p o iles {aN1∈AN1,...,aNh−1∈ANh−1}and Σis a chain {σ1,...,σh}o
Nash equilib ia o G=G(aN0), G(aN1),...,G(aNh−1), espec i ely, such ha a σl he playe s o
G(aNl−1) ecei ing payo s s ic ly g ea e han hei minimax payo a e exac ly hose in Nl Nl−1:
o each i∈Nl Nl−1,ϕi(σl)> i, and o each i∈N Nl,ϕi(σl)≤ i.
Le he se s in Nbe he ungs o he ladde . In algo i hmic e ms, i he i s l−1 ungs o
he ladde ha e been cons uc ed, hen, o he l- h ung o exis , he e mus be aNl−1∈ANl−1
such ha he game G(aNl−1)has an equilib ium σl. Mo eo e , σlhas o be such ha he e a e
playe s i∈N Nl−1 o whom ϕi(σl)> i. Le Nl Nl−1be his subse o playe s o G(aNl−1).
The game played in he nex s ep is de ined by some ac ion p o ile aNl. The se Nhis he op
ung o he ladde . A ladde wi h op ung Nhis maximal i he e is no ladde wi h op ung Nh′
such ha Nh(Nh′. A game Gis decomposable as a comple e minimax-be e ing ladde i i has
a minimax-be e ing ladde wi h Nas i s op ung. We show below ha being decomposable as a
comple e minimax-be e ing ladde is a necessa y and su icien condi ion o i o be possible o
app oxima e all payo ec o s in ¯
Fby Nash equilib ia o G(δ, T) o some δand T. Clea ly, being
decomposable as a comple e minimax-be e ing ladde is a weake p ope y han he equi emen
in Smi h (1995), ha a each s ep l−1o a simila kind o ladde he e be ac ion p o iles
aNl−1,bNl−1such ha he games G(aNl−1)and G(bNl−1)ha e Nash equilib ia σl
aand σl
bwi h
ϕi(σl
a)6=ϕi(σl
b) o a nonemp y se o playe s ( hose in Nl Nl−1).
2.2.4 An Example
Le G∈ GN, le Lbe a maximal ladde o G, and Nmax i s op ung. Fo each i∈N, le li
be he unique in ege such ha i∈Nli Nli−1. In he equilib ium s a egy p o ile cons uc ed
2O , ψi(σ)≡ψi(ρ) := (1/T)
P
T
=1 ϕ
i(ρ)i he e a e no discoun s (δ= 1).
2.2. Basic No a ion, De ini ions and an Example 25
in Theo em 2.1 below, he ac ion p o ile sequence in he e minal phase Qi e e ed o in he
In oduc ion, consis s o epe i ions o (aNli−1, σli),(aNli−2, σli−1),...,(aN2, σ2)and σ; and he
σja e Nash equilib ia o he co esponding games G(aNj−1). Since playe iis a playe in all hese
games, he can indeed gain no hing by unila e al de ia ion du ing his phase. In he po en ially
punishing se ies o ounds Q0
i, he ac ion p o ile sequence consis s o epe i ions o (aNli−1, σli),
in which iob ains mo e han his minimax payo , wi h he accompanying h ea o punishing a
p io unila e al de ia ion by iby minimaxing him ins ead.
l m l m
T 0, 0, 3 0,-1, 0 0,-1, 0 T 0, 3,-1 0,-1,-1 1,-1,-1
M -1, 0, 0 0,-1, 0 0,-1, 0 M -1, 0,-1 -1,-1,-1 0,-1,-1
B -1, 0, 0 0,-1, 0 0,-1, 0 B -1, 0,-1 -1,-1,-1 0,-1,-1
L R
Figu e 2.2: A game ha is decomposable as a comple e minimax-be e ing ladde
As an illus a ion o he abo e ideas, conside he h ee-playe game Gshown in Figu e 2.2.
I s minimax payo ec o is (0,0,0), and i s unique Nash equilib ium is he ac ion p o ile σ1=
(T, l, L), wi h associa ed payo ec o (0,0,3). Hence, N1={3}; playe 3 can be punished by 1
and 2 by playing one o his minimax p o iles ins ead o playing (T, l, ·). I playe 3 now plays R
(aN1=R), he esul ing game G(aN1) = G(R)has an equilib ium σ2= (T, l)wi h payo ec o
(0,3). Hence, N2={2,3}and playe 2 can be punished by 1 and 3 by playing one o his minimax
p o iles ins ead o playing (T, ·, R). Finally i playe s 2 and 3 now play and R(aN2= ( , R)),
he esul ing game G(aN2) = G( , R)has he i ial equilib ium σ3= (T)wi h payo 1 o playe
1. Hence, playe 1 can be punished by 2 and 3 i hey play one o his minimax p o iles ins ead o
playing (·, , R).
2.2.5 Fu he P elimina ies
As a consequence o he nex Lemma we can unambiguously e e o he op ung o a game G.
Lemma 2.1. Le G∈ GN. Then, all i s maximal ladde s ha e he same op ung.
P oo . Suppose he e a e maximal ladde s L={N,A,Σ},L′={N′,A′,Σ′}wi h N={N0(
N1(··· (Nh}and N′={N′
0(N′
1(··· (N′
k}such ha Nh6=N′
k. Assume, wi hou
loss o gene ali y, ha N′
k Nh6=∅. Fo each j∈N′
k, le ljbe he unique in ege such ha
j∈N′
lj N′
lj−1. Le i∈a gminj∈N′
k Nhlj. Then, N′
li−1⊆Nh. Le aNhbe he ac ion p o ile
de ined as ollows:
o each j∈N, (aNh)j=((a′
N′
li−1)jj∈N′
li−1
(σ′li)jj∈Nh N′
li−1,
whe e σ′li∈Σ′is an equilib ium o he game G(a′
N′
li−1)induced by he ac ion p o ile a′
N′
li−1∈ A′.

26 Chap e 2. Fini ely Repea ed Games: A Gene alized Nash Folk Theo em
Now, le σh+1 be he es ic ion o σ′li o N Nh. Since σ′liis an equilib ium o G(a′
N′
li−1),
and N Nh⊆N N′
li−1,σh+1 is an equilib ium o G(aNh). Mo eo e , he se o playe s j∈N Nh
o whom ϕj(σh+1)> jis N′
li Nh. Le Nh+1 := N′
li Nh. Since Nh+1 con ains i, i is nonemp y.
Le L′′ ={N′′,A′′,Σ′′}be he ladde de ined by
N′′ ={N0(N1(···(Nh(Nh+1},
A′′ ={aN1,...,aNh−1, aNh},
Σ′′ ={σ1,...,σh, σh+1}.
The op ung o L′′ s ic ly con ains ha o L. Hence, L is no maximal, which p o es he
Lemma.
Le Gbe a game wi h se o playe s Nand le N′⊆N. We say ha G∈TRN′(GN)i he
op ung o any maximal ladde o Gis N′. Hence, a game Gis decomposable as a comple e
minimax-be e ing ladde i and only i G∈TRN(GN).
Le G∈TRNmax (GN)and ˆa∈ANmax . Le Λ(ˆa) := {λ= (ˆa, σ)∈A:σNash equilib ium
o G(ˆa)}and Λ := Sˆa∈ANmax Λ(ˆa). Le ϕ(Λ) := {ϕ(λ) : λ∈Λ}. Le ¯
FNmax be he se o
Nmax -a ainable payo s o G:¯
FNmax := ¯
F∩co ϕ(Λ). No e ha , by he de ini ion o Nmax, o
each u∈¯
FNmax and each i∈N Nmax,ui= i. Mo eo e , when Nmax =Nwe ha e Λ = Aand
¯
FNmax =¯
F.
Lemma 2.2. Le G∈TRNmax (GN). Then, he se ¯
FNmax is closed.
P oo . Fi s , we show ha Λis closed. Le {(an, σn)}be a sequence o ac ion p o iles in Λwi h
limi (a, σ). Since ANmax is compac , a∈ANmax . Since ϕis con inuous, σis a Nash equilib ium
o G(a). Hence, (a, σ)∈Λ.
The se ϕ(Λ) is he image o a closed se unde a con inuous unc ion. Since ϕhas a compac
domain, ϕ(Λ) is closed. Hence, ¯
F∩co ϕ(Λ) is closed.
The p omised esul conce ning he app oximabili y o all payo s in ¯
Fby Nash equilib ium
payo s is ob ained below as an immedia e co olla y o a mo e gene al heo em conce ning he
app oximabili y o all payo s in ¯
FNmax . In his mo e gene al case, he collabo a ion o he playe s
in Nmax is secu ed by a s a egy analogous o ha ske ched in he Example o Sec ion 2.2.4, while
he collabo a ion o he playe s in N Nmax is also ensu ed because none o hem is able o ob ain
any ad an age by unila e al de ia ion om any ac ion p o ile in Λ.
2.3 The Theo em
In he heo em ha ollows, he se o ac ion p o iles Amay consis ei he o pu e o mixed ac ion
p o iles; in he la e case, we assume ha all playe s a e cognizan no only o he pu e ac ions
ac ually pu in o e ec a each s age, bu also o he mixed ac ions o which hey a e ealiza ions.
2.3. The Theo em 27
We discuss unobse able mixed ac ions in Sec ion 2.4. Also, we assume public andomiza ion:
a each s age o he epea ed game, playe s can le hei ac ions depend on he ealiza ion o an
exogenous con inuous andom a iable. The assump ion o public andomiza ion is wi hou loss
o gene ali y. Gi en a co ela ed mixed ac ion, i s payo can be app oxima ed by al e na ing pu e
ac ions wi h he app op ia e equencies. Mo e p ecisely, o each u∈¯
Fand each ε > 0, he e
a e pu e ac ions a1,...,alsuch ha ||u−(a1+...+al)/l|| < ε. Hence, i he discoun pa ame e
δis close enough o 1, he same inequali y is s ill ue i we conside discoun ed payo s. Then,
since we s a e Theo em 2.1 in e ms o app oxima ed payo s, public andomiza ion assump ion
can be dispensed wi h.3
Theo em 2.1. Le G∈TRNmax (GN). Le u∈F. Then, a necessa y and su icien condi ion
o he e o be o each ε > 0, an in ege T0and a posi i e eal numbe δ0<1such ha o each
T≥T0and each δ∈[δ0,1],G(δ, T)has a Nash equilib ium payo wsuch ha kw−uk< ε is
ha ube Nmax -a ainable ( i.e.,u∈¯
FNmax ).
P oo . su ic
⇐=Le a∈Λbe an ac ion p o ile o Gsuch ha ϕ(a) = u, and le L={N,A,Σ}be
a maximal minimax-be e ing ladde o G. By he de ini ion o Λ, playe s in N Nmax ha e no
incen i e o unila e al de ia ion om a. Le ρbe he ollowing ac ion p o ile sequence:
ρ:= {a, . . . , a
|{z }
T−T0+q0
, λh,...,λh
|{z }
qh
, λh−1,...,λh−1
| {z }
qh−1
, . . . , λ1,...,λ1
| {z }
q1
},
whe e o each l∈ {1,...h},λl= (aNl−1, σl)wi h aNl−1∈ A and σl∈Σ. Le ε > 0. Nex , we
ob ain (in his o de ) alues o qh,...,q1, he discoun δ0,q0, and T0 o ensu e ha o each
T≥T0and each δ∈(δ0,1], he e is a Nash equilib ium o G(δ, T)whose pa h is ρand such ha
||ϕ(ρ)−u|| < ε.
Fi s , we calcula e how many epe i ions o G(aNli−1)a e necessa y o he playe s in N {i}
o be able o punish a playe i∈Nmax o p io de ia ion. Fo each ac ion p o ile ˆa∈A, le
¯µi(ˆa) := µi(ˆa−i)−ϕi(ˆa),i.e., he maximum “illici ” p o i ha playe ican ob ain by unila e al
de ia ion om ˆa. Le ¯µi= max{¯µi(a),¯µi((aNh−1, σh)),...,¯µi(σ1)}and mi= min{ϕi(a) : a∈
A}. Le li∈Nbe such ha i∈Nli Nli−1. Le δ0∈(0,1) and le qh,...,q1be he na u al
numbe s de ined h ough he ollowing i e a i e p ocedu e:
S ep 0:
Fo each i∈Nh Nh−1, le i∈Nand δi∈(0,1) be
i:= min{ ∈N: (ϕi(σli)− i)>¯µi},4
δi:= min{δi∈(0,1) : ¯µi−P i
=1 δ
i(ϕi(σli)− i)<0}.
Le qh∈Nbe
3Fo u he discussion on public andomiza ion e e o Fudenbe g and Maskin (1991) and Olszewski (1997).
Also, e e o Gossne (1995) o a pape in which public andomiza ion is no assumed and he app oxima ion
p ocedu e we desc ibed abo e is explici ly made ( hough discoun s a e no conside ed).
4The na u al numbe iis such ha , a each s ep, punishing playe idu ing is ages su ices o wipe ou any
s age gain he could ge by de ia ing om ρwhen he discoun is δ= 1.
28 Chap e 2. Fini ely Repea ed Games: A Gene alized Nash Folk Theo em
qh:= max{ i:i∈Nh Nh−1}.
S ep k(k < h):
Le Tk:= Pk−1
l=0 qh−l.
Fo each i∈Nh−k Nh−k−1, le i∈Nand δi∈(0,1) be
i:= min{ ∈N: (ϕi(σli)− i)>¯µi+Tk( i−mi)},
δi:= min{δi∈(0,1) : ¯µi+PTk
=1 δ
i( i−mi)−PTk+ i
=Tk+1 δ
i(ϕi(σli)− i)<0}.
Le qh−k∈Nbe
qh−k:= max{ i:i∈Nh−k Nh−k−1}.
S ep h:
δ0:= maxi∈Nδi.
The na u al numbe s qh,...,q1and he discoun δ0a e such ha o each l∈ {1,...,h},ql
epe i ions o G(aNl−1)su ice o allow any playe in Nl Nl−1 o be punished. Nex , we ob ain
he alues o q0and T0. Le q0be he smalles in ege such ha :




q0ϕ(a) + qhϕ(λh) + ···+q1ϕ(λ1)
q0+qh+···+q1−ϕ(a)


< ε. (2.1)
Le T0:= q0+q1+···+qh. Le T≥T0and δ∈[δ0,1]. We p esc ibe o G(δ, T) he s a egy
p o ile in which all playe s play acco ding o ρunless and un il he e is a unila e al de ia ion.
In such a de ia ion occu s, he de ia ing playe is minimaxed by all he o he s in he emaining
s ages o he game. I is s aigh o wa d o check ha his p o ile is a Nash equilib ium o G(δ, T ).
Mo eo e , by inequali y (2.1), i s associa ed payo ec o wdi e s om uby less han T0
Tεi
δ= 1. Hence, he same obse a ion is ce ainly ue i δ < 1, in which case payo ec o s o he
ea ly s ages, ϕ(a), ecei e g ea e weigh han he payo ec o s o he endgame.
necess
=⇒Le u /∈¯
FNmax . Suppose ha Nmax =N. Then, ¯
FNmax =¯
F. Hence, uis no
indi idually a ional. Hence, i can no be he payo associa ed o any Nash equilib ium. Then,
we can assume Nmax (N. Since ¯
FNmax is a closed se , he e is ε > 0such ha kw−uk< ε
implies w /∈¯
FNmax . Hence, i o some Tand δ he e is a s a egy p o ile σo G(δ, T)such ha
kϕ(σ)−uk< ε, hen ϕ(σ)/∈¯
FNmax . Hence, by he de ini ion o ¯
FNmax , he e is a leas one s age
o G(δ, T)in which, wi h posi i e p obabili y, σp esc ibes an ac ion p o ile no belonging o Λ.
Le qbe he las such s age and ¯a= (¯aNmax ,¯aN Nmax ) he co esponding ac ion p o ile. By he
de ini ion o ¯
FNmax ,¯aN Nmax canno be a Nash equilib ium o G(¯aNmax ). Hence, he e is a playe
j∈N Nmax who can inc ease his payo in ound qby de ia ing unila e ally om ¯a. Since, by
he de ini ion o q,σassigns ja s age payo o jin all subsequen ounds, his de ia ion canno
subsequen ly be punished. Hence, σis no an equilib ium o G(δ, T).
Co olla y 2.1. Le G∈ GNbe decomposable as a comple e minimax-be e ing ladde , (i.e.,
G∈TRN(GN)). Then, o each u∈¯
Fand each ε > 0, he e is T0∈Nand δ0<1such
ha o each T≥T0and each δ∈[δ0,1], he e is a Nash equilib ium payo wo G(δ, T)wi h
kw−uk< ε.
2.4. Unobse able Mixed Ac ions 29
P oo . N=Nmax ⇒¯
F=¯
FNmax . Hence, his esul is a consequence o Theo em 2.1.
Co olla y 2.2. Le G∈ GNbe no decomposable as a comple e minimax-be e ing ladde ( i.e.,
G /∈TRN(GN)). Then, o each T∈N, each δ∈(0,1], each i∈N Nmax , and each Nash
equilib ium σo G(δ, T)we ha e ϕi(σ) = i.
P oo . Fo each u∈¯
FNmax and o each i∈N Nmax,ui= i. Hence, his esul ollows by an
a gumen pa alleling he p oo o necessi y in Theo em 2.1.
2.4 Unobse able Mixed Ac ions
In wha ollows, we d op he assump ion ha mixed ac ions a e obse able. Hence, i a mixed
ac ion is chosen by one playe , he o he s can only obse e i s ealiza ion. To a oid con usion,
o each game G, le Gube he co esponding game wi h unobse able mixed ac ions. We need
o in oduce one addi ional piece o no a ion o dis inguish be ween pu e and mixed ac ions. Le
Aiand Sibe he se s o playe i’s pu e and mixed ac ions espec i ely (wi h gene ic elemen s ai
and si). Simila ly, le Aand Sbe he se s o pu e and mixed ac ion p o iles. Hence, a game is
now a iple (N, S, ϕ).
The game G(o Gu) in Figu e 2.3 illus a es some o he di e ences be ween he wo ame-
wo ks. Al hough i is no en i ely s aigh o wa d, i is no di icul o check ha he minimax
payo o Gis = (0,0,0). Le s3= (0,0.5,0.5) be he mixed ac ion o playe 3 in which he plays
L wi h p obabili y 0, and M and R wi h p obabili y 0.5. Le σ2∈A{1,2}. Le N={∅,{3}, N},
S={s3}and Σ = {(T, l, L), σ2}. Then, L={N,S,Σ}is a comple e minimax-be e ing ladde
o G ega dless o σ2(no e ha in he game G(s3), o each σ2∈A{1,2}, bo h playe s 1 and 2
ecei e he cons an payo 0.5). Hence, Gsa is ies he assump ions o Co olla y 2.1, so e e y
payo in ¯
Fcan be app oxima ed in Nash equilib ium.
l l l
T 0, 0, 2 0, 0, 0 T 0, 0,-1 2,-1,-1 T 1, 1,-8 -1, 2,-8
B 0, 0, 0 0, 0, 0 B -1, 2,-1 1, 1,-1 B 2,-1,-8 0, 0,-8
L M R
Figu e 2.3: A game whe e unobse able mixed ac ions make a di e ence
Conside now he game Gu. Le u∈¯
F, and le abe such ha ϕ(a) = u( ecall ha we
assumed public andomiza ion). I we ollow he pa h ρcons uc ed in he p oo o Theo em 2.1,
he e a e na u al numbe s q0,q1, and q2such ha ρleads o play (i) adu ing he i s q0s ages,
(ii) (σ2, s3)du ing he ollowing q2s ages, and (iii) (T,l,L) du ing he las q1s ages. Le Qbe he
phase desc ibed in (ii). Since playe 3 is no indi e en be ween he wo ac ions in he suppo
o s3, we need a de ice o de ec possible de ia ions om ha suppo . Bu , once such a de ice
has been chosen, i is no clea whe he we can ensu e ha he e a e no ealiza ions o he i s
36 Chap e 3. Unila e al Commi men s in Repea ed Games
Fbe he se o easible payo s, F:= co{ϕ(a) : a∈A}. Now, o each i∈N, le p−i∈
a gmina−i∈A−i{µi(a−i)}.
To a oid con usion wi h he s a egies o he epea ed game, in wha ollows we e e o he
s a egies ai∈Aiand he s a egy p o iles a∈Ao he s age game as ac ions and ac ion p o iles,
espec i ely.
Nex , gi en a game G= (N, A, ϕ), we de ine he epea ed game G(δ, T); he T- old epe i ion
o Gwi h discoun pa ame e δ∈(0,1]. A his o y a s age ∈ {1,...,T}is de ined as ollows:
(i) o = 1, an elemen o A0={∗}, whe e ∗is any elemen no belonging o Sk∈NAk.
(ii) o ∈ {2,...,T}, an elemen o A −1.
The se o all his o ies is H:= ST
=1 A −1. In he epea ed game we assume pe ec moni o ing,
i.e., each playe can choose his ac ion in he cu en s age in he ligh o all ac ions aken by all
playe s in all p e ious s ages. Hence, le G(δ, T)be he iple (N, S, ϕδ), whe e:
The se o playe s N emains he same.
S:= Qi∈NSiis he se o s a egy p o iles, whe e Si:= AH
i,i.e., he se o mappings
om H o Ai. Le σ= (σ1,...,σn)∈Sand h∈H; hen, we deno e he ac ion p o ile
(σ1(h),...,σn(h)) by σ(h). A s a egy p o ile σ∈S ecu si ely de e mines he sequence o
ac ion p o iles π(σ)∈ATas ollows: π1(σ) := σ(∗)and, o each ∈ {2,...,T},π (σ) =
σ(π1(σ),...,π −1(σ)). We e e o π(σ)as he pa h de e mined by σ.
The payo unc ion ϕδis de ined as ollows. Le σ∈S. Then, playe i’s payo in G(δ, T)
is his a e age discoun ed s age payo :
ϕδ
i(σ) := 1−δ
1−δT
T
X
=1
δ −1ϕi(π (σ)).1
Finally, ecall ha , om ou de ini ions, we only use pu e ac ions. I mixed ac ions a e o be
aken in o accoun o a gi en game, hen we jus de ine a new game ha ing hem as pu e ac ions.
Hence, we a e implici ly assuming ha , when wo king wi h mixed ac ions, hey a e obse able,
i.e., he playe s do no only obse e he ealiza ion o a mixed ac ion, bu also he andomiza ion
p ocess ha leads o such a ealiza ion.
3.2.1 Vi ually Subgame Pe ec Equilib ia
A epea ed game wi h pe ec moni o ing can be ep esen ed as an ex ensi e game and, mo e
speci ically, as a mul i-s age game wi h obse ed ac ions.2Subgame pe ec equilib ium (Sel en,
1965), sho ly SPE, is p obably he mos impo an equilib ium concep wi hin his class o games.
1I he e a e no discoun s (i.e., i δ= 1), we ha e ϕδ
i(σ) := (1/T )
P
T
=1 ϕi(π (σ)).
2We model ex ensi e games ollowing he amewo k used in K eps and Wilson (1982), excep o he ac ha
we conside ha he se s o nodes may be in ini e.

3.2. No a ion 37
I s main a ge is o dis ega d hose Nash equilib ia which a e only possible i some playe s gi e
c edi o i a ional plans o o he s. Mo e o mally, a SPE is a Nash equilib ium which, mo eo e ,
induces a Nash equilib ium in e e y subgame.
In his Sec ion we in oduce a new equilib ium concep o ex ensi e games which is essen-
ial o his Chap e : he i ually subgame pe ec equilib ium, sho ly VSPE. This equilib ium
concep has he same e ec as subgame pe ec ion, bu i only concen a es on hose subgames
which a e ele an o a gi en s a egy p o ile; ele an in he sense ha hey a e eachable i
exac ly one playe de ia es om he s a egy p o ile in any subgame which has al eady been
classi ied as ele an . Despi e o being based on he same idea, SPE and VSPE a e di e en
concep s, he la e exis ing in many games which do no ha e SPE. Hence, VSPE is especially
use ul when dealing wi h ex ensi e games ha ing la ge ees. The e a e many ex ensi e games
wi hou SPE, bu s ill, hey can ha e sensible equilib ia. This is he case when he non-exis ence
o SPE is because some subgames which a e i ele an o a ce ain s a egy p o ile do no ha e
Nash equilib ia.
Le Γbe an ex ensi e game and le xand σbe a single-node in o ma ion se and a s a egy
p o ile, espec i ely. Then, Γxdeno es he subgame o Γ ha begins a node xand σx he
es ic ion o σ o Γx. Now, le Γbe an ex ensi e game, σa s a egy p o ile o Γ, and xa single-
node in o ma ion se . Then, he subgame Γxis σ- ele an i ei he (i) Γx= Γ, o (ii) he e a e a
playe i, a s a egy σ′
i, and a single-node in o ma ion se ysuch ha Γyis σ- ele an and node x
is eached by (σ−i, σ′
i)y.
De ini ion 3.1. Le Γbe an ex ensi e game. The s a egy p o ile σis a i ually subgame pe ec
equilib ium o Γi o each σ- ele an subgame Γx, hen σxis a Nash equilib ium o Γx.
Le SPE(Γ) and VSPE(Γ) deno e he se s o SPE and VSPE o game Γ, espec i ely. By
de ini ion, o each ex ensi e game Γ, we ha e SPE(Γ) ⊆VSPE(Γ). Howe e , he ecip ocal is
no ue as he ollowing example illus a es.
Example 3.1. Conside he ex ensi e game depic ed in Figu e 3.1.
Le σ=(D1, ai
1),(D2, ai
2), wi h i∈ {1,2}. Clea ly, since he subgame ha begins a e
playing (U1, U2)is σ-i ele an , σis a VSPE. Howe e , his game does no ha e any SPE (in
pu e s a egies). Mo eo e , he equilib ium σis a sensible one.
Nex , we poin ou one mo e ela ion be ween SPE and VSPE. Le Γbe an ex ensi e game.
Le σand ˆσbe wo s a egy p o iles o Γ. Now, le ¯σbe he s a egy p o ile which consis s o
playing in acco dance wi h σin he σ- ele an subgames and in acco dance wi h ˆσelsewhe e.
Then, he ollowing s a emen s hold:
(i) The payo s associa ed wi h σand ¯σcoincide ( hey de ine he same pa h).
(ii) I σ∈VSPE(Γ), hen ¯σ∈VSPE(Γ).
(iii) I σ∈VSPE(Γ) and ˆσ∈SPE(Γ), hen ¯σ∈SPE(Γ).
38 Chap e 3. Unila e al Commi men s in Repea ed Games
1
2
1
2
(1,1)
(1,0)
(0,1)
(1,-1)
(-1,1)
(-1,1)
(1,-1)
U1
D1
U2
D2
U2
D2
a1
1
a2
1
a1
2
a2
2
a1
2
a2
2
Figu e 3.1: A game wi hou SPE, bu wi h VSPE.
Rema k. In his Chap e we s udy a special amily o mul is age games wi h obse ed ac ions.
The main eason why we need he concep o VSPE is ha we wo k wi h pu e s a egies. Hence,
al hough we mainly deal wi h ini e ex ensi e games wi h pe ec ecall, we canno apply he
gene al esul s o he exis ence o subgame pe ec equilib ia.
3.2.2 Unila e al Commi men s
The main objec i e o his Chap e is o s udy he e ec o unila e al commi men s on he
appea ing o cons uc i e beha io in epea ed games. Gi en a game G, he co esponding game
wi h unila e al commi men s consis s o adding an ini ial s age o G; in his new s age each playe
can commi no o play ce ain s a egies o game G. Mo eo e , hese commi men s a e made
simul aneously and unila e ally. The ac ha he commi men s ha e o be unila e al is qui e
impo an ; i playe s could condi ion hei commi men s on he commi men s o he o he s, hen
we would be in a comple ely coope a i e model, and hence, he playe s could easily achie e in
equilib ium he coope a i e payo s o he game.
The p oblem o unila e al commi men s, hence o h UC, has al eady been ackled in Ga cía-
Ju ado e al. (2000). They ob ained a Nash olk heo em o ini ely epea ed games wi h UC. In
his Chap e we deepen a li le bi mo e in he impac o UC in he assump ions needed o he
olk heo ems. Nex , ollowing Ga cía-Ju ado e al. (2000), we o mally de ine he UC-ex ension
o a game.
Gi en a game G= (N, A, ϕ), we de ine he UC-ex ension o G,U(G), as ollows. The e
is a p elimina y s age in which playe s choose, simul aneously and independen ly, a nonemp y
subse o hei se s o s a egies. Fo mally, each playe i∈Nchooses Ac
i⊆Ai, whe e Ac
ihas
o be a compac se . This elec ion is in e p e ed as a commi men o play s a egies only in Ac
i.
Then, his p elimina y s age ends and he commi men s o he playe s, Ac, a e made public, i.e.,
hey become common knowledge. Finally, a educed e sion o game Gin which playe s ha e
o espec hei commi men s is played. No e ha , as we ha e al eady poin ed ou , his kind o
3.3. The Folk Theo ems 39
commi men s a e unila e al because we do no allow hem o be condi ional on he o he playe s’
commi men s. The compac ness assump ion o he se s Ac
i esponds, as usually, o echnical
easons; i ensu es ha he subgames s a ing a e he s age o commi men s belong o he class
o games de ined a he beginning o his Sec ion. No e ha , in he pa icula case in which he
se s o s a egies o he game unde conside a ion a e ini e, he compac ness equi emen imposes
no es ic ion a all. Th oughou he es o his Sec ion, wi h a sligh abuse o no a ion, gi en a
se A, we use 2A o deno e he se o compac subse s o A. Now, U(G) := (N, AU, ϕU), whe e:
The se o playe s N emains he same.
AU:= Qi∈NAU
i, whe e AU
iis he se o all couples (Ac
i, αi)such ha
(i) ∅(Ac
i⊆Ai,
(ii) αi:Qj∈N2Aj−→ Aiand, o each Ac∈Qj∈N2Aj,αi(Ac)∈Ac
i.
The payo associa ed wi h a s a egy p o ile (Ac, α)is ϕU(Ac, α) := ϕ(α(Ac)).
3.3 The Folk Theo ems
The appea ing o cons uc i e beha io in epea ed games has been widely ea ed in he game
heo e ical li e a u e.3Gi en a game G, he classic Nash olk heo em o ini ely epea ed games
(Benoî and K ishna, 1987) s a es ha i he game Gis such ha , o each playe i, he e a e wo
Nash equilib ia ha gi e idi e en payo s, hen e e y easible and indi idually a ional payo
o Gcan be app oxima ed by a Nash equilib ium o G(δ, T ) o big enough Tand δclose enough
o 1. Recen ly, González-Díaz (2003) in oduced a new condi ion, namely ha he game Gis
decomposable as a comple e minimax-be e ing ladde ; his new condi ion, besides being weake
han he o me , u ned ou o be bo h necessa y and su icien o he ini e ho izon Nash olk
heo em.
Nex , we s a e and p o e a Nash olk heo em o ini ely epea ed games wi h unila e al
commi men s. This esul , Theo em 3.1, is a a ia ion o he main esul in Ga cía-Ju ado e al.
(2000) o place i wi hin ou amewo k. Mo e p ecisely, he e we deal wi h u ili ies ins ead o wi h
p e e ences, we allow o discoun s, and we conside he se Fins ead o he se {ϕ(a) : a∈A}.
We assume public andomiza ion: a each s age o he epea ed game, he playe s can le hei
ac ions depend on he ealiza ion o an exogenous con inuous andom a iable. The assump ion
o public andomiza ion is wi hou loss o gene ali y. Gi en a co ela ed ac ion, i s payo can be
app oxima ed by al e na ing ac ions wi h he app op ia e equencies. Mo e p ecisely, o each
u∈Fand each ε > 0, he e a e ac ions a1,...,alsuch ha ||u−(a1+. . . +al)/l|| < ε. Hence,
i he discoun pa ame e δis close enough o 1, he same inequali y is s ill ue i we conside
discoun ed payo s. Then, since we s a e Theo em 3.1 in e ms o app oxima ed payo s, public
andomiza ion assump ion can be dispensed wi h.4
3Re e o Benoî and K ishna (1996) o a comple e su ey on he opic.
4Fo u he discussion on public andomiza ion e e o Fudenbe g and Maskin (1991) and Olszewski (1997).
40 Chap e 3. Unila e al Commi men s in Repea ed Games
Theo em 3.1. Le G= (N, A, ϕ)and le be i s minimax payo ec o . Le u∈F,u > .
Then, o each ε > 0, he e a e δ0∈(0,1) and T0∈Nsuch ha o each δ∈[δ0,1] and each
T≥T0, he game U(G(δ, T)) has a Nash equilib ium payo wsuch ha kw−uk< ε.
P oo . Le G= (N, A, ϕ). Le u∈Fand le ¯a∈Abe a (possibly co ela ed) ac ion p o ile such
ha ϕ(¯a) = u. Now, o each δ∈(0,1] and each T∈N, le G(δ, T ) = (N, S, ϕδ). We de ine he
ollowing s a egy p o ile (¯
Sc,¯α)o U(G(δ, T)):
(i) Fo each i∈N,¯
Sc
i:= “I ¯ais played in he i s s age, hen I play ¯ai o e e ”.
(ii) Fo each i∈Nand each Sc∈Qj∈N2Sj, we de ine ¯αi(Sc)as ollows:
I Sc=¯
Sc:
–iplays ¯aiin he i s s age.
–I ¯ais played in he i s s age, hen iplays ¯ai o e e .
–I in he i s s age only playe j6=ihas de ia ed om ¯a, hen, iplays (p−j)i
o e e .
–O he wise, iplays ad libi um.
I Sc= (Sc
j,¯
Sc
−j), whe e j6=iand Sc
j6=¯
Sc
j:iplays (p−j)i o e e .
O he wise: iplays ad libi um.
No e ha ϕc(¯
Sc,¯α) = ϕδ(¯α(¯
Sc)) = ϕ(¯a) = u. Fo each i∈N, le Tibe such ha Tiui>
µi(¯a−i)+ (T−1) iand le δi∈(0,1) be such ha PTi
=1 δ −1ui> µi(¯a−i)+ PTi
=2 δ −1 i. Finally,
le T0:= maxi∈NTiand δ0:= maxi∈Nδi.
Now, i is s aigh o wa d o check ha o each δ∈[δ0,1] and each T≥T0, he s a egy
p o ile (¯
Sc,¯α)is a Nash equilib ium o U(G(δ, T)) whose payo wis such ha kw−uk= 0 < ε
(No e ha we ha e ob ained an exac esul , i.e.,w=ubecause o he public andomiza ion
assump ion).5
The main pu pose o he es o his Sec ion is o s a e and p o e a subgame pe ec olk
heo em wi h UC. The ick o he p oo o Theo em 3.1, in which he s a egies co esponding
wi h many subgames we e de ined ad libi um, does no wo k o subgame pe ec ion. Mo eo e ,
when dealing wi h unila e al commi men s, we ace ex emely la ge game ees. They ha e many
subgames, some o which may co espond o senseless commi men s. Thus, we need o use he
VSPE concep ins ead o he classical SPE. Theo em 3.1 says ha , when unila e al commi men s
a e possible, no condi ion is needed o he Nash olk heo em o hold. No e ha he Nash
equilib ium p o ile (¯
Sc,¯α)de ined in he p oo o Theo em 3.1 is nei he a SPE no a VSPE; his
is because, in gene al, he punishmen s o a playe who de ia es om he commi men a e no
c edible. Now, P oposi ion 3.1 shows ha no only he p oo o Theo em 3.1 ails when we w i e
VSPE ins ead o Nash equilib ium, bu also he esul i sel is alse.
5The eade willing o deepen in o he a gumen s o his p oo is e e ed o Ga cía-Ju ado e al. (2000).
3.3. The Folk Theo ems 41
P oposi ion 3.1. The coun e pa o Theo em 3.1 o VSPE does no hold.
P oo . We do he p oo by means o an example. Le G= (N, A, ϕ)be he game de ined in
Figu e 3.2. The game Gdoes no ha e a Nash equilib ium. Mo eo e , = (1,1) and ϕ(U, L) =
L R
U 10,11 1,10
D 11,0 0,1
Figu e 3.2: A coun e example o P oposi ion 3.1
(10,11) > . Howe e , o each T∈Nand each δ∈(0,1],U(G(δ, T)) does no ha e a VSPE.
Suppose, on he con a y, ha he e a e δ∈(0,1] and T∈Nsuch ha (Sc, α)is a VSPE o
U(G(δ, T)). I Sccon ains a unique elemen , hen one o he playe s can change his commi men
o no commi men a all (i.e.,Sc
i=Sii iis such a playe ) and de ia e om he s a egy in he
inal s age. Hence, he e is a las s age in which, acco ding o he pa h de ined by (Sc, α), one o
he playe s is ee o play any ac ion. Le be ha s age and assume, wi hou loss o gene ali y,
ha , ollowing he pa h o (Sc, α), playe 1 can play bo h Uand Da s age . Mo eo e , le x∗
be he co esponding single-node o G(δ, T).
Now, le playe 2 de ia e o he s a egy (¯
Sc
2,¯α2)de ined as ollows: (i) ¯
Sc
2:= “ om s age
+ 1 on, I play acco ding o he pa h de ined by (Sc, α)” and (ii) o each ˆ
Sc
1∈2S1,¯α2(ˆ
Sc
1,¯
Sc
2) :=
α2(Sc). Le ybe he single-node eached a e (Sc
1,¯
Sc
2)is played. By de ini ion, U(G(δ, T ))y
is a ele an subgame. Le now playe 1 de ia e, in U(G(δ, T))y, o he s a egy ¯α1de ined as
ollows: o each ˆ
Sc
2∈2S2,¯α1(Sc
1,ˆ
Sc
2) := α1(Sc). The subgame U(G(δ, T))yis such ha , when
playing acco ding o (α1, α2), he single-node x∗o G(δ, T)is eached again a s age . Hence,
he subgame beginning a he co esponding single-node o U(G(δ, T)), namely x, is ele an o
(Sc, α). Acco ding o he commi men s, bo h playe s can choose hei wo ac ions a xand, om
he s age + 1 on, playe 2’s ac ions a e de e mined by he commi men . Now, i is immedia e o
check ha he ele an subgame U(G(δ, T))xdoes no ha e any Nash equilib ium. Hence, (Sc, α)
canno be a VSPE.
In he coun e example we used in he p oo abo e, we de ined a game Gwi h no Nash equi-
lib ium. Mo eo e , o each T∈Nand each δ∈(0,1], he game G(δ, T )did no ha e any Nash
equilib ium. On he o he hand, we ha e he ollowing posi i e esul conce ning he exis ence o
VSPE o games wi h UC.
P oposi ion 3.2. Le G= (N, A, ϕ)and le ¯a∈Abe a Nash equilib ium o G. Then, he game
U(G)has a VSPE (¯
Ac,¯α)wi h payo ϕ(¯a).
P oo . Le (¯
Ac,¯α)be such ha o each i∈N, we ha e
(i) ¯
Ac
i={¯ai},
(ii) o each j6=iand each Ac
j∈2Aj,¯αi(¯
Ac
−j, Ac
j) = ¯ai. Finally, o each Ac
i∈2Ai,
¯αi(¯
Ac
−i, Ac
i) = ˆai, whe e ˆai∈a gmaxai∈¯
Ac
i{ϕi(¯a−i, ai)}.

42 Chap e 3. Unila e al Commi men s in Repea ed Games
I is immedia e o check ha each such s a egy p o ile (¯
Ac,¯α)is a VSPE o U(G).
In iew o P oposi ion 3.2, i is clea ha e e y Nash olk heo em o ini ely epea ed
games can be easily adap ed o p o ide a subgame pe ec olk heo em o ini ely epea ed
games wi h unila e al commi men s. Mo e p ecisely, he necessa y and su icien condi ion o
he Nash olk heo em in González-Díaz (2003), “ ha he game is decomposable as a comple e
minimax-be e ing ladde ”, is a su icien condi ion o he VSPE olk heo em wi h UC. The
o me condi ion implies among o he hings, he exis ence o a Nash equilib ium in he s age
game G; his implica ion is all we use in his Chap e . Example 3.2 shows ha such condi ion is
no necessa y.
Example 3.2. Le G= (N, A, ϕ)be he game de ined in Figu e 3.3.
L M R
U 10,10 0,1 1,0
D 11,0 1,1 0,2
Figu e 3.3: A game wi hou Nash equilib ia
The game Gdoes no ha e a Nash equilib ium. Hence, Gi is no decomposable as a comple e
minimax-be e ing ladde . Mo eo e , = (1,2). Now, o each T∈Nand each δ∈(0,1], he
payo (10,10) can be suppo ed by a VSPE o U(G(δ, T)) = (N, SU, ϕU). To check his asse ion,
conside he s a egy p o ile (¯
Sc,¯α)o U(G(δ, T)) de ined as ollows: (i) ¯
Sc
1:= “I play Uin e e y
s age”, (ii) ¯
Sc
2:= “I ne e play R”, and (iii) o each i∈ {1,2}and each Sc
i∈2Si,¯α(¯
Sc
−i, Sc
i)
consis s o playing, a each s age, he unique Nash equilib ium o he co esponding one s age
game. Then, (¯
Sc,¯α)is a VSPE and ϕU(¯
Sc,¯α) = (10,10).
P oposi ion 3.2 says ha we can use he UC o make ac ions c edible, e en ac ions ha in he
o iginal game could be domina ed. On he o he hand, Example 3.2 shows ha we can use he UC
o go u he han ha . Hence, some mo e esea ch is needed o ind new su icien condi ions o
he VSPE olk heo em; condi ions weake han he exis ence o a comple e minimax-be e ing
ladde . Al hough we ha e made some esea ch in his speci ic issue, we ha e no ound any
sa is ac o y condi ion. Ne e heless, we ha e ound he ollowing esul , which, wi h he aid o
P oposi ion 3.2, is s aigh o wa d.
Theo em 3.2. Le G= (N, A, ϕ)and le be i s minimax payo ec o . Le u∈F,u > .
Then, o each ε > 0, he e a e δ0∈(0,1) and T0∈Nsuch ha o each δ∈[δ0,1] and each
T≥T0, he game U(U(G(δ, T))) has a VSPE wi h payo wsuch ha kw−uk< ε.
P oo . Immedia e om he combina ion o Theo em 3.1 and P oposi ion 3.2.
Theo em 3.2 implies ha , when wo s ages o commi men s a e possible, any easible and
indi idually a ional payo o he o iginal game can be achie ed as a VSPE o he epea ed
game wi h unila e al commi men s. No assump ion is needed o he o iginal game, no e en he
exis ence o a Nash equilib ium.
3.3. The Folk Theo ems 43
Nex , we b ie ly discuss he impac o Theo em 3.2 wi hin he delega ion amewo k discussed
in he In oduc ion. Fi s , om he poin o iew o ou model wi h unila e al commi men s,
he game U(U(G(δ, T))) can be di icul o mo i a e. I is ue ha we ge a e y s ong esul
o he se o equilib ium payo s o his game, bu he ac ha we allow o commi men s
on commi men s migh ha e unna u al ea u es in some models. The poin is ha , when we
in oduced unila e al commi men s, we emphasized he ac ha hey we e unila e al, i.e., he
commi men s o one playe could no be condi ional on he o he playe s’ commi men s; i we allow
o wo s ages o commi men s, hen we a e indi ec ly allowing o commi men s on commi men s,
and hence, we achie e he same payo s we could ge wi h a coope a i e model. On he o he hand,
i we eassess he delega ion si ua ion co esponding wi h ou unila e al commi men s model, and
we do i in a simila way o ha in he In oduc ion, hen we ha e he ollowing in e p e a ion
o he wo s ages o commi men s. Conside a si ua ion in which wo i ms a e engaged in a
compe i i e si ua ion. Ini ially, he playe s a e he p esiden s, and hence, in he i s s age each
p esiden signs a con ac wi h his p incipal in which he la e is commi ed no o play ce ain
s a egies and he will be paid p opo ionally o he payo he inally ge s. Then, in a second
s age, a simila con ac is signed be ween each p incipal and his agen . Finally, he agen s play
he o iginal game bu hono ing he commi men s. This si ua ion has some impo an di e ences
wi h he one s age si ua ion: (i) he commi men s ha he p esiden includes in he con ac
in he i s s age can ake in o accoun he commi men s ha he p incipal will make wi h he
agen a s age wo, i.e., he con ac be ween each p esiden and his p incipal also commi s he
la e on he commi men s he can sign wi h his agen , (ii) in he second s age he p incipals,
being consis en wi h he commi men s o hei con ac wi h he p incipals and in iew o he
commi men s made by he i als, choose a new commi men o he agen s, i.e., a commi men on
he commi men , and (iii) inally, he agen s ha e o play being consis en wi h all he p e ious
commi men s. The hie a chical delega ion model we ha e jus desc ibed is qui e na u al and i
is no di icul o hink o eal li e si ua ions wi h hese sub-delega ion s uc u es. Hence, i such
si ua ions also co espond o some epea ed game, hen Theo em 3.2 says ha , ega dless o he
p ope ies o he unde lying s age game, he “coope a i e” (collusi e) payo s can be suppo ed
as a VSPE in he game wi h wo s ages o commi men s.
3.3.1 In ini ely Repea ed Games
Al hough we ha e no o mally in oduced he model wi h in ini ely epea ed games, he de ini-
ions can be immedia ely ex ended o encompass also his amily o games; basically, eplacing T
by ∞in he de ini ion o his o y and in he subsequen ones. Now, wi hin his new amewo k,
P oposi ion 3.2 s ill ca ies o e . Now, ecall ha he classic Nash olk heo em o in ini ely e-
pea ed games (see, o ins ance, Fudenbe g and Maskin (1986)) s a es ha , i he discoun is close
enough o 1, e e y easible and indi idually a ional payo can be achie ed as a Nash equilib ium
o he in ini ely epea ed game. Hence, i we combine his classic esul wi h P oposi ion 3.2 we
ge he ollowing Co olla y:
44 Chap e 3. Unila e al Commi men s in Repea ed Games
Co olla y 3.1. Le G= (N, A, ϕ)and le be i s minimax payo ec o . Le u∈F,u > .
Then, he e is δ0∈(0,1) such ha o each δ∈[δ0,1] he game U(G(δ, ∞)) has a VSPE wi h
payo u.
P oo . I is immedia e om he combina ion o P oposi ion 3.2 wi h he classic Nash olk heo em
o in ini ely epea ed games.
3.3.2 The S a e o A
Table 3.1 summa izes he esul s we ha e p o ed in his Chap e along wi h he classic olk
heo ems o epea ed games wi h comple e in o ma ion. In pa icula , i shows he s eng h o
P oposi ion 3.2, ha allows o ob ain many olk heo ems o epea ed games wi h unila e al
commi men s as immedia e co olla ies o he classic ones. Hence, by looking a Table 3.1, one
easily unde s ands he s eng h o unila e al commi men s wi hin his amewo k. No e ha
all he cells in he Table con ain necessa y and su icien condi ions, all o hem bu he one
co esponding wi h he i ual subgame pe ec olk heo em o ini ely epea ed games wi h
unila e al commi men s; some mo e esea ch is s ill needed conce ning his case.
Wi hou UC 1 s age o UC 2 s ages
o UC
Nash Theo em None None None
In ini e Ho izon (Fudenbe g and Maskin, 1986) (P op. 3.2) (P op. 3.2)
(Vi ual) Pe ec Th. Non-Equi alen U ili ies None None
In ini e Ho izon (Ab eu e al., 1994) (P op. 3.2) (P op. 3.2)
Nash Theo em Minimax-Be e ing Ladde None None
Fini e Ho izon (González-Díaz, 2003) (Ga cía-Ju ado e al., 2000) (P op. 3.2)
(Vi ual) Pe ec Th. Recu si ely-dis inc Minimax-Be e ing Ladde None
Fini e Ho izon Nash payo s (Smi h, 1995) (P op. 3.2, only su icien ) (Th. 3.2)
Table 3.1: Necessa y and Su icien condi ions o he olk heo ems
3.4 Concluding Rema ks
In his Chap e we ha e deepened in he li e a u e o commi men s. Mo e speci ically, we ha e
s udied he impac o unila e al commi men s in he olk heo ems o epea ed games.
We wan o emphasize again he ollowing ac . Because o he way we ha e modeled unila e al
commi men s, i could seem ha hey a e e y a om he mo e s anda d models o commi men
ia delega ion. Bu , as we poin ed ou in he In oduc ion and in he discussion o Theo em 3.2,
unila e al commi men s can be used o model si ua ions in which he e is a p incipal who signs a
con ac wi h his agen wi h wo na u al ea u es: (i) The agen has commi ed no play ce ain
s a egies and (ii) among he emaining ones his payo is p opo ional o ha o he p incipal,
i.e., he agen can be hough o as a sha eholde o he i m.
3.4. Concluding Rema ks 45
Mo eo e , we ha e shown ha unila e al commi men s ha e e y s ong implica ions wi hin
he li e a u e o epea ed games wi h comple e in o ma ion. They lead o new olk heo ems in
which he assump ions needed o he classic esul s ha e been no ably elaxed.
Finally, he e a e se e al open ques ions ha should be ackled in he u u e. One o hem
is o e ine he condi ions o he ini e ho izon pe ec olk heo em wi h unila e al commi -
men s. The e is ano he impo an issue whe e some esea ch is needed: he impac o unila e al
commi men s in epea ed games wi h incomple e in o ma ion.
52 Chap e 4. A Noncoope a i e App oach o Bank up cy P oblems
Suppose ha he p o ile α∗is a Nash equilib ium and ha , o some ixed i, j ∈N, we ha e
α∗
j> α∗
iand mi> α∗
i. I πj(α∗) = 0, hen playe jcan ensu e o himsel a posi i e payo wi h
he s a egy ε, o εsmall enough. Hence, πj(α∗)mus be posi i e. Now, playe ican ob ain a
g ea e payo by swi ching o s a egy α′
i∈(α∗
i,min{α∗
j, mi}); playe ihas s ill a lowe index
han playe jand, since iis inc easing, his payo inc eases. Hence, i α∗is a Nash equilib ium
and α∗
j> α∗
i o some i, j ∈N, we ha e α∗
i=mi.Combining his wi h he ac ha ρis he
unique posi i e eal numbe o which F(ρ) = E, we ge ha he s a egies α∗
i= min{ρ, mi}
de ine a Nash equilib ium.
No e ha he e can exis j∈N, such ha o each i6=j, (i) α∗
i=mi, and (ii) α∗
j> α∗
i; in
his case playe jcan change his s a egy o a new αj> α∗
j, ob aining a new Nash equilib ium
o he game. None heless, he payo emains unchanged.
Case 2: Func ions ia e dec easing.
Take again he unc ion F, now we ha e (i) F(0) = Pi∈Ndi> E and (ii) F(maxi∈N{mi}) = 0.
De ine again ρas he unique eal numbe in (0,maxi∈N{mi})such ha F(ρ) = E. The si ua ion
is simila o he case wi h inc easing unc ions: he p o ile α∗wi h α∗
i= min{ρ, mi}is again a
Nash equilib ium.
Again, suppose ha πi(α∗) = 0 o some i∈N. In his si ua ion, i playe ichanges his
s a egy, no ma e how, he new p o ile is s ill a Nash equilib ium. None heless, he payo
emains unchanged.
Mo eo e , all he Nash equilib ia in he P oposi ion abo e a e in ac s ong equilib ia, as he
ollowing P oposi ion shows.
P oposi ion 4.2. Le (N, E, d)be a bank up cy p oblem, hN, D, πian associa ed noncoope a i e
bank up cy game, and α∗a s a egy p o ile. Then, unde Axioms 4.1 and 4.2, α∗is a Nash
equilib ium i and only i α∗is a s ong equilib ium.
P oo . Since a s ong equilib ium is a Nash equilib ium only one implica ion has o be p o ed.
Assume ha he unc ions ia e inc easing. Suppose ha α∗is a Nash equilib ium which is
no s ong. Then, he e a e T⊆Nand αT∈Qj∈TDjsuch ha o each j∈T,πj(α∗)<
πj(α∗
N T, αT). By P oposi ion 4.1, he e is ρsuch ha o each i∈N,α∗
i= min{ρ, mi}.
Mo eo e , i is easy o check ha , o each i∈N,πi(α∗) = i(α∗
i). Now, o each j∈T,
j(αj)≥πj(α∗
N T, αT)> πj(α∗) = j(α∗
j).
Hence, αj> α∗
j. Hence, α∗
j< mj. Hence, α∗
j=ρand αj> ρ. Now, since o each i∈N T,
α∗
i≤ρ, hen o each j∈Tand each i∈N T, we ha e αj> α∗
i. Hence, o each i∈N T,
πi(α∗
N T, αT) = i(α∗
i) = πi(α∗). Since Pi∈Nπi(α∗
N T, αT)≤E, hen canno be he case ha ,
o each j∈T,πj(α∗)< πj(α∗
N T, αT). In he dec easing case, a simila a gumen can be
o mula ed.

4.3. Bank upc y Games and Bank up cy Rules 53
4.3 Bank upc y Games and Bank up cy Rules
Now, we illus a e how he esul s in Sec ion 4.2 apply o he s anda d bank up cy ules.
The p opo ional ule,P, which is p obably he bes known and mos widely used solu ion
concep , dis ibu es awa ds p opo ionally o claims. I is de ined as ollows: o each (N, E, d),
P(N, E, d) = λd, wi h λ=E
P
i∈Ndi.I is easy o see ha , i we ake, o each i∈N,Di= [0,1]
and i(αi) = αidi, hen he (unique) Nash equilib ium o he game p oduces he p opo ional
solu ion o he bank up cy p oblem.
The cons ained equal-awa ds ule, A, applies an egali a ian p inciple on he awa ds ecei ed,
p o ided no playe ge s mo e han he claims. I is de ined as ollows: o each (N, E, d)and each
i∈N,Ai(N, E, d) = min{di, λ}, whe e λsol es Pi∈Nmin{di, λ}=E. By le ing Di= [0, di]
and i(αi) = αi,we ge he cons ained equal awa ds solu ion as he unique Nash equilib ium o
he associa ed bank up cy game.
The cons ained equal-loss ule,L, is he dual o he la e . I dis ibu es equally he di e ence
be ween he amoun a ailable and he agg ega e claims, wi h one p o iso: no playe ends up wi h a
nega i e ans e . Namely, Li(N, E, d) = max{0, di−λ},whe e λsol es Pi∈Nmax{0, di−λ}=E.
Taking Di= [0, di]and de ining i(αi) = di−αi,we ob ain he cons ained equal-losses solu ion
as he Nash equilib ium payo o he game.
Aumann and Maschle (1985) in oduced he Talmud ule as he consis en ex ension o he
con es ed ga men ule. I is de ined as ollows: o each (N, E, d)and each i∈N, Ti(N, E, d) =
min{1
2di, λ}i E≤1
2Pi∈Ndi,and Ti(N, E, d) = max{1
2di, di−µ}i E≥1
2Pi∈Ndi,whe e λ
and µa e chosen such ha Pi∈NTi(N, E, d) = E. I we le Di= [0, di]and
i(αi) = (1
2αiE≤1
2Pi∈Ndi
1
2di−αiE≥1
2Pi∈Ndi,
he Nash equilib ium payo o he game yields he alloca ion co esponding o he Talmud ule.
Mo e gene ally, i we le Di= [0, di]and
i(αi) = (θαiE≤θPi∈Ndi
θdi−αiE≥θPi∈Ndi,
we gene a e he solu ions co esponding o he TAL- amily (Mo eno-Te ne o and Villa , 2003)
which encompasses he cons ained equal awa ds, he cons ained equal losses, and he Talmud
ule.1
These esul s illus a e on he applicabili y o his p ocedu e o p o ide a noncoope a i e sup-
1The TAL- amily consis s o all ules wi h he ollowing o m: he e is θ∈[0,1] such ha o each bank up cy
p oblem (N, E, c)and each i∈N,
Rθ
i(N, E, d) =

min {θdi, λ}E≤θ
P
i∈Ndi
max {θdi, di−µ}E≥θ
P
i∈Ndi,
whe e and λand µa e chosen such ha
P
i∈NRθ
i(N, E, d) = E.
54 Chap e 4. A Noncoope a i e App oach o Bank up cy P oblems
po o he bes known bank up cy ules. Bu hese esul s can ac ually be ex ended o i ually
any meaning ul ule. Conside now he ollowing de ini ion which in oduces an ex emely mild
equi emen on bank up cy ules:
De ini ion 4.1. A bank up cy ule Ris called accep able i he e a e no bank up cy p oblem
(N, E, d)and playe s i, j ∈Nsuch ha Ri(N, E, d) = 0 and Rj(N, E, d) = dj.
Accep able ules a e hose which ne e concede a playe his claim in ull whe eas some o he
playe ge s no hing. Mos o he ules which ha e been s udied in he li e a u e a e accep able.
The ollowing p oposi ion shows ha o all accep able bank up cy ules he e is a bank-
up cy game whose equilib ium payo coincides wi h he alloca ion p oposed by he selec ed
ule. Fo mally:
P oposi ion 4.3. Le R be an accep able bank up cy ule and (N, E, d)a bank up cy p oblem.
Then, he e is a noncoope a i e bank up cy game hN, D, πi, sa is ying Axioms 4.1 and 4.2, whose
unique equilib ium payo coincides wi h R(N, E, d).
P oo . The p oo consis s o showing ha we can de ine se s o s a egies Diand unc ions iin
such a way ha he esul is a consequence o P oposi ion 4.1.
Le (N, E, d).To simpli y no a ion we w i e Riins ead o Ri(N, E, d).Since he ule is ac-
cep able, ei he o each i∈N,Ri>0, o o each i∈N,Ri< di. Nex , we de ine he se s o
s a egies and he unc ions i.
Case 1: Fo each i∈N,Ri>0. Le
mi:= R1
Ri
diand i(αi) := Ri
R1
αi.
I is clea ha he unc ions ia e mono one (in ac , inc easing) and ha , o each i∈N, i
is a bijec ion mapping [0, mi]on o [0, di].
By P oposi ion 4.1, he noncoope a i e bank up cy game has a unique equilib ium payo .
Clea ly, in his case, ρ=R1. Hence, α∗= (R1,...,R1)is a Nash equilib ium (which is, mo eo e ,
s ong by P oposi ion 4.2); i s associa ed payo is R(N, E, d).
Case 2: Fo each i∈N,Ri< di.
The easoning is he same as be o e, excep in ha , now, we de ine:
mi:= d1−R1
di−Ri
diand i(αi) := di−di−Ri
d1−R1
αi.
Now, since (d1−R1, . . . , d1−R1)is a Nash equilib ium o his game and i s associa ed payo
ec o is R(N, E, d), hen P oposi ion 4.1 gi es again he desi ed esul .
4.4. Concluding Rema ks 55
4.4 Concluding Rema ks
We ha e p esen ed in his Chap e a simple and in ui i e game o m which suppo s i ually all
bank up cy ules. The alloca ion p oposed by each ule is ob ained as he unique payo ec o
co esponding o he Nash equilib ium o a speci ic game. In his espec , choosing he ules o
he game (and mos pa icula ly he s a egy space o he playe s) de e mines he bank up cy
ule ha will eme ge.
In e es ingly enough, he game o m ha allows o implemen hose bank up cy ules is a one-
sho game in which e e y playe sends a message conce ning his own awa ds exclusi ely. Those
messages e e o he cu s in hei claims hey migh be eady o accep , gi en hei claims and he
exis ing sho age. The game o m induces an equilib ium in which all playe s choose “ he same”
message. Selec ing he na u e o hose messages (e.g. awa ds, sha es, losses) amoun s o deciding
on he bank up cy ule whose alloca ion will esul ( he equal awa ds- ule, he p opo ional ule,
he equal-losses ule).
The game o m p oposed he e implici ly assumes ha all he da a o he p oblem a e public
knowledge. In pa icula ha he planne may know bo h he playe s’ claims and he amoun
o di ide. This is a na u al assump ion in mos o he bank up cy si ua ions, whe e claims ha e
o be e en ually c edi ed. The case o axa ion p oblems may be an excep ion in his espec .
Dagan e al. (1999) show ha hose p oblems a e implemen able when all playe s o he han he
planne know all he da a o he p oblem. E en hough his is an a guable assump ion in his
con ex , hey also show an impossibili y esul when his is no he case (see also Co chón and
He e o (2004) on his poin ).
56 Chap e 4. A Noncoope a i e App oach o Bank up cy P oblems
Bibliog aphy
Aumann, R. J. (1959): “Accep able Poin s in Gene al Coope a i e n-Pe son Games,” in Con i-
bu ions o he heo y o games IV, ed. by A. Tucke and R. Luce, P ince on Uni e si y P ess,
287–324. (Quo ed in pp. 51)
Aumann, R. J. and M. Maschle (1985): “Game Theo e ic Analysis o a Bank up cy P oblem
om he Talmud,” Jou nal o Economic Theo y, 36, 195–213. (Quo ed in pp. 53)
Chun, Y. (1989): “A Noncoope a i e Jus i ica ion o he Egali a ia Su plus Sha ing,” Ma he-
ma ical Social Sciences, 17, 245–261. (Quo ed in pp. 48)
Co chón, L. and C. He e o (2004): “A Decen P oposal,” Spanish Economic Re iew, 6,
107–125. (Quo ed in pp. 49, 55)
Dagan, N., R. Se ano, and O. Volij (1997): “A Noncoope a i e View o Consis en Bank-
upc y Rules,” Games and Economic Beha io , 18, 55–72. (Quo ed in pp. 48)
——— (1999): “Feasible Implemen a ion o Taxa ion Me hods,” Re iew o Economic Design, 4,
52–72. (Quo ed in pp. 49, 55)
de F u os, M. A. (1999): “Coali ional Manipula ion in a Ban up cy P oblem,” Jou nal o
Economic Theo y, 4, 255–272. (Quo ed in pp. 49)
He e o, C. (2003): “Equal Awa ds e sus Equal Losses: Duali y in Bank up cy,” in Ad ances
in Economic Design, ed. by M. Se el and S. Ko ay, Sp inge -Ve lag. (Quo ed in pp. 48)
He e o, C., J. D. Mo eno-Te ne o, and G. Pon i (2003): “An Expe imen o Bank-
up cy,” Tech. Rep. Wo king pape AD 2003-03, I ie. (Quo ed in pp. 49)
Ju, B.-G. (2003): “Manipula ion ia Me ging and Spli ing in Claims P oblems,” Re iew o
Economic Design, 8, 205–215. (Quo ed in pp. 49)
Mo eno-Te ne o, J. D. (2004): “Bank up cy Rules and Coali ional Manipula ion,” Tech. ep.,
Yale Uni e si y. (Quo ed in pp. 49)
Mo eno-Te ne o, J. D. and A. Villa (2003): “The TAL-Family o Rules o Ban up cy
P olems,” Tech. ep., Uni e si y o Alican e. (Quo ed in pp. 53)
Moulin, H. (2002): “Axioma ic Cos and Su plus Sha ing,” in Handbood o Social Choice and
Wel a e, ed. by K. A ow, A. Sen, and K. Suzumu a, Else ie Science B.V., ol. 1. (Quo ed in
pp. 48)
O’Neill, B. (1982): “A P oblem o Righ s A bi a ion om he Talmud,” Ma hema ical Social
Sciences, 2, 345–371. (Quo ed in pp. 48)
Se ano, R. (1995): “S a egic Ba gaining, Su plus Sha ing P oblems and he Nucleolus,” Jou -
nal o Ma hema ical Economics, 24, 319–329. (Quo ed in pp. 48)
Sonn, S. (1992): “Sequen ial Ba gaining o Bank up cy P oblems,” P ep in . (Quo ed in pp. 48)
Thomson, W. (2003): “Axioma ic and Game Theo e ic Analysis o Bank up cy and Taxa ion
P oblems,” Ma hema ical Social Sciences, 45, 249–297. (Quo ed in pp. 48)
Pa II
Coope a i e Game Theo y

59
In oduc ion o Coope a i e Game Theo y
This second Pa is de o ed coope a i e game heo y. We se he ocus on he geome y unde lying
some o he bes known solu ion concep s in he TU games li e a u e. We desc ibe he s uc u e
o his Pa below.
The i s h ee Chap e s deal wi h he geome y o he co e o a TU game. Mo e speci ically,
we de ine a new solu ion concep o balanced games, he co e-cen e , which is deeply s udied
in his Pa o he disse a ion. These h ee Chap e s a e based on he pape s González-Díaz
and Sánchez-Rod íguez (2003a,b). In Chap e 5 we o mally in oduce he co e-cen e as he
ba ycen e o he co e and we ca y ou an analysis o he p ope ies sa is ied by his new alloca ion
ule. The main ocus is on he con inui y p ope y, which u ns ou o be a se ious conce n. We
ha e also made an impo an e o s udying he mono onici y p ope ies o he co e-cen e ; he
necessi y o his e o comes om he exis ing nega i e esul s conce ning he possibili y o
de ining mono onic selec ions om he co e o a TU game (Young, 1985; Housman and Cla k,
1998). In Chap e 6 we combine some o he p ope ies s udied in Chap e 5 wi h an addi i i y
p ope y o ob ain an axioma ic cha ac e iza ion o he co e-cen e . Nex , in Chap e 7, we
de elop some ools o es ablish a connec ion be ween he co e-cen e and he Shapley alue
(Shapley, 1953) wi hin he class o con ex games. In his Chap e , we desc ibe he o ma ion
o he co e as he esul o a dynamic p ocess among coali ions. Based on his in e p e a ion,
we de ine he u opia games, a amily o games associa ed wi h each TU game which na u ally
a ise om he men ioned desc ip ion. The u opia games a e he co ne s one o he connec ion
be ween he co e-cen e and he Shapley alue.
Finally, in Chap e 8 we swi ch o he geome y unde lying he τ alue (Tijs, 1981). In his
Chap e , which is based on he pape González-Díaz e al. (2005), we cha ac e ize he τ alue as
he ba ycen e o he edges o he co e-co e o a quasi-balanced game (mul iplici ies ha e o be
aken in o accoun ).
Summa izing, in his second Pa we deepen in he geome y o he TU games. We do i by
es ablishing some connec ions be ween se alued solu ions and alloca ion ules. I is a well known
p ope y o he Shapley alue he ac ha i is he cen e o g a i y o he ec o s o ma ginal
con ibu ions. On he o he hand, he nucleolus is many imes e e ed o as he lexicog aphic
cen e o he co e. These wo “cen al” p ope ies o he Shapley alue and he nucleolus ha e
been used many imes o mo i a e he use o hese wo alloca ion ules. He e, we add wo mo e
“cen al” ela ions, namely, (i) we in oduce he co e-cen e , de ined as he cen e o g a i y o he
co e, and hence, an alloca ion ule occupying a cen al posi ion wi hin he co e and (ii) we show
ha he τ alue lies, in gene al, in a cen al posi ion inside he co e-co e o a quasi-balanced
game.
60 In oduc ion o Coope a i e Game Theo y
Sho Bibliog aphy
González-Díaz, J., P. Bo m, R. Hend ickx, and M. Quan (2005): “A Geome ic Cha ac-
e isa ion o he Comp omise Value,” Ma hema ical Me hods o Ope a ions Resea ch, 61. (Quo ed
in pp. 59)
González-Díaz, J. and E. Sánchez-Rod íguez (2003a): “The Co e-Cen e and he Shapley
Value: A Compa a i e S udy,” Repo s in S a is ics and Ope a ions Resea ch 03-10, Uni e si y
o San iago de Compos ela. (Quo ed in pp. 59)
——— (2003b): “F om Se -Valued Solu ions o Single-Valued Solu ions: The Cen oid and he
Co e-Cen e ,” Repo s in S a is ics and Ope a ions Resea ch 03-09, Uni e si y o San iago de
Compos ela. (Quo ed in pp. 59)
Housman and Cla k (1998): “Co e and Mono onic Alloca ion Me hods,” In e na ional Jou nal
o Game Theo y, 27, 611–616. (Quo ed in pp. 59)
Shapley, L. S. (1953): “A Value o n-Pe son Games,” in Con ibu ions o he heo y o games
II, ed. by H. Kuhn and A. Tucke , P ince on: P ince on Uni e si y P ess, ol. 28 o Annals o
Ma hema ics S udies.(Quo ed in pp. 59)
Tijs, S. (1981): “Bounds o he Co e and he τ-Value,” in Game heo y and ma hema ical
economics, ed. by O. Moeschlin and D. Pallaschke, Ams e dam: No h Holland Publishing
Company, 123–132. (Quo ed in pp. 59)
Young, H. (1985): “Mono onic Solu ions o Coope a i es Games,” In e na ional Jou nal o
Game Theo y, 14, 65–72. (Quo ed in pp. 59)
Chap e 5
A Na u al Selec ion om he Co e
o a TU game: The Co e-Cen e
Con en s
5.1 Game Theo y Backg ound . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 The Co e-Cen e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.1 A Fai ness P ope y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.3 Mono onici y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.4 Con inui y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.5 Compu a ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 Con inui y o he Co e-Cen e . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.1 The P oblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.2 A New F amewo k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.3 Back o Game Theo y . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.4 Concluding Rema ks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.A Appendix (Classical Resul s) . . . . . . . . . . . . . . . . . . . . . . . 81
5.A.1 The Riesz Rep esen a ion Theo em . . . . . . . . . . . . . . . . . . . . 81
5.A.2 The Weak∗Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.A.3 Lebesgue’s Domina ed Con e gence Theo em . . . . . . . . . . . . . . 82
Bibliog aphy ................................... 84
61
68 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
in he co e, i canno no sa is y coali ional mono onici y when he numbe o playe s is g ea e
han h ee. Hence, he co e-cen e does no sa is y coali ional mono onoci y. Things do no ge
be e i we weaken he mono onici y p ope y in he di ec ion o agg ega e mono onici y.
P oposi ion 5.1. Le n≥4. Then, he co e-cen e does do sa is y agg ega e mono onici y
wi hin he class o balanced games wi h n-playe s.
P oo . The p oo is made by means o an example when n= 4. I n > 4 he example can be
adap ed by adding dummy playe s. Le (N, )∈Gnbe such ha N={1,2,3,4}and is de ined
as ollows:
S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N
(S)0 0 0 0 0 1 1 1 1 0 1 1 1 2 2
Now, C(N, ) = {(0,0,1,1)}and hence, µ(N, ) = (0,0,1,1). Le co(A)s and o he con ex hull
o he se A. Le (N, w)be such ha w(N) = 3 and o each S6=N,w(S) = (S). Then,
S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N
w(S)0 0 0 0 0 1 1 1 1 0 1 1 1 2 3
and
C(N, w) = co{(1,0,1,1),(0,0,2,1),(0,0,1,2),(0,1,1,1),(1,1,1,0),(1,1,0,1),(1,2,0,0)}.
Nex , we p o e ha he co e-cen e does no sa is y agg ega e mono onici y by showing ha
µ3(N, )> µ3(N, w). Le (N, ˆw)be he game de ined as ollows:
S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N
ˆw(S)0 0 0 0 0 1 1 1 1 0 1 1 2 2 3
wi h co e
C(N, ˆw) = co{(1,0,1,1),(0,0,2,1),(0,0,1,2),(0,1,1,1),(1,1,1,0),(1,1,0,1)}.
The game (N, ˆw)only di e s om (N, w)in he alue o he coali ion {1,3,4}. Figu es 5.2
and 5.3 show he co es o (N, w)and (N, ˆw), espec i ely. No e ha , because o he s onge
es ic ion o coali ion {1,3,4},C(N, ˆw)(C(N, w). Now, C(N, ˆw)is symme ic wi h espec
o he poin (0.5,0.5,1,1),i.e.,x∈C(N, ˆw)⇔ −x−(0.5,0.5,1,1)+ (0.5,0.5,1,1) ∈C(N, ˆw).
Hence, µ(N, ˆw) = (0.5,0.5,1,1).
Now, C(N, w) C(N, ˆw)(co{(1,1,1,0),(0,1,1,1),(1,1,0,1),(1,2,0,0)}. Hence, o each x∈
C(N, w) C(N, ˆw),x3≤1. Mo eo e , he olume o he poin s in C(N, w) C(N, ˆw)wi h he
hi d coo dina e smalle han 1 is posi i e. Hence, by he de ini ion o he co e-cen e , since
µ3(N, ˆw) = 1, we ha e µ3(N, w)<1 = µ3(N, ). Hence, he co e-cen e does no sa is y agg ega e
mono onici y.

5.2. The Co e-Cen e 69
1
2
4
3
Figu e 5.2: The co e o he game (N, w)
1
2
4
3
Figu e 5.3: The co e o he game (N, ˆw)
The nucleolus (Schmeidle , 1969) also iola es he h ee mono onici y p ope ies we ha e
s udied so a . Zhou (1991) in oduces he weak coali ional mono onici y and shows ha he
nucleolus sa is ies i . This weakening o he coali ional mono onici y only equi es ha , when
one coali ion imp o es mo ing om (N, w) o (N, )and he e is no di e ence o all he o he
coali ions, hen, he coali ion as a whole (ins ead each playe sepa a ely) has o be be e o in
he alloca ion selec ed o (N, ).
P oposi ion 5.2. The co e-cen e sa is ies weak coali ional mono onici y.
P oo . Le (N, )and (N, w)be wo balanced games as in he de ini ion o weak coali ional
mono onici y, i.e., hey only di e in he ac ha w(T)> (T) o a gi en coali ion T. I
T=N he esul is immedia ely de i ed om he e iciency p ope y. Hence, we can assume
T(N. I C(N, w) = C(N, ) hen µ(N, w) = µ(N, )and Pi∈Tµi(N, w)≥Pi∈Tµi(N, ).
Hence, we can assume ha C(N, w)(C(N, ). Le x∈C(N, ) C(N, w)and y∈C(N, w), hen
Pi∈Tyi≥w(T)>Pi∈Txi. Since he co e-cen e is he expec a ion o he uni o m dis ibu ion
o e he co e, and passing om C(N, ) o C(N, w)we ha e emo ed he “bad” alloca ions o
coali ion T(as a whole), his coali ion is be e o in he co e-cen e o (N, w).
Hence, he co e-cen e and he nucleolus ha e an analogous beha io wi h espec o all
mono onici y p ope ies discussed in his Chap e .
5.2.4 Con inui y
When in oducing a new alloca ion ule, one o he i s hings o s udy is whe he i is con inuous
o no . In ui i ely, one could hink ha he cen e o g a i y o he co e o a game (N, ) a ies
con inuously as a unc ion o (N, ). Al hough he esul is ue, ha in ui ion could lead o w ong
a gumen s. The co e is a se - alued mapping om R2n−1 o Rn, and he e is a huge li e a u e
70 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
s udying he p oblem o con inuous selec ion om se - alued mappings (see, o ins ance, Michael
(1956)).
I wo balanced games a e close enough (as ec o s o R2n−1), hen he co esponding co es a e
also close o each o he (as se s). We a e compu ing he cen e o g a i y o hese se s when hey
a e endowed wi h he uni o m dis ibu ion. Hence, he ques ion is: a e also he co esponding
measu es (associa ed wi h he uni o m dis ibu ion) close o each o he ? This p oblem is no
i ial a all. The ollowing example shows wha he p oblem is:
Example 5.1. Conside he iangle wi h e ices (a, 0),(−a, 0) and (0,1). The cen e o g a i y
o his iangle is (0,1/3), no ma e he alue a akes. I we le a end o 0 hen, “in he limi ”,
we ge he segmen joining he poin s (0,0) and (0,1), whose cen e o g a i y is (0,1/2), which
is no he limi o he cen e s o g a i y.
The p oblem wi h he con inui y a ises when he numbe o dimensions o he space unde
conside a ion is no ixed, i.e., an (n−2)-poly ope can be exp essed (as a se ) as he limi o
(n−1)-poly opes. As we ha e shown in he p e ious example, he con inui y p ope y is qui e
sensi i e o his kind o degene a ions. Hence, his p oblem mus be handled ca e ully, aking in o
accoun ha he cen e o g a i y o a con ex poly ope does no necessa ily a y wi h con inui y
i degene a ions a e pe mi ed. E en so, he ollowing s a emen is ue:
Theo em 5.1. The co e-cen e is con inuous.
The p oo o his s a emen is qui e echnical. In Sec ion 5.3 we o mally in oduce he p oblem
along wi h he concep s needed o he p oo .
5.2.5 Compu a ion
The complexi y o he compu a ion o any alloca ion ule is a concep which also needs o be
s udied. He e, we p o ide some insigh s o his p oblem when wo king wi h he co e-cen e . The
compu a ion o he cen e o g a i y o a con ex poly ope is a p oblem which has been widely
s udied in compu a ional geome y. The e a e many nega i e esul s conce ning he complexi y
o his p oblem. In he case o he co e-cen e , e en i we a e gi en a polynomial desc ip ion o
he game (i.e., o he unc ion ), he compu a ion ime can g ow exponen ially wi h he numbe
o playe s. Basically, he e a e wo ways o ob aining he cen e o g a i y o a con ex poly ope.
The classical one consis s o he exac compu a ion; many algo i hms ha e al eady been de eloped
o his issue, bu all o hem a e exponen ial in he numbe o playe s. The second app oach
consis s o using andomizing p ocedu es o es ima e he cen e o g a i y. Roughly speaking,
hese p ocedu es lead o algo i hms which allow o ob ain he es ima ions in polynomial ime
whene e we a e able o ind ou whe he a poin belongs o no o he co e in polynomial ime;
his is no a mild assump ion, bu i canno be dispensed wi h.
5.3. Con inui y o he Co e-Cen e 71
5.3 Con inui y o he Co e-Cen e
5.3.1 The P oblem
Fi s , we in oduce he exac o mula ion o he p oblem o be sol ed. Hence o h, we deno e a
game (N, )by . No e ha in o de o p o e Theo em 5.1 i is enough o show ha o each
balanced game , and each sequence o balanced games con e ging o (unde he usual con e -
gence o ec o s in R2n−1), he associa ed sequence o he co e-cen e s o he games con e ges o
he co e-cen e o . Fo mally,
Theo em 5.2. Le ¯ be a balanced game and { }a sequence o balanced games such ha
lim →∞ = ¯ . Then, lim →∞ µ( ) = µ(¯ ).
Clea ly, Theo ems 5.1 and 5.2 a e equi alen . The nex P oposi ion, which is a weake e -
sion o he p e ious Theo em con ains he di icul pa o he p oo . Theo em 5.2, and hence
Theo em 5.1, a e an easy consequence.
P oposi ion 5.3. Le ¯ be a balanced game and { }a sequence o balanced games such ha
(i) o each ∈N, we ha e ¯ (N) = (N),
(ii) lim →∞ = ¯ .
Then, lim →∞ µ( ) = µ(¯ ).
In con as wi h Theo em 5.2, whe e e e y possible sequence o games is conside ed, P opo-
si ion 5.3 only conce ns speci ic sequences. Nex , we p epa e he g ound o P oposi ion 5.3. We
do i by s a ing and p o ing a gene al esul . Then, P oposi ion 5.3 is easily de i ed. We make
use o some measu e heo y and unc ional analysis esul s, which help us o place ou esul on
a i m basis.
5.3.2 A New F amewo k
Nex , we in oduce a new amewo k in which we s a e and p o e a gene al con e gence esul o
uni o m measu es. Then, he main pa o he p oo o P oposi ion 5.3 is a pa icula case. The
idea o he whole p ocedu e can be summa ized as ollows: whene e we hink abou a balanced
game and i s co e-cen e , we can jus hink o a poly ope (i s co e) and i s cen e o g a i y.
Simila ly, whene e we ha e a poly ope and i s cen e o g a i y, we can jus hink o he uni o m
measu e de ined o e he poly ope and he in eg al o he iden i y unc ion wi h espec o i .
Following his idea, i we wan o p o e ha he co e-cen e o a sequence o games con e ges o
he co e-cen e o he limi game (Theo em 5.2), i is enough o p o e ha he in eg als o e he
co esponding uni o m measu es also con e ge.
72 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
No a ion
A (con ex) polyhed on is de ined as he in e sec ion o a ini e numbe o closed hal spaces. A
polyhed on Pis an m-polyhed on i i s dimension is m,i.e., he smalles in ege such ha P
is con ained in an m-dimensional space. A (con ex) poly ope is a bounded polyhed on. Le
Mm
λs and o he Lebesgue measu e on Rm. Le A⊆Rmbe a Lebesgue measu able se and le
m′≥m; we deno e Mm′
λ(A)by Volm′(A),i.e., he m′-dimensional olume o A; hence, i A⊆Rm
and m′> m, hen, Volm′(A) = 0. Le Pbe an m-poly ope and XPi s cha ac e is ic unc ion;
le MPbe he Bo el measu e such ha MP:= 1
Volm(P)XPMm
λ,i.e., he uni o m measu e de ined
o e poly ope P.
Le ube a ec o in Rm. Le Hu
αbe he ollowing hype plane no mal o u,Hu
α:= {x∈Rm:
Pm
j=1 ujxj=α}. Le BH be he hal space below hype plane H. Le Pbe a poly ope, hen
we say ha hype plane His a suppo ing hype plane o Pi H∩P6=∅and BH con ains P.
Usually, a ace o a poly ope Pis de ined as (i) Pi sel , (ii) he emp y se , o (iii) he in e sec ion
o Pwi h some suppo ing hype plane. Wi h a sligh abuse o language, we use he e m ace o
designa e only (m−1)-dimensional aces o an m-poly ope. Le F(P)be he se o all aces o P
and Fbe an a bi a y ace.
Le Pbe an m-poly ope. Then, he ini e se o poly opes {P1,...,Pk}is a dissec ion o Pi
(i) P=Sk
j=1 Pjand (ii) o each pai {j, j′} ⊆ {1,...,k}, wi h j6=j′,Volm(Pj∩Pj′) = 0.
Nex , we s a e, wi hou p oo , wo elemen al esul s.
Lemma 5.2. Le Pand P′be wo m-poly opes such ha P′⊆P. Then, P′belongs o some
dissec ion o P.
Lemma 5.3. Le Pbe an m-polyhed on, le u∈Rm, and le α, β ∈R. Le P∩Hu
α6=∅and
P∩Hu
β6=∅. Then, P∩Hu
αis bounded i and only i P∩Hu
βis bounded.
Le Pbe an m-poly ope, le > 0be such ha P((− , )m( Rm. Le R:= [− , ]m. The
pai (R, B), whe e Bs ands o he collec ion o Bo el se s o R, is a measu e space. Le M(R)be
he se o all complex- alued egula Bo el measu es de ined on (R, B)and M+(R) he subse o
eal- alued and posi i e Bo el measu es. Also, le C(R)and CR(R)be he se s o all con inuous
unc ions :R→Cand :R→R espec i ely.
As a consequence o he Riesz Rep esen a ion Theo em, C(R)∗=M(R),i.e.,M(R)is he
dual o C(R). This allows us o use he weak∗ opology (hence o h w∗) in M(R). Acco ding
o his opology, a sequence o measu es {M }con e ges o a measu e Mi and only i o each
∈C(R),lim →∞ R dM =R dM. Fo each ∈C(R), and each measu e M∈ M(R),h , Mi
deno es R dM.
Rema k. We apologize o he eade s ha a e no amilia wi h hese concep s. They lead o
a mo e consis en no a ion, cleane s a emen s, and less edious p oo s. Hence o h, con e gence
o a sequence o measu es {M } o a measu e Munde w∗jus means ha , o each con inuous
unc ion , he sequence o eal numbe s ob ained by in eg a ion o unde he M ’s con e ges o
5.3. Con inui y o he Co e-Cen e 73
he in eg al unde M. Mo eo e , o no a ional con enience, we deno e hose in eg als by h , M i
and h , Mi, espec i ely.
The esul s
Nex , we p o e wo echnical lemmas.
Lemma 5.4. Le :R2→Rbe a con inuous unc ion and K( R a compac se . Then, he
unc ion h:R→Rde ined by h(x) := maxy∈K (x, y)is con inuous.
P oo . Suppose, on he con a y, ha his no con inuous. Then, he e is a sequence o eal
numbe s {x }such ha (i) lim →∞ x =x, and (ii) he sequence {h(x )}does no con e ge o
h(x). Le y∗∈Kbe such ha (x, y∗) = maxy∈K (x, y) = h(x).
Fo each ∈N, le y ∈Kbe such ha h(x ) = (x , y ). Since each y ∈K, he sequence
{y }has a con e gen subsequence. Assume, wi hou loss o gene ali y, ha {y }i sel con e ges
and le y′be i s limi . Then,
(x, y∗) = h(x)
assump
6= lim
→∞h(x ) = lim
→∞ (x , y ) con
= (x, y′).
Hence, (x, y∗)> (x, y′). Then, he e is δ > 0such ha
|x −x|< δ
|y −y′|< δ ) con
=⇒ (x , y∗)− (x , y )>0, con adic ing h(x ) = (x , y ).
Co olla y 5.1. Le :Rm→Rbe a con inuous unc ion and K( Rl,1< l < m, a compac
se . Then, he unc ion h:Rm−l→Rde ined by h(x) := maxy∈K (x, y)is con inuous.
P oo . The p oo o Lemma 5.4 can be immedia ely adap ed o his gene al case.
No e ha analogous esul s o Lemma 5.4 and Co olla y 5.1 can be s a ed using min ins ead
o max.
Lemma 5.5. Le M∈ M(R)and le {M }be a sequence o measu es in M(R)such ha o
each ∈CR(R),lim →∞h , M i=h , Mi. Then, o each ∈C(R),lim →∞h , M i=h , Mi.
P oo . Fo each ∈C(R), he e exis unc ions 1and 2in CR(R)such ha o each x∈R,
(x) = 1(x) + 2(x)i. Then,
h , M i=Z dM =Z 1dM +iZ 2dM
→∞
−→ Z 1dM +iZ 2dM =h , Mi.
As a consequence o Lemma 5.5, o p o e a con e gence unde w∗, i su ices o s udy unc ions
in CR(R).
Now we a e eady o s a e he main esul .

74 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
Theo em 5.3. Le Pbe an m-poly ope and Ran m-dimensional cube [− , ]mcon aining Pin
i s in e io . Le u∈Rm. Le ¯α∈Rand le {α }be a sequence in [¯α, ∞)wi h limi ¯α. Le
P := P∩BHu
α and ¯
P:= P∩BHu
¯α. Then, MP
w∗
−→ M¯
P.
P oo . Wi hou loss o gene ali y, we assume ha u=e1= (1,0,...,0) (o he wise a change o
coo dina es can be ca ied ou ) and ha {α }is a dec easing sequence o posi i e numbe s. I ¯
P
is an m-poly ope, he e a e no degene acies and he esul is s aigh o wa d. Hence, we assume
ha ¯
Pis no an m-poly ope. Hence, ¯α= minx∈Px1. Now, we dis inguish wo cases: ¯
Pis an
(m−1)-poly ope, and ¯
Pis an (m−l)-poly ope, wi h l > 1(mul iple degene acy).
Case 1: ¯
Pis an (m−1)-poly ope.
Le Qbe he polyhed on de ined as ollows,
Q:= {y∈Rm:y=x+γe1,whe e x∈¯
Pand γ > 0}.
Now, o each ∈N, we de ine he auxilia y poly opes Q := Q∩BHe1
α . Also, le ¯
Q:=
Q∩BHe1
¯α(see Figu e 5.4). No e ha , by de ini ion, ¯
Q=¯
P.
¯
P
Q −1Q
He1
α
He1
α −1
···He1
¯α
x Q (x)
R
P
Figu e 5.4: The Q poly opes
The p oo is in h ee s eps. In S ep 1 we p o e ha he sequence o measu es induced by
he auxilia y poly opes, {MQ }, con e ges o M¯
Q. In S ep 2, we s udy he ela ions be ween he
olumes o P Q ,Q P , and Q . Finally, in S ep 3 we ob ain he desi ed con e gence esul ,
i.e., ha o he sequence {MP } o M¯
P. Recall ha , by Lemma 5.5, we can es ic ou a en ion
o unc ions in CR(R)whene e we ha e o p o e some con e gence unde w∗.
S ep 1: MQ
w∗
−→ M¯
Q.
We wan o p o e ha o each ∈CR(R),lim →∞h , MQ i=h , M ¯
Qi.
S ep 1.a: Le ∈CR(R)be such ha he e exis s c: [− , ]m−1→Rwi h he ollowing
p ope y: o each x∈[− , ]m, (x) = c(x−1). Le dx−1s and o dx2. . . dxm. Also, o each
5.3. Con inui y o he Co e-Cen e 75
x∈¯
Qand each ∈N, we de ine he 1-poly opes Q (x) := {y∈Q :y−1=x−1}. No e ha , i
x6=x′, hen Q (x)∩Q (x′) = ∅and Vol1(Q (x)) = Vol1(Q (x′)) = α −¯α. Mo eo e , o each
x∈¯
Q, is cons an in Q (x). Then,
h , MQ i=1
Volm(Q )Z¯
QZQ (x)
c(x−1)dx−1dx1
=α −¯α
Volm(Q )Z¯
Q
c(x−1)dx−1
=1
Volm−1(¯
Q)Z¯
Q
c(x−1)dx−1
=h , M ¯
Qi.
S ep 1.b: Le ∈CR(R). De ine he h ee auxilia y unc ions
∗(x1, x−1) := (¯α, x−1),
c (x1, x−1) := max
z∈[¯α,α ] (z, x−1),and
c (x1, x−1) := min
z∈[¯α,α ] (z, x−1).
By Co olla y 5.1, unc ions c and c a e con inuous. Hence, by S ep 1.a, we ha e hc , MQ i=
hc , M ¯
Qiand hc , MQ i=hc , M ¯
Qi. By he con inui y o , o each x∈R,lim →∞ c (x) =
∗(x) = lim →∞ c (x). Le gbe he cons an unc ion such ha o each x∈R,g(x) :=
maxx∈R| (x)|. Since Rg dM ¯
Q= maxx∈R| (x)|,gis Lebesgue in eg able wi h espec o M¯
Q.
Mo eo e , o each x∈R,|c (x)| ≤ g(x)and |c (x)| ≤ g(x). Since MQ ∈ M+(R), hen
hc , MQ i ≤ h , MQ i ≤ hc , MQ i. Now, he Lebesgue’s Domina ed Con e gence Theo em
comple es S ep 1,
hc , MQ i ≤ h , MQ i ≤ hc , MQ i
S ep 1.a
hc , M ¯
Qi
→ ∞ ↓Dom Con
h ∗, M ¯
Qi
∗(x) = (x),x∈¯
Q
h , M ¯
Qi
S ep 1.a
hc , M ¯
Qi
→ ∞ ↓Dom Con
h ∗, M ¯
Qi
∗(x) = (x),x∈¯
Q
h , M ¯
Qi.
Hence, o each ∈CR(R),lim →∞h , MQ i=h , M ¯
Qi.
S ep 2: lim
→∞
Volm(P Q )
Volm(Q )= lim
→∞
Volm(Q P )
Volm(Q )= 0 and lim
→∞
Volm(P )
Volm(Q )= 1.
We show ha lim →∞ Volm(P Q )
Volm(Q )= 0, being he p oo o Q P analogous. By Lemma 5.2,
he e a e poly opes P1
1, . . . , Pk
1,k≥1, such ha {P1
1,...,Pk
1, Q1∩P1}is a dissec ion o P1.
Hence, P1 Q1(∪k
j=1Pj
1= co(P1 Q1). No e ha co(P1 Q1)coincides wi h he closu e o
P1 Q1. Now, o each ∈Nand each j∈ {1,...,k}, le Pj
:= Pj
1∩BHe1
α . Then, o each
76 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
∈N,{P1
,...,Pk
, Q ∩P }is a dissec ion o P and P Q (∪k
j=1Pj
= co(P Q ). Hence,
Volm(P Q )≤Pk
j=1 Volm(Pj
)(ac ually, hey a e equal).
Now, since Volm(Q ) = Volm−1(¯
P)(α −¯α),Volm(Q ) = O(α −¯α),i.e.,Volm(Q )is a linea
unc ion o (α −¯α).1Le j∈ {1,...,k}, since ¯
Q=¯
P,Pj
1∩BHe1
¯αis con ained in some ace
o ¯
P,i.e., i is in he bounda y o ¯
P. Hence, Pj
1∩BHe1
¯αis, a mos , an (m−2)-poly ope.
Hence, i o each ∈N,Pj
is an m-poly ope, we ha e ha , in he limi , he e is, a leas , a
2-dimensional degene acy. Hence, Volm(Pj
) = o((α −¯α)2).2Now, since he numbe o poly opes
in he dissec ion is ini e, we ha e Volm(P Q ) = o((α −¯α)2).
Finally, lim
→∞
Volm(P Q )
Volm(Q )= lim
→∞
o((α −¯α)2)
O(α −¯α)= 0.
We u n now o Volm(P )
Volm(Q ). Since P =Q (Q P )∪(P Q ), and Q (Q P )and P Q a e
disjoin se s, hen Volm(P ) = Volm(Q )−Volm(Q P ) + Volm(P Q ). Hence,
lim
→∞
Volm(P )
Volm(Q )= lim
→∞1−Volm(Q P )
Volm(Q )+Volm(P Q )
Volm(Q )= 1.
S ep 3: MP
w∗
−→ M¯
P.
Z dMP =Z XP
Volm(P )dMm
λ
=1
Volm(P )Z (XQ −XQ P +XP Q )dMm
λ
=Z XQ
Volm(P )dMm
λ−Z XQ P
Volm(P )dMm
λ+Z XP Q
Volm(P )dMm
λ.
We wan o show ha bo h he second and he hi d addend end o 0. We can assume
ha Volm(Q P )6= 0, o he wise, R XQ P dMm
λ= 0 and we a e done wi h he co esponding
addend. Simila ly, we assume ha Volm(P Q )6= 0. Now,
Z dMP =A1−A2+A3,
whe e,
A1=Volm(Q )
Volm(P )Z XQ
Volm(Q )dMm
λ=Volm(Q )
Volm(P )Z dMQ ,
A2=Volm(Q P )
Volm(P )Z XQ P
Volm(Q P )dMm
λ=Volm(Q P )
Volm(P )Z dMQ P ,and
A3=Volm(P Q )
Volm(P )Z XP Q
Volm(P Q )dMm
λ=Volm(P Q )
Volm(P )Z dMP Q .
1We say ha ( ) = O(g( )) i he e a e c1, c2>0and ′∈Nsuch ha , o each > ′,c1|g( )| ≤ | ( )| ≤
c2|g( )|. The no a ion ( ) = o(g( )) means ha he e is c > 0and ′∈Nsuch ha , o each > ′,| ( )| ≤ c|g( )|.
2Jus because, oughly speaking, he olume o a poly ope is a linea unc ion o i s “leng h” in each dimension.
5.3. Con inui y o he Co e-Cen e 77
Since R dMQ P ≤maxx∈R (x)and R dMP Q ≤maxx∈R (x), hen, by S ep 2, bo h A2
and A3 end o 0. We mo e now o A1. By S ep 2, lim →∞ Volm(Q )
Volm(P )= 1. Since, by S ep 1,
lim →∞ R dMQ =R dM ¯
P, we ha e lim →∞ R dMP =R dM ¯
P.
Case 2: ¯
Pis an (m−l)-poly ope, l > 1.
We ha e mul iple degene acy. To s udy his case, new auxilia y poly opes Q and ¯
Qha e o
be de ined, bu he idea o he p oo is he same. Assume ha he degene acies a e in he i s l
componen s. Then, he e exis a1,...,al∈Rsuch ha o each x∈¯
P,x1=a1,...,xl=al. Le
{F1,...,Fk} ⊆ F(P)be he se o he aces o Pcon aining ¯
P; since ¯
Pis an (m−l)-poly ope,
k≥2. Fo each j∈ {1, . . . , k}, le Hjbe he hype plane con aining Fjand assume, wi hou loss
o gene ali y, ha P(BHj. Fo each i∈ {1,...,m}, le ei∈Rmbe he i- h canonical ec o .
Le Qbe he polyhed on de ined as ollows,
Q:= (y∈Rm: o each j∈ {1,...,k}, y ∈BHjand
y=x+Pl
i=1 γiei,whe e x∈¯
Pand, o each i∈ {1,...,l}, γi>0).
Now, o each ∈N, we de ine he auxilia y poly opes Q := Q∩BHe1
α . Also, le ¯
Q:=
Q∩BHe1
¯α(see Figu e 5.5). No e ha , by de ini ion, ¯
Q=¯
P. Since Q ∩He1
¯α=¯
Qis bounded,
applying Lemma 5.3, we ha e ha Q is bounded. Hence, each Q is indeed a poly ope.
Now, all he s eps in Case 1 can be adap ed o he Q ’s. Only some mino (and na u al)
changes ha e o be made. Nex , we go h ough hese s eps, s essing whe e modi ica ions a e
needed.
S ep 1: MQ
w∗
−→ M¯
Q.
S ep 1.a: Le xL:= (x1,...,xl)and x¯
L:= (xl+1,...,xm). Le ∈CR(R)be such ha he e
exis s c: [− , ]m−l→Rwi h he ollowing p ope y: (xL, x¯
L) = c(xL). Also, o each x∈¯
Q
and each ∈N, we de ine he l-poly ope Q (x) := {y∈Q :y−L=x−L}(Figu e 5.6). Again, i
x6=x′, hen Q (x)∩Q (x′) = ∅and Voll(Q (x)) = Voll(Q (x′)) = Volm(Q )
Volm−l(¯
Q). Mo eo e , o each
x∈¯
Q, is cons an in Q (x). The es is analogous o Case 1.
S ep 1.b: Le ∈CR(R). Le ˆx∈¯
Q. Fo each ∈N, we de ine he compac se
K := {z∈Rl:z=yL,whe e (yL, y¯
L) = y∈Q (ˆx)},i.e.,K is he p ojec ion o Q (x)in o Rl.
No e ha he de ini ion o K is independen o he selec ed ˆx∈¯
Q. De ine he h ee auxilia y
unc ions
∗(xL, x¯
L) := (a1,...,al, x¯
L),
c (xL, x¯
L) := max
z∈K
(z, x¯
L),and
c (xL, x¯
L) := min
z∈K
(z, x¯
L).
Wi h hese de ini ions Co olla y 5.1 s ill applies. The es is analogous o Case 1.
S ep 2: lim
→∞
Volm(P Q )
Volm(Q )= lim
→∞
Volm(Q P )
Volm(Q )= 0 and lim
→∞
Volm(P )
Volm(Q )= 1.
84 Chap e 5. A Na u al Selec ion om he Co e o a TU game: The Co e-Cen e
Bibliog aphy
Aumann, R. J. and M. Maschle (1964): “The Ba gaining Se o Coope a i e Games,”
in Ad ances in Game Theo y, ed. by M. D eshe , L. S. Shapley, and A. Tucke , P ince on
Uni e si y P ess, ol. 52 o Annals o Ma hema ical S udies, 443–476. (Quo ed in pp. 62)
Billingsley, P. (1968): Con e gence o P obabili y Measu es, New Yo k: Wiley. (Quo ed in pp. 81)
Conway, J. B. (1990): A Cou se in Func ional Analysis, Sp inge -Ve lag. (Quo ed in pp. 81)
Da is, M. and M. Maschle (1965): “The Ke nel o a Coope a i e Game,” Na al Resea ch
Logis ics Qua e ly, 12, 223–259. (Quo ed in pp. 62)
Du a, B. and D. Ray (1989): “A Concep o Egali a ianism unde Pa icipa ion Cons ain s,”
Econome ica, 57, 615–635. (Quo ed in pp. 65)
Gau ie , S. and R. Mo chadi (1992): “A Selec ion o Con ex-Compac -Valued Mul i-
Func ions wi h Rema kable P ope ies: he S eine Selec ion,” Nume ical Func ional Analysis
and Op imiza ion, 13, 513–522. (Quo ed in pp. 62)
Gillies, D. B. (1953): “Some Theo ems on n-Pe son Games,” Ph.D. hesis, P ince on. (Quo ed
in pp. 62, 64)
González-Díaz, J., P. Bo m, R. Hend ickx, and M. Quan (2005): “A Geome ic Cha ac-
e isa ion o he Comp omise Value,” Ma hema ical Me hods o Ope a ions Resea ch, 61. (Quo ed
in pp. 63)
Housman and Cla k (1998): “Co e and Mono onic Alloca ion Me hods,” In e na ional Jou nal
o Game Theo y, 27, 611–616. (Quo ed in pp. 67)
Maschle , M., B. Peleg, and L. S. Shapley (1979): “Geome ic P ope ies o he Ke nel,
Nucleolus, and Rela ed Solu ion Concep s,” Ma hema ics o Ope a ions Resea ch, 4, 303–338.
(Quo ed in pp. 62, 67)
Michael, E. (1956): “Con inuous Selec ions. I,” The Annals o Ma hema ics, 63, 361–382. (Quo ed
in pp. 62, 70)
Rudin, W. (1966): Real and Complex Analysis, McG aw-Hill. (Quo ed in pp. 81)
Schmeidle , D. (1969): “The Nucleolus o a Cha ac e is ic Func ion Game,” SIAM Jou nal on
Applied Ma hema ics, 17, 1163–1170. (Quo ed in pp. 62, 69)
Shapley, L. S. (1953): “A Value o n-Pe son Games,” in Con ibu ions o he heo y o games
II, ed. by H. Kuhn and A. Tucke , P ince on: P ince on Uni e si y P ess, ol. 28 o Annals o
Ma hema ics S udies.(Quo ed in pp. 62)
Tijs, S. (1981): “Bounds o he Co e and he τ-Value,” in Game heo y and ma hema ical
economics, ed. by O. Moeschlin and D. Pallaschke, Ams e dam: No h Holland Publishing
Company, 123–132. (Quo ed in pp. 62)
on Neumann, J. and O. Mo gens e n (1944): Theo y o Games and Economic Beha io ,
P ince on: P ince on Uni e si y P ess. (Quo ed in pp. 62)

BIBLIOGRAPHY 85
Young, H. (1985): “Mono onic Solu ions o Coope a i es Games,” In e na ional Jou nal o
Game Theo y, 14, 65–72. (Quo ed in pp. 67)
Zhou, L. (1991): “A Weak Mono onici y P ope y o he Nucleolus,” In e na ional Jou nal o
Game Theo y, 19, 407–411. (Quo ed in pp. 69)
Chap e 6
A Cha ac e iza ion o he
Co e-Cen e
Con en s
6.1 In oduc ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.2 Game Theo y Backg ound . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.2.1 The Co e and i s Rela i es . . . . . . . . . . . . . . . . . . . . . . . . 90
6.2.2 Some Geome ic Conside a ions . . . . . . . . . . . . . . . . . . . . . . 90
6.2.3 The Co e-Cen e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.3 Fai Addi i i y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3.1 T-Solu ions and RT -Solu ions . . . . . . . . . . . . . . . . . . . . . . 92
6.3.2 RT -Solu ions and Balanced Games: Fai Addi i i y . . . . . . . . . . 94
6.4 The Cha ac e iza ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4.1 An Elemen al Co e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4.2 The Co e is Full Dimensional . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.3 The Co e is No Full Dimensional . . . . . . . . . . . . . . . . . . . . 104
6.5 Concluding Rema ks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.A Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.A.1 The Geome y o he Co e-Cen e in Dep h . . . . . . . . . . . . . . . 106
Bibliog aphy ...................................109
87
88 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
6.1 In oduc ion
In González-Díaz and Sánchez-Rod íguez (2003), he co e-cen e , a new alloca ion ule o he
class o balanced games is in oduced. Tha pape con ains a i s app oach bo h o he s udy o
he axioma ic p ope ies o he co e-cen e and o he sea ch o an axioma ic cha ac e iza ion.
This Chap e ocuses in he la e . We o mally de elope and e ine he cha ac e iza ion p o ided
he e.
The key p ope y o he cha ac e iza ion is a weigh ed addi i i y, based on a p inciple o
ai ness wi h ega d o he co e, ha we call ai addi i i y. This p ope y, along wi h o he
s anda d p ope ies in game heo y leads o he axioma ic cha ac e iza ion o he co e-cen e . I
has a ce ain pa allelism wi h he cha ac e iza ion o he Shapley alue based on he addi i i y
p ope y. Fi s , we p o e he esul o games wi h a simplicial co e, which play he ole o he
unanimi y games in Shapley’s cha ac e iza ion. Second, we p o e he esul o a bi a y games
by means o simplicial dissec ions o hei co es.
In he ai addi i i y p ope y he weigh s depend on he olumes o he co es. The e a e
an eceden s in game heo y ha look o his kind o ai ness. One o he solu ions o wo pe son
ba gaining p oblems which depends on he whole easible se is he Equal A ea Solu ion. Anba ci
and Bigelow (1994) in e p e ed equal a ea as equal concessions. La e Cal o and Pe e s (2000)
looked a he unde lying dynamic p ocess.
The s uc u e o his Chap e is as ollows. In Sec ion 6.2 we in oduce he p elimina y game
heo e ical concep s along wi h he de ini ion o he co e-cen e . In Sec ion 6.3 we in oduce and
discuss he ai addi i i y p ope y. In Sec ion 6.4 we s a e and p o e he cha ac e iza ion o he
co e-cen e . Finally, in he Appendix we p o ide igo ous p oo s o some echnical s a emen s
which ha e been skipped in he ex ; mo eo e , i also includes o mal de ini ions and p ope ies
o some geome ic concep s used along he Chap e .
6.2 Game Theo y Backg ound
A ans e able u ili y o TU game is a pai (N, ), whe e N:= {1, . . . , n}is a se o playe s
and : 2N→Ris a unc ion assigning o each coali ion S⊆Na payo (S). By con en ion,
(∅) = 0. Since each game assigns a eal alue o each nonemp y subse o N, i co esponds wi h
a ec o in R2n−1. Le |S|be he numbe o elemen s o coali ion S. Sa ing no a ion, when no
ambigui y a ises, we use i o deno e {i}. Gi en a game (N, ), he impu a ion se is de ined by
I(N, ) := {x∈Rn:Pi∈Nxi= (N)and, o each i∈N,xi≥ (i)}.
Le x∈Rnbe an alloca ion. Then, xis e icien i Pn
i=1 xi= (N). A game (N, )is
supe addi i e i o each S, T ⊆Nsuch ha T∩S=∅, we ha e (S∪T)≥ (S) + (T). We
es ic ou a en ion o e icien alloca ions. Wi hin his amewo k, i is widely accep ed ha
supe addi i i y is qui e a easonable equi emen o he game. This is because we expec he
g and coali ion o o m, and hen, sha e he amoun (N)among he playe s; i he game was no
6.2. Game Theo y Backg ound 89
supe addi i e his expec a ion migh be un ounded. Hence, in he p esen Chap e we es ic o
he class o supe addi i e TU games, deno ed by G(Gndeno es he supe addi i e games wi h n
playe s).
An alloca ion ule is a unc ion which, gi en a game (N, ), selec s an alloca ion in Rn,i.e.,
ϕ: Ω ⊆Gn−→ Rn
(N, )7−→ ϕ(N, ).
Nex , we de ine some p ope ies o alloca ion ules. Le (N, )∈Gnand le ϕbe an alloca ion
ule: ϕis con inuous i he unc ion ϕ:R2n−1→Rnis con inuous; ϕis e icien i i always
selec e icien alloca ions; ϕis ansla ion in a ian i o each wo games (N, )and (N, w),
and each α= (α1,...,αn)∈Rnsuch ha o each S⊆N,w(S) = (S) + Pi∈Sαi, hen
ϕ(N, w) = ϕ(N, ) + α.
Nex , we de ine some p ope ies ega ding symme y. Le (N, )∈Gnand le i, j ∈N. Then,
iand ja e symme ic i o each S⊆N {i, j}, (S∪i)− (S) = (S∪j)− (S);iand ja e
quasi-symme ic i o each S⊆N {i, j}, (S∪i)−( (S)+ (i)) = (S∪j)−( (S)+ (j)). Now,
(N, )is symme ic i o each pai i, j ∈N,iand ja e symme ic; (N, )is quasi-symme ic i o
each pai i, j ∈N,iand ja e quasi-symme ic o , equi alen ly, a game is quasi-symme ic i he
co esponding 0-no malized game is symme ic. No e ha , o a symme ic game, (S)depends
only on he ca dinali y o S( his gi es an idea o he s eng h o his p ope y). Quasi-symme ic
games a e impo an in his Chap e because hei co es a e symme ic se s om he geome ic
poin o iew.
Finally, we de ine wo symme y p ope ies o an alloca ion ule. Le ϕbe an alloca ion
ule. We say ϕsa is ies weak symme y i o each symme ic game (N, )and each pai i, j ∈N,
ϕi(N, ) = ϕj(N, );ϕsa is ies ex ended weak symme y i o each quasi-symme ic game (N, )
and each pai i, j ∈N,ϕi(N, )− (i) = ϕj(N, )− (j). The ex ended weak symme y p ope y
says ha i o each pai i, j ∈N, hei con ibu ion o any coali ion di e s only in (i)− (j),
hen, he di e ence in he payo s is also (i)− (j). This p ope y, besides being a symme y
p ope y (i implies weak symme y) has some la o o ansla ion in a iance; oughly speaking,
i says ha he alloca ion ule sa is ies weak symme y and, mo eo e , ansla ion in a iance
wi hin he class o quasi-symme ic games. Nex Lemma illus a es his poin .
Lemma 6.1. T ansla ion in a iance +weak symme y ⇒ex ended weak symme y.
P oo . Le ϕbe an alloca ion ule sa is ying bo h ansla ion in a iance and weak symme y. Le
(N, )be a quasi-symme ic game and α= (− (1),...,− (n)). Now, le (N, w)∈Gnbe such
ha , o each S⊆N,w(S) = (S) + Pi∈Sαi. Then (N, w)is symme ic. Hence, by weak
symme y, o each pai i, j ∈N,ϕi(N, w) = ϕj(N, w). Now, by ansla ion in a iance, we ha e
ϕi(N, ) + αi=ϕj(N, ) + αj. Since αi=− (i)and αj=− (j), he esul is p o ed.

90 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
6.2.1 The Co e and i s Rela i es
We in oduce now he no ions o co e (Gillies, 1953) and s ong ε-co e (Maschle e al., 1979);
bo h o hem a e based on e iciency and s abili y. An alloca ion x∈Rnis s able i he e is no
coali ion S⊆Nsuch ha Pi∈Sxi< (S), analogously, o each ε∈R,xis ε-s able i he e is
no coali ion S⊆Nsuch ha Pi∈Sxi< (S)−ε.
The co e o a game (N, ),C(N, ), is he se o all e icien and s able alloca ions
C(N, ) := {x∈Rn:X
i∈N
xi= (N)and, o each S(N, X
i∈S
xi≥ (S)}.
The class o games wi h nonemp y co e is he class o balanced games. Le BG (Gbe he
class o supe addi i e balanced games (BGn(Gndeno es he se o supe addi i e balanced
games wi h nplaye s).
Le ε∈R. The s ong ε-co e o a game (N, ),Cε(N, )is he se o all e icien and ε-s able
alloca ions:
Cε(N, ) := {x∈Rn:X
i∈N
xi= (N)and, o each S(N, X
i∈S
xi≥ (S)−ε}.
By de ini ion, i ε= 0,C0(N, )≡C(N, ). The leas co e o (N, ),LC(N, ), is he in e sec ion
o all nonemp y s ong ε-co es. Equi alen ly, le ε0(N, )be he smalles εsuch ha Cε(N, )6=∅,
hen LC(N, ) = Cε0(N, )(N, ).1
Le (N, )∈Gn. The amily o “shi ed” games (N, ε)is de ined by:2
ε(S) := ( (S)−ε∅(S(N
(S)S=∅o S=N.
Finally, we in oduce a las concep ela ed o balanced games: a balanced game (N, )is
exac (Schmeidle , 1972) i o each S⊆N, he e is x∈C(N, )such ha Pi∈Sxi= (S).
Mo eo e , le (N, )∈BGnwi h co e C(N, ), hen, he e is a unique exac game (N, ˆ )such
ha C(N, ˆ ) = C(N, ); his game is he exac en elope o (N, ). No e ha i we ha e wo exac
games wi h he same co e, hen hey a e he same game. F om he poin o iew o s abili y, we
can say ha (N, ˆ ) h ows away he edundan in o ma ion o (N, ).
6.2.2 Some Geome ic Conside a ions
Fo he sake o cla i y, and i i does no en ail con usion, hence o h we deno e a game (N, )by
. We need o in oduce some no a ion and make some conside a ions ega ding he unde lying
geome y o a TU game. We deno e he e icien hype plane by HN
; hence, HN
:= {x∈Rn:
1In Maschle e al. (1979) i is shown ha ε0(N, )exis s and is unique.
2This concep has also been aken om Maschle e al. (1979)
6.2. Game Theo y Backg ound 91
Pi∈Nxi= (N)}. All he se s we conside in his Chap e a e con ained in HN
and hence, we
de elop all ou amewo k in an (n−1)-dimensional euclidean space.
A(con ex) poly ope Pis he con ex hull o a ini e se o poin s V={x1,...,xk}in Rn,
equi alen ly, i is a bounded subse o Rnwhich can be exp essed as he in e sec ion o a ini e
numbe o hal spaces. The co e o a game, when nonemp y, is a con ex poly ope (i is he
in e sec ion o hal spaces in HN
). An m-poly ope is a poly ope ha lies in an m-dimensional
space bu he e is no (m−1)-dimensional space con aining i . Le Pbe an m-poly ope and le
m′≥m, hen, Volm′(P)deno es he m′-dimensional olume o P. Le Pbe an m-poly ope.
Then, a se o poly opes {P1,...,Pk}de ine a dissec ion o Pi (i) P=Sk
l=1 Pland (ii) o each
pai l, l′∈ {1,...,k}, wi h l6=l′,Volm(Pl∩Pl′) = 0.
Lemma 6.2. Excep o he leas co e, all nonemp y s ong ε-co es a e (n−1)-poly opes. The
leas co e is always an m-poly ope wi h m < n −1.
P oo . The s a emen in his lemma has been aken om Maschle e al. (1979). Hence, we do
no p o e i . Anyway, no being a comple ely s aigh o wa d esul , i is qui e in ui i e.
Whene e he co e o a game in Gnis an (n−1)-poly ope, we say i is a ull dimensional
co e. O he wise, i is degene a e. By de ini ion, all he es ic ions in he co e o a game a e as
ollows: le S(N,RS
:= {x∈Rn:Pi∈Sxi≥ (S)}. Le RS
be a es ic ion, hen we say
ha RS
is a |S|- es ic ion. The 1- es ic ions play a special ole in his Chap e ; we call hem
elemen al es ic ions. We say a es ic ion is edundan in he co e i emo ing i does no change
he co e. Con e sely, he es ic ions which a e no edundan ones a e ac i e es ic ions. Le
HS
be he hype plane associa ed wi h he es ic ion RS
,i.e.,x∈HS
i and only i x∈HN
and Pi∈Sxi= (S). No e ha , because o he e iciency condi ion, he hype planes HS
ha e
dimension n−2.
Lemma 6.3. Le ∈Gnand le ∅(S(N. Then, he hype planes HS
and HN S
a e pa allel
in HN
.
P oo . Le ∈Gnand ∅(S(N. Then, HS
:= {x∈Rn:Pi∈Sxi= (S)}. We claim ha
he e is k∈Rsuch ha HS
can be exp essed as Pi∈N Sxi=k. Once his claim is p o ed, he
s a emen o he Lemma is immedia ely de i ed. Since we wo k in HN
,Pi∈Sxi+Pi∈N Sxi=
(N). I we impose he es ic ion Pi∈Sxi= (S), we ha e (S) + Pi∈N Sxi= (N). Hence,
Pi∈N Sxi= (N)− (S) = k.
6.2.3 The Co e-Cen e
The co e o a game is he se o all he s able and e icien alloca ions. Now, i we conside
ha all hese alloca ions a e equally easonable, hen i makes sense o hink o he co e as i i
was endowed wi h a uni o m dis ibu ion. The co e-cen e summa izes he in o ma ion o such
a dis ibu ion o p obabili y. Le U(A)be he uni o m dis ibu ion de ined o e he se Aand
E(P) he expec a ion o he p obabili y dis ibu ion P.
92 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
De ini ion 6.1. Le (N, )be a balanced game wi h co e C(N, ). The co e-cen e o (N, ),
µ(N, ), is de ined as ollows:
µ(N, ) := E[U(C(N, ))] .
6.3 Fai Addi i i y
We de o e his Sec ion o he mo i a ion and de ini ion o he ai addi i i y p ope y. This
p ope y is c ucial in he cha ac e iza ion o he co e-cen e we ob ain in Sec ion 6.4. Fi s ,
be o e in oducing he ai addi i i y p ope y, we de ine a gene al amily o alloca ion ules, ha
we call T-solu ions. Then, we say ha an alloca ion ule sa is ies he ai addi i i y p ope y i
i belongs o a special sub amily o T-solu ions.
6.3.1 T-Solu ions and RT-Solu ions
We need o in oduce some concep s be o e o mally de ining wha a T-solu ion is. Le ∈Gn,
∅(T(N, and k≥ (T). We use cons an k o de ine wo games: , a good game o coali ion
T, and a good game o coali ion N T. Suppose ha , because o some change in he si ua ion
unde lying ou TU game, coali ion Talone can ob ain kins ead o (T). We de ine as he game
ob ained when in oducing his change in :
(S) = (max{ (S), (S T) + k}T⊆S
(S)o he wise.
We de ine ¯ (S)as max{ (S), (S T) + k} o ensu e ha is a supe addi i e game. Supe -
addi i i y also implies ha (T)≤ (N)− (N T). Hence, i we wan game o emain in he
class o supe addi i e games, kmus belong o he in e al [ (T), (N)− (N T)].
So, o alue k, we ha e na u ally de ined a game in which coali ion Thas imp o ed wi h
espec o . Now, o his cons an k, we de ine a game in which coali ion Tis wo s -o . We
do i by le ing coali ion N Timp o e, i.e., de ining (N T) := (N)−k. The mo i a ion o
his de ini ion comes om he idea o s abili y. Since (T) = k, coali ion Tshould ecei e a
leas kin game . On he o he hand, (N T) = (N)−kimplies ha coali ion N Tshould
ecei e, a leas , (N)−kand hence, coali ion Tshould ob ain a mos k. This change leads o
he supe addi i e game:
(S) = (max{ (S), (S (N T)) + (N)−k}N T⊆S
(S)o he wise.
A his poin , we ha e de ined wo games: , in which coali ion Thas imp o ed wi h espec
o , and , in which coali ion N Tis he one ha is be e -o . A cu on he game o coali ion
Ta heigh k∈[ (T), (N)− (N T)] is deno ed by χT,k( )and de ined as he pai o games
{ , }. The eason o he name cu becomes clea when dealing wi h balanced games below.
6.3. Fai Addi i i y 93
An ex a condi ion needs o be imposed on cu s, namely, i (T) = (N)− (N T), hen no
cu is pe mi ed o coali ion T. This las equi emen is qui e na u al, i omi ed, we could
ha e a si ua ion in which = = , and he cu makes no sense. No e ha , by de ini ion, i
χT,k( ) = { , }and χN T, (N)−k( ) = { ′, ′}, hen = ′and = ′. Lemma 6.4 shows ha
he games and a e supe addi i e.
Lemma 6.4. Le ∈Gn. Le ∅ 6=T(Nbe such ha (T)< (N)− (N T). Le χT,k( ) =
{ , }. Then, bo h and a e supe addi i e games.
P oo . Le χT,k( ) = { , }. We do he p oo o he supe addi i i y o , being he one o
analogous (jus hink o he cu χN T, (N)−k( ) = { ′, ′}whe e ′= ). Le S, S′⊆N,
S∩S′=∅. We wan o show ha (S) + (S′)≤ (S∪S′). Now we ha e ou possibili ies:
(i) T*S∪S′. Now, (S) = (S), (S′) = (S′), and (S∪S′) = (S∪S′). Hence, he esul
ollows om he supe addi i i y o .
(ii) T⊆S∪S′,T*S, and T*S′. Now, (S) = (S), (S′) = (S′), and (S∪S′)≥ (S∪S′).
Hence, he esul ollows om he supe addi i i y o .
(iii) T*Sand T⊆S′. By de ini ion o , (S) = (S)and (S′) = max{ (S′), (S′ T) +
k}. I (S′) = (S′), hen, since (S∪S′)≥ (S∪S′), we a e done. Hence, we can
assume ha (S′) = (S′ T) + k. Now, since S∩S′=∅, we ha e T∩S=∅and hence,
(S∪S′) T=S∪(S′ T). Hence, by he de ini ion o and he supe addi i i y o ,
(S∪S′)≥ ((S∪S′) T) + k≥ (S) + (S′ T) + k= (S) + (S′).
(i ) T⊆Sand T*S′. Analogous o (iii).
Nex , we in oduce he de ini ion o T-solu ion, whe e Ts ands o ade-o .
De ini ion 6.2. An alloca ion ule ϕis a T-solu ion i o each game and each cu χT,k( ) =
{ , }, he e is α∈[0,1] such ha
ϕ( ) = αϕ( ) + (1 −α)ϕ( ).
The idea o a T-solu ion is ha ϕ( ), he solu ion o he o iginal game, mus be a ade-o
be ween ϕ( )and ϕ( ). The esul o a gi e and ake be ween coali ions Tand N T. The
coe icien αmeasu es how impo an and a e o he o iginal game when ϕis being
conside ed. Once he alloca ion ule is ixed, he coe icien αis a unc ion depending on he
game , he coali ion T, and he cons an k. The e o e, he concep o T-solu ion is e y gene al
and dealing wi h he whole amily o T-solu ions is no an easy ask. Nex , we impose a egula i y
condi ion on how he ade-o has o be made.
Le ∈Gnand le { 1, 2}be a cu on . Now, a new cu { 2, 2}can be de ined on 2.
Hence, we ha e cu he o iginal game in o he games { 1, 2, 2}. The gene aliza ion o his idea
leads o he de ini ion o dissec ion. The collec ion o games G={ 1, 2, . . . , }is a dissec ion
100 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
P oo . I C( )is elemen al, C( ) = I( ). Fo each ∈Gn,I( )is a egula simplex4wi h e ices
u1,...,unwhe e, o each i∈N,
ui= ( (1), (2),...,
i
z}| {
(N)−X
j6=i
(j),..., (n)).
Hence, o ob ain he esul , we only need o calcula e he cen e o g a i y o he simplex, i.e.,
he a e age o he e ices.
Lemma 6.8. Le ∈BGn. I C( ) = I( ), hen, is quasi-symme ic.
P oo . I( )is a egula (n−1)-simplex. Hence, i C( ) = I( ), hen, o each S(N, wi h |S|>1,
he es ic ions RS
a e edundan . Le S(N,|S|>1. By supe addi i i y, (S)≥Pi∈S (i).
Mo eo e , since RS
is edundan , (S)≤Pi∈S (i). Hence, (S) = Pi∈S (i). Now, ega dless
o (N), he game is quasi-symme ic.
P oposi ion 6.2. Le ∈BGnbe such ha C( )is elemen al. Le ϕbe an alloca ion ule
sa is ying e iciency and ex ended weak symme y. Then, ϕ( ) = µ( ).
P oo . Since has an elemen al co e, C( ) = I( ). By Lemma 6.8, is quasi-symme ic. Now,
by ex ended weak symme y, we ha e ha , o each pai i, j ∈N,ϕi( )− (i) = ϕj( )− (j).
Hence, he e is k∈Rsuch ha , o each i∈N,ϕi( ) = k+ (i). The la e commen , along
wi h he e iciency p ope y, implies ha , o each i∈N,
ϕi( ) = (N)−Pj∈N (j)
n+ (i).
Now, by Lemma 6.7, ϕ( )is he cen e o g a i y o C( ),i.e., he co e-cen e . Hence, ϕ( ) =
µ( ).
6.4.2 The Co e is Full Dimensional
In his Sec ion we combine P oposi ion 6.2 wi h he con inui y and he ai addi i i y p ope ies
o show ha a game wi h a non degene a e co e belongs o TG.
A his poin we know ha games wi h an elemen al co e belong o TG. The class o games
wi h an elemen al co e plays an impo an ole in he o hcoming esul s. This ole is simila o
ha o he unanimi y games in he cha ac e iza ion o he Shapley alue using addi i i y. The
ou line o his pa o he p oo is as ollows. Le be a balanced game and le C( )be ull
dimensional. Fi s , successi ely cu ing , we ob ain a dissec ion o C( ); being his dissec ion
p ima ily composed by small pa allelepipeds. Second, we cu he games co esponding o hese
pa allelepipeds, ob aining an elemen al co e inside each o hem. Then, we successi ely epea
his p ocedu e wi h he emaining non-elemen al co es. Finally, we show ha , using cu s, he
4Go o e he Appendix o ind a igo ous de ini ion o a simplex and ela ed concep s.

6.4. The Cha ac e iza ion 101
co e o can be co e ed wi h elemen al co es ( his is indeed a kind o iangula ion). Finally,
he ai addi i i y p ope y leads o he conclusion o his pa o he p oo . Figu e 6.2 illus a es
his ou line.
=⇒
O iginal si ua ion, I( ),C( )Dissec ing I( )in o pa allelepipeds
=⇒
All da k shaded co es Cu ing he pa allelepipeds
a e pa allelepipeds o ob ain elemen al co es
Figu e 6.2: Scheme o he p oo o ull dimensional co es
P oposi ion 6.3. Le ∈BGnbe such ha C( )is ull dimensional. Le ϕbe an alloca ion
ule sa is ying he ou p ope ies T1-T4. Then, ϕ( ) = µ( ).
P oo . Le ϕbe an alloca ion ule sa is ying he p ope ies T1-T4. Le ∈BGnbe a game wi h
a ull dimensional co e. The body o he p oo consis s o dissec ing C( )in o elemen al co es;
we do i in such a way ha we can combine P oposi ion 6.2 wi h he con inui y and he ai
addi i i y p ope ies o ge ϕ( ). Hence, we desc ibe a p ocedu e which “nea ly” iangula es any
ull dimensional co e. Hence o h, ill he end o he p oo , Vol(P)deno es he (n−1)-dimensional
olume o poly ope P.
Fi s , we di ide I( )in o small (n−1)-pa allelepipeds.5Le i∈N,i’s payo in his bes
alloca ion wi hin I( )is (N)−Pj6=i (j), and in his wo s one is (i); hence, ega dless o i, he
5A igo ous de ini ion o a k-pa allelepiped can be ound in he Appendix.
102 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
di e ence be ween hese wo payo s is (N)−Pj∈N (j). Le L:= (N)−Pj∈N (j). F om
now on, and o he sake o cla i y, (i)is deno ed by mi. Le q∈N( o simplici y we assume
q > 2), and le δ=L/q. Fo each ace in I( ), di e en o ha co esponding wi h he hype plane
xn=mn, we make q+ 1 cu s on i , all o hem pa allel o he hype plane in which ha ace
lies. Hence, we pa i ion I( )using he ollowing hype planes: o each i∈N,i6=n, and o
each k∈ {0,...,q},Hi
k:= {x∈Rn:xi=mi+kδ}. We use hese hype planes o de ine a
dissec ion o C( ). Le χi,k be a cu , and le Gbe a collec ion o games. We deno e by χi,k(G) he
esul o cu ing successi ely all he co es o he games in Gwi h he hype plane xi=k. Hence,
χi,k({w, w′, w′′,...}) = {w, w, w′, w′,w′′, w′′,...}. I can be he case ha some o hese cu s is
no pe mi ed, i.e.,k /∈[w(i), w(N)−w(N i)]; besides, i is also possible ha one o he games
in χi,k(w)is no balanced. In he las wo cases we ake {w}ins ead o χi,k(w),i.e., we do no
conside hose cu s.
Le ∈BGnbe such ha C( )is ull dimensonal. Le Gδbe he collec ion o games de ined
as ollows:
S age 0:We begin wi h he se o games G0≡ G0,q ={ }.
.
.
.
S age i, i ∈N, i 6=n:We de ine he cu s o playe i.
S ep i.0:We cu I( )wi h xi=mi;Gi,0=χi,mi(Gi−1,q).
S ep i.1:Gi,1=χi,mi+δ(Gi,0).
.
.
.
S ep i.k:Gi,k =χi,mi+kδ(Gi,k−1).
.
.
.
S ep i.q:Gi,q =χi,mi+qδ(Gi,q−1).
Le Gδdeno e he se Gn−1,q. In o de o sa e no a ion, i no ambigui y a ises, we deno e
C( ′)by C′. Now, S ′∈GδC′=Cand, o each pai 1, 2∈ Gδ,Vol(C( 1)∩C( 2)) = 0,i.e., he
co es o he games in Gδde ine a dissec ion o C. I is qui e in ui i e ha , o each 0< ε < 1,
we can ind δ > 0such ha he sum o he olumes o he co es o games in Gδwhich a e
no pa allelepipeds is, a mos , εVol(C)(no e ha εis ixed now o all he p oo ). All hese
pa allelepipeds a e equal and hey ha e posi i e (n−1)-dimensional olume. Le GNP (Gδ
be he se o games such ha hei co e is no a pa allelepiped. The second pa o he p oo
consis s o cu ing each one o he pa allelepipeds o ob ain an elemen al co e, a simplex, inside
he pa allelepiped. I is qui e in ui i e, and no di icul o check, ha o 0< α < 1small
enough, we can ind a p ocedu e which di ides each pa allelepiped Pin such a way ha he co e
6.4. The Cha ac e iza ion 103
o one o he esul ing games is elemen al and i s olume is, a leas , αVol(P).6Le GNE be he
se o games ob ained in his second s ep such ha hei co e is no elemen al.
We can ensu e now ha a leas a olume α(1 −ε) Vol(C)has been co e ed by elemen al
co es. Pe iod 1is inished. The p ocedu e con inues as ollows. We begin pe iod 2: o each
game ′∈ GNP ∪ GNE, we epea he p ocedu e we ha e made o (we ha e o ind a new
cons an δ′which will p obably be smalle han δ), co e ing a leas a olume α(1 −ε) Vol(C′)
o i s co e wi h elemen al co es. No e ha he cons an αkeeps cons an . This is because in his
second pe iod we ob ain he same kind o pa allelepipeds we had in he i s one (bu smalle ).
Hence, he p ocedu e ob ained o “pu ” a simplex inside each pa allelepiped is he same, and he
p opo ion o co e ed olume also emains unchanged.
No e ha δ a ies as he pe iod changes bu bo h αand εkeep cons an . We claim ha i
we epea successi ely his p ocedu e, he olume o Cwhich is no co e ed by elemen al co es
ends o 0. We begin wi h a olume RV 0= Vol(C)which needs o be co e ed by elemen al co es.
A e he i s pe iod, his olume has been educed o RV 1= (1 −α)(1 −ε) Vol(C) + εVol(C).
Then, a e pe iods we ha e RV = (a+b) Vol(C), whe e a= (1 −α)(1 −ε)and b=ε. The
p oo o his s a emen is easily done by induc ion:
Case 1: RV 1= (1 −α)(1 −ε) Vol(C) + εVol(C) = (a+b) Vol(C).
Case : Assume he esul is ue o his case (induc ion assump ion).
Case +1: Finally, we ha e RV +1 = (1 −α)(1 −ε)RV +εRV =aRV +bRV induc
=
a(a+b) Vol(C) + b(a+b) Vol(C) = (a+b) +1 Vol(C).
Hence, since a+b= (1 −α)(1 −ε) + ε < 1, we ha e lim →∞ RV = lim →∞(a+b) Vol(C) = 0.
This means ha , in he limi , his p ocedu e de ines an in ini e dissec ion o C( ). Le G be
he collec ion o games a e pe iod and EG hose wi h an elemen al co e. Now, by he ai
addi i i y o ϕ:
ϕ( ) = X
′∈G
Vol(C′)
Vol(C)ϕ( ′) = 1
Vol(C)X
′∈EG
Vol(C′)ϕ( ′) + X
′∈G EG
Vol(C′)ϕ( ′).(6.1)
By P oposi ion 6.2, we ha e al eady cha ac e ized ϕ o he games in he i s addend o he las
e m in Equa ion (6.1). Mo eo e , since ϕis con inuous, i is uni o mly con inuous in he se
B={w∈Gn: o each S⊆N, (S)≤w(S)≤ (N)}. Hence, ϕis bounded in B. Since all he
games we ha e de ined so a belong o B, we ha e lim →∞ P ′∈G EG Vol(C′)ϕ( ′) = 0. Now,
6We p o e in he Appendix ha he cu s di ide he co e o he o iginal game in many pa allelepipeds and ha
he p opo ion o he co e co e ed by hese se s is as close o one as needed. We also p o ide he e an example o
a p ocedu e o “pu ” an elemen al co e inside each pa allelepiped.
104 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
o each ∈N,ϕ( ) = P ′∈G
Vol(C′)
Vol(C)ϕ( ′). Then,
ϕ( ) = lim
→∞ X
′∈G
Vol(C′)
Vol(C)ϕ( ′)
=1
Vol(C)lim
→∞ X
′∈EG
Vol(C′)ϕ( ′) + lim
→∞ X
′∈G EG
Vol(C′)ϕ( ′)
= lim
→∞
1
Vol(C)X
′∈EG
Vol(C′)ϕ( ′)
P op 6.2
= lim
→∞
1
Vol(C)X
′∈EG
Vol(C′)µ( ′)
=µ( ).
6.4.3 The Co e is No Full Dimensional
Now, he co e is an m-poly ope wi h 1≤m≤n−2.
P oposi ion 6.4. Le ∈BGnbe such ha C( )is no ull dimensional. Le ϕbe an alloca ion
ule sa is ying he p ope ies T1-T4. Then, ϕ( ) = µ( ).
P oo . By Lemma 6.2, C( )is he leas co e o . Le { 1/ } ∈Nbe a sequence o shi ed games.
Now, lim →∞ 1/ = . The co e o 1/ coincides wi h he 1
-co e o . By Lemma 6.2, all hese
1
-co es a e ull dimensional, and now, by P oposi ion 6.3 we know ha hese games ha e al eady
been cha ac e ized. Hence,
ϕ( )con
= lim
→∞ϕ( 1/ )P op 6.3
= lim
→∞µ( 1/ )con
=µ( ).
P oo o Theo em 6.1.The asse ion o he heo em ollows om P oposi ions 6.2, 6.3, and 6.4.
Nex , we p o e ha he p ope ies in Theo em 6.1 a e igh . In o de o do his we need a
las Lemma.
Lemma 6.9. Le be a quasi-symme ic game. Then, C( )ei he is a poin o is ull dimen-
sional.
P oo . This is a geome ic esul . As we ha e al eady seen, he co e o a quasi-symme ic game
can be ans o med in ha o a symme ic game jus using a ansla ion. To p o e his Lemma i
su ices o show ha he esul is ue o symme ic games. Hence, le be a symme ic game,
and assume ha i has a degene a e co e. Hence, he e a e 1≤s≤n−1and an s-playe coali ion
S, such ha (S) + (N S) = (N). By e iciency and s abili y, we ha e ha he e is k∈Rsuch
ha , o each x∈C( ),Pi∈Sxi= (S) = k( his is he eason o he degene a ion). Now, by
6.4. The Cha ac e iza ion 105
symme y, o each x∈C( )and each s-playe coali ion S′, we ha e Pi∈S′xi=k. I s= 1, we
ha e ha , o each i∈Nand each x∈C( ),xi=kand we a e done. Hence, we can assume
ha s > 1. Now, we claim ha , o each x∈C( )and each i∈N,xi=k/s. Suppose, on he
con a y, ha he e a e x∈C( )and i∈Nsuch ha xi> k/s. Hence, o each s-playe coali ion
Scon aining i, he e is j∈Ssuch ha xj< k/s. Bu his con adic s ha , o each s-playe
coali ion Pi∈Sxi=k(jus aking an s-playe coali ion wi h all hese j’s such ha xj< k/s and
he lowe o he emaining o ha e splaye s). Hence, we ha e ha , o each i∈N,xi=k/s.
Now, by e iciency, k=s (N)/n. Hence C( ) = {x}, whe e, o each i∈N,xi= (N)/n.
P oposi ion 6.5. None o he p ope ies used in Theo em 6.1 o cha ac e ize he co e-cen e is
edundan .
P oo . Nex , we show ha i we emo e one o hese p ope ies he e a e alloca ion ules di e en
om he co e-cen e sa is ying he emaining ones.
Remo e Fai Addi i i y: Bo h Shapley alue and nucleolus sa is y e iciency, ex ended weak
symme y, and con inui y.
Remo e E iciency: Take k6= 0. The alloca ion ule ϕ( ) = µ( ) + (k,...,k)whe e µ( )
deno es he co e-cen e o he game sa is ies ai addi i i y, ex ended weak symme y, and
con inui y.
Remo e ex ended weak symme y: The alloca ion ule ϕ( ) = ( (N),0,...,0) sa is ies ai
addi i i y, e iciency and con inui y.
Remo e con inui y: This is he mos complex si ua ion, we need o dis inguish di e en cases
in he de ini ion o ou alloca ion ule ϕ:
The co e is a single poin : ϕselec s he poin ( he co e-cen e ).
The co e is degene a e bu no a single poin : In his case he alloca ion ϕselec s
he poin ( (N),0,...,0).
The co e is no degene a e: ϕselec s he co e-cen e .
This alloca ion ule sa is ies ai addi i i y, e iciency and ex ended weak symme y. I
sa is ies ai addi i i y because o he ollowing: i a cu di ides a co e in wo new co es, and
one o hem is no ull dimensional while he o iginal was, hen, he weigh o his degene a e
co e is 0. E iciency is s aigh o wa d. I also sa is ies ex ended weak symme y: in he
non-degene a e case i coincides wi h he co e-cen e so ex ended weak symme y is me ;
in he degene a e case, as a consequence o Lemma 6.9 he e a e no quasi-symme ic games
wi h degene a e co e wi h mo e han one poin and hence, ex ended weak symme y can
ne e be iola ed.

106 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
6.5 Concluding Rema ks
In his Chap e we ha e p esen ed a cha ac e iza ion o he co e-cen e . The main esul we
s a ed uses h ee s anda d p ope ies along wi h a new one, he ai addi i i y p ope y. Recall
ha , acco ding o he de ini ions o T-solu ion and ai addi i i y, gi en a game we can “cu ”
i using any nonemp y coali ion di e en om he g and coali ion. None heless, he p oo s we
p esen ed he e in ol e cu s ha only use 1-playe coali ions and hence, we could s a e and p oo
a new cha ac e iza ion esul , simila o Theo em 6.1, bu wi h a weakened e sion o he ai
addi i i y.
Al hough we ha e p o ided a i s cha ac e iza ion o he co e-cen e , mo e esea ch is needed
in o de o ind mo e con incing cha ac e iza ions. One possibili y is o deepen in o he concep s
o T-solu ion and RT-solu ion, and y o cha ac e ize he co e-cen e wi hou he addi ional e-
s ic ion imposed by he ai addi i i y p ope y. Simila ly, he p oblem o inding an independen
cha ac e iza ion ha does no need he concep o T-solu ion is s ill o be sol ed.
6.A Appendix
6.A.1 The Geome y o he Co e-Cen e in Dep h
-De ini ion o Simplex.
Le {a0, a1,...,an}( Rnbe a geome ically independen se .7The simplex ∆nspanned by
a0, a1,...,anis he se o all x∈Rnsuch ha x=Pn
i=0 iai, whe e Pn
i=0 i= 1 and, o each
i∈ {1,...,n}, i≥0. Each aiis a e ex o he n-simplex. The supe sc ip no ∆nco esponds
wi h he dimension o he simplex. An n-simplex is egula i he dis ance be ween any wo
e ices is cons an .
The ba ycen e o a simplex ∆nspanned by he poin s a0, a1,...,anis Θ(∆n) := Pn
i=0 ai
n+1 .
Le m≤n, le ∆mbe an m-simplex con ained in Rn, and le a0,...,ambe i s e ices. The
m-dimensional olume o ∆m,Volm(∆m), can be compu ed in he ollowing way: Le B= (βij)
deno e he (m+ 1) ×(m+ 1) ma ix gi en by βij =kai−ajk2. Then,
2m(m!)2Volm(∆m)2=|de ( ˆ
B)|,
whe e ˆ
Bis he (m+2)×(m+2) ma ix ob ained om B by bo de ing i wi h a op ow (0,1,...,1)
and le column (0,1,...,1)T. This is known as he Cayley-Menge de e minan o mula.8
7A se {a0, a1,...,an}( Rnis geome ically independen i o each ec o ( 0, 1,..., n)∈Rn+1, he
equa ions
P
n
i=0 i= 0 and
P
n
i=0 iai= (0, . . . , 0), hold only i 0= 1=···= n= 0. No e ha {a0, a1,...,an}
is geome ically independen i and only i he ec o s a1−a0,...,an−a0a e linea ly independen .
8Fo e e ences on his and o he o mulas o compu ing simplicial olumes look a G i zman and Klee (1994).
6.A. Appendix 107
-De ini ion o Pa allelepiped.
Le {u1, u2,...,um}be mlinea ly independen ec o s in Rn, wi h m≤n. The m-pa allelepiped
Pmspanned by u1, u2,...,umis he se o all x∈Rnsuch ha x=Pm
i=1 iui, whe e, o each
i∈ {1,...,m},0≤ i≤1. Le Abe he ma ix whose ows a e he ec o s u1, u2,...,um. The
m-dimensional olume o Pmis |de ATA|1/2.
P oo o he s a emen s ela i e o P oposi ion 6.3 ( oo no e 6).
We di ide his p oo in h ee pa s. Fi s , we show ha he p ocedu e de ined in he p oo
o P oposi ion 6.3 p o ides a dissec ion o I( ); his dissec ion is mainly o med by (n−1)-
pa allelepipeds. Second, we show ha o each ε > 0, he e is δ > 0such ha he sum o he
he olumes o he pa allelepipeds in he induced dissec ion o Cis ε-close o Vol(C). Finally, we
show a p ocedu e o “pu ” an elemen al co e inside a pa allelepiped. In o de o make his p oo
mo e eadable we assume, wi hou loss o gene ali y, ha o each i∈N,mi= 0.
The p ocedu e desc ibed in he p oo o P oposi ion 6.3 is a “quasi-dissec ion
in pa allelepipeds” o I( ):
Le x∈I( ). The e is = ( 1,..., n−1)∈Rn−1such ha , (i) o each i∈N, i∈ {0,...,q}
and (ii) o each i∈N,i6=nwe ha e iδ≤xi≤( i+ 1)δ; no e ha he second inequali y is
equi alen o Pj6=ixj≥ (N)−( i+ 1)δ. Nex , we ind he pa allelepiped co esponding wi h
his ec o (no e ha he same poin xcan lie mo e han one pa allelepiped a he same ime).
Le Pbe he pa allelepiped spanned by he ec o s {u1,...,un−1}, whe e ui=eiδ−enδ(ei
deno es he i h ec o o he canonical base in Rn). Now, since he ec o s {u1,...,un−1}a e
independen , hey gene a e a pa allelepiped. Now, o each x∈I( ), and an associa ed ec o
∈Rn−1,xlies in he pa allelepiped P := P+( 1δ, 2δ,..., n−1δ, (N)−Pi6=n iδ). No e ha
we ha e also shown ha all he pa allelepipeds a e equal (changing he ansla ion we jus mo e
Pon o a di e en posi ion). Bu now, as i can be seen in Figu e 6.2, a small amoun o hese
pa allelepipeds is no comple ely included in I( ); hose o whom he es ic ion xn≥0is no
edundan . We show in he nex s ep ha his is no a p oblem.
The induced “quasi-dissec ion in pa allelepipeds” in Ccan be a bi a ily igh :
Nex , we show ha , o each 0< ε < 1, we can ind δ > 0such ha he sum o he olumes
o he co es o he games in Gδwhich a e no pa allelepiped is, a mos , εVol(C).
The si ua ion we ha e is simila o ha in Figu e 6.2, mos o he co es o games in Gδa e
s ic ly con ained in C. Le ′∈ Gδbe such ha C′is nonemp y. The e is a pa allelepiped P′such
ha C′=P′∩C. We wan o show ha , in mos o he cases, we ha e C′=P′∩C=P′and C′
is a pa allelepiped (da k shaded zone in he hi d pic u e o Figu e 6.2). Le dδbe he maximum
euclidean dis ance be ween any wo poin s in P(since all he pa allelepipeds a e ansla ions o
each o he , dδis common o all o hem). By de ini ion o P,limδ→0dδ= 0.9
9The maximum dδis achie ed when x= (0,...,0) and y=
P
n−1
i=1 ui= (δ, . . . , δ, −(n−1)δ). The dis ance
be ween hese wo poin s is (n(n−1))1/2δ. Hence, i goes o 0as δdoes.
108 Chap e 6. A Cha ac e iza ion o he Co e-Cen e
Each ace o Cis de e mined by a es ic ion RS
, whe e ∅(S(N. Hence, he maximum
numbe o aces o he co e o a game wi h nplaye s is n= 2n−2. Le F(C)deno e he se o
all aces o C.
Le y∈Cbe such ha he dis ance om y o each ace in F(C)is mo e han dδ. Then, y
is inside a co e C′such ha C′=P′∩C=P′ o some pa allelepiped P′,i.e.,C′is i sel a
pa allelepiped. Hence, we can ind an uppe bound o he olume o he poin s y∈Cwhich
a e no in a pa allelepiped. Le F∈F(C). Le B(F, δ) := {x∈Rn:d(x, F)< dδ}. Now,
limδ→0B(F, δ) = Fand, since Flies in an (n−2)-dimensional space, Voln−1(F) = 0. Now,
since o each F∈F(C),B(F, δ)is bounded, we ha e ha Vol(B(F, δ)) goes o 0as δdoes.
Hence, o each 0< ε < 1, we can ind δ > 0such ha o each F∈F(C),Vol(B(F, δ)) <ε
n.
Once one such δhas been chosen, i y∈Cbu i is no in a pa allelepiped, hen i mus lie in
B(F, δ) o some ace Fo C. Hence, he o al olume o hese poin s is bounded om abo e by
PF∈F(C)Vol(B(F, δ)<PF∈F(C)ε
n= nε
n=ε.
Cu ing a pa allelepiped o ob ain an elemen al co e: Le be he game such
ha i s co e is he pa allelepiped P de ined by P+ ( 1δ, 2δ,..., n−1δ, (N)−Pi6=n iδ). Le
χn,k( )be he cu whe e k= (N)−(1 + Pi6=n i)δ. The game has an elemen al co e ∆
whose e ices a e he ollowing nex eme poin s:
o each i∈N, pi= ( 1δ, 2δ,..., n−1δ, (N)−X
i6=n
iδ) + eiδ−enδ.
The cons an αused in he p oo can be calcula ed as he quo ien o he (n−1)-dimensional
olumes o he simplex ∆and he pa allelepiped Pcon aining i . Making some compu a ions
wi h he o mulas we in oduced when we de ined simplices and pa allelepipeds we ha e
Vol(∆) = √n
(n−1)!δn−1and Vol(P) = √nδn−1.
Hence, α=Vol(S)
Vol(P)=1
(n−1)! . Once nis ixed, αkeeps cons an . 
Bibliog aphy 109
Bibliog aphy
Anba ci, N. and J. Bigelow (1994): “The A ea Mono onic Solu ion o he Coope a i e Ba -
gaining P oblem,” Ma hema ical Social Sciences, 28, 133–142. (Quo ed in pp. 88)
Cal o, E. and H. Pe e s (2000): “Dynamics and Axioma ics o he Equal A ea Ba gaining
Solu ion,” In e na ional Jou nal o Game Theo y, 29, 81–92. (Quo ed in pp. 88)
Gillies, D. B. (1953): “Some Theo ems on n-Pe son Games,” Ph.D. hesis, P ince on. (Quo ed
in pp. 90)
González-Díaz, J. and E. Sánchez-Rod íguez (2003): “F om Se -Valued Solu ions o Single-
Valued Solu ions: The Cen oid and he Co e-Cen e ,” Repo s in S a is ics and Ope a ions
Resea ch 03-09, Uni e si y o San iago de Compos ela. (Quo ed in pp. 88)
G i zman, P. and V. Klee (1994): “On he Complexi y o Some Basic P oblems in Compu-
a ional Con exi y: Volume and Mixed olumes,” in Poly opes: Abs ac , con ex and compu-
a ional, ed. by T. Bisz iczky, P. McMullen, R. Schneide , and A. Weiss, Kluwe , Bos on MA,
373–466. (Quo ed in pp. 106)
Maschle , M., B. Peleg, and L. S. Shapley (1979): “Geome ic P ope ies o he Ke nel,
Nucleolus, and Rela ed Solu ion Concep s,” Ma hema ics o Ope a ions Resea ch, 4, 303–338.
(Quo ed in pp. 90, 91)
Rudin, W. (1966): Real and Complex Analysis, McG aw-Hill. (Quo ed in pp. 97)
Schmeidle , D. (1972): “Co es o Exac Games,” Jou nal o Ma hema ical Analysis and Appli-
ca ions, 40, 214–225. (Quo ed in pp. 90)
116 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
Co olla y 7.1. Le (N, )∈G2be such ha (N)> ({1}) + ({2}). Then,
Sh(N, ) = Θ(I(N, )) = µ(N, ).
Mo eo e , hey coincide wi h he ba ycen e (midpoin ) o he segmen joining he wo poin s
 ({1}), (N)− ({1})and  (N)− ({2}), ({2}).
P oo . Immedia e om Lemma 7.1.
Le D be he se o dummy playe s o (N, )and d i s ca dinali y. Recall ha , i d =n,
hen he game is addi i e.
Lemma 7.2. Le (N, )∈Gn. Then, he ollowing s a emen s a e ue:
(i) d 6=n−1.
(ii) Le (N, )∈BGnand d < n. Then, xN∈C(N, )i and only i (i) o each i∈D , xi=
({i})and (ii) xN D ∈C(N D , N D ).
(iii) Le (N, )∈CGnand d < n. Then, (N D , N D )∈CGn−d ,i.e., i is a con ex game
wi h ull dimensional co e.
P oo . a) Suppose ha d ≥n−1. Then, he e is i∈Nsuch ha N {i} ⊆ D . Suppose now ha
i /∈D . Le Sbe a minimal coali ion among hose such ha i /∈Sand (S∪{i})− (S)6= ({i}).
Clea ly, S6=∅. Le j∈S, hen,
((S∪{i}) {j}) = ((S∪{i}) {j})− (S {j}) + (S {j})
S {j}(S
= ({i}) + X
l∈S {j}
({l}).
Now, ({j}) = (S∪ {i})− ((S∪ {i}) {j}) = (S∪ {i})− ({i})−Pl∈S {j} ({l}). Hence,
since Pl∈S ({l}) = (S), we ha e (S∪{i})− (S) = ({i}), con adic ing he de ini ion o S.
Hence, i∈D and d =n.
b) Follows om he equali y (N) = (N D ) + Pj∈D ({j}).
c) Each subgame o a con ex game is a con ex game. Hence, (N D , N D )is a con ex
game wi h no dummy playe s. Le (N, w)be a con ex game. Since (i) o each i∈N, he e is a
ma ginal ec o such ha mσ
i= ({i})and (ii) C(N, w)is he con ex hull o he ma ginal ec o s,
C(N, w)has a leas one poin in each ace o I(N, w). Now, i (N, w)has no dummy playe s,
hen, o each i∈N, he e is a ma ginal ec o such ha mσ′
i> ({i}). The ull dimensionali y
o he co e o each con ex game wi h no dummy playe s ollows om he combina ion o he wo
p e ious obse a ions.
Co olla y 7.2. Le (N, )be a con ex game wi h n−2dummy playe s. Then, Sh(N, ) = µ(N, ).
P oo . I ollows om Lemma 7.2 and Co olla y 7.1.

7.4. The U opia Games 117
Rema k. Lemma 7.2 shows ha coali ions in ol ing dummy playe s a e no needed in o de
o compu e he co e-cen e . Then,
µi(N, ) = ( ({i})i∈D
µi(N D , N D )i /∈D .
No e ha he Shapley alue also sa is ies ha o each i∈D ,Shi(N, ) = ({i}).
Because o he p e ious Rema k, we do no conside games wi h dummy playe s anymo e. The
main esul s in he nex Sec ion hold o con ex games wi hou dummy playe s o , equi alen ly,
con ex games wi h ull dimensional co e.
7.4 The Dynamic P ocess be ween Coali ions. The U opia
Games
The class o exac games (Schmeidle , 1972) is a subclass o BGn. The main p ope y o he games
in his subclass is ha , gi en wo exac games, i hey ha e he same co e, hen hey a e he same
game, i.e., no wo dis inc exac games ha e he same co e. Hence, when wo king wi h exac
games, he co e uses all he in o ma ion o he unde lying game. Since he class o con ex games
is con ained in he class o exac games, he las obse a ion is also ele an o ou amewo k:
no wo dis inc con ex games ha e he same co e. This p ope y ein o ces he mo i a ions o
he co e-cen e wi hin he class o con ex games. Since he co e uses all he in o ma ion o he
game, why no o selec he alloca ion ule ha summa izes all he in o ma ion o he co e?
The esul s in his Sec ion a e o games wi h ull dimensional co e. Hence, when no con usion
a ises, Vol(P)deno es he (n−1)-dimensional olume o poly ope P.
Le Nbe a se o playe s and suppose ha he game (N, )is g adually de ined. Fi s , he
playe s ag ee on he amoun (N) ha is o be di ided. Then, hey ag ee on he indi idual
alues. Hence, only (N)and, o each i∈N, he alue ({i})a e de e mined. To o malize his
s ep we de ine he game (N, ∅), whe e he playe s do no gain any hing by o ming coali ions
di e en om N,
∅(S) = (Pl∈S ({l})S6=N
(N)S=N.
A his poin , a ai alloca ion ule should p o ide some payo in he impu a ion se , and wi hou
any mo e in o ma ion, why no choose he cen e o he impu a ion se ?
Suppose now ha coali ions en e in he game and, o ins ance, playe s 1 and 2 announce
ha , oge he , hey can ge ({1,2}). A his poin , he se o “s able” poin s is C1,2={x∈
I(N, ) : x1+x2≥ ({1,2})}. Clea ly, C1,2is a subse o he impu a ion se and, he la ge is he
di e ence ({1,2})−( ({1})+ ({2})), he smalle is C1,2. Nex , we wan measu e how big is his
se o “s able” poin s, which is con ained in I(N, ). One na u al way is h ough he di e ence
o he olumes, i.e.,Vol(I(N, )) −Vol(C1,2)(no e ha alloca ions in I(N, ) C1,2a e he good
118 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
ones o coali ion N {1,2}). Now, we can epea he a gumen wi h some o he coali ion di e en
om {1,2}; we can compa e he di e en coali ions and “measu e” hei di e ences.
Nex , we in oduce a new class o games: he u opia games. Roughly speaking, hese games
a e such ha he co e o he u opia game o coali ion Sis p ecisely he se o alloca ions ha
a e no “s able” a e coali ion N Sannounces (N S). Fo mally, le (N, )be a con ex game,
and le T∈2N ∅. Le H∈2T ∅. Then, we de ine he game (N, H
T)∈Gnas ollows:5
H
T(S) = 


((T∩S)∪(N T)) − (N T) + (S (T∩S)) H⊆S
((T∩S)∪(N T)) − (N T) + P
l∈S (T∩S)
({l})o he wise.
Despi e o he appa en complexi y o his de ini ion, he speci ic u opia games we look a in his
Chap e allow o mo e anspa en exp essions.
I is easy o check ha
H
T(∅) = 0,
H
T(N) = (N),
i T∩S=∅, H
T(S) = Pl∈S ({l}).
Nex , we in e p e he game (N, H
T). Fo each coali ion S6=T, he alue H
T(S)is he sum
o wo quan i ies. Fi s , he ma ginal con ibu ion o he playe s in S ha a e in T o N T.
Second, he con ibu ion o playe s in S ha a e no in T. Hence, wha a coali ion S⊆Tob ains
in he game H
Tis i s ma ginal con ibu ion o N T,i.e., H
T(S) = (S∪(N T)) − (N T); no e
ha , i S=T, H
T(T) = (N)− (N T).
Take now S⊆Nsuch ha ∅(T∩S(S. The con ibu ion o he playe s in S ha a e no
in Tdepends on he coali ion H. Fixed H, i H⊆S, he con ibu ion o playe s in S (T∩S)
is he u ili y ha hey can gua an ee hemsel es by joining oge he , i.e., (S (T∩S)). On he
o he hand, i H*S, ha con ibu ion is compu ed by Pl∈S (T∩S) ({l}). Roughly speaking,
playe s in Hcan be hough as he ones who ha e he key o allow o coope a ion.
The main idea unde lying he games H
Tis ha he playe s in Ta e he ones who ha e he
powe in he game, bu always espec ing he minimum igh s o playe s in N T. In addi ion,
he game also es ablishes, ia coali ion H, a hie a chical s uc u e among playe s in T. As nex
p oposi ion eads, hese games a e con ex.
P oposi ion 7.1. Le (N, )∈CGn,T∈2N ∅, and H∈2T ∅. Then, (N, H
T)∈CGn.
P oo . See he Appendix.
Nex , we s udy u opia games de ined by coali ions wi h, a mos , wo playe s. Fo hese
special u opia games, he in ui ions highligh ed in he discussion abo e should become clea e .
5We do no use he subgames (S, S)anymo e. Hence, no con usion can a ise because o he no a ion o
u opia games.
7.4. The U opia Games 119
Le i∈Nand T={i}; in his case H=T. Hence o h, we deno e, o each i∈N, he game
(N, {i}
{i})by (N, i). The game (N, i)is he u opia game o playe i, sho ly, i-u opia game:
Fo each S⊆N, i(S) = ( (N)− (N {i}) + (S {i})i∈S
Pl∈S ({l})i /∈S.
In his game playe ihas he key o coope a ion. The o he playe s by hemsel es can only
ge he sum o hei indi idual alues.
We desc ibe now he games H
Twhe e Tis a 2-playe coali ion, T={i, j} ⊆ Nwi h i6=j.
To his ex en , we de ine wo games:
(N, {i}
{i,j})and (N, {j}
{i,j}),6
ha we deno e by (N, (i,j))and (N, (j,i)), espec i ely. The o me , ha we call (i, j)-u opia
game is good o bo h playe s 1and 2, bu excellen o playe 1:
(i,j)(S) = ( ((T∩S)∪(N T)) − (N T) + (S (T∩S)) i∈S
((T∩S)∪(N T)) − (N T) + Pl∈S (T∩S) ({l})i /∈S
=










(N)− (N {i, j}) + (S {i, j})i∈S, j ∈S
(N {j})− (N {i, j}) + (S {i})i∈S, j /∈S
(N {i})− (N {i, j}) + Pl∈S {j} ({l})i /∈S, j ∈S
Pl∈S {l})i /∈S, j /∈S.
Analogously, by in e changing he ole o iand j, we can de ine he (j, i)-u opia game.
The nex concep leads o a classi ica ion o he games in CGn. This classi ica ion looks a he
size o he smalle coali ion, say S, such ha (S)>Pi∈S ({i}),i.e., joining oge he o o m S
is p o i able o he playe s in S. Fo mally, le (N, )∈CGn,n > 2. Le ∈ {1,...,n−1}. Then,
(N, )∈CGn
i (i) o each S⊆Nwi h |S| ≤ , (S) = Pi∈S ({i})and (ii) he e is a coali ion
S,|S|= + 1, such ha (S)>Pi∈S ({i}). On he o he hand, i (N) = Pi∈N ({i}), hen
(N, )∈CGn
n. Le (N, )∈CGn, hen he e is ∈ {1,...,n}such ha (N, )∈CGn
.No e
ha I(N, ) = C(N, )i and only i (N, )∈CGn
, wi h ≥n−1, and hen, by Lemma 7.1
bo h Shapley alue and co e-cen e coincide wi h he ba ycen e o he impu a ion se . Le
(N, )∈CGn
, wi h < n, hen, (i) he co e es ic ions o igina ed by he m-playe coali ions,
1< m ≤ , a e edundan and (ii) he e is a leas one coali ion wi h mo e han playe s imposing
a non- edundan es ic ion on C(N, ).
Lemma 7.3. Le (N, )∈CGn
n−2, n > 2.Then:
6We could also de ine he game (N, {i,j}
{i,j}), whe e H=T. Bu , since we do no use i in ou esul s, we skip
i s de ini ion.
120 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
1
2
4
3
Figu e 7.1: Co e o a game in CG4
2
1
2
4
3
1-u opia co e
2-u opia co e
Figu e 7.2: Co es o wo u opia games
(i) Fo each i∈N, C(N, i) = I(N, i)and
Vol(C(N, i))
Vol(I(N, )) = (N {i})−Pl∈N {i} ({l})
(N)−Pl∈N ({l})!n−1
.
(ii) Le i, j ∈N, i 6=j. Then, C(N, ( i)j) = mσ(N, ), whe e σ∈Π(N)is such ha σ(i) = n
and σ(j) = n−1.
(iii) I(N, ) = Si∈NC(N, i)∪C(N, ).
(i ) Vol(I(N, )) = Pi∈NVol(C(N, i)) + Vol(C(N, )).
P oo . See he Appendix.
Le (N, )∈CGn
n−2. Le p:= Vol(C(N, )),p0= Vol(C(N, ∅)), and, o each i∈N,
pi= Vol(C(N, i). Le he ai game associa ed wi h (N, ),(N, ∗), be de ined as ollows:
∗(S) = 1
pp0 ∅(S)−X
i∈N
pi i(S).
Theo em 7.1. Le (N, )∈CGn
n−2,n > 2. Then, µ(N, ) = Sh(N, ∗).
P oo . The co e-cen e sa is ies w-addi i i y and, by Lemma 7.3, he impu a ion se can be
dissec ed in o n+ 1 poly opes, he co e o (N, )and he co es o he u opia games. Hence,
µ(N, ∅) = p
p0µ(N, ) + Pi∈N
pi
p0µ(N, i). By Lemma 7.1, µ(N, ∅) = Sh(N, ∅),and, o each
7.4. The U opia Games 121
i∈N,µ(N, i) = Sh(N, i). Hence,
µ(N, ) = p0
pµ(N, ∅)−X
i∈N
pi
p0
µ(N, i)=p0
pSh(N, ∅)−X
i∈N
pi
pSh(N, i)
=1
pp0Sh(N, ∅)−X
i∈N
piSh(N, i)= Sh(N, ∗),
whe e he las equali y holds by he addi i i y o he Shapley alue.
Rema k. This p oo has he ollowing ea u e: we s a wi h he co e-cen e o a game and,
in wo s eps, using bo h he w-addi i i y o he co e-cen e and he addi i i y o he Shapley
alue, we end up wi h he Shapley alue o he ai game.
Co olla y 7.3. Le (N, )∈CG3. Then, µ(N, ) = Sh(N, ∗).
P oo . Immedia e om Theo em 7.1.
Rema k. I (N, )∈CG3, he game (N, ∗)summa izes all he in o ma ion o he co e.
The co e o he ai game coincides wi h i s impu a ion se and con ains C(N, ). Following he
de ini ion o (N, ∗)we ha e, o each i∈N, ∗({i}) = ({i})−pi
p (N)− (N {i}) + ({i}).
Hence,
µ(N, ) = ∗({i}) + 1
n (N)−X
k∈N
∗({k}).
Example 7.1. Le (N, )∈G3be such ha , o each i∈N, ({i}) = 0; ({1,2}) = 2, ({1,3}) =
({2,3}) = 5,and (N) = 10.Then,
S ∅ 1 2 3 {1,2} {1,3} {2,3} ∗
{1}0 5 0 0 5 2 0 −2.7174
{2}0 0 5 0 5 0 2 −2.7174
{3}0 0 0 8 0 5 5 −0.6957
{1,2}0 5 5 0 10 2 2 −5.4348
{1,3}0 5 0 8 5 10 5 −3.4130
{2,3}0 0 5 8 5 5 10 −3.4130
N10 10 10 10 10 10 10 10
and,
Sh(N, ) = (2.8333,2.8333,4.3333)
µ(N, ) = (2.6594,2.6594,4.6812).
Le := p/p0and, o each i∈N, i:= pi/p0. In his example we ha e 1= 2= 1/4, 3= 1/25
and = 1 −( 1+ 2+ 3) = 23/50. Hence, playe s 1 and 2 a e less powe ul han playe 3. No e

122 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
ha C(N, (1,2)) = C(N, (2,1)) = (5,5,0). Mo eo e , x∈C(N, {1,2})i and only i
({1,3})− (3) ≤x1≤ (N)− ({2,3}),
({2,3})− (3) ≤x2≤ (N)− ({1,3}),and
x3= ({3}).
1
2
3
C(N, )
I(N, )
Figu e 7.3: Co e o a game in CG3
1
2
3
I(N, )
C(N, )
C(N, ∗) = I(N, ∗)
Figu e 7.4: The co e o he ai game
Since P i= 1 and, o each i∈N,0≤ i≤1, he a ios iha e he ollowing in e p e a ion.
They de e mine a p obabili y dis ibu ion o e he co es o he u opia games and hence, o e
he impu a ion se ; is he p obabili y ha an alloca ion in I(N, )belongs o C(N, )and, o
each i∈N, iis he p obabili y ha an alloca ion in I(N, )belongs o C(N, i). Hence, he
g ea e he co e o he i-u opia game is, he wo se is i’s si ua ion in he game. Roughly speaking,
Figu es 7.3 and 7.4 show ha o (N, ), he “big” u opia co es a e hose o he u opia games o
playe s 1 and 2. Hence, in he co e o he ai game, he “bad” sec ion ha has been added o
playe 3 (wi h espec o he co e o he o iginal game) is smalle han hose o playe s 1 and 2.
We u n now o s udy games in CGn
n−3. We deno e he game ( (i,j))jby (i,j)j.
Lemma 7.4. Le (N, )∈CGn
n−3,n > 3, and le i∈N. Then,
(i) (N, i)∈CGn
n− , < 3.
(ii) Fo each i, j ∈N,i6=j,C(N, ( i)j) = I(N, ( i)j).
(iii) µ(N, i) = Sh(N, ( i)∗).
P oo . (i) I su ices o show ha , o each S⊆Nsuch ha |S| ≤ n−2, we ha e i(S) =
7.4. The U opia Games 123
1
2
4
3
1-u opia co e
1
2
4
3
1-u opia co e
2-u opia co e
(1,2)-u opia co e

1
2
4
3
1-u opia co e
2-u opia co e
1
2
4
3
1-u opia co e
2-u opia co e
(1,2)-u opia co e
(1,2)2-u opia co e
 o
Figu e 7.5: Example o a game in CG4
3wi h some o i s u opia games
124 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
Pk∈S i({k}). Now, o each S⊆N,
i(S) = 




(N)− (N {i}) + (S {i})i∈S, |S| ≥ n−2
(N)− (N {i}) + Pl∈S {i} ({l})i∈S, |S|< n −2
Pl∈S ({l})i /∈S.
Hence, i |S|< n −2, he esul is immedia e; i |S|=n−2, since |S {i}| =n−3we ha e
(S {i}) = Pl∈S {i} ({l}). Hence, o each S⊆Nsuch ha |S| ≤ n−2, i(S) = Pk∈S i({k}).
(ii) and (iii) ollow om Lemma 7.3 and Theo em 7.1.
Lemma 7.5. Le (N, )∈CGn
n−3,n > 3. Le i, j ∈N,i6=jand le (N, (i,j))be he (i, j)-u opia
game. Then, i C(N, (i,j))is ull dimensional we ha e
(i) Sh(N, (i,j)) = µ(N, (i,j)).
(ii) Vol(C(N, (i,j))) =
=√n
(n−2)! (N {i, j})−X
l∈N {i,j}
({l})n−2 (N)− (N {i}) + (N {i, j})− (N {j})
P oo . See he Appendix.
Lemma 7.6. Le (N, )∈CGn
n−3,n > 3. Le i, j ∈N,i6=jand le (N, (i,j))be he (i, j)-u opia
game. Then,
(i) Fo each S⊆N, (i,j)j(S) = ( j)i(S)and C(N, (i,j)j) = C(N, ( j)i).
(ii) µ(N, (i,j)j) = Sh(N, (i,j)j).
(iii) We ha e he ollowing dissec ion o he se o impu a ions:
I(N, ) = C(N, ∅) = [
i∈N
C(N, i)∪[
i<j C(N, (i,j))∪C(N, (i,j)j)∪C(N, ).
P oo . See he Appendix.
Le (N, )∈CGn
n−3. As be o e, le p:= Vol(C(N, )),p0= Vol(C(N, ∅)), and, o each
i∈N,pi= Vol(C(N, i). Mo eo e , o each pai i, j ∈N, le p(i,j)= Vol(C(N, (i,j))) and
p(i,j)j= Vol(C(N, (i,j)j)). Le he ai game associa ed wi h (N, ),(N, ∗), be de ined as
ollows:
∗(S) = 1
pp0 ∅(S)−X
i∈N
pi i(S)−X
i6=j
1
2p(i,j) (i,j)(S) + p(i,j)j (i,j)j(S).
Since o each (N, )∈CGn
n−2, he coe icien s p(i,j)and p(i,j)ja e 0, his de ini ion o ai game
is consis en wi h he old one.
7.4. The U opia Games 125
Le (i,j)=p(i,j)/p0and (i,j)j=p(i,j)j/p0. Then,
(i,j)=
√n
(n−2)!  (N {i,j})−
P
l∈N {i,j} ({l})n−2 (N)− (N {i})+ (N {i,j})− (N {j})
√n
(n−1)!  (N)−
P
l∈N ({l})n−1
= (n−1)  (N {i,j})−
P
l∈N {i,j} ({l})
(N)−
P
l∈N ({l})n−1 (N)− (N {i})+ (N {i,j})− (N {j})
(N)−
P
l∈N ({l}),
and,
(i,j)j= (N {i, j})−Pl∈N {i,j} ({l})
(N)−Pl∈N ({l})!n−1
.
Again, he numbe s (i,j)and (i,j)jcan be in e p e ed as he p obabili ies ha an alloca ion in
C(N, (i,j))o C(N, (i,j)j), espec i ely, is chosen. Acco ding o ou in e p e a ion o he u opia
games, i an alloca ion in C(N, (i,j))is chosen, he coali ion {i, j}would ecei e an “u opic”
payo , i.e., alloca ions in C(N, (i,j))a e he bes o coali ion {i, j}wi hin I(N, ). No e ha
(i,j)= (j,i)and (i,j)j= (j,i)i. This obse a ion is c ucial o unde s and he ollowing esul .
Lemma 7.7. Le (N, )∈CGn
n−3,n > 3. Le i, j ∈N,i6=jand le (N, (i,j))be he (i, j)-u opia
game. Then,
(i,j)µ(N, (i,j)) + (i,j)jµ(N, ( (i,j)){j}) = (j,i)µ(N, (j,i)) + (j,i)iµ(N, ( (j,i)){i}).
P oo . This esul is a consequence o he ollowing equali y:
C(N, (i,j))∪C(N, (i,j)j) = C(N, (j,i))∪C(N, (j,i)i).
Lemma 7.7 shows ha , gi en any wo playe s, he e is an impo an symme y be ween he
wo co esponding 2-playe u opia games. Nex , we s a e ou main Theo em. I p o ides a di ec
ela ion be ween he co e-cen e and he Shapley alue o he ai game.
Theo em 7.2. Le (N, )∈CGn
n−3,n > 3. Then, µ(N, ) = Sh(N, ∗).
P oo . Since
C(N, ∅) = [
i∈N
C(N, i)∪[
i<j C(N, (i,j))∪C(N, (i,j)j)∪C(N, ),
we ha e
µ(N, ∅) = P
i∈N
pi
p0µ(N, i) + P
i<j p(i,j)
p0µ(N, (i,j)) + p(i,j)j
p0µ(N, (i,j)j)+p
p0µ(N, )
=P
i∈N
pi
p0µ(N, i) + P
i6=jp(i,j)
2p0µ(N, (i,j)) + p(i,j)j
2p0µ(N, (i,j)j)+p
p0µ(N, ),
132 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
Again, since (N, )∈CGn
n−3, he la e exp ession can be educed o
mσ
k(N, (i,j)) = 










(N {j})− (N {i, j})k=i
(N)− (N {j})k=j
(N {i, j})−Pl∈N {i,j,k} ({l})σ(k) = n
({k})σ(k)< n.
Now, |Π4a(N)|=(n−1)!
2(n−2) wi h, a mos , n−2di e en ma ginal ec o s.
Le Π4b(N) = {σ∈Π(N) : σ(j) = nand σ(i)< n −1}. Le σ∈Π4b(N). Again, he
ollowing exp essions o he ma ginal ec o s can be de i ed:
mσ
k(N, (i,j)) = 










(N {j})− (N {i, j})k=i
(N)− (N {j})k=j
(N {i, j})−Pl∈N {i,j,k} ({l})σ(k) = n−1
({k})σ(k)< n −1.
Now, |Π4b(N)|= (n−2)!(n−2) wi h, a mos , n−2di e en ma ginal ec o s.
Le Π4(N) = Π4a(N)∪Π4b(N). Then, |Π4(N)|=|Π4a(N)|+|Π4b(N)|=n2−n−2
2(n−2)!.
Mo eo e , i is easy o check ha he pe mu a ions in Π4(N)de ine, a mos , n−2di e en
ma ginal poin s.
Finally, we ha e ha he pe mu a ions in Π(N)de ine, a mos , 2n−2di e en poin s. Fo
ease o exposi ion we assume ha hese poin s a e di e en o each o he .8
Compu a ion o he Shapley alue:
Shi(N, (i,j)) = 1
n!X
σ∈Π(N)
mσ
i(N, (i,j)) = 1
n!
4
X
l=1 X
σ∈Πl(N)
mσ
i(N, (i,j)).
Playe i
Shi(N, (i,j)) = (n−1)!
n! (N)− (N {i}) + (N {i, j})−Xl∈N {i,j} ({l})
+(n−1)!
2n!(n−2) (N)− (N {i})
+(n−2)!
n! (N {j})−Xl6=i,j ({l})
+n2−n−2
2n!(n−2)! (N {j})− (N {i, j}).
8This assump ion does no a ec he algeb a used in his p oo , bu i helps o ge a be e unde s anding o
he geome ic si ua ion unde lying he esul .

7.A. Appendix 133
Simpli ying we ha e,
Shi(N, (i,j)) = (N) + (N {j})− (N {i})
2−1
n−1(n−3)
2 (N {i, j}) + X
l∈N {i,j}
({l}).
Playe j:
Shj(N, (i,j)) = (N {i})− (N {i, j}) + (N)− (N {j})
2.
Playe k6=i, j:
Shk(N, (i,j)) = (n−1)!
n! ({k}
+(n−1)!
2n!(n−3) ({k}) + (n−1)!
2n! (N {i, j})−Xl∈N {i,j,k} ({l}
+(n−2)!
n! ({k})
+n2−n−2
2n!(n−3)!(n−3) ({k}) + (N {i, j})−Xl∈N {i,j,k} ({l}.
Simpli ying we ha e,
Shk(N, (i,j)) = ({k}+1
n−1 (N {i, j})−X
l∈N {i,j}
({l}).
Compu a ion o he co e-cen e :
Fi s , we desc ibe he geome y o C(N, (i,j))(Figu e 7.6 illus a es he geome y o he co e
in an example wi h ou playe s). No e ha , o playe j,
1
2
4
3
Figu e 7.6: The co e o he game (N, (i,j))
134 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
mσ
j(N, (i,j)) = ( (N {i})− (N {i, j})σ∈Π1(N)∪Π2(N)
(N)− (N {j})σ∈Π3(N)∪Π4(N).
Hence, he ma ginal ec o s lie ei he in he hype plane xj= (N)− (N {j})o in he
hype plane xj= (N {i})− (N {i, j})and he e a e, a mos , n−1di e en ma ginal ec o s
in each one o he wo hype planes. Now, i he e is a pai o coinciden poin s in one o he wo
hype planes, hen he e is also a pai o coinciden poin s in he o he one; inducing a degene acy
in he co e. Hence, since C(N, (i,j))is ull dimensional, hese n−1poin s in each hype plane
ha e o be di e en .
Le k∈N {i, j}and σ∈Π(N). We ha e al eady shown ha ei he mσ
k(N, (i,j)) = ({k})
o mσ
k(N, (i,j)) = (N {i, j})−Pl∈N {i,j,k} ({l}). Now, le σ∈Π3(N)∪Π4(N). Then,
mσ(N, (i,j))lies in he hype plane (N)− (N {j}). Mo eo e , he e a e σ1, σ2∈Π3(N)∪Π4(N)
such ha (i) mσ1
k(N, (i,j)) = ({k})and (ii) mσ2
k(N, (i,j)) = (N {i, j})−Pl∈N {i,j,k} ({l}).
An analogous obse a ion is ue o he hype plane xj= (N {i})− (N {i, j})and a pai o
pe mu a ions σ′
1, σ′
2∈Π1(N)∪Π2(N).
Nex , we ake he n−1ma ginal ec o s in he hype plane xj= (N)− (N {j})and
we show ha hey span an (n−2)-simplex. The same can be done o he n−1poin s in
xj= (N {i})− (N {i, j}).
Le k∈N {i, j})and le ukbe he ma ginal ec o lying on he hype plane xj= (N)−
(N {j})in which playe kis be e o . The coo dina es o each uka e he ollowing:
(uk)l=










(N {j})− (N {i, j})l=i
(N)− (N {j})l=j
(N {i, j})−Pl∈N {i,j,k} ({l})l=k.
({l})l6=i, j, k.
Besides, le u0be he emaining ma ginal ec o in xj= (N)− (N {j}):
(u0)l=




(N {j})−Pl∈N {i,j} ({l})l=i
(N)− (N {j})l=j
({l})l6=i, j.
Now, since he ec o s uk−u0a e linea ly independen , he n−1ma ginal ec o s in xj=
(N)− (N {j})de ine a geome ically independen se in Rn. Hence, hey span an (n−2)-
simplex.
Now, o he hype plane xj= (N {i})− (N {i, j})we de ine he same n−1poin s bu
wi h he ollowing di e ences: (i) he j- h coo dina e is (N {i})− (N {i, j})and (ii) he i-
h coo dina e is changed o eco e e iciency (iii) he emaining coo dina es emain unchanged.
Now, since (N, (i,j))is con ex, C(N, (i,j)) = co{mσ(N, ) : σ∈Π(N)}. Hence, he e is an
(n−2)-simplex ∆n−2such ha , o each ∈R, ei he he in e sec ion o C(N, (i,j))wi h he
7.A. Appendix 135
hype plane xj= is emp y o i is a ansla ion o ∆n−2. Hence,
µj(N, (i,j)) = (N {i})− (N {i, j}) + (N)− (N {j})
2,
and i coincides wi h he co esponding coo dina e o he Shapley alue.
Now, because o he symme ies in C(N, (i,j)), o compu e he co e-cen e i su ices o
compu e he ba ycen e o he simplex gene a ed by he n−1poin s on he hype plane xj=
µj(N, (i,j)). Hence, o each k∈N {i, j},
µk(N, (i,j)) = ({k}) + 1
n−1 (N {i, j})−X
l∈N {i,j}
({l})= Shk(N, (i,j)).
Finally, because o he e iciency p ope y o bo h he Shapley alue and he co e-cen e , we
ha e Shi(N, (i,j)) = µi(N, (i,j)).
(ii) Immedia e om he desc ip ion o C(N, (i,j))we ha e made abo e.
7.A.4 P oo o Lemma 7.6
P oo . (i) Since
j(S) = ( (N)− (N {j}) + (S {j})i j∈S
Pl∈S ({l})i j /∈S
and
(i,j)(S) = 










(N)− (N {i, j}) + (S {i, j})i∈S, j ∈S
(N {j})− (N {i, j}) + (S {i})i∈S, j /∈S
(N {i})− (N {i, j}) + Pl∈S {j} ({l})i /∈S, j ∈S
Pl∈S ({l})i /∈S, j /∈S.
Then,
( (i,j))j(S) = ( {i,j}(N)− {i,j}(N {j}) + {i,j}(S {j})j∈S
Pl∈S {i,j}({l})j /∈S
=










(N)− (N {i, j}) + (S {i, j})i∈S, j ∈S
(N)− (N {j}) + Pl∈S {j} ({l})i /∈S, j ∈S
(N {j})− (N {i, j}) + Pl∈S {j,i} ({l})i∈S, j /∈S
Pl∈S ({l})i /∈S, j /∈S.
136 Chap e 7. The Co e-Cen e and he Shapley Value: A Di ec Connec ion
Finally,
( j)i)(S) = ( j(N)− j(N {i}) + j(S {i})i∈S
Pl∈S j({l})i /∈S.
=










(N)− (N {i, j}) + (S {i, j})i∈S, j ∈S
(N {j})− (N {i, j}) + Pl∈S {i} ({l})i∈S, j 6∈ S
(N)− (N {j}) + Pl∈S {j} ({l})i /∈S, j ∈S
Pl∈S ({l})i /∈S, j 6∈ S.
(ii) I ollows om he combina ion o (i) and Lemma 7.4.
The p oo s o (iii) ollow simila lines o he p oo s o hei coun e pa s in Lemma 7.3.
Bibliog aphy 137
Bibliog aphy
Gillies, D. B. (1953): “Some Theo ems on n-Pe son Games,” Ph.D. hesis, P ince on. (Quo ed
in pp. 113)
González-Díaz, J. and E. Sánchez-Rod íguez (2003): “F om Se -Valued Solu ions o Single-
Valued Solu ions: The Cen oid and he Co e-Cen e ,” Repo s in S a is ics and Ope a ions
Resea ch 03-09, Uni e si y o San iago de Compos ela. (Quo ed in pp. 112)
G i zman, P. and V. Klee (1994): “On he Complexi y o Some Basic P oblems in Compu-
a ional Con exi y: Volume and Mixed olumes,” in Poly opes: Abs ac , con ex and compu-
a ional, ed. by T. Bisz iczky, P. McMullen, R. Schneide , and A. Weiss, Kluwe , Bos on MA,
373–466. (Quo ed in pp. 115)
Schmeidle , D. (1972): “Co es o Exac Games I,” Jou nal o Ma hema ical Analysis and Ap-
plica ions, 40, 214–225. (Quo ed in pp. 117)
Shapley, L. S. (1953): “A Value o n-Pe son Games,” in Con ibu ions o he heo y o games
II, ed. by H. Kuhn and A. Tucke , P ince on: P ince on Uni e si y P ess, ol. 28 o Annals o
Ma hema ics S udies.(Quo ed in pp. 112)

Chap e 8
A Geome ic Cha ac e iza ion o he
Comp omise Value
Con en s
8.1 In oduc ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.2 The τ∗Value .................................140
8.3 Main Resul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.4 P oo o he Main Resul . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.5 Concluding Rema ks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Bibliog aphy ...................................159
139
140 Chap e 8. A Geome ic Cha ac e iza ion o he Comp omise Value
8.1 In oduc ion
Mos game- heo e ic solu ion concep s ha ha e been p oposed in he li e a u e a e de ined on
he basis o o cha ac e ized by p ope ies. These p ope ies a e usually o mula ed in e ms o
indi idual payo s and e lec no ions like mono onici y and a ionali y. Fo some alues, he e
exis addi ional cha ac e iza ions in e ms o geome y. The bes -known example is he Shapley
alue (Shapley, 1953), which is he ba ycen e o he ec o s o ma ginal con ibu ions.
Fo some classes o games, he e exis nice geome ic exp essions o he comp omise o τ
alue (Tijs, 1981). In pa icula , he comp omise alue is he ba ycen e o he ex eme poin s o
he co e co e in big boss games (Mu o e al., 1988) and 1-con ex games (D iessen, 1988).
In his Chap e , we ex end he APROP ule o bank up cy p oblems (Cu iel e al., 1987) o
he whole class o comp omise admissible (o quasi-balanced) games (Tijs, 1981). This ex ended
ule, which we call τ∗, u ns ou o be he ba ycen e o he edges o he co e co e , which is ou
main esul . Mo eo e , τ∗and he comp omise alue coincide o mos o quasi-balanced games.
This Chap e is o ganized as ollows. In Sec ion 8.2, we ex end he APROP ule and de ine
he ba ycen e ζo he edges o he co e co e . In Sec ion 8.3, we s a e ou main esul and gi e
an o e iew o he p oo , which consis s o six s eps. Finally, in Sec ion 8.4, we p o e ou main
esul .
8.2 The τ∗Value
A ans e able u ili y o TU game is a pai (N, ), whe e N={1,...,n}is a se o playe s and
: 2N→Ris a unc ion assigning o e e y coali ion S⊆Na payo (S). By con en ion,
(∅) = 0.
Following Tijs and Lippe s (1982), he u opia ec o o a game (N, ),M( )∈RN, is de ined,
o each i∈N,by
Mi( ) := (N)− (N {i}).
The minimum igh ec o mi( )∈RNis de ined, o each i∈N, by
mi( ) := max
S⊆N,i∈S{ (S)−X
j∈S {i}
Mj( )}.
The co e co e o a game (N, )consis s o hose alloca ions o (N)acco ding o which e e y
playe ecei es a mos his u opia payo and a leas his minimal igh :
CC( ) := {x∈RN:X
i∈N
xi= (N), m( )≤x≤M( )}.
A game is comp omise admissible i i has a nonemp y co e co e . We deno e he class o
comp omise admissible games wi h playe se Nby CAN. An alloca ion ule on a subclass
8.2. The τ∗Value 141
A⊆CANis a unc ion ϕ:A→RNassigning o each ∈Aa payo ec o ϕ( )∈RN.
Mo eo e , we say ha ϕis e icien i Pi∈Nϕi( ) = (N).
The comp omise alue o τ alue (Tijs, 1981) is he ule on CANde ined as he poin on he
line segmen be ween m( )and M( ) ha is e icien :
τ( ) := λm( ) + (1 −λ)M( ),
whe e λ∈[0,1] is such ha Pi∈Nτi= (N).
Abank up cy p oblem is a iple (N, E, c), whe e E≥0is he es a e o be di ided and
c∈RN
+wi h Pi∈Nci≥Eis he ec o o claims. The co esponding coope a i e bank up cy
game (N, E,c)is de ined, o each S⊆N, by E,c(S) = max{E−Pi∈N Sci,0}. We deno e he
class o bank up cy p oblems wi h playe se Nby BRN. The class o co esponding games is
a p ope subclass o CAN. A bank up cy ule is a unc ion :BRN→RNassigning o e e y
bank up cy p oblem (N, E, c)∈BRNa payo ec o (E, c)∈RN
+such ha Pi∈N i(E, c) = E.
In he li e a u e, many bank up cy ules ha e been p oposed. One in e es ing ques ion is how
hese can be ex ended in a na u al way o he whole class o comp omise admissible games. In
his Chap e , we conside he p opo ional ule and he adjus ed p opo ional ule (Cu iel e al.,
1987). The p opo ional ule P ROP simply di ides he es a e p opo ional o he claims, i.e.,
o each (N, E, c)∈BRNand each i∈N,
PROPi(E, c) = ci
Pj∈Ncj
E.
The adjus ed p opo ional ule APROP i s gi es each playe i∈Nhis minimal igh mi(E, c) =
max{E−Pj∈N {i}cj,0}and he emainde is di ided using he p opo ional ule, whe e each
playe ’s claim is unca ed o he es a e le :
APROP(E, c) = m(E, c) + P ROP (E′, c′),
whe e E′=E−Pi∈Nmi(E, c)and o each i∈N,c′
i= min{ci−mi(E, c), E′}.
The comp omise alue can be seen as an ex ension o he PROP ule:
τ( ) = m( ) + PROP( (N)−X
i∈N
mi( ), M( )−m( )).
No e ha i ollows om he de ini ion o comp omise admissibili y ha he a gumen o PROP
is indeed a bank up cy p oblem.
Simila ly, we can ex end he APROP ule:
τ∗( ) = m( ) + APROP( (N)−X
i∈N
mi( ), M( )−m( )).
To simpli y he exp ession o τ∗, we show ha he minimum igh s in he associa ed bank up cy