On he enume a ion o bipa i e simple games
Josep F eixas and Dani Samaniego∗
Ma ch 24, 2021
Abs ac
This pape p o ides a classi ica ion o all mono onic bipa i e simple games. The p ob-
lem we deal wi h is e y e sa ile since simple games a e inequi alen mono onic Boolean
unc ions, unc ions ha a e used in many ields such as game heo y, neu al ne wo ks, a i i-
cial in elligence, eliabili y o mul iple-c i e ia decision-making. The ob ained classi ica ion
can be implemen ed in an algo i hm able o enume a e bipa i e simple games. These numbe s
p o ide some ligh on enume a ions o se e al subclasses o bipa i e simple games, o which
we ind o mulas.
Comple e simple games, a subclass o all simple games o which he desi abili y ela ion
is a comple e p eo de ing, we e al eady classi ied by means o wo pa ame e s: a ec o
and a ma ix ul illing some condi ions. Comple e simple games a e inequi alen mono onic
egula Boolean unc ions. In his pape , we deduce a p ocedu e o bipa i e non-comple e
games, which allows enume a ing he numbe o bipa i e simple games. Se e al o mulas a e
ob ained, in pa icula polynomial exp essions o he numbe o bicame al mee games and
he numbe o bicame al join games, wo ypes o o ing sys ems widely used in p ac ice.
Key wo ds: Dedekind numbe s and simple games; Inequi alen mono onic Boolean unc ions;
Classi ica ion o bipa i e simple games and bipa i e Boolean unc ions; Enume a ion o bi-
pa i e simple games and bipa i e Boolean unc ions; Enume a ion o he bicame al mee and
bicame al join o ing sys ems.
Ma h. Subj. Class.: 40B05, 65Q30, 68R05, 91A12, 91A80, 91B12
1 In oduc ion
In his pape we conside mono onic simple games wi h wo ypes o equi alen playe s, bipa i e
simple games, by he well-known desi abili y ela ion [26, 33]. I his ela ion is a comple e p e-
o de ing hen he simple game is called comple e o linea [5, 7, 43]. A classi ica ion heo em o
comple e simple games was ob ained in [7], which made i possible o enume a e some subclasses
o hese simple games and o s udy o he game heo y p oblems. Fo ins ance, he cha ac e iza ion
o weigh ed games by means o he p ope ies o ade obus ness and in a ian ade obus -
ness [19, 15] o he s udy o weigh ed games wi h a unique ep esen a ion in in ege s, [20, 18, 28].
∗The au ho s a e wi h he Uni e si a Poli `
ecnica de Ca alunya (Campus Man esa), in he Depa men o Ma he-
ma ics; e-mails: [email p o ec ed], [email p o ec ed]; pos al add ess: EPSEM, A da. Bases de
Man esa, 61-73, E-08242 Man esa, Spain.
1
Ano he consequence was he enume a ion o bipa i e comple e games, in [21]. Le BCG(n)be
he numbe o bipa i e comple e games wi h nplaye s. The ollowing closed o mula (sequence
A163250 in OEIS, [37]) was deduced:
BCG(n) = F(n+ 6) −(n2+ 4n+ 8) ∈Θ 1 + √5
2!n!,(1)
whe e F(n)a e he Fibonacci numbe s which cons i u e a well-known sequence o in ege num-
be s de ined by he ollowing ecu ence ela ion: F(n) = F(n−1) + F(n−2) o all n > 1and
F(0) = 0,F(1) = 1. See also [30] o an al e na i e sho e p oo based on gene a ing unc ions.
Close games o bipa i e comple e games a e also enume a ed in [16].
The pu pose o he pape is o classi y all bipa i e simple games, up o isomo phism. As
comple e games we e al eady classi ied, we a e conce ned he e wi h bipa i e non-comple e simple
games. Fo hese games, we p opose a classi ica ion ha allows o gene a e and o enume a e all o
hem o a mode a e numbe o playe s. This enume a ion oge he wi h he one in Equa ion (1) o
bipa i e comple e games allows o gene a e and enume a e bipa i e simple games o a mode a e
numbe o playe s. C i e ia o algeb aically cha ac e ize weigh ed games wi hin bipa i e simple
games can be ound in [24, 17, 15].
Many eal-wo ld examples a e bipa i e simple games. Bipa i e simple games wi h a House
and a Sena e a e common in almos all he coun ies in he wo ld. A p oposal passes i and only i
i passes in bo h chambe s ( he mee o he games in he wo chambe s) o in ei he chambe ( he
join o he games in he wo chambe s). The i s si ua ion is known as he bicame al mee and he
second as he bicame al join, see [43, 12] o mo e de ails on hese games. The bicame al mee
and bicame al join games a e bipa i e simple games, which a e classi ied and enume a ed in his
pape wi h espec o he numbe o playe s.
I is wo h no ing ha he p oblem we deal wi h in his pape is o in e es in many di e en
ields. In ma hema ics, he Dedekind numbe s (sequence A000372 in he OEIS) o m a apidly
g owing sequence o in ege s. This sequence coun s he numbe o mono onic Boolean unc ions
o n a iables. I wo mono onic Boolean unc ions jus di e in he labels o some a iables, hey
a e said o be equi alen . A a ian o he Dedekind numbe s is he sequence o he numbe o
inequi alen mono onic Boolean unc ions (sequence A003182 in he OEIS). No e ha mono onic
simple games up o isomo phism a e he same as inequi alen mono onic Boolean unc ions, and,
comple e simple games a e he same as egula Boolean unc ions. Bipa i e simple games a e he
same as Boolean unc ions wi h wo ypes o equi alen a iables. Thus, he esul s in his pape
a e o in e es in a ious scien i ic disciplines such as Game Theo y [9, 10, 42, 6, 3, 4, 30, 29],
Boolean Algeb a [22, 23], Reliabili y [2, 40, 31, 32], Neu al Ne wo ks [41, 38], Th eshold Logic
and Cohe en S uc u es [11, 35, 36, 39], C yp og aphy and Sec e Sha ing [34, 25, 24], Mul iple-
C i e ia Decision Analysis (MCDA) [8] and e en in Risk Analysis [1, 27].
The es o he pape is o ganized as ollows. Sec ion 2 is de o ed o he necessa y p elimina -
ies o ollow up he pape . Sec ion 3 con ains pa ame iza ions o bipa i e comple e games and
o bipa i e non-comple e games, which allow o gene a e all o hese games, up o isomo phism.
Enume a ions o bipa i e simple games o small numbe s o playe s is p o ided in Sec ion 4,
which ollows om he pa ame e iza ions in Sec ion 3. A o mula o he numbe o bipa i e
simple games wi h a unique minimal winning model ep esen a i e is ob ained in Sec ion 5 and
2
ano he o mula o he numbe o bipa i e simple games wi h a maximal numbe o minimal
winning model ep esen a i es is ob ained in Sec ion 6. Some widely-used o ing sys ems, he
bicame al mee and he bicame al join, a e p esen ed in Sec ion 7 and we show ha hei enume -
a ions a e di ec ly connec ed o he enume a ions ound in Sec ion 5. The Conclusion ends he
pape in Sec ion 8.
2 P elimina ies
Le N={1,2, . . . , n}be a se o playe s. Any subse S⊆Nis a coali ion and sdeno es i s
ca dinali y |S|. Le Wbe a se o coali ions such ha : (i)∅/∈W,(ii)i S⊂Tand S∈W hen
T∈W, and (iii)N∈W. The pai (N, W)de ines a (mono onic) simple game. The coali ions in
N ha a e in Wa e called winning coali ions and he coali ions in N ha a e no in Wa e called
losing coali ions. The in ui ion he e is ha a coali ion Sis a winning coali ion i and only i he
bill o amendmen passes when he playe s in Sa e he ones who o ed o i . A minimal winning
coali ion is a winning coali ion all o whose p ope subse s a e losing. Because o mono onici y,
any simple game is de e mined by i s se o minimal winning coali ions, he e deno ed by Wm.
Two simple games (N, W)and (N0, W0)a e isomo phic i he e exis s a one- o-one co e-
spondence :N→N0such ha S∈Wi and only i (S)∈W0; is called and isomo phism
o simple games.
Le (N, W )be a simple game. Le Wa={S∈W:a∈S},τab :N→Ndeno es
he ansposi ion o playe s a, b ∈N. The desi abili y ela ion is he bina y ela ion %on N:
a%bi and only i τab(Wb)⊆Wa,and say ha ais a leas as desi able as b. The
ela ion %is a p eo de . The equi-desi abili y ela ion, is he equi alence ela ion ≈on N:a≈
bi and only i a%band b%a. The p eo de %induces an o de ing ⩾in he quo ien se
N/ ≈o equi-desi able classes, N1, N2, . . . , N . Hence, Np⩾Nqi and only i a%b o any
a∈Npand any b∈Nq.
A game (N, W)is comple e i he desi abili y ela ion is a o al p eo de ing. I he numbe ,
, o equi-desi able classes o a simple game is = 1 hen he game is comple e and i is called a
symme ic game, o mo e speci ically a k-ou -o -ngame wi h k= 1, . . . , n, which indica es ha a
minimum o k o es o e na e equi ed o de ea he s a us quo. The numbe o non-isomo phic
symme ic games o nplaye s is nsince kcan be any in ege be ween 1and n. In pa icula , he
n-ou -o -ngame is called he unanimi y game.
Abipa i e simple game is a simple game wi h = 2 equi-desi able classes, N1and N2. I he
bipa i e simple game is comple e, we assume, w.l.o.g., ha N1> N2. A bipa i e simple game is
no necessa ily comple e. Wi h as ew as n= 4 playe s one may ind bipa i e simple games no
being comple e.
Example 2.1 Le N={1,2,3,4}and Wm={{1,2},{3,4}}. Then, (N, W)is a bipa i e
game wi h N1={1,2}and N2={3,4}which is no comple e since, o example, 1%/3and
3%/1.
3
3 Two pa ame iza ions o bipa i e simple games
The pu pose o his sec ion is o p esen bipa i e simple games in a mo e compac way ha allows
hei enume a ion. We dis inguish be ween comple e and non-comple e games.
Assume (N, W )is a bipa i e game wi h classes N1and N2. We can associa e o each coali ion
Si s pai s= (|S∩N1|,|S∩N2|). Le Rand Sbe wo coali ions, no ice ha i =s, hen
Ris winning i and only i Sis winning, and, Ris minimal winning i and only i Sis minimal
winning. In 2Nwe de ine he equi alence ela ion R∼Si and only i =s. Thus, he elemen s
in he quo ien se 2N= 2N/∼a e pa i ioned in o winning and losing pai s, deno ed he e W
and L espec i ely. The minimal winning pai s s∈Wm e i y: s∈Wand ∈Li ≤sand
6=s. Thus, a bipa i e game admi s he mo e compac ep esen a ion gi en by nand he lis o
minimal winning pai s s1, s2, . . . , s . I sand s0a e dis inc minimal winning pai s, hey canno
ha e he same i s coo dina e o he same second coo dina e because o mono onici y, hus we
can ake s1, s2, . . . , s indexed so ha he i s coo dina es o he pai s o m a s ic ly dec easing
sequence (and he second coo dina es o m a s ic ly inc easing sequence).
Example 3.1 (Example 2.1 e isi ed) As shown, his bipa i e game is no comple e. Clea ly, 1≈
2and 3≈4. Thus, we can a bi a ily choose N1={1,2}and N2={3,4}so ha (n1, n2) =
(2,2). The se o winning pai s is W={(2,0),(0,2),(2,1),(1,2),(2,2)}, he se o losing pai s
is L={(0,0),(0,1),(1,0),(1,1)}and he se o minimal winning pai s is Wm={(2,0),(0,2)},
hus = 2. The pai (2,0) ep esen s he coali ion {1,2}and he pai (0,2) ep esen s he coali-
ion {3,4}. No e ha he losing pai (1,1) ep esen s he coali ions {1,3},{1,4},{2,3},{2,4}
and he winning pai (2,1) ep esen s he coali ions {1,2,3},{1,2,4}.
Le M(N, W )be he 2× ma ix whose i- h ow is he pai si, we claim ha n oge he
wi h he ma ix Mo minimal winning coali ion pai s de ines he simple game. O cou se, he
condi ions ha Mmus e i y di e depending on whe he he game is comple e o no . These
espec i e condi ions a e s a ed in he nex wo subsec ions.
3.1 Pa ame e iza ion o bipa i e non-comple e games
Playe s aand ba e incompa able i and only i he e a e minimal winning coali ions Sand S0such
ha :
a. Scon ains abu no b.
b. I ais eplaced by bin S, he coali ion becomes losing.
c. S0con ains bbu no a.
d. I bis eplaced by ain S, he coali ion becomes losing.
We now ecall a s anda d no a ion. Le x∈(N∪{0})2and y∈(N∪{0})2, we w i e ha
x≥yi ei he x=yo xi≥yi o i= 1,2and w i e x > y i x≥yand x6=y.
F om he abo e commen s abou playe s incompa abili y and mono onici y, i ollows ha
he e is a ow (s1, s2)in Mwi h s1>0and s2< n2such ha (s1−1, s2+ 1) is no g ea e o
4
equal han a ow o M(i.e., he pai (s1−1, s2+ 1) ep esen s losing coali ions) and (s1, s2)in
Mwi h s1< n1and s2>0such ha (s1+ 1, s2−1) is no g ea e o equal han a ow o M
(i.e., he pai (s1+ 1, s2−1) ep esen s losing coali ions).
Thus, e e y bipa i e non-comple e game can be ep esen ed by nand Mwi h hese wo
p ope ies, and choose n1≥n2 o a oid duplici ies in he p esen a ion o he game. We dis inguish
he case n16=n2 o he case n1=n2.
I n1> n2, and he ec o n= (n1, n2) oge he wi h Mde ine a bipa i e non-comple e
game, hen n0= (n2, n1) oge he wi h M0, whe e M0is ob ained om Mby swaping he wo
columns and in e ing hei o de ings, is isomo phic o he bipa i e non-comple e game gi en by
nand M. Hence, i n16=n2i is su icien o conside only n1> n2 o gene a ing all easible
(non-isomo phic) bipa i e non-comple e games.
I n1=n2 he p e ious p ocess leads o he same bipa i e non-comple e game since n=n0
and M=M0. Ne e heless, ano he ype o duplici y may a ise, o a oid i conside he ollowing
ela ion o ec o s. Le x∈(N∪{0}) and y∈(N∪{0}) , we w i e ha x L y i ei he x=y
o he e is some i(1≤i≤ ) such ha xi> yiand xj=yj o all jwi h j < i. Then he
duplici ies o n1=n2a e a oided by demanding o he ma ix M he condi ion:
(s1,1, s2,1, . . . , s ,1)L(s ,2, s −1,2, . . . , s1,2).
The nex example illus a es hese wo si ua ions.
Example 3.2 a. The bipa i e non-comple e game gi en by n= (4,3) and M=3 0
1 2 is
isomo phic o he bipa i e non-comple e game gi en by n0= (3,4) and M0=2 1
0 3 .
By con en ion, we will only conside he o me game since n1> n2. This non-comple e
game o 7playe s is de ined by 16 minimal winning coali ions: (3,0) ep esen s 4minimal
winning coali ions and (1,2) ep esen s he o he 12.
b. The bipa i e non-comple e game gi en by n= (4,4) and M=3 0
1 2 is isomo phic
o he bipa i e non-comple e game n= (4,4) and M0=2 1
0 3 . By con en ion, we
will only conside he o me game since (3,1) L(2,0).
F om he explana ions in his sec ion and he simila i y wi h he classi ica ion o comple e
games p o ided in [7], we s a e an equi alen , bu mo e compac , way o p esen bipa i e non-
comple e games.
De ini ion 3.3 The pai (n,M) associa ed wi h a bipa i e non-comple e simple game (N, W)
sa is y he ollowing p ope ies:
(1) n1≥n2>0,
(2) 0 < si< n o i= 1,2, . . . , ,
5
(3) si,1> si+1,1and si,2< si+1,2 o i= 1,2, . . . , −1,
(4) i exis s a ow sp= (sp,1, sp,2)o Msuch ha 0< sp+ (−1,1) < n and sp+ (−1,1) is
no g ea e o equal han a ow o M,
(5) i exis s a ow sp= (sp,1, sp,2)o Msuch ha 0< sp+ (1,−1) < n and sp+ (1,−1) is
no g ea e o equal han a ow o M,
(6) (s1,1, s2,1, . . . , s ,1)L(s ,2, s −1,2, . . . , s1,2)i n1=n2.
Mo eo e , each bipa i e non-comple e game (N, W)can be ob ained om a pai (n, M)sa is y-
ing he condi ions (1)-(6).
Obse e ha nei he 0no ncan be a ow o Mbecause 0co esponds o he emp y coali ion,
which is always losing, and, nco esponds o he g and coali ion N, which canno be minimal
in a bipa i e game. Condi ion (4) gua an ees ha N2⩾/ N1and condi ion (5) ha N1⩾/ N2.
F om he condi ions o De ini ion 3.3 we can exhaus i ely lis all bipa i e non-comple e games
o mode a e alues o n. The nex example shows all o hese games o n < 7.
Example 3.4 a. Fo n= 1 he e a e no bipa i e simple games and o n= 2 and n= 3 all
bipa i e simple games a e comple e.
b. Fo n= 4 he e a e wo bipa i e non-comple e games, which a e ob ained om he ec o
n= (2,2) and he ma ices:
(1 1); 2 0
0 2 .
No e ha he second game is a compac p esen a ion o he game in oduced in Example
2.1.
c. Fo n= 5 he e a e six bipa i e non-comple e games, which a e ob ained om he ec o
n= (3,2) and he ma ices:
(2 1); (1 1); 3 0
1 2 ;3 0
1 1 ;3 0
0 2 ;2 0
0 2 .
d. Fo n= 6 he e a e 27 bipa i e non-comple e games, which a e ob ained om he ec o s
(3,3) and (4,2). The ma ices o (3,3) a e:
(2 2); (2 1); (1 1); 3 1
1 3 ;3 1
1 2 ;3 0
1 3 ;3 0
1 2 ;3 0
1 1 ;
3 0
0 3 ;3 0
0 2 ;2 1
1 2 ;2 0
0 2 ;
3 0
2 2
0 3
;
3 0
2 1
0 3
;
3 0
1 1
0 3
.
The ma ices o (4,2) a e:
(3 1); (2 1); (1 1); 4 0
2 2 ;4 0
2 1 ;4 0
1 2 ;4 0
1 1 ;
4 0
0 2 ;3 0
1 2 ;3 0
1 1 ;3 0
0 2 ;2 0
0 2 .
6
3.2 A pa ame e iza ion o bipa i e comple e games
A pa ame e iza ion o comple e simple games was ob ained in [7] by using models o shi -
minimal winning coali ions (a subclass o minimal winning coali ions). He e we adap i o he
bipa i e case and o pai s o minimal winning coali ions. As he game is comple e we can assume
w.l.o.g. ha N1> N2so ha i a∈N1,b∈N2and Sis a minimal winning coali ion con aining b
bu no a, hen (S {b})∪{a}is winning (see condi ion (3) in De ini ion 3.5). Mo eo e , i exis s
a minimal winning coali ion T ha con ains abu no bsuch ha (T {a})∪{b}is no winning
(see condi ion (4) in De ini ion 3.5).
De ini ion 3.5 The pai (n,M) associa ed wi h a bipa i e comple e simple game (N, W)sa is-
ies he ollowing p ope ies:
(1) 0 < si< n o i= 1,2, . . . , ,
(2) ei he s1,1=n1o s1,2= 0,
(3) si+1,1=si,1−1and si,2< si+1,2 o i= 1,2, . . . , −1,
(4) i exis s a ow sp= (sp,1, sp,2)o Msuch ha 0< sp+ (−1,1) < n and sp+ (−1,1) is
no g ea e o equal han a ow o M.
Mo eo e , each bipa i e comple e game (N, W )can be ob ained om a pai (n, M)sa is ying
he condi ions (1)-(4).
Condi ion (1) exp esses ha he pai s o minimal winning coali ions a e well-de ined o he
bipa i e game. Condi ion (2) gua an ees ha N1⩾N2i = 1, and, condi ions (2) and (3)
gua an ee ha N1⩾N2i > 1, because o each ow spo Msuch ha 0< sp+ (1,−1) < n,
i holds ha sp+ (1,−1) is equal o g ea e han a ow o M. Finally, condi ion (4) wi nesses he
exis ence o a minimal winning coali ion Tsuch ha (T {a})∪{b}is no winning wi h a∈N1
and b∈N2. Hence, N2⩾/ N1and he e o e N1> N2.
Obse e ha i s ,1>0and si+1,2=si,2+ 1 o all i= 1,2, . . . , −1, hen s ,2< n2,
o he wise (4) would ail.
4 Enume a ion o bipa i e simple games o a small numbe o play-
e s
Some enume a ions can be deduced om he classi ica ions gi en in De ini ions 3.3 and 3.5. Fo
his pu pose we espec i ely deno e by BCG(n),BNCG(n)and BSG(n) he numbe o bipa i e
comple e games, bipa i e non-comple e games and bipa i e simple games o nplaye s. Le
be he numbe o minimal winning pai s o a bipa i e simple game, we espec i ely deno e by
BCG(n, ),BNCG(n, )and BSG(n, ) he numbe o bipa i e comple e games, bipa i e non-
comple e games and bipa i e simple games o nplaye s and minimal winning pai s.
The aim o he nex esul is o iden i y he in easible combina ions o nand .
7
Lemma 4.1 BNCG(n)=0 i n≤3and BNCG(n, )=0 i n > 3and > jn
2k.
P oo : I n≤3,nhas a leas a componen equal o 1so ha ei he (4) o (5) ail in De ini ion 3.3.
F om De ini ion 3.3 (condi ions (1) and (3)) we ha e n1≥n2and si,1> si+1,1and si,2< si+1,2
o i= 1, . . . , −1. These condi ions oge he wi h (2) imply ha he maximal numbe o minimal
winning pai s is ≤min{n1+ 1, n2+ 1}, bu he condi ions (4) and (5) in De ini ion 3.3 imply
ha none o he wo columns in he ma ix o minimal winning pai s is o med by consecu i e
numbe s. Thus, he maximal numbe o ows is = min{n1, n2}. As n2=n−n1and n1=
1, . . . , n −1, i holds:
max
n1
min{n1, n −n1}=jn
2k
and, he e o e, bn
2cis an uppe bound o i he bipa i e game is no comple e and n≥4.
In Sec ion 6 we will see ha BNCG(n, )6= 0 i n > 3and ≤jn
2k. The ollowing esul
is immedia ely deduced om Lemma 4.1.
Co olla y 4.2
BNCG(n) =
0i n≤3
bn/2c
P
=1
BNCG(n, )i n > 3
F om he condi ions o De ini ion 3.3 we ha e ob ained, by he implemen a ion o a ou ine,
he numbe o bipa i e non-comple e games o some small combina ions o nand , see Table 1.
n↓/ →123456
4 1 1
5 2 4
6 6 18 3
7 10 45 16
8 19 107 72 6
9 28 206 210 39
10 44 381 543 190 10
11 60 634 1190 633 76
12 85 1025 2425 1817 406 15
13 110 1556 4528 4480 1522 130
Table 1: The posi i e numbe s o bipa i e non-comple e games BNCG(n, ), up o isomo phisms,
o n < 14.
Table 2 shows BNCG(n),BCG(n)and BSG(n) o small alues o n. The numbe s BNCG(n)
a e deduced om Co olla y 4.2 and Table 1, which a e bo h consequences o De ini ion 3.3. The
numbe s BCG(n)a e de i ed om Equa ion (1) and he numbe s BSG(n)a e simply he sum o
BCG(n)and BNCG(n).
8
nBCG(n)BNCG(n)BSG(n)
1 0 0 0
2 1 0 1
3 5 0 5
4 15 2 17
5 36 6 42
6 76 27 103
7 148 71 219
8 273 204 477
9 485 483 968
10 839 1168 2007
11 1424 2593 4017
12 2384 5773 8157
13 3952 12326 16278
Table 2: The numbe s o bipa i e non-comple e BNCG(n), bipa i e comple e BCG(n), and bi-
pa i e simple games BSG(n), up o isomo phisms, o n < 14.
5 A o mula o he numbe o bipa i e simple games wi h a unique
minimal winning pai
The aim o his sec ion is o de e mine he numbe o bipa i e simple games wi h a unique pai
o minimal winning coali ions, i.e., o de e mine BSG(n, = 1) o all n. We s a by inding
BNCG(n, = 1) o all n.
Lemma 5.1 Le = 1 and n=n1+n2. The condi ions in De ini ion 3.3 imply ha :
a. he e a e (n1−1)(n2−1) bipa i e non-comple e games wi h = 1 o each ec o decom-
posi ion (n1, n2)such ha n1> n2,
b. he e a e n(n−2)/8bipa i e non-comple e games wi h = 1 o each ec o decomposi-
ion (n1, n2)such ha n1=n2.
P oo :
a. Assume n1> n2. Fo he ow (s1, s2)o Mwe can choose any s1such ha 0< s1< n1
and any s2such ha 0< s2< n2. Any o hese choices e i y he condi ions in De ini-
ion 3.3. Thus, he e a e (n1−1)(n2−1) bipa i e non-comple e games.
b. Assume n1=n2=n/2. Fo he ow (s1, s2)o Mwe can choose any s1such ha
0< s1< n/2and any s2such ha 0< s2≤s1. Any o hese choices e i y he condi ions
in De ini ion 3.3. Thus, he e a e n(n−2)/8bipa i e non-comple e games.
9
a. The bicame al mee o he wo chambe s is he simple game (N, W)such ha N=N1∪N2
and S∈Wi and only i S=S1∪S2wi h S1∈W1and S2∈W2.
b. The bicame al join o he wo chambe s is he simple game (N, W)such ha N=N1∪N2
and S∈Wi and only i ei he S⊇S1o S⊇S2wi h S1∈W1and S2∈W2.
Whene e N1and N2a e known (and hus n1and n2a e also known), we e e o he i s
game as he (k1, k2)-bicame al mee and o he second as he (k1, k2)-bicame al join. No e ha
nei he he (k1, k2)-bicame al mee game no he (k1, k2)-bicame al join ha e null o e s because
he in ege numbe s kia e posi i e.
These wo ypes o games a e linked by duali y as shown in he nex esul . Recall ha he
dual game (N, W ∗)o a simple game (N, W)is de ined as W∗={S⊆N:N S /∈W}. I is
easy o e i y ha %∗=%and ≈∗=≈and a game is comple e i and only i he dual is.
P oposi ion 7.1 The dual game o he (k1, k2)-bicame al mee game is he
(n1−k1+ 1, n2−k2+ 1)-bicame al join game.
P oo : Conside he (k1, k2)-bicame al mee game. Any coali ion S o med by ei he k1−1
membe s o he i s ype and n2membe s o he second ype o by n1membe s o he i s ype
and k2−1membe s o he second ype is no winning, mo eo e any supe se o Sis a winning
coali ion. Thus, N Sis a minimal winning coali ion in he dual game and i has ei he n1−k1+1
membe s o he i s ype o n2−k2+ 1 membe s o he second ype.
P oposi ion 7.2 The (k1, k2)-bicame al mee game o wo chambe s wi h espec i e ca dinali ies
n1and n2is:
a. a bipa i e game i and only i k1+k2< n1+n2.
b. a bipa i e comple e game i ki=ni o one o he wo chambe s i= 1,2.
c. a bipa i e non-comple e game i ki< ni o e e y i= 1,2.
P oo :
a. The condi ions k1=n1and k2=n2imply unanimi y in bo h chambe s and hen unanimi y
in he bicame al mee game. Thus, he game has only one minimal winning coali ion, N,
and all playe s a e equi-desi able. Hence, he game is no bipa i e bu symme ic. The nex
wo pa s p o e he o he implica ion.
b. As ki=ni o one o he wo chambe s i= 1,2, he playe s o such chambe ha e e o in
he (k1, k2)-bicame al mee game o he wo chambe s and he playe s in he o he chambe
ha e no e o in he (k1, k2)-bicame al mee game. Thus, he playe s in he o me chambe ,
ha wi h ki=ni, s ic ly domina e playe s in he o he chambe in he (k1, k2)-bicame al
mee game. Hence, he game is bipa i e and comple e.
16
c. As 0< ki< ni o e e y i= 1,2. Bo h (k1+1, k2−1) and (k1−1, k2+1) a e well-de ined
pai s o losing coali ions, which imply ha nei he N1≥N2no N2≥N1a e ue. Thus,
he game is bipa i e and non-comple e.
The nex esul is a consequence o he duali y esul , P oposi ion 7.1, and P oposi ion 7.2.
P oposi ion 7.3 The (k1, k2)-bicame al join game o wo chambe s wi h espec i e ca dinali ies
n1and n2is:
a. a bipa i e game i and only i k1+k2>2.
b. a bipa i e comple e game i ki= 1 o one o he wo chambe s i= 1,2.
c. a bipa i e non-comple e game i ki>1 o e e y i= 1,2.
Le BMCG(n),BMNCG(n)and BMSG(n)be he espec i e numbe o bicame al mee : com-
ple e games, non-comple e games, and simple games o nplaye s. Le BJCG(n),BJNCG(n)and
BJSG(n)be he espec i e numbe o bicame al join: comple e games, non-comple e games, and
simple games o nplaye s. F om P oposi ion 7.2-(c) and P oposi ion 7.3-(c) i ollows:
Co olla y 7.4
BMNCG(n) = BJNCG(n) = BNCG(n, = 1).
Mo eo e , BMCG(n) = BJCG(n)bu hey do no coincide wi h BCG(n, = 1) because null
playe s a e admi ed when enume a ing bipa i e comple e games wi h = 1, bu his is no he
case when enume a ing bipa i e comple e games coming om a bicame al mee o a bicame al
join. The enume a ion o BMCG(n)o BJCG(n)is ob ained by sub ac ing he numbe o bipa i e
comple e games wi h = 1 and ha ing null playe s o BCG(n, = 1). F om his obse a ion, we
ob ain:
BMCG(n) = BJCG(n) = 1
2(n−1)(n−2).
F om he las equali ies, Co olla y 7.4 and Theo em 5.2 i ollows:
BMSG(n) = BJSG(n) =
(n−2)(n2−4n+ 6)
12 +(n−1)(n−2)
2,i nis e en
(n−1)(n−2)(n−3)
12 +(n−1)(n−2)
2,i nis odd
which a e simpli ica ion becomes:
BMSG(n) = BJSG(n) =
n(n−2)(n+ 2)
12 ,i nis e en
(n−1)(n−2)(n+ 3)
12 ,i nis odd
17
8 Conclusion
In his pape , we ha e p o ided wo pa ame iza ions use ul o gene a e all bipa i e non-comple e
games up o isomo phism and all bipa i e comple e games up o isomo phism; pu ing hem o-
ge he we could gene a e all bipa i e simple games. The p oblem we ha e deal wi h in his pape
is e y e sa ile since mono onic simple games up o isomo phisms a e inequi alen mono onic
Boolean unc ions. Thus, he p oblem o enume a ing bipa i e simple games is equi alen o he
p oblem o enume a ing inequi alen mono onic Boolean unc ions wi h wo ypes o equi alen
a iables.
We ha e ob ained polynomial exp essions o he numbe o bipa i e games wi h a unique pai
o minimal winning coali ions and wi h a maximal numbe o minimal winning coali ion pai s.
These enume a ions conce n he numbe o bipa i e: comple e games, non-comple e games and
simple games. These closed o mulas ha e also equi alences in e ms o inequi alen mono onic
Boolean unc ions.
The bicame al mee and he bicame al join a e wo eal-wo ld o ing sys ems widely used in
p ac ice. These commonly used o ing sys ems a e bipa i e games. We ha e s udied o hem
hei ela ion and hei common enume a ion.
As a as we know, he enume a ions ob ained in his pape do no appea in “The On-Line En-
cyclopedia o In ege Sequences” (www.oeis.o g). The only excep ion is he sequence A005993,
which appea s he e in a di e en con ex .
We sugges some lines o u u e esea ch ela ed o ou pape . Fi s , he gene aliza ion o
ou pa ame iza ions om bipa i e games o ipa i e games o o games wi h mo e han wo
equi alence classes, i.e., he ex ension o = 3 o any > 2o De ini ions 3.3 and 3.5. The
classi ica ion we ob ain in his pape o non-comple e bipa i e games gi es some hin s on a
gene al classi ica ion o mo e han wo equi alence classes. Second, inding closed o mulas o
he numbe o bipa i e games wi h wo o mo e pai s o minimal winning coali ions, i.e., he
ex ensions o ≥2o Theo em 5.2, P oposi ion 5.3 and Co olla y 5.4. Thi d, p o ing ha
BNCG(n)∈Θ (2n).
which would imply ha BSG(n)∈Θ (2n)since BSG(n) = BCG(n) + BNCG(n)and 1+√5
2<2.
The analogous enume a ions ob ained in his pape o ipa i e games wi h ei he e oes o nulls
and o quad ipa i e games wi h e oes and nulls ha e been ob ained, in [13], qui e ecen ly as an
applica ion o he esul s ound in his pape .
A complemen a y s udy could be o de e mine he dimension (and codimension), he mini-
mum numbe o weigh ed games equi ed o exp ess he game as in e sec ion (union) o hem, o
bipa i e simple games o inding an uppe bound o he dimension o bipa i e games depending
on he numbe o playe s.
Ano he in e es ing p oblem is o de e mine whe he he cha ac e iza ion o weigh ed games
wi hin he class o simple games in e ms o pseudoweigh ings ob ained in Theo em 1 in [14], can
be elaxed o in e io le els o bipa i e simple games.
18
Acknowledgemen s
This esea ch has been pa ially suppo ed by unds om he Minis y o Science, Inno a ion and
Uni e si ies g an PID2019-104987GB-I00.
We hank William Zwicke o his help ul commen s on his pape , especially hose conce ning
he bicame al mee and he bicame al join connec ion wi h bipa i e simple games. We a e also
g a e ul o wo e e ees o hei cons uc i e commen s ha helped us o imp o e he p esen
e sion.
We also hank o wo anonymous e iewe s whose commen s g ea ly con ibu ed o imp o e
he pape .
Re e ences
[1] T. A en. Reliabili y and isk analysis. Else ie Applied Science, London, G ea B i ain,
1992.
[2] T. A en and U. Jensen. S ochas ic Models in Reliabili y. Sp inge , New Yo k, 1999.
[3] M. Axeno ich and S. Roy. On he s uc u e o minimal winning coali ions in simple o ing
games. Social Choice and Wel a e, 34(3):429–440, 2010.
[4] S. Bolus. Powe indices o simple games and ec o -weigh ed majo i y games by means
o bina y decision diag ams. Eu opean Jou nal o Ope a ional Resea ch, 210(2):258–272,
2011.
[5] F. Ca e as. A cha ac e iza ion o he Shapley–Shubik index o powe ia au omo phisms.
S ochas ica, 8:171–179, 1984.
[6] F. Ca e as. A decisi eness index o simple games. Eu opean Jou nal o Ope a ional Re-
sea ch, 163(2):370–387, 2005.
[7] F. Ca e as and J. F eixas. Comple e simple games. Ma hema ical Social Sciences,
32(2):139–155, 1996.
[8] W.D. Cook. Dis ance–based and ad hoc consensus models in o dinal p e e ence anking.
Eu opean Jou nal o Ope a ional Resea ch, 172:369–385, 2006.
[9] E. Einy. The desi abili y ela ion o simple games. Ma hema ical Social Sciences, 10(2):155–
168, 1985.
[10] E. Einy and E. Leh e . Regula simple games. In e na ional Jou nal o Game Theo y,
18(2):195–207, 1989.
[11] C.C. Elgo . T u h unc ions ealizable by single h eshold o gans. In AIEE Con e ence
Pape 60-1311 (Oc obe ), e ised No embe 1960; pape p esen ed a IEEE Symposium on
Swi ching Ci cui Theo y and Logical Design, Sep embe 1961.
19
[12] D.S. Felsen hal, M. Macho e , and W.S. Zwicke . The bicame al pos ula es and indices o a
p io i o ing powe . Theo y and Decision, 44(1):83–116, 1998.
[13] J. F eixas. On he enume a ion o Boolean unc ions wi h dis inguished a iables. So
Compu ing, 2020. h ps://doi.o g/10.1007/s00500-020-05422-5
[14] J. F eixas. A cha ac e iza ion o weigh ed simple games based on pseudoweigh ings. Op i-
miza ion Le e s, 2020. h ps://doi.o g/10.1007/s11590-020-01647-3
[15] J. F eixas, M. F eixas, and S. Ku z. On he cha ac e iza ion o weigh ed simple games.
Theo y and Decision, 83(4):469–498, 2017.
[16] J. F eixas and S. Ku z. The golden numbe and Fibonacci sequences in he design o o ing
sys ems. Eu opean Jou nal o Ope a ional Resea ch, 226(2):246–257, 2013.
[17] J. F eixas and S. Ku z. Enume a ions o weigh ed games wi h minimum and an analysis o
o ing powe o bipa i e comple e games wi h minimum. Annals o Ope a ions Resea ch,
222:317–339, 2014.
[18] J. F eixas and X. Moline o. On he exis ence o a minimum in ege ep esen a ion o
weigh ed o ing sys ems. Annals o Ope a ions Resea ch, 166(1):243–260, 2009.
[19] J. F eixas and X. Moline o. Simple games and weigh ed games: a heo e ical and compu a-
ional iewpoin . Disc e e Applied Ma hema ics, 157(7):1496–1508, 2009.
[20] J. F eixas and X. Moline o. Weigh ed games wi hou a unique minimal ep esen a ion in
in ege s. Op imiza ion Me hods and So wa e, 25(2):203–215, 2010.
[21] J. F eixas, X. Moline o, and S. Rou a. Comple e o ing sys ems wi h wo ypes o o e s:
weigh edness and coun ing. Annals o Ope a ions Resea ch, 193(1):273–289, 2012.
[22] P.L. Hamme and R. Holzman. App oxima ions o pseudoboolean unc ions; applica ions o
game heo y. ZOR Me hods and Models o Ope a ions Resea ch, 36:3–21, 1992.
[23] P.L. Hamme , T. Iba aki, and U.N. Peled. Th eshold numbe s and h eshold comple ions. In
P. Hansen, edi o , S udies on G aphs and Disc e e P og amming, pages 125–145. No hHol-
land, Ams e dam, The Ne he lands, 1981.
[24] J. He anz. Any 2-asummable bipa i e unc ion is weigh ed h eshold. Disc e e Applied
Ma hema ics, 159:1079–1084, 2011.
[25] J. He anz and G. S´
aez. New esul s on mul ipa i e access s uc u es. IEEE P oceedings-
In o ma ion Secu i y, 153(4):153–162, 2006.
[26] J.R. Isbell. A class o majo i y games. Qua . J. Ma h. Ox o d Se ., 7(2):183–187, 1956.
[27] W. Kuo and X. Zhu. Impo ance measu es in eliabili y, isk, and op imiza ion. Wiley,
Malaysia, 2012.
[28] S. Ku z. On minimum sum ep esen a ion o weigh ed o ing games. Annals o Ope a ions
Resea ch, 196(1):361–369, 2012.
20
[29] S. Ku z, A. Maye , and S. Napel. Weigh ed commi ee games. Eu opean Jou nal o Ope a-
ional Resea ch, 282(3):972–979, 2020.
[30] S. Ku z and N. Tau enhahn. On Dedekind’s p oblem o comple e simple games. In e na-
ional Jou nal o Game Theo y, 42(2):411–437, 2013.
[31] G. Le i in. Op imal alloca ion o mul i-s a e elemen s in linea consecu i ely connec ed
sys ems wi h ulne able nodes. Eu opean Jou nal o Ope a ional Resea ch, 150(2):406–
419, 2003.
[32] G. Le i in, L. Podo illini, and E. Zio. Gene alised impo ance measu es o mul i–s a e
elemen s based on pe o mance le el es ic ions. Reliabili y Enginee ing and Sys em Sa e y,
82(3):287–298, 2003.
[33] M. Maschle and B. Peleg. A cha ac e iza ion, exis ence p oo , and dimension bounds o
he ke nel o a game. Paci ic Jou nal o Ma hema ics, 18:289–328, 1966.
[34] C. Mi chell. Enume a ing boolean unc ions o c yp og aphic signi icance. Jou nal o C yp-
ology, 2(3):155–170, 1990.
[35] S. Mu oga, I. Toda, and S. Takasu. Theo y o majo i y decision elemen s. Jou nal F anklin
Ins i u e, 271(5):376–418, 1961.
[36] S. Mu oga, T. Tsuboi, and R. Baugh. Enume a ion o h eshold unc ions o eigh a iables.
IEEE T ansac ions on Compu e s, C-19(9):818–825, 1970.
[37] N.J.A. Sloane. h ps://oeis.o g/, 1964.
[38] P.D. Pic on. Neu al Ne wo ks. The Macmillan P ess LTD (2nd Edi ion), London, G ea
B i ain, 2000.
[39] K.G. Ramamu hy. Cohe en s uc u es and simple games. Kluwe Academic Publishe s,
Do d ech , The Ne he lands, 1990.
[40] M. Rausand and A. Høyland. Sys em eliabili y heo y: Models, s a is ical me hods and
applica ions. 2nd ed. Hoboken. John Wiley & Sons, New Je sey, USA, 2004.
[41] V.P. Roychowdhu y, K.Y. Siu, and A. O li sky (Eds.). Theo e ical Ad ances in Neu al Com-
pu a ion and Lea ning. Kluwe Academic Publishe s, S an o d, USA, 1994.
[42] A.D. Taylo and W.S. Zwicke . Weigh ed o ing, mul icame al ep esen a ion, and powe .
Games and Economic Beha io , 5:170–181, 1993.
[43] A.D. Taylo and W.S. Zwicke . Simple games: desi abili y ela ions, ading, and pseu-
doweigh ings. P ince on Uni e si y P ess, New Je sey, USA, 1999.
21
