G oup s a egy-p oo social choice unc ions
wi h bina y anges and a bi a y domains: cha -
ac e iza ion esul s1
Sal ado Ba be ày
Dolo s Be gaz
and
Be na do Mo enox
Ap il 28 h, 2010
Abs ac : We de…ne di¤e en concep s o g oup s a egy-p oo ness o social choice
unc ions. We discuss he connec ions be ween he de…ned concep s unde di¤e en
assump ions on hei domains o de…ni ion. We cha ac e ize he social choice
unc ions ha sa is y each one o hem and whose anges consis o wo al e na i es,
in e ms o wo ypes o basic p ope ies.
JEL Classi…ca ion Numbe : D71.
Keywo ds: Social choice unc ions, Bina y anges, g oup s a egy-p oo ness,
xy-mono onici y, xy-based ules.
1We would like o hank he commen s o Wal e Bosse and Luis Co chón. Sal ado
Ba be à g a e ully acknowledges suppo om he Spanish Minis y o Science and Inno-
a ion h ough g an "Consolida ed G oup-C" ECO2008-04756, and by he Gene ali a
de Ca alunya, Depa amen d’Uni e si a s, Rece ca i Socie a de la In o mació h ough
he Dis inció pe a la P omoció de la Rece ca Uni e si à ia, g an SGR2009-0419 and he
Ba celona GSE Resea ch Ne wo k. Dolo s Be ga acknowledges he suppo o he Spanish
Minis y o Science and Inno a ion h ough g an SEJ2007-60671 and o Gene ali a de
Ca alunya, h ough g an SGR2009-0189. She also acknowledges he Resea ch Recogni-
ion P og amme o he Ba celona GSE. Be na do Mo eno acknowledges …nancial suppo
om he Spanish Minis y o Science and Inno a ion h ough g an ECO2008-03674.
yMOVE, Uni e si a Au ònoma de Ba celona, and Ba celona GSE, Edi…ci B, 08193
Bella e a, Spain. E-mail: sal ado .ba b[email p o ec ed]
zDepa amen d’Economia, Campus de Mon ili i, Uni e si a de Gi ona, 17071 Gi ona,
Spain. E-mail: dolo s.b[email p o ec ed]
xDepa amen o de Teo ía e His o ia Económica, Facul ad de Ciencias Económicas y
Emp esa iales, Campus de El Ejido, 29071 Málaga, Spain. E-mail: b[email p o ec ed]
1 In oduc ion
The Gibba d-Sa e hwai e Theo em es ablishes ha , when a social choice
unc ion is de…ned on he uni e sal se o p e e ence p o…les o e kal e na-
i es (k > 2), and i s ange con ains a leas h ee al e na i es, i can only
be s a egy-p oo i i is dic a o ial.
This esul is subjec o di¤e en quali…ca ions. One is ha , when he
ule is de…ned on smalle se s o p o…les, he e may o may no exis o he
ules ha a e s a egy-p oo , in addi ion o he dic a o ial ones. This is he
case unde a a ie y o domains, ha include he ones o med by he Ca e-
sian p oduc o single-peaked p e e ences, o o single-dipped p e e ences, o
o sepa able p e e ences, among o he s. Ou s a emen s in his pape will be
essen ially ue o unc ions de…ned on any domain, howe e small, asym-
me ic o special i may be.1
A second quali…ca ion conce ns he ange o he social choice unc ion.
In his pape we conside he subclass o unc ions ha ail o mee Gibba d
and Sa e hwai e’s equi emen ha hei ange should con ain a leas h ee
al e na i es. Speci…cally, we concen a e on ules ha a e no cons an and
whose ange consis s o exac ly wo al e na i es, xand y. Because o his,
i is known ha in ha case he e a e possibili ies o design non-dic a o ial
s a egy-p oo ules. We wan o cha ac e ize hem all. This leads us o
no ice ha he ange o a social choice unc ion may be bina y because
he e a e only wo al e na i es in he ele an wo ld, bu i may also be
bina y in he p esence o mo e han wo al e na i es, in which case his may
be conside ed as one pa o he possible choices open o he mechanism
designe . As we shall see, he cha ac e iza ion o bina y ules in his con ex
equi es a numbe o p ecisions and ca e ul ea men ha can be a oided in
wo lds whe e only wo al e na i es a e p esen o begin wi h.
A hi d quali…ca ion e e s o he no ion o s a egy-p oo ness o be used.
When we concen a e on ules wi h bina y anges, he e exis a numbe o
a ac i e s a egy-p oo ules, and i becomes hen much mo e in e es ing
o explo e he ex en o which some o hem may also be immune o ma-
nipula ion by g oups. We analyze his ques ion ca e ully, unde a numbe o
di¤e en possible no ions o g oup s a egy-p oo ness, and also by keeping in
mind ha we wan ou s a emen s o hold o unc ions de…ned on any ype
1By "essen ially ue" we mean ha hey a e ei he ue wi hou quali…ca ion, o ue
unde e y mino assump ions, o be discussed case by case.
1
o domains.
One de…ni ion o g oup s a egy-p oo ness equi es ha i should no be
possible o a g oup o agen s o de ia e om decla ing hei ue p e e ences
and ge a s ic gain o each one o hem. Social choice unc ions a oiding
his s ong ype o manipula ion a e called Weakly G oup S a egy-P oo . A
second de…ni ion s a s om conside ing ha a g oup can p o… ably de i-
a e i some o i s membe s de i e a s ic gain om doing so, while o he s
simply emain indi¤e en while helping hei pa ne s. Rules ha a oid his
weake o m o manipula ion a e called S ongly G oup S a egy-P oo . In
an in e media e e sion o he p ope y, ha we simply call G oup S a egy-
P oo ness, we allow ha only some agen s may gain om he de ia ion,
bu we equi e ha all agen s in ol ed in ge ing he change should ac i ely
pa icipa e in he manipula ion by ac ually de ia ing om hei u h ul p e -
e ence. We p o ide cha ac e iza ions o he classes o social choice unc ions
ha sa is y each one o hese h ee p ope ies, and also we elabo a e on why
we single ou hese pa icula de…ni ions.
Ou main cha ac e iza ion esul s iden i y wo ypes o basic p ope ies
ha hese ules mus sa is y. These p ope ies mus be quali…ed in each
case. Since we allow indi iduals o be indi¤e en be ween xand y, in some
cases we will equi e ha hey a e sa is…ed "essen ially", and in o he cases
no . By "essen ially" we mean ha he p ope ies will hold condi ional o
he ac ha he p e e ences o indi iduals ha a e indi¤e en be ween he
wo al e na i es in he ange emain cons an . Ou … s condi ion is ha
o essen ial xy-mono onici y: i xob ains a a p o…le, and hen some people
change hei p e e ences so ha he suppo o xinc eases, while he suppo
o ydoes no , hen xmus s ill ob ain a he new p o…le. A mo e demanding
equi emen in a simila spi i is ha o xy-s ong mono onici y. In ha case
i xob ains a a p o…le, and p e e ence changes induce la ge suppo o x;
hen xs ill be chosen a he new p o…le e en i suppo o ymay ha e also
inc eased.2A second ype o equi emen e e s o he ype o in o ma ion on
which ou ules may be based. We say ha hey a e xy-based i wha hey
choose a each p e e ence p o…le only depends on he ela i e posi ion o x
wi h espec o y o each indi idual. I is essen ially xy-based i he p ope y
holds when we only compa e p o…les whe e indi iduals indi¤e en be ween
2In his second de…ni ion we d op he quali…ca ion o he p ope y being essen ial
because he s a emen is no longe condi ioned o he p e e ences o indi¤e en indi iduals
emaining cons an .
2
xand ykeep hei p e e ences unchanged. No ice also ha he equi emen
will no apply in he case whe e all indi iduals a e indi¤e en be ween bo h
al e na i es in he ange.
We es ablish h ee cha ac e iza ion esul s in e ms o he abo e condi-
ions, one o each o ou h ee ypes o g oup s a egy-p oo ness equi e-
men s. A social choice unc ion is weakly g oup s a egy-p oo i and only i
i is essen ially xy-based and essen ially xy-mono onic. I is s ongly g oup
s a egy-p oo i and only i i is xy-based and xy-s ong mono onic. Finally,
we show ha , when n3and unde a mild condi ion on he ichness o he
domain, ules ha mee ou in e media e no ion o g oup s a egy-p oo ness
a e also s ongly g oup s a egy-p oo , and hus sa is y he same p ope ies.
The sophis ica ed eade will ealize ha ou condi ions a e pa o a la ge
se o di¤e en equi emen s ha ha e been used by di¤e en au ho s unde
di¤e en names o he cha ac e iza ion o s a egy-p oo ules o e uni e sal
domains. Names like Maskin mono onici y, s ong posi i e associa ion, and
o he s ha e been used o deno e a ia ions o p ope ies ha one expec s o
be sa is…ed by ules ha a e s a egy-p oo . And, indeed, many combina ions
o p ope ies end up cha ac e izing he same ules when hese a e de…ned on
ich enough domains. We eel ha ou choice o p ope ies is especially … ,
because hey allow us o cha ac e ize ules de…ned on all kinds o domains,
possibly e y asymme ic and con aining ew p e e ences. The equi alence
be ween ou s and o he p ope ies is no g an ed unde hese ci cums ances.
Also no ice ha we do no insis on indi idual s a egy-p oo ness as a special
case o cha ac e ize. This is because by a ecen esul o ou s, i is an es ab-
lished ac ha indi idual and weak g oup s a egy-p oo ness a e equi alen
when he ange o he social choice unc ion consis s o only wo (o h ee)
elemen s (see Ba be à, Be ga, and Mo eno, 2010).
A di¤e en ype o cha ac e iza ion esul s a e based on desc ip ions o
how he ules would choose al e na i es a each p e e ence p o…le. The e
exis wo ele an pape s ha ake his poin o iew. One is by La sson
and S ensson (2006), who p o ide a cha ac e iza ion o s a egy-p oo ules:
unde ou assump ion ha he ange is bina y, s a egy-p oo ness is equi -
alen o weak g oup s a egy-p oo ness, as p o en in Ba be à, Be ga, and
Mo eno (2010). Hence, hei cha ac e iza ion in e ms o he unc ional o m
p o ides an al e na i e o he one we p esen he e. A second esul , his one
due o Manjuna h (2009a), cha ac e izes he unc ional o m o s ong g oup
s a egy-p oo ules when he e a e only wo al e na i es. We e-s a e he
esul wi h some addi ional p ecisions and in o de o co e he case whe e
3
he ange is bina y bu p e e ences a e de…ned on a la ge se o al e na i es,
and p o ide a no el p oo o i .
The pape p oceeds as ollows. In Sec ion 2, we p o ide he amewo k,
we p esen di¤e en e sions o g oup s a egy-p oo ness and discuss hei
ela ionships unde di¤e en domain assump ions. In Sec ion 3 we p o ide
he cha ac e iza ions in e ms o p ope ies. In Sec ion 4 we p o ide he
announced addi ional cha ac e iza ion o s ongly g oup s a egy-p oo ules,
he no el p oo , ha also allows us o comple e he p oo o one o he
heo ems in he p eceding sec ion. Sec ion 5 concludes.
2 The se up and de…ni ions
Le Abe a …ni e se o al e na i es A= x; y; z; w:::g:Le Nbe a …ni e se
o agen s N= 1;2; :::; ng:Le Ube he se o all p eo de s on A(comple e,
e‡exi e, and ansi i e bina y ela ions on A). Le Ri U be he se o
admissible p e e ences o agen i2Nand le R  i2NRi.
Fo any p e e ence ela ion Ri2 Ri, we deno e by Piand Ii he s ic
and indi¤e ence pa o Ri, espec i ely. A p e e ence p o…le is deno ed by
R= (R1; ::; Rn)2 R o also by R= (RC; RC)2 R when we wan o s ess
he ole o a coali ion CN. Then RC2 RC i2CRiand RC2 RNnC
deno e he p e e ences o agen s in Cand in NnC, espec i ely.
Asocial choice unc ion (o ule)on a domain Ris a unc ion :R ! A.
The ange o is deno ed by A . In his pape we concen a e on he amily
o social choice unc ions wi h bina y ange, ha is, whose ange consis s o
exac ly wo elemen s, ha we call xand y om now on.
Le Rx
ijRibe he subse o p e e ences such ha o any Rx
i2 Rx
i,
xPx
iy. Simila ly, de…ne Ry
i. Le Rxy
ijRibe he subse o p e e ences such
ha o any Rxy
i2 Rxy
i,xIxy
iy.
We s a e ou esul s unde he ollowing minimal assump ion on he
domain o admissible p e e ences: each indi idual has a leas one admissi-
ble p e e ence whe e xis p e e ed o y, one whe e yis p e e ed o x; and
one whe e he is indi¤e en be ween he wo. Tha is, o any i2Nand any
2 x; y; xyg,R
i6=?.3
3Fo se e al o ou esul s, we could e en weaken his minimal condi ion on he domain
and allow o some o he se s R
i o be emp y.
4

The bes known nonmanipulabili y axiom is s a egy-p oo ness. I e-
qui es he u h o be a dominan s a egy and i is a necessa y condi ion
o implemen a ion in dominan s a egies (Gibba d, 1973 and Sa e hwai e,
1975).
De…ni ion 1 An agen i2Ncan manipula e a social choice unc ion on
Ra R2 R i he e exis s R0
i2 Risuch ha Ri6=R0
iand (R0
i; Ri)Pi (R).
A social choice unc ion is s a egy-p oo on Ri no agen i2Ncan
manipula e on R.
Ano he o m o manipula ion is by means o coali ions. The ollowing
de…ni ions e e o cases whe e agen s may gain om join changes o de-
cla ed p e e ences. They di¤e on wo accoun s: he equi ed gains om
manipula ion and he ac ions expec ed om coali ion membe s. Rega ding
gains om manipula ion we may equi e ha each membe om de ia ing
coali ions ob ains a s ic gain o else ha only some o hem do wi h he
es no losing. Rega ding de ia ions we may ask ha all membe s o a coali-
ion mis ep esen hei p e e ences o ha jus some o hem do. The h ee
de…ni ions below will e‡ec hese modelling choices.4
De…ni ion 2 A coali ion Ccan s ongly manipula e a social choice unc ion
on Ra R2 R i he e exis s R0
C2 RCsuch ha o all agen i2C,
Ri6=R0
iand (R0
C; RC)Pi (R). A social choice unc ion is weakly g oup
s a egy-p oo on Ri no coali ion CNcan s ongly manipula e on
R.
De…ni ion 3 A coali ion Ccan manipula e a social choice unc ion on R
a R2 R i he e exis s R0
C2 RCsuch ha o all agen i2C,Ri6=R0
i
and (R0
C; RC)Ri (R), and o some j2C, (R0
C; RC)Pj (R). A social
choice unc ion is g oup s a egy-p oo on Ri no coali ion CNcan
manipula e on R.
De…ni ion 4 A coali ion Ccan weakly manipula e a social choice unc ion
on Ra R2 R i he e exis s R0
C2 RCsuch ha o some agen l2C,
4We shall omi wha could ha e been a ou h e sion o g oup s a egy-p oo ness, one
ha would equi e all agen s o gain bu would allow o some o hem no o change hei
p e e ences. Tha would u n ou o be equi alen o weak g oup s a egy-p oo ness (see
De…ni ion 2).
5
Rl6=R0
l, o all agen i2C, (R0
C; RC)Ri (R), and o some j2C,
(R0
C; RC)Pj (R). A social choice unc ion is s ongly g oup s a egy-
p oo on Ri no coali ion CNcan weakly manipula e on R.
Rema ks (1) S a egy-p oo ness and weak g oup s a egy-p oo ness a e
equi alen o social choice unc ions wi h bina y ange (see P oposi ion 1
and Theo em 1 in Ba be à, Be ga, and Mo eno, 2010).
(2) When indi¤e ences a e no allowed, all h ee de…ni ions o g oup s a egy-
p oo ness collapse in a single one.
(3) S ong g oup s a egy-p oo ness implies g oup s a egy-p oo ness and he
la e implies weak g oup s a egy-p oo ness. The con e se implica ions do
no hold in gene al, as shown by he ollowing examples.
Example 1 A ule ha is g oup s a egy-p oo bu no s ongly. Le n2
and #A2,x; y 2A. Then, o any R2 UN, de…ne he social choice
unc ion as ollows:
(R) = xi xPiy o any i2N,
yo he wise.
We show ha is no s ongly g oup s a egy-p oo . Le Rbe such ha each
agen s ic ly p e e s x o yand le R0be such ha n1agen s s ic ly p e e
xo e y, and he o he agen is indi¤e en be ween xand y. Obse e ha
(R) = xand (R0) = y: Then, coali ion Ncould weakly manipula e a R0
ia R. The eade may check ha he ule sa is…es he wo weake s a egic
condi ions.
Example 2 A ule ha is weakly g oup s a egy-p oo bu no g oup. Le
n2,#A2and agen s’p e e ences such ha o any i2N,R
i6=?
o any 2 x; y; xyg. Le kbe a dic a o on x; yg, ha is, (R) = xwhen
Rk2 Rx
k[ Rxy
kand (R) = yo he wise.
No e ha is (weakly g oup) s a egy-p oo . Howe e , coali ion C= k; jg
j6=kcould manipula e a (Rxy
k; Ry
j; R j;kg) ia (Ry
k; R0
j; R j;kg) o any
R0
j2 Rx
i[ Rxy
iand any R j;kg2 RNn j;kg. Thus, is no g oup s a egy-
p oo ( hus no s ongly).
Be o e cha ac e izing he ules ha sa is y ou di¤e en equi emen s, le
us ema k ha g oup s a egy-p oo ness and s ong g oup s a egy-p oo ness
become equi alen unde he mild complemen a y domain condi ion e-
qui ed in he ollowing p oposi ion.
6
P oposi ion 1 Le #A3and Rbe such ha each indi idual has a leas
wo admissible p e e ences in Riwhe e xis p e e ed o yand wo whe e y
is p e e ed o x: Then, any g oup s a egy-p oo social choice unc ion on
Rwi h a bina y ange is also s ongly g oup s a egy-p oo .
P oo . Le be a g oup s a egy-p oo social choice unc ion. Suppose ha
is no s ongly g oup s a egy-p oo . Tha is, he e exis R2 R, a coali ion
CN, and R0
C2 RCsuch ha o some agen l2C,Rl6=R0
l, o all agen s
i2C; (R0
C; RC)Ri (R), and o some j2C, (R0
C; RC)Pj (R). I o
any agen l2C,Rl6=R0
l, hen we ge a con adic ion o g oup s a egy-
p oo ness.
Thus, he e exis l2Csuch ha Rl=R0
l:De…ne CP= j2C:Rj=R0
jand
(R0
C; RC)Pj (R)gand CI= k2C:Rk=R0
kand (R0
C; RC)Ik (R)g.
By he complemen a y domain condi ion, o any j2CP, he e exis s R00
j2
RjnRjsuch ha (R0
C; RC)P00
j (R). I (R00
CP; R0
CnCP; RC) = (R) he e
exis a coali ion CP, a p o…le (R00
CP; R0
CnCP; RC)2 R, and R0
CP=RCPsuch
ha o any agen j2CPR00
j6=Rjand (R0
C; RC)Pj (R00
CP; R0
CnCP; RC) =
(R)which is a con adic ion o g oup s a egy-p oo ness.
Thus, (R00
CP; R0
CnCP; RC) = (R0
C; RC):
I CI=? hen obse e ha he e exis R2 R, a coali ion CN, and
R00
C(R00
CP; R0
CnCP)2 RCsuch ha o any agen i2C,Ri6=R00
iand
(R00
CP; R0
CnCP; RC)Ri (R), and o some j2C, (R00
CP; R0
CnCP; RC)Pj (R).
Then we ge a con adic ion o g oup s a egy-p oo ness.
Thus, CI6=?. By he complemen a y domain condi ion, o any k2
CI, he e exis s R00
k2 RknRksuch ha (R00
CP; R0
CnCP; RC)P00
k (R). I
(R00
CP[CI; R0
Cn(CP[CI); RC) = (R)coali ion CIcould manipula e ia RCI
a (R00
CP[CI; R0
Cn(CP[CI); RC), which con adic s g oup s a egy-p oo ness.
Thus, (R00
CP[CI; R0
Cn(CP[CI); RC) = (R0
C; RC). Then obse e ha he e
exis R2 R, a coali ion CN, and R000
C(R00
CP[CI; R0
Cn(CP[CI))2 RCsuch
ha o any agen i2C,Ri6=R000
iand (R00
CP[CI; R0
Cn(CP[CI); RC)Ri (R),
and o some j2C, (R00
CP[CI; R0
Cn(CP[CI); RC)Pj (R), and hen we ge a
con adic ion o g oup s a egy-p oo ness.
Rema k 1 We ha e assumed in P oposi ion 1 ha #A3:This is because
he complemen a y domain condi ion ha we assume in ou s a emen can
only be sa is…ed in his case. When #A= 2, his condi ion canno be sa is…ed
7
and in ac he equi alence does no hold ( he ule in Example 1 when #A= 2
p o ides a coun e example).
3 Cha ac e iza ion esul s: p ope ies
In his sec ion we p o ide ou … s se o cha ac e iza ion esul s. We p o e
ha ou di¤e en e sions o he condi ion ha a ule should be xy-based
and mono onic a e necessa y and su¢ cien o gua an ee ha hey sa is y ou
di¤e en e sions o g oup s a egy-p oo ness.5
Fo each p e e ence p o…le R2 R;de…ne he se X(R) = i2N:xPiyg;
Y(R) = j2N:yPjxg, and I(R) = k2N:yIkxg.
We now de…ne he condi ions ha will cha ac e ize weak and s ong g oup
s a egy-p oo ness.
De…ni ion 5 A bina y social choice unc ion is essen ially xy-mono onic6
i and only i o any R; R02 R such ha Rh=R0
h o all h2I(R) I(R0);
he ollowing holds:
[X(R0)X(R); Y (R)Y(R0)(a leas one s ic inclusion), and (R) = x]
) (R0) = x; and
[Y(R0)Y(R); X(R)X(R0)(a leas one s ic inclusion), and (R) = y]
) (R0) = y:
De…ni ion 6 A bina y social choice unc ion is xy-s ongly mono onic i
and only i o any R; R02 R he ollowing holds:
[i ei he X(R0)X(R); Y (R)Y(R0)(a leas one s ic inclusion), o
X(R0)X(R),?6=Y(R)$Y(R0)] and (R) = x) (R0) = x;
[i ei he Y(R0)Y(R); X(R)X(R0)(a leas one s ic inclusion), o
Y(R0)Y(R),?6=X(R)$X(R0)] and (R) = y) (R0) = y.
5Examples showing he ela ionship be ween he p ope ies de…ned in his sec ion a e
a ailable upon eques .
6Lemma 7 in Manjuna h (2009b) shows ha when he se o admissible p e e ences is
he se o all single-dipped p e e ences and a speci…c bina y ange es ic ion, some e sion
o essen ially xy-mono onici y is a consequence o s a egy-p oo ness.
8
be ween xand y. Bu hen he second agen ob ains his bes ou come.
This ends he p oo o S ep 1.
S ep 2 Any s ongly g oup s a egy-p oo social choice unc ion wi h
bina y ange is xy-based and xy-s ong mono onic.
P oo o S ep 2:
By Theo em 1, we know ha is essen ially xy-based and essen ially xy-
mono onic.
We now p o e by con adic ion ha is xy-based. Suppose no , hen he e
exis R; R02 R such ha X(R)[Y(R)6=?,X(R) = X(R0); Y (R) = Y(R0),
(R)6= (R0). Suppose … s ha X(R) = ?and hus Y(R)6=?(a simila
a gumen applies i Y(R) = ?). By Lemma 1, (R) = (R0) = ywhich is a
con adic ion. Thus, X(R)6=?and Y(R)6=?.
By essen ially xy-based, (R0
X(R)[Y(R); RI(R)) = (R).
I n= 2,R0= (R0
X(R)[Y(R); RI(R))and we ge he desi ed con adic ion since
(R0)mus be di¤e en om (R).
I n3, since (R)6= (R0) he e mus exis an agen i2Nsuch ha xIiy
ha is xy-pi o al o (R0
X(R)[Y(R); RI(R)). By Lemma 2, is no s ongly
g oup s a egy-p oo which is a con adic ion.
We now p o e by con adic ion ha is xy-s ong mono onic. Suppose
no , ha is he e exis R; R02 R such ha ei he (1) X(R0)X(R),
Y(R)Y(R0)(a leas one inclusion s ic ), (R) = xbu (R0) = y; o
else (2) X(R0)X(R),?6=Y(R)$Y(R0); (R) = xand (R0) = y. A
simila a gumen holds o he o he possibili y whe e he oles o xand y
a e exchanged. Fi s obse e ha by Lemma 1, X(R)6=?and Y(R)6=?
(o he wise, i Y(R) = ?, hen Y(R0) = ?and X(R0)%X(R). By Lemma 1,
(R0) = xwhich is he desi ed con adic ion. I X(R) = ?and Y(R)6=?,
hen by Lemma 1 (R) = ywhich is he desi ed con adic ion).
I case (1) holds, by essen ial xy-mono onici y and essen ial xy-basedness,
(R0
X(R)[Y(R); RI(R)) = x(de…ne R00 = (R0
X(R)[Y(R); RI(R)), i ei he X(R00)%
X(R)and Y(R00)$Y(R)o X(R00) = X(R)and Y(R00)$Y(R)we apply
essen ial xy-mono onici y. I X(R00) = X(R)and Y(R00) = Y(R)we apply
essen ial xy-basedness).
I n= 2,R0= (R0
X(R)[Y(R); RI(R))and we ge he desi ed con adic ion since
(R0)mus be di¤e en om (R).
I n3, since (R)6= (R0) he e mus exis an agen i2Nsuch ha xIiy
ha is xy-pi o al o (R0
X(R)[Y(R); RI(R)). By Lemma 2, is no s ongly
15

g oup s a egy-p oo which is a con adic ion.
I case (2) holds, by essen ial xy-mono onici y and essen ial xy-basedness,
(R0
X(R0); RNnX(R0)) = x(i X(R0)%X(R), ha is, X(R0)includes some
agen s in I(R), we apply essen ial xy-mono onici y. I X(R0) = X(R)we
apply essen ial xy-basedness). Then, (R0
X(R0); R0
Y(R); RNn X(R0)[Y(R)g) = x
by essen ial xy-basedness.
I n= 2,R0= (R0
X(R0); R0
Y(R); RNn X(R0)[Y(R)g)and we ge he desi ed con-
adic ion since (R0)mus be di¤e en om (R).
I n3, since (R)6= (R0) he e mus exis an agen i2N ha is xy-
pi o al agen o (R0
X(R0); R0
Y(R); RNn X(R0)[Y(R)g)such ha xIiy. By Lemma
2, is no s ongly g oup s a egy-p oo which is a con adic ion.
This ends he p oo o S ep 2.
S ep 3 Any xy-based and xy-s ong mono onic social choice unc ion
wi h bina y ange can be desc ibed as a e o ule when n3:When n= 2,
is ei he a e o ule o a se ial dic a o .
To show S ep 3, we use he ollowing claims.
Obse e … s ha since is xy-based hen o any R
i,R
i2 R
i, (R
i; Ri) =
(R
i; Ri) o any Ri2 RNn igwhe e 2 x; y; xyg.
In wha ollows, when we use R
iwe e e o any R
i2 R
iwi hou loss o
gene ali y. This is because all he s a emen s we make in his p oo om
now on hold wha e e he ep esen a i e o he se R
iis.
Claim 1 Le n2. I is xy-based and xy-s ong mono onic hen is
xy-Pa e ian.
P oo o Claim 1 Le Rx2 i2NRx
i, ha is, X(Rx) = N. Suppose o
ge a con adic ion ha (Rx) = y. No e ha by xy-based and xy-s ong
mono onici y, o any o he p o…le R2 R, (R) = ywhich con adic s ha
has a bina y ange. Thus, (Rx) = x.
Suppose ha he e is Rsuch ha xRiy o any i2Nand xPjy o some
j2N; X(R)6=Nand (R) = y. Then X(R)6=?and Y(R) = ?. No e
ha X(R)$X(Rx)and Y(R) = Y(Rx), o any Rx2 i2NRx
i. By xy-
s ong mono onici y, (Rx) = ywhich con adic s wha we ha e jus p o ed.
This ends he p oo o Claim 1.
No e ha he coun e pa esul s o Claims 2 and 3 below exchanging he
oles o xand ydo also hold.
Claim 2 Le n2. I o some i2Nand some Ry
i2 Ry
i; (Ry
i; Rx
i) = y,
16
hen (Ry
i; R0
i) = y o any R0
i2 RNn ig:
P oo o Claim 2 Le R0
i2 RNn ig. Obse e ha (Ry
i; R0
i) = yei he
by xy-based i X(Ry
i; R0
i) = Nn ig=X(Ry
i; Rx
i), o else by xy-s ong
mono onici y i X(Ry
i; R0
i)$Nn ig=X(Ry
i; Rx
i). This ends he p oo o
Claim 2.
Claim 3 Le n3. I o some i2Nand some Ry
i2 Ry
i; (Ry
i; Rx
i) = y,
hen o any j2Nwe ha e ha (Ry
j; Rx
j) = y.
P oo o Claim 3 By con adic ion, suppose ha (Ry
i; Rx
i) = yand
(Ry
j; Rx
j) = x. I (Rxy
i; Ry
j; Rx
 i;jg) = y hen (Ry
j; Rx
j) = yby xy-s ong
mono onici y since ?6=X(Rxy
i; Ry
j; Rx
 i;jg)$X(Ry
j; Rx
j)and Y(Rxy
i; Ry
j; Rx
 i;jg) =
Y(Ry
j; Rx
j). Thus, (Rxy
i; Ry
j; Rx
 i;jg) = x. By xy-s ong mono onici y,
(Ry
i; Ry
j; Rx
 i;jg) = x, since X(Rxy
i; Ry
j; Rx
 i;jg) = X(Ry
i; Ry
j; Rx
 i;jg)and
?6=Y(Rxy
i; Ry
j; Rx
 i;jg)$Y(Ry
i; Ry
j; Rx
 i;jg). By Claim 2, since (Ry
i; Rx
i) =
y hen (Ry
i; Ry
j; Rx
 i;jg) = ywhich con adic s wha we ob ained abo e.
This ends he p oo o Claim 3.
Claim 4 Le n3. I o some i2Nand some Ry
i2 Ry
i, (Ry
i; Rx
i) = x
hen (Ry
C; Rx
C) = x o any C,? $ C$N.
P oo o Claim 4 Suppose, o ge a con adic ion, ha o some C,? $
C$N; (Ry
C; Rx
C) = y. Clea ly, C6= ig. No e also ha Ccan no be
a single on (o he wise, i C= jg,j6=i, we would ge a con adic ion by
Claim 3). Thus, #C > 1. No e also ha (Ry
k; Rx
k) = x o any k2N
(o he wise, (Ry
k; Rx
k) = y, by Claim 4, (Ry
i; Rx
i) = ywhich is no he
case). The e o e, wi hou loss o gene ali y, we can suppose ha i2C. We
dis inguish wo subcases:
Subcase 1 Le (Ry
i; Rxy
Cn ig; Rx
C) = x. No e ha X(Ry
i; Rxy
Cn ig; Rx
C) =
X(Ry
C; Rx
C)and ?6=Y(Ry
i; Rxy
Cn ig; Rx
C)$Y(Ry
C; Rx
C). The e o e, by xy-
s ong mono onici y (Ry
C; Rx
C) = x, which is a con adic ion.
Subcase 2 Le (Ry
i; Rxy
Cn ig; Rx
C) = y. No e ha Y(Ry
i; Rxy
Cn ig; Rx
C) =
Y(Ry
i; Rx
i)and ?6=X(Ry
i; Rxy
Cn ig; Rx
C)$X(Ry
i; Rx
i). The e o e, by xy-
s ong mono onici y, (Ry
i; Rx
i) = y, which is a con adic ion. This ends he
p oo o Claim 4.
P oo o S ep 3:
Fi s , by Claim 1, (R) = x o any Rsuch ha xRiy o any i2Nand
xPjy o some j2Nand (R) = y o any Rsuch ha yRix o any i2N
and yPjx o some j2N. Second, (R)can be any ou come o any Rwhe e
17
all agen s a e indi¤e en . Thi d, he a gumen di¤e s depending on nbeing
wo o highe .
I n= 2, suppose … s ha is such ha o some p o…le (Ry
1; Rx
2), whe e
Ry
12 Ry
1and Rx
22 Rx
2, (Ry
1; Rx
2) = yand o some p o…le (Ry
2; Rx
1), whe e
Ry
22 Ry
2and Rx
12 Rx
1, (Ry
2; Rx
1) = y. By Claim 2, o any Ry
12 Ry
1and
Rx
22 Rx
2, (Ry
1; R2) = yand (Ry
2; R1) = y o any R22 R2and R12 R.
Thus, can be ew i en as a e o ule o x.
Second, suppose ha o some p o…le (Ry
2; Rx
1), whe e Ry
22 Ry
2and Rx
12 Rx
1,
(Ry
2; Rx
1) = yand o any p o…le (Ry
1; Rx
2), whe e Ry
12 Ry
1and Rx
22 Rx
2,
(Ry
1; Rx
2) = x. By Claim 2, o any Ry
22 Ry
2; (Ry
2; R1) = yand o any
R12 R1. No e ha his ule can be ew i en as a se ial dic a o wi h
o de 21.
Thi d, suppose ha o some p o…le (Ry
1; Rx
2), whe e Ry
12 Ry
1and Rx
22 Rx
2,
(Ry
1; Rx
2) = yand o any p o…le (Ry
2; Rx
1), whe e Ry
22 Ry
2and Rx
12 Rx
1,
(Ry
2; Rx
1) = x. By Claim 2, o any Ry
12 Ry
1; (Ry
1; R2) = yand o any
R22 R2. No e ha his ule can be ew i en as a se ial dic a o wi h
o de 12.
Finally, suppose ha o any p o…le (Ry
2; Rx
1), whe e Ry
22 Ry
2and Rx
12 Rx
1,
(Ry
2; Rx
1) = xand o any p o…le (Ry
1; Rx
2), whe e Ry
12 Ry
1and Rx
22 Rx
2,
(Ry
1; Rx
2) = x. By he coun e pa o Claim 2, o any Ry
22 Ry
2; (Ry
2; R1) =
x o any R12 R1;and o any Ry
12 Ry
1; (Ry
1; R2) = x o any R22 R2.
Thus, can be ew i en as a e o ule o y.
I n3, suppose … s ha is such ha o some p o…le (Ry
i; Rx
i), whe e
Ry
i2 Ry
iand Rx
j2 Rx
j o any j2Nn ig, (Ry
i; Rx
i) = y. Then, by
Claims 2 and 3, (Ry
k; Rk) = y o any k; any Rk2 Ry
k;and any Rj2 Rj;
j2Nn kg. Tha is, he ou come will be y o any p o…le whe e he e is one
agen ha s ic ly suppo s yo e x. Thus, is a e o ule o x.
Le now suppose ha is such ha o all p o…les (Ry
i; Rx
i), whe e Ry
i2 Ry
i
and Rx
j2 Rx
j o any j2Nn ig, (Ry
i; Rx
i) = x. Then, by Claim 4 and he
coun e pa s o Claims 2 and 3, he ou come will be x o any p o…le whe e
he e is one agen ha s ic ly suppo s xo e y. Thus, is a e o ule o
y.
This ends p oo o S ep 3, and hence he p oo o Theo ems 2, 3, and 4.
18
5 Final Rema ks
In his pape we ha e p o ided di¤e en de…ni ions o s a egy-p oo ness in
on o possible manipula ions by g oups, and se e al cha ac e iza ions o
ules sa is ying hese p ope ies when hei ange is es ic ed o co e wo
al e na i es.
We eel ha , when a ainable, non-manipulabili y by g oups (in i s di¤e -
en o ms) is an a ac i e p ope y, since in many con ex s di¤e en agen s
can be expec ed o explo e he possibili y o bene… ing om join ac ions, in
addi ion o indi idual ones. Ea ly au ho s on he issue o s a egy-p oo ness
did indeed e e o he in e es o a oiding such join s a egic beha io (Pa -
anaik, 1978, Dasgup a, Hammond, and Maskin, 1979, Peleg, 1984 and 2002).
T ue, in many domains, and o unc ions wi h non-bina y anges, i may be
excessi e o ask o hese p ope ies. Bu no always! Fo in e es ing cases
when hey may be ul…lled because o domain es ic ions, see Moulin (1999),
Pápai (2000), Ba be à and Jackson (1995). In ac , ou pape con empla es
ano he case whe e join manipula ions can be a oided, his ime because
he anges o ou unc ions a e es ic ed.
We ha e allowed o agen s o ha e p e e ences o e o he al e na i es
ha a e no in he ange, and been ca e ul in ollowing up he implica ions
o ha ex ension in he domains o he ules. This is in con as wi h he
wo k o au ho s who assume ha only wo al e na i es a e a ailable when
he ange consis s o wo o hem. We insis in he di¤e ence, because we
wan o emphasize ha he choice o es ic he ange is indeed a possible
ool o he mechanism designe , e en when mo e han wo choices a e in
p inciple socially a ailable.
We ha e also looked o cha ac e iza ions ha a e essen ially independen
o he cha ac e is ics o he domains o de…ni ion o he ules. This is because
he se s o ules sa is ying ou di¤e en e sions o non-manipulabili y by
g oups could in p inciple be a ying as he domains o de…ni ion change
om one applica ion o ano he . By selec ing p ope ies ha a e necessa y
and su¢ cien o ou condi ions o be sa is…ed, we go o he essen ials o he
ques ion. And, when needed, ou quali…ca ions on he minimal equi emen s
on domains o ou esul s o hold a e made explici a each poin .
We ha e also insis ed in examining he ole o indi iduals who a e in-
di¤e en be ween he al e na i es in he ange (bu no iden ical in o he
espec s). The p esence o indi¤e ences is always a sou ce o p oblems in
social choice, and i also complica es and en iches ou analysis he e.
19
We lea e i o he in e es ed eade o examine how ou analysis would
be simpli…ed (and some imes educed o p e iously exis ing esul s) when
only wo al e na i es a e p esen a all, and/o when indi¤e ences among
al e na i es a e uled ou .
Le us also men ion ha we ha e concen a ed on he no ions o weak and
s ong g oup s a egy-p oo ness, The in e media e no ion o g oup s a egy-
p oo ness has been p o en o be equi alen o he s ong e sion unde mild
domain assump ions, bu no o he pa icula case o wo al e na i es only.
Cha ac e iza ions o ules sa is ying he in e media e p ope y in his pa ic-
ula case a e le as an open p oblem.
Re e ences
[1] S. Ba be à, D. Be ga, and B. Mo eno, Indi idual e sus g oup s a egy-
p oo ness: when do hey coincide?, J. Econ. Theo y (2010), o hcoming.
[2] S. Ba be à and M. Jackson, S a egy-p oo Exchange, Econome ica 63
(1995), 51-87.
[3] P. Dasgup a, P. Hammond, and E. Maskin, The Implemen a ion o So-
cial Choice Rules: Some Gene al Resul s on Incen i e Compa ibili y, Re .
Econ. S ud. 46 (1979), 185-216.
[4] A. Gibba d, Manipula ion o Vo ing Schemes: A Gene al Resul , Econo-
me ica 41 (1973), 587-601.
[5] V. Manjuna h, G oup S a egy-p oo ness And Social Choice Be ween
Two Al e na i es, Mimeo (2009a).
[6] V. Manjuna h, E¢ cien and S a egy-p oo Social Choice When P e e -
ences A e Single-dipped, Mimeo (2009b).
[7] B. La sson and L.-G. S ensson, S a egy-p oo o ing on he ull p e -
e ence domain, Ma h. Soc. Sci. 52 (2006), 272-287.
[8] H. Moulin, Inc emen al cos -sha ing: Cha ac e iza ion by coali ion s a egy-
p oo ness, Soc. Choice Wel a e 16 (1999), 279-320.
[9] S. Pápai, S a egyp oo Assignmen by Hie a chical Exchange, Econo-
me ica 68 (2000), 1403-1433.
[10] P. K. Pa anaik, S a egy and G oup Choice, No h-Holland Publishing
Company (1978).
[11] B. Peleg, Game Theo e ic Analysis o Vo ing in Commi ees, Econo-
20

me ic Socie y monog aphs in pu e heo y-7, Camb idge Uni e si y P ess
(1984).
[12] B. Peleg, Game heo e ic analysis o o ing in commi ees, Handbook
o Social Choice and Wel a e, olume 1, edi ed by K.J. A ow, A.K. Sen and
K. Suzumu a, No h-Holand (2002).
[13] M. Sa e hwai e, S a egy-P oo ness and A ow’s Condi ions: Exis-
ence and Co espondence Theo ems o Vo ing P ocedu es and Social Wel-
a e Func ions, J. Econ. Theo y 10 (1975), 187-217.
21