COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS∗
JES´
US MARIO BILBAO†
SIAM J. DISCRETE MATH.c
2003 Socie y o Indus ial and Applied Ma hema ics
Vol. 17, No. 1, pp. 122–133
Abs ac . The goal o his pape is o de elop a heo e ical amewo k in o de o analyze coop-
e a i e games in which only ce ain coali ions a e allowed o o m. We will axioma ize he s uc u e
o such allowable coali ions using he heo y o an ima oids, a no ion de eloped o combina o ially
abs ac se s. The e ha e been p e ious models de eloped o con on he p oblem o unallowable
coali ions. Games es ic ed by a communica ion g aph we e in oduced by Mye son and Owen.
We in oduce a new combina o ial s uc u e called augmen ing sys em, which is a gene aliza ion o
he an ima oid s uc u e and he sys em o connec ed subg aphs o a g aph. The main esul o
he pape is a di ec o mula o Shapley and Banzha alues o games unde augmen ing sys ems
es ic ions.
Key wo ds. coope a i e game, Shapley alue, Banzha alue, se sys ems
AMS subjec classifica ion. 91A12
DOI. 10.1137/S0895480102402745
1. In oduc ion. Coope a i e games unde combina o ial es ic ions a e coop-
e a i e games in which he playe s ha e es ic ed communica ion possibili ies, which
a e defined by a combina o ial s uc u e. The fi s model in which he es ic ions a e
defined by he connec ed subg aphs o a g aph is in oduced by Mye son [11]. Since
hen, many o he si ua ions whe e playe s ha e communica ion es ic ions ha e been
s udied in coope a i e game heo y. Con ibu ions on g aph- es ic ed games include
Owen [12], Bo m, Owen, and Tijs [3], and Hamiache [8]. In hese models he pos-
sibili ies o coali ion o ma ion a e de e mined by he posi ions o he playe s in a
communica ion g aph. Ano he ype o combina o ial s uc u e in oduced by Gilles,
Owen, and an den B ink [7] is equi alen o a subclass o an ima oids. This line
o esea ch ocuses on he possibili ies o coali ion o ma ion de e mined by he posi-
ions o he playe s in he so-called pe mission s uc u e. Sandholm e al. [14] analyze
coali ion o ma ion in combina o ial p oblems.
In he p esen pape , we use he es ic ed coope a ion model de i ed om a
combina o ial s uc u e called augmen ing sys em. Sec ion 2 in oduces his s uc u e,
which is a gene aliza ion o he an ima oid s uc u e and he sys em o connec ed
subg aphs o a g aph. Fu he mo e, his new se sys em includes he conjunc i e
and disjunc i e sys ems de i ed om a pe mission s uc u e. Sec ion 3 in oduces
games unde augmen ing sys ems which gene alize he ones s udied on g aphs and
pe mission s uc u es. Using he s uc u al p ope ies om hese sys ems we will be
able o exp ess he di idends in e ms o he o iginal game. This esul will be essen ial
in sec ion 4 o p o ide di ec o mulas o compu e he Shapley and Banzha alues
o games unde augmen ing sys ems es ic ions. In hese o mulas, hese alues a e
compu ed by means o he o iginal game wi hou ha ing o calcula e he es ic ed
game and aking in o accoun only he coali ions in he augmen ing sys em. Finally,
in sec ion 5 we conside he po en ial and he Owen mul ilinea ex ension (MLE) o
he es ic ed game. These esul s gene alize, uni y and simpli y esul s o Owen [12],
∗Recei ed by he edi o s Feb ua y 15, 2002; accep ed o publica ion (in e ised o m) May 11,
2003; published elec onically Oc obe 2, 2003.
h p://www.siam.o g/jou nals/sidma/17-1/40274.h ml
†Depa men o Applied Ma hema ics II, Escuela Supe io de Ingenie os, Camino de los Des-
cub imien os, 41092 Se illa, Spain ([email p o ec ed], h p://www.esi2.us.es/˜mbilbao/).
122
COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 123
Gilles, Owen, and an den B ink [7], and Bilbao [2].
2. Augmen ing sys ems. An ima oids we e in oduced by Dilwo h [5] as
pa icula examples o semimodula la ices. Since hen, se e al au ho s ha e ob ained
he same concep by abs ac ing a ious combina o ial si ua ions (see Ko e, Lo ´asz,
and Sch ade [10]). In his sec ion, a gene al coope a ion s uc u e is in oduced,
which is a weakening o he an ima oid s uc u e.
Le Nbe a fini e se . A se sys em o e Nis a pai (N,F) whe e F⊆2Nis a
amily o subse s. The se s belonging o Fa e called easible. We will w i e S∪iand
S iins ead o S∪{i}and S {i}, espec i ely.
De ini ion 2.1. A se sys em (N,A)is an an ima oid i
A1. ∅∈A,
A2. o S, T ∈A,we ha e S∪T∈A,
A3. o S∈Awi h S=∅, he e exis s i∈Ssuch ha S i∈A.
The defini ion o an ima oid implies he ollowing augmen a ion p ope y:I
S, T ∈Awi h |T|>|S|, hen he e exis s i∈T Ssuch ha S∪i∈A. We call a
se sys em (N,F)no mal i N=S∈F S.I (N,A) is a no mal an ima oid, hen
p ope y A2 implies ha N∈A.
De ini ion 2.2. An augmen ing sys em is a no mal se sys em (N,F)wi h he
ollowing p ope ies:
P1. ∅∈F,
P2. o S, T ∈F wi h S∩T=∅,we ha e S∪T∈F,
P3. o S, T ∈F wi h S⊂T, he e exis s i∈T Ssuch ha S∪i∈F.
Rema k. I ollows om he defini ion ha no mal an ima oids a e always aug-
men ing sys ems.
P oposi ion 2.3. An augmen ing sys em (N,F)is an an ima oid i and only
i Fis closed unde union.
P oo . The necessa y condi ion ollows om A2. Con e sely, we only ha e o
p o e A3. Le S∈Fwi h S=∅. By p ope y P3 he e exis s a chain o easible
subse s
∅=S0⊂S1⊂···⊂Ss−1⊂Ss=S
such ha Sk∈Fand |Sk|=k o 0 ≤k≤s. Hence he e exis s an elemen i∈S
such ha S i=Ss−1∈F.
Example. The ollowing collec ions o subse s o N={1,... ,n}, gi en by F=2
N
and F={∅,{1},... ,{n}} ,a e he maximum augmen ing sys em and a minimal
augmen ing sys em o e N, espec i ely.
Example. In a communica ion g aph G=(N,E), he se sys em (N,F) gi en by
F={S⊆N:(S, E(S)) is a connec ed subg aph o G}is an augmen ing sys em.
Example. Gilles, Owen, and an den B ink [7] showed ha he easible coali-
ions sys em (N,F) de i ed om he conjunc i e o disjunc i e app oach con ains
he emp y se and he g ound se Nand ha i is closed unde union. Algaba e
al. [1] showed ha he coali ions sys ems de i ed om he conjunc i e and disjunc-
i e app oach we e iden ified o pose an ima oids and an ima oids wi h he pa h
p ope y, espec i ely. Thus, hese coali ions sys ems a e augmen ing sys ems.
Con ex geome ies a e a combina o ial abs ac ion o con ex se s in oduced by
Edelman and Jamison [6].
De ini ion 2.4. A se sys em (N,G)is a con ex geome y i i sa isfies he
ollowing p ope ies:
C1. ∅∈G,
124 JES´
US MARIO BILBAO
C2. o S, T ∈G, we ha e S∩T∈G,
C3. o S∈Gwi h S=N, he e exis s i∈N Ssuch ha S∪i∈G.
P oposi ion 2.5. An augmen ing sys em (N,F)is a con ex geome y i and
only i Fis closed unde in e sec ion and N∈F.
P oo . The necessa y condi ions ollow om p ope ies C2 and C3. To p o e
sufficiency, no e ha (N,F) sa isfies C1 and C2, i.e., i is a closu e sys em o e N.
Mo eo e , (N,F) sa isfies p ope y P3 and N∈F. Then o e e y S∈Fwi h
S=N, he e exis s i∈N Ssuch ha S∪i∈F.
De ini ion 2.6. Le (N,F)be an augmen ing sys em. Fo a easible coali ion
S∈F, we define he se S∗={i∈N S:S∪i∈F}o augmen a ions o Sand he
se S+=S∪S∗={i∈N:S∪i∈F}.
P oposi ion 2.7. Le (N,F)be an augmen ing sys em. Then he in e al
[S, S+]F={C∈F:S⊆C⊆S+}is a Boolean algeb a o e e y nonemp y S∈F.
P oo . I is suffices o show ha [S, S+]F={C⊆N:S⊆C⊆S+}, i.e., o
e e y C⊆Nsuch ha S⊆C⊆S+we ha e C∈F.I S∗=∅, hen [S, S+]F={S}.
O he wise, S∗={i1,... ,i
p}and S⊆C⊆S+implies C=S∪{i1,... ,i
q} o some
1≤q≤p. We p o e ha C∈Fby induc ion on q. Fo q= 1 we know ha S∪{i1}∈
F. Assume S∪{i1,... ,i
k}∈F. Since S∪{ik+1}∈Fand (S∪{i1,... ,i
k})∩
(S∪{ik+1})=S=∅,p ope y P2 yields S∪{i1,... ,i
k,i
k+1}∈F.
Le (N,F) be a se sys em and le S⊆Nbe a subse . A easible subse C∈F
wi h C⊆Sis called a basis o Si C∪i/∈F o all i∈S C. The maximal nonemp y
easible subse s o Sa e called componen s o S. Clea ly, e e y componen o Sis a
basis o S. Howe e , he con e se is no ue, as he ollowing example shows.
Example. I N={1,2,3}and F={∅,{1},{2},{2,3},N}, hen C={1}is a
basis o N, bu he only componen o Nis he g ound se N.
Obse e ha i (N,A) is an an ima oid, hen any subse S⊆Nhas a unique
basis gi en by he ollowing ope a o in (S)={C∈A:C⊆S}.This easible se
is also he unique componen o S.
P oposi ion 2.8. Le (N,F)be an augmen ing sys em and le S⊆Nbe a
subse . Then a nonemp y easible subse C⊆Sis a basis o Si and only i Cis a
componen o S.
P oo . Le C∈Fbe a basis o Sand suppose Cis no a componen o S,
i.e., he e exis s D∈Fsuch ha C⊂D⊆S. Then because o P3 he e exis s
i∈D C⊆S Csuch ha C∪i∈F,which is a con adic ion.
We deno e by CF(S) he se o he componen s o a subse S⊆N. Obse e ha
he se CF(S) may be he emp y se . This se will play a ole in he concep o a
game es ic ed by an augmen ing sys em.
P oposi ion 2.9. A se sys em (N,F)sa isfies p ope y P2 i and only i o
any S⊆Nwi h CF(S)=∅, he componen s o S o m a pa i ion o a subse o S.
P oo . We suppose ha (N,F) sa isfies P2 and le S1,S
2be componen s o S.
I S1∩S2=∅, hen S1∪S2∈Fand we ha e ha Si⊂S1∪S2⊆S o i∈{1,2}.
This con adic s he ac ha S1and S2a e componen s o S. Con e sely, assume
o any Swi h CF(S)=∅ ha i s componen s o m a pa i ion o a subse o S.
Suppose ha (N,F) does no sa is y P2. Then he e a e A, B ∈F,wi h A∩B=∅
and A∪B/∈F. Hence he e mus be a componen C1∈CF(A∪B) wi h A⊆C1
and a componen C2∈CF(A∪B) wi h B⊆C2such ha C1=C2. This con adic s
he ac ha he componen s o A∪Ba e disjoin .
Le N={1,... ,n}be a se o playe s wi h n>2 and we conside a subse S
o s a ing playe s. I i∈S, hen he se {i}is easible. Each s a ing playe ilooks
COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 125
o a playe k/∈S o gene a e a new easible coali ion {i, k}. These coali ions wi h
ca dinali y 2 sea ch o new playe s, which ag ee o join one by one. I we assume
ha common elemen s o wo easible coali ions a e in e media ies be ween he wo
coali ions in o de o es ablish he easibili y o i s union, we ob ain an augmen ing
sys em (N,F). Since he indi idual playe s k/∈Sa e no easible, he amily Fis
no gene a ed by he connec ed subg aphs o a g aph. Mo eo e , i playe s i, j ∈S,
hen {i},{j}∈Sand {i, j}/∈Sand hence (N,F) is no an an ima oid.
Example. Le N={1,2,3,4}and we conside S1={1,2,4}and S2={1,4}.By
using he abo e coali ion o ma ion model we can ob ain he ollowing augmen ing
sys ems, ep esen ed in Figu e 1.
{2, 3}
{1} {4} {1} {4}
{2}
{}
{}
{3, 4}
{1, 2}
Fig. 1.
The se s o maximal easible coali ions a e pa i ions o he playe s in o dis-
join coali ions, ha is, he coali ion s uc u es CS1={{1},{4},{2,3}} and CS2=
{{1,2},{3,4}}. Coali ion s uc u e gene a ion has been s udied by Sandholm e al.
[14].
Example. Le us conside N={1,2,3,4}and
F={∅,{1},{4},{1,2},{3,4},{1,2,3},{2,3,4},N}.
Since {1,2,3}and {2,3,4}a e easible, p ope y P2 implies ha he g and coali ion
Nis a easible se ; see Figu e 2.
{1, 2, 3}
{1, 2}
{1}
{}
{4}
{3, 4}
{2, 3, 4}
{1, 2, 3, 4}
Fig. 2.
126 JES´
US MARIO BILBAO
Example. The se sys em gi en by N={1,2,3,4}and
F={∅,{1},{4},{1,2},{1,3},{2,4},{3,4},
{1,2,3},{1,2,4},{1,3,4},{2,3,4},N}
is an augmen ing sys em. Since {1,4}/∈F, he sys em (N,F) ep esen ed in Figu e
3 is no an an ima oid.
{}
{1, 2}
{1, 2, 3}
{1, 2, 3, 4}
{1}
{3, 4}
{2, 3, 4}
{2, 4}
{1, 3, 4}
{1, 3}
{1, 2, 4}
{4}
Fig. 3.
3. Games es ic ed by augmen ing sys ems.
De ini ion 3.1. Le :2
N→Rbe a coope a i e game and le (N,F)be an
augmen ing sys em. The es ic ed game F:2
N→Ris defined by
F(S)= 
T∈CF(S)
(T).
Rema k. I (N,F) is he augmen ing sys em gi en by he connec ed subg aphs
o a g aph G=(N,E), hen he game N, Fis a g aph- es ic ed game which is
s udied by Mye son [11] and Owen [12].
I S∈F, hen F(S)= (S).Le us deno e by ΓN he ec o space o all
coope a i e games (N, ), i.e., unc ions :2
N→Rsuch ha (∅)=0. E -
e y coope a i e game (N, ) is uniquely de e mined by he collec ion o i s alues
{ (S):S⊆N, S =∅}. Then ΓNwill be iden ified wi h R2n−1. Fo any S⊆N, S =
∅,we define he unanimi y game
uS(T)=1i S⊆T,
0 o he wise.
E e y game is a unique linea combina ion o unanimi y games (c . Shapley [15]),
=
S⊆N
dSuS,whe e dS=
T⊆S
(−1)|S|−|T| (T).
We shall call dS he di idend o Sin he game . Owen [12] showed he ollowing
p ope y: The unanimi y games uS, whe e Sis connec ed in he g aph G, o m a
basis o he g aph- es ic ed games.
Le (N,F) be he sys em o connec ed subg aphs o a g aph G=(N,E). Hami-
ache [8] p o ed a o mula o compu ing he di idends in he game Fby using he

COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 127
alues in he o iginal game . Nex , we ex end Hamiache’s o mula and Owen’s p op-
e y o he case when (N,F) is an augmen ing sys em.
P oposi ion 3.2. Le (N,F)be an augmen ing sys em and le (N, )be a game.
Then he es ic ed game N, Fsa isfies F=C∈F dCuC, whe e he di idend
dC=
{S∈F :S⊆C⊆S+}
(−1)|C|−|S| (S)
o e e y nonemp y C∈F and dC=0o he wise.
P oo . The game Fsa isfies o e e y C⊆N
F(C)= 
T⊆N
dTuT(C)= 
T⊆C
dT,
whe e dT he di idend o Tin he game F. Then, he M¨obius in e sion o mula
implies (see S anley [16]) ha
dC=
T⊆C
(−1)|C|−|T| F(T).
I ollows om F(∅) = 0 ha d∅= 0. So we may assume ha C=∅. The
defini ion o Fimplies ha
dC=
T⊆C
(−1)|C|−|T|

S∈CF(T)
(S)

=
{S∈F :S⊆C}

{T⊆C:S∈CF(T)}
(−1)|C|−|T|
 (S).
Le S∈F wi h S⊆C. We fi s show ha
{T⊆C:S∈CF(T)}=T⊆C:T S⊆C S+.
We ake T⊆C.I S∈CF(T), hen by P oposi ion 2.8, Sis a basis o Tand
hence he se o i s augmen a ions S∗sa isfies S∗∩T=∅.Then o each i∈T Swe
ha e i∈Cand i/∈S∪S∗=S+.
Con e sely, le T⊆Cbe a se such ha T S⊆C S+. Then o each i∈T S
we ha e i/∈S+and hence S∪i/∈F. Thus, he easible se Sis a basis o Tand we
conclude ha S∈CF(T).
The e o e, he coefficien s o dCsa is y

{T⊆C:S∈CF(T)}
(−1)|C|−|T|=
{T⊆C:S⊆T, T S⊆C S+}
(−1)|C|−|T|
=(−1)|C|−|S|

R⊆C S+
(−1)−|R|
.
Nex , we compu e

R⊆C S+
(−1)−|R|=
R⊆C S+
(−1)|R|=(1−1)|C S+|=1i C S+=∅,
0 o he wise.
128 JES´
US MARIO BILBAO
The e o e, C S+=∅⇔C⊆S+, and hence
dC=
{S∈F :S⊆C, C S+=∅}
(−1)|C|−|S| (S)
=
{S∈F :S⊆C⊆S+}
(−1)|C|−|S| (S).
To comple e he p oo we obse e ha P oposi ion 2.7 implies ha he se C∈F.
O he wise C S+=∅, and so dC= 0 o all C/∈F.
4. The Shapley and Banzha alues. Le (N, ) be a game and le (N,F)
be an augmen ing sys em. The Shapley alue o playe iin he es ic ed game F
is gi en by
ΦiN, F=
{S⊆N:i∈S}
(s−1)!(n−s)!
n! F(S)− F(S i),
whe e n=|N|and s=|S|. This alue is an a e age o he ma ginal con ibu ions
F(S)− F(S i)o aplaye i o all coali ions S∈2N {∅}. In his alue, he se s S
o diffe en size ge diffe en weigh . The Banzha alue o playe iin he es ic ed
game Fis gi en by
β
iN, F=
{S⊆N:i∈S}
1
2n−1 F(S)− F(S i)
o all i∈N. I he numbe o playe s is n, hen he unc ion ha measu es he
wo s case unning ime o compu ing hese indices is in O(n2n) (see Deng and
Papadimi iou [4]). Mo eo e , o ob ain he es ic ed game Fwe need o compu e
he se o he componen s CF(S) o e e y subse S⊆N. Then i is necessa y o
conside all he easible subse s o S, and hence he ime complexi y is O( ),whe e
=
n

s=0 n
s2s=3
n.
The Shapley and Banzha alues a e linea mappings wi h espec o he cha ac-
e is ic unc ion, and he images o he unanimi y games a e, espec i ely (c . Owen
[12]),
Φi(N,uS)=1/|S|i i∈S,
0 o he wise,
β
i(N,uS)=12|S i|i i∈S,
0 o he wise.
In e ms o di idends dSin game F, we ha e ha
ΦiN, F=
{S⊆N:i∈S}
dS
|S|,(1)
β
iN, F=
{S⊆N:i∈S}
dS
2|S i|.
COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 129
In he nex heo em, wo explici o mulas, in e ms o , o he Shapley and
Banzha alues o he playe s in he es ic ed game Fa e p o ed. These o mulas
gene alize he esul s ob ained by Bilbao [2] o games es ic ed by con ex geome ies.
Theo em 4.1. Le (N,F)be an augmen ing sys em and le (N, )be a game.
Then
ΦiN, F=
{T∈F :i∈T}
( −1)! ∗!
+! (T)−
{T∈F :i∈T∗}
!( ∗−1)!
+! (T),
β
iN, F=
{T∈F :i∈T}
1
2 +−1 (T)−
{T∈F :i∈T∗}
1
2 +−1 (T),
whe e =|T|, ∗=|T∗|, and +=|T+|.
P oo . By P oposi ion 3.2, we know ha dS= 0 unless S∈F. We use he
o mula (1) and P oposi ion 3.2 o compu ing
ΦiN, F=
{S∈F :i∈S}
dS
|S|
=
{S∈F :i∈S}
1
|S|

{T∈F :T⊆S⊆T+}
(−1)|S|−|T| (T)
.
Re e sing he o de o summa ion and deno ing s=|S|and =|T|, we ob ain
ΦiN, F=
T∈F 

{S∈F :i∈S, T ⊆S⊆T+}
(−1)s−
s
 (T)
=
T∈F
ci(T) (T),
whe e
ci(T)= 
{S∈F :T∪i⊆S⊆T+}
(−1)s−
s.
Fi s , we suppose i∈T. By P oposi ion 2.7 he in e al [T,T+] is a Boolean
algeb a and hence he summa ion index is {S⊆N:T⊆S⊆T+}. Now we conside
S=T∪R, whe e R=S T, =|R|, and ∗=|T∗|. Then
ci(T)= 
R⊆T∗
(−1)
+ =
∗

=0  ∗
(−1)
+
=
∗

=0  ∗
(−1) 1
0
x + −1dx
=1
0
x −1
∗

=0  ∗
(−x) dx
=1
0
x −1(1 −x) ∗dx
=( −1)! ∗!
+!.
130 JES´
US MARIO BILBAO
Nex , assume ha i/∈T; hence he index is {S∈F:T∪i⊆S⊆T+}. Then
i∈T+ Tand hence i∈T∗. Now he p e ious esul yields (no e ha [T∪i, T+]is
a Boolean algeb a)
ci(T)=−
{S⊆N:T∪i⊆S⊆T+}
(−1)s−( +1)
s=− !( ∗−1)!
+!.
Inse ing he coefficien s, we ha e
ΦiN, F=
{T∈F :i∈T}
( −1)! ∗!
+! (T)−
{T∈F :i∈T∗}
( )!( ∗−1)!
+! (T).(2)
The p oo o he o mula o he Banzha alue is simila . The only diffe ence is
ha he coefficien s a e
ci(T)=
∗

=0  ∗
(−1) 1
2 + −1
=1
2 +−1
i i∈T,
ci(T)=−1
2 +−1
i i∈T∗.
Rema k. No ice ha i F=2
N, hen T∗=N Tand T+=N o e e y T∈F.
Thus, he o mulas ob ained in he abo e heo em a e equal o he classical Shapley
and Banzha alues o he game . Mo eo e , equa ion (2) is equal o he equa ion
o Shapley [15].
Le us conside a se sys em (N,F). An elemen io a easible se S∈Fis an
ex eme poin o Si S i∈F. The se o ex eme poin s o Sis deno ed by ex(S).
The o mulas o compu ing he Shapley and Banzha alues o he playe s in he
es ic ed game Fcan be u he simplified when he playe is an ex eme poin o
e e y easible coali ion. Be o e doing so, we will need a lemma.
Lemma 4.2. Le (N,F)be an augmen ing sys em. I i∈ex(S) o all S∈F
which con ains iwi h S={i}, hen (S i)+=S+.
P oo . No e fi s ha i∈(S i)+and i∈S+.Fo e e y j∈(S i)+wi h j=i,
we ha e (S i)∪j∈F. Then ((S i)∪j)∩S=S i=∅implies ((S i)∪j)∪S=
S∪j∈Fand hence j∈S+.Con e sely, o e e y j∈S+,j=i, we know ha
S∪j∈F. Since i∈S⊆S∪j, he assump ion implies ha i∈ex(S∪j).Then
(S∪j) i=(S i)∪j∈F and hus j∈(S i)+.
Theo em 4.3. Le (N,F)be an augmen ing sys em and le (N, )be a game
such ha (i)=0 o all i∈N.I i∈ex (S) o all S∈F ha con ains i, hen
ΦiN, F=
{S∈F :i∈S, |S|>1}
(s−1)! s∗!
s+![ (S)− (S i)] ,
β
iN, F=
{S∈F :i∈S, |S|>1}
1
2s+−1[ (S)− (S i)] ,
whe e s=|S|,s∗=|S∗|, and s+=|S+|.
P oo . We ema k fi s ha i isa isfies he hypo hesis, hen
{S∈F:i∈S, |S|>1}={S∈F:i∈ex (S),|S|>1}.