De Simone, Anna; Bhaska a Rao, K. P. S.
A icle
Two- alued s ongly g oup s a egy-p oo social choice
unc ions
Games
P o ided in Coope a ion wi h:
MDPI – Mul idisciplina y Digi al Publishing Ins i u e, Basel
Sugges ed Ci a ion: De Simone, Anna; Bhaska a Rao, K. P. S. (2024) : Two- alued s ongly g oup
s a egy-p oo social choice unc ions, Games, ISSN 2073-4336, MDPI, Basel, Vol. 15, Iss. 6, pp. 1-9,
h ps://doi.o g/10.3390/g15060044
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/330113
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h ps://c ea i ecommons.o g/licenses/by/4.0/
Ci a ion: De Simone, A.; Bhaska a
Rao, K.P.S. Two-Valued S ongly
G oup S a egy-P oo Social Choice
Func ions. Games 2024,15, 44.
h ps://doi.o g/10.3390/g15060044
Academic Edi o : Ul ich Be ge
Recei ed: 8 Oc obe 2024
Re ised: 26 No embe 2024
Accep ed: 6 Decembe 2024
Published: 10 Decembe 2024
Copy igh : © 2024 by he au ho s.
Licensee MDPI, Basel, Swi ze land.
This a icle is an open access a icle
dis ibu ed unde he e ms and
condi ions o he C ea i e Commons
A ibu ion (CC BY) license (h ps://
c ea i ecommons.o g/licenses/by/
4.0/).
A icle
Two-Valued S ongly G oup S a egy-P oo Social
Choice Func ions
Anna De Simone 1,* and K. P. S. Bhaska a Rao 2
1Dipa imen o di Ma ema ica e Applicazioni R. Caccioppoli, Uni e si à Fede ico II di Napoli,
80126 Napoli, I aly
2Depa men o Compu e In o ma ion Sys ems, Indiana Uni e si y No hwes , Ga y, IN 46408, USA;
[email p o ec ed]
*Co espondence: [email p o ec ed]
Abs ac : We p esen simple and di ec a gumen s o cha ac e ize s ongly g oup s a egy-p oo social
choice unc ions whose ange is o ca dinali y wo. The unde lying socie y is o a bi a y ca dinali y,
and agen s can be indi e en among al e na i es.
Keywo ds: social choice unc ions; weak p e e ences; weak manipulabili y; e o ule; se ial dic a o
MSC: 91B14
JEL Classi ica ion: D71
1. In oduc ion
In his no e, we cha ac e ize he s ong g oup s a egy-p oo ness o social choice
unc ions in he ollowing amewo k: The social choice occu s be ween wo al e na i es,
bu i is based on a p o ile o weak p e e ences ha he agen s exp ess o e a la ge se
o al e na i es. In o he wo ds, despi e he ac ha we ocus on social choice unc ions
wi h ange consis ing o wo elemen s, hey belong o an a bi a y se o al e na i es, in
gene al consis ing o mo e han wo elemen s. Such a se ing ecei ed a limi ed a en ion
wi h espec o he one in which he e a e only wo al e na i es on he scene. Rela ed o
he la e amewo k, among o he s, we men ion [
1
–
5
]. The highe le el o gene ali y we
adop in his pape de e mines some di icul ies ha one needs o ackle, mainly because
he dependence o i ele an (i.e., hose no in he ange) al e na i es eme ges. Conce ning
his, see [
6
] (Example 2.4). Howe e , he di icul ies a e compensa ed by he signi icance
o he se ing. This signi icance has been cla i ied in pape s like [
6
–
10
], whe e he same
as ou amewo k is adop ed. In pa icula , di e en ly om he au ho s who assume ha
only wo al e na i es a e a ailable when he ange is o ca dinali y wo, e . [
7
] emphasizes
ha he choice o es ic he ange is a possible ool o he mechanism designe , e en
when mo e han wo choices a e socially a ailable in p inciple. In [8], i is p o ed ha he
use o single-dipped p e e ences leads exac ly o social choice unc ions wi h he ange o
ca dinali y wo wi hin a la ge se o al e na i es. In [
6
,
9
], he implemen a ion o a social
choice unc ion ha asks o p e e ences on a la ge se o al e na i es a he han only
on he wo in he ange is p esen ed as a ool o balancing be ween simplici y (only one
be ween wo al e na i es may o m he collec i e ou come) and, exac ly since he i ele an
al e na i es coun , ca e ul a en ion o agen s’ opinion (by equi ing hei p e e ences o e
all al e na i es in o de o de ine a p o ile o p e e ences).
The cha ac e iza ion we p esen (Theo em 3) s a es ha s ong g oup s a egy-p oo ness
is equi alen o Pa e ian p ope y join wi h a u he p ope y. This is he almos indepen-
dence o i ele an al e na i es (De ini ion 5, a p ope y p esen ed in [
7
] unde he name
ab
-based i
{a
,
b}
is he ange o he social choice unc ion), in case o a socie y consis ing o
Games 2024,15, 44. h ps://doi.o g/10.3390/g15060044 h ps://www.mdpi.com/jou nal/games
Games 2024,15, 44 2 o 9
wo agen s only. Whe eas in case he agen s a e h ee o mo e, he p ope y ha one has o
add o Pa e o is he independence om con lic , a p ope y we in oduce in De ini ion 5.
The cha ac e iza ion o wo- alued s ongly g oup s a egy-p oo social choice unc-
ions is also one o he asks o [
7
]. We poin ou he e ha we ob ain a cha ac e iza ion
di e en om [
7
] (Theo em 2). Mo eo e , whe eas he la e leads us o iden i y he
unc ional o m o s ongly g oup s a egy-p oo social choice unc ions ([
7
], Theo em 3
1
)
h ough he in es iga ion o se e al cases and subcases, ou cha ac e iza ion Theo em 3
gi es [
7
] (Theo em 3) as an immedia e co olla y. Finally, we also ema k ha he a gumen s
we p o ide do no equi e he ini eness o he unde lying se o agen s.
In Sec ion 2, we desc ibe he model and we in oduce he no a ions. Sec ion 3con ains
he cha ac e iza ion o s ongly g oup s a egy-p oo social choice unc ions. In Sec ion 4,
we p esen a desc ip ion o he conside ed unc ions. Sec ion 5concludes.
2. The Model
We deno e a socie y by
V
, whose membe s a e called agen s, and we deno e a se o
al e na i es by A. Bo h se s can be o any ca dinali y ( ini e o in ini e).
Agen s “o de ” al e na i es by means o weak p e e ences, i.e., comple e and ansi i e
bina y ela ions on A.
We deno e he se o all weak p e e ences on he se
A
o al e na i es by
W
. Fo
simplici y, we only say p e e ence o indica e a weak p e e ence. I
p
is a p e e ence on
A
, we w i e
x⪰py
o elemen s
x
and
y
o
A
o mean ha he pai
(x
,
y)
belongs o he
bina y ela ion
p
. This ansla es o he s a emen ha acco ding o he p e e ence
p
, he
al e na i e xis a leas as good as he al e na i e y.
We w i e
x≻py
o mean ha he pai
(x
,
y)
belongs o he bina y ela ion
p
, and he
pai
(y
,
x)
does no . In his case, acco ding o he p e e ence
p
, he al e na i e
x
is be e
han he al e na i e y.
Finally, we w i e
x∼y
o mean ha bo h pai s
(x
,
y)
and
(y
,
x)
belong o
p
. This
means ha acco ding o he p e e ence
p
, he wo al e na i es a e indi e en o each o he .
A p o ile o p e e ences is a speci ica ion o a p e e ence o each agen . Thus, a p o ile
is a unc ion P:V→ W. We w i e P= (P ) ∈V, o , mo e b ie ly, P= (P ) o a p o ile.
De ini ion 1. Asocial choice unc ion (sc o b e i y) is a map
ϕ:P→A
, whe e
P⊆ WV
.
Nonemp y subse s o
V
a e called coali ions. Gi en a p o ile
P
and a coali ion
D
, we
w i e
PD
o indica e
(P ) ∈D
, and we use he no a ion
P= (PD
,
P−D)
, whe e
−D
deno es
he se heo e ical complemen
V D
o
D
. I he coali ion consis s o only one agen , say
D={u}, we w i e P= (Pu,P−u) o simplici y.
De ini ion 2. A coali ion
D
can weakly manipula e a sc
ϕ:P→A
a he p o ile
P∈P
i he e exis s a p o ile
Q= (QD
,
P−D)∈P
such ha o e e y agen
in
D
,
ϕ(Q)⪰P ϕ(P)
,
and o a leas one agen
0
in
D
,
ϕ(Q)≻P 0ϕ(P)
. In his case, we also say ha
D
can weakly
manipula e ϕa P, decla ing Q.
I we wan o ule ou he possibili y ha agen s coo dina e and o m a g oup (a
coali ion) ha can weakly manipula e he ou come o he social choice in he sense desc ibed
in he p e ious de ini ion, hen we de ine he no ion o s ong g oup s a egy-p oo ness,
which is o malized below.
De ini ion 3. A sc
ϕ
is said o be s ongly g oup s a egy-p oo (sGSP o simplici y) i i
canno be weakly manipula ed a any p o ile by any coali ion.
I a sc is sGSP, he g and coali ion
V
, in pa icula , canno weakly manipula e i a any
p o ile. This implies a kind o weak Pa e o e iciency o he sc . We nex gi e he de ini ion.
Games 2024,15, 44 3 o 9
De ini ion 4. A sc
ϕ:P→A
wi h ange
R
is said o be Pa e ian wi h espec o
R
(weakly
Pa e o e icien wi h espec o
R
) i , o each p o ile
P
, he e is no al e na i e
x
in he ange
R
such
ha o e e y agen in V, x ⪰P ϕ(P), and o a leas one agen 0in V, x ≻P 0ϕ(P).
In he case o on o sc s, his is he s anda d de ini ion o weak Pa e o e iciency.
P oposi ion 1. Any sGSP sc is Pa e ian wi h espec o i s ange.
P oo .
I no , o a sGSP unc ion
ϕ
, conside a p o ile
P
and an al e na i e
x
ha iola e
De ini ion 4. The ela ion
x∈ϕ(P)
ensu es ha o a ce ain p o ile
Q∈P
, i is
ϕ(Q) =
x
. Hence, coali ion
V
can weakly manipula e
ϕ
a p o ile
P
, decla ing
Q
, which is a
con adic ion.
We speci y below he assump ions on he sc s we deal wi h.
-
( ange): he ange o he sc s consis s o wo elemen s o
A
. Fo he es o he
conside a ions in his pape , we ix ha he ange is {a,b} ⊆ A;
-
(domain): he domain
P
o he sc s is o he o m
P=× ∈VW
, whe e o each agen
,
W
is a subse o
W
ha con ains a leas one p e e ence whe e
a
is p e e ed o
b
, one p e e ence whe e
b
is p e e ed o
a
, and one p e e ence whe e
a
and
b
a e
indi e en o each o he 2.
Fo a p o ile P= (P ), we w i e
D(a,P):={ ∈V:a≻P b},
D(b,P):={ ∈V:b≻P a},
I(P):={ ∈V:a∼P b}.
F om now on, we simply w i e Pa e o p ope y and Pa e ian sc wi hou e e ing o
he ange, since i is assumed o coincide wi h he se
{a
,
b}
. Fo wo- alued social choice
unc ions, he p ope y o Pa e o can be clea ly cha ac e ized as ollows:
P oposi ion 2. I
ϕ:P→ {a
,
b}
, hen
ϕ
is Pa e ian i and only i he ollowing wo condi ions
hold ue:
D(a,P)=∅=D(b,P)⇒ϕ(P) = a, (1)
D(b,P)=∅=D(a,P)⇒ϕ(P) = b. (2)
We use he no a ions
P0:={P∈P:D(a,P) = ∅=D(b,P)},
P′:={P∈P:D(a,P)=∅=D(b,P)}.
Fo a p o ile
P
in
P0
,
I(P) = V
. Any such p o ile is called a p o ile o unanimous
indi e ence. O cou se, unless A={a,b},P0con ains mo e han one elemen .
A p o ile in
P′
exp esses a con lic si ua ion in he ob ious sense ha in he socie y
V
a leas one agen conside s he al e na i e
a
be e han he al e na i e
b
and a leas one
agen conside s
b
be e han
a
. Fo his eason, we e e o such p o iles as con lic p o iles.
3. Cha ac e iza ion o S ongly G oup S a egy-P oo Social Choice Func ions
F om P oposi ions 1and 2, i ollows ha
P oposi ion 3 ([
7
], Lemma 1).I
ϕ:P→ {a
,
b}
is sGSP, hen i e i ies P ope ies (1) and (2)
o P oposi ion 2.
P oposi ion 3 e eals ha he alues o a sGSP social choice unc ion a wo p o iles,
which a e nei he o unanimous indi e ence no con lic p o iles, coincide i hey ha e he
same es ic ion o he se
{a
,
b}
. We now p o e ha he same is also ue o con lic p o iles.
Games 2024,15, 44 4 o 9
We could say ha on he se
P P0
, a so o independence o i ele an al e na i es
(iia) holds.
Le us in oduce a de ini ion ha ex ends ha o sc s, which is iia
De ini ion 5. A sc ϕis said o be almos -iia i
P,Q∈P P0
D(a,P) = D(a,Q)
D(b,P) = D(b,Q)
⇒ϕ(P) = ϕ(Q). (3)
No e ha i he equi emen
P
,
Q/∈P0
is omi ed, (3) is exac ly he independence o
i ele an al e na i es.
P oposi ion 4. Any sGSP sc is almos -iia.
P oo .
I one o he wo se s
D(a
,
P)
o
D(b
,
P)
is emp y, he hesis ollows om
P oposi ion 3. We can hen assume bo h p o iles Pand Q o be con lic p o iles.
Assume by con adic ion ha
ϕ(P)=ϕ(Q)
. Fo example, wi hou any loss o gene al-
i y, assume ϕ(P) = aand ϕ(Q) = b. We de ine wo p o iles, Rand T, as ollows:
R =
P i ∈D(a,P)∪D(b,P)
Q i /∈D(a,P)∪D(b,P)
T =
P i ∈D(a,P)
Q i /∈D(a,P)
O cou se, bo h p o ile Rand Tbelong o P.
F om
ϕ(P) = a
, i ollows ha
ϕ(R) = a
: i no , coali ion
D(b
,
P)∪I(P)
can weakly
manipula e
ϕ
a p o ile
P
, decla ing
R
. Analogously, om
ϕ(Q) = b
, i ollows ha
ϕ(T) = b
: i no , coali ion
D(a
,
Q)
can weakly manipula e
ϕ
a p o ile
Q
, decla ing
T
. A
his poin , coali ion
D(b
,
P)
can weakly manipula e
ϕ
a p o ile
R
, decla ing
T
. This is a
con adic ion ha p o es he hesis.
Acco ding o he e minology o [
7
], P oposi ion 4s a es ha any sGSP social choice
unc ion wi h ange {a,b}is ab-based.
We s a e a consequence o P oposi ion 4 ha will be use ul in he sequel.
Rema k 1. Le
ϕ
be a sGSP sc , le
u
be an agen , and le
P
and
P′
be wo p o iles such ha ei he
u∈D(a,P)∩D(a,P′)o u ∈D(b,P)∩D(b,P′). Then, ϕ(P′) = ϕ((Pu,P′
−u)).
Le us p o e ha in he case o a socie y consis ing o jus wo agen s, almos -iia,
oge he wi h he Pa e o p ope y, is he same ha s ong g oup s a egy-p oo ness.
Theo em 1. I
|V|=
2, hen a sc
ϕ:P→ {a
,
b}
is sGSP i and only i i is Pa e ian and
almos -iia: in o he wo ds, i and only i i e i ies (1) and (2) and (3).
P oo .
By P oposi ions 3and 4, any sGSP sc e i ies (1), (2) and (3). To p o e he con e se,
assume by con adic ion ha a sc
ϕ
e i ying (1), (2) and (3) can be weakly manipula ed
a a ce ain p o ile
P
. I
D(a
,
P) = ∅
, hen ei he
P
is a p o ile o unanimous indi e ence
o Condi ion (2) applies. In bo h cases, no manipula ion is possible. The same conclusion
holds o he case
D(b
,
P) = ∅
. Hence,
P
mus be a con lic p o ile. The only possibili y
is ha
P= (Pu
,
P )
, wi h
a≻Pub
and
b≻P a
. Assume
ϕ(P) = a
( he case
ϕ(P) = b
is
analogous). The only coali ion ha can weakly manipula e
ϕ
a
P
is hen
{ }
. We now
e i y ha he e is no p o ile
Q= (Pu
,
Q )
such ha
ϕ(Q) = b
; hence, manipula ion
Games 2024,15, 44 5 o 9
is impossible. I
a⪰Q b
, hen Condi ion (1) implies
ϕ(Q) = a
. On he o he hand, i
b≻Q a
, hen he wo p o iles
P
and
Q
ha e he same es ic ion o
{a
,
b}
; hence, he
ela ion ϕ(Q) = a ollows om (3).
When he e a e mo e han wo agen s in he socie y, a di e en condi ion added o he
Pa e o p ope y cha ac e izes s a egy-p oo ness o a social choice unc ion: i s es ic ion
o he se o con lic p o iles has o be cons an . We o mally in oduce he condi ion.
De ini ion 6. A sc
ϕ:P→ {a
,
b}
is said o be con lic -independen i i is cons an on he se
P′o con lic p o iles. In o he wo ds, his is alid i he ollowing implica ion holds ue:
P,Q∈P′⇒ϕ(P) = ϕ(Q). (4)
P oposi ion 5. I |V|>2, hen any sGSP sc is con lic -independen .
P oo .
Conside a p o ile
P∈P
such ha bo h he se s
D(a
,
P)
and
D(b
,
P)
a e single ons,
say
D(a
,
P) = {u}
and
D(b
,
P) = { }
. Wi hou any loss o gene ali y, assume
ϕ(P) = a
.
Since
ϕ
is sGSP, necessa ily
ϕ(P′) = a
o each p o ile
P′
wi h
u∈D(a
,
P′)
. I no , by
Rema k 1, coali ion V {u}can weakly manipula e ϕa p o ile P, decla ing P′.
Conside a p o ile
R
ha ing
D(a
,
R) = {u}
and
D(b
,
R) = {w}
, whe e he agen
w
is
di e en om
. F om he p e ious obse a ion, we ha e
ϕ(R) = a
. The la e ela ion
implies ha he alue o
ϕ
is
a
a each p o ile
R′
, ha ing
D(b
,
R′) = {w}
and
D(a
,
R′) = {z}
( o any
z=w
). In ac , i o such a p o ile
ϕ(R′) = b
, hen, by Rema k 1, coali ion
V {w}
could weakly manipula e
ϕ
a p o ile
R′
, decla ing
R
. Applying o p o ile
R′
, encompassing
he same easoning used o p o ile
P
, i ollows ha
ϕ(P) = a
o any p o ile
P
, such ha
o a leas one agen z=w, i is z∈D(a,P).
Since he choice o
w
was a bi a y in
V {u}
, he ela ion
ϕ(P) = a
holds o any
p o ile Psuch ha he se D(a,P)is no emp y, pa icula ly o any p o ile in P′.
No e ha sGSP social choice unc ions a e no necessa ily con lic -independen i
|V|=2, as he ollowing example shows.
Example 1. Le V ={1, 2}. The unc ion ϕ:WV→ {a,b}de ined by se ing
ϕ(P) =
a i |D(a,P)|>|D(b,P)|
b i |D(a,P)|<|D(b,P)|
a i |D(a,P)|=|D(b,P)|and 1∈D(a,P)
b i |D(a,P)|=|D(b,P)|and 1 /∈D(a,P)
is sGSP and i is no con lic -independen 3.
Also no e ha o p o e P oposi ion 5, we used he he minimal assump ion on he
domain. I was necessa y o ob ain ha he p o iles used in he p oo belong o he
domain
P
o he conside ed unc ion. We canno a oid ha assump ion, as he ollowing
example p o es.
Example 2. Le
V={
1, 2, 3
}
, and o each
in
V
, le
P=× ∈VS
, whe e
S
consis s o
all he s ic p e e ence ela ions on
A
( his means an i-symme ic p e e ences; in o he wo ds, i
encompasses p e e ences acco ding o which wo elemen s indi e en o each o he mus coincide).
The unc ion ϕ:P→ {a,b}de ined by se ing
ϕ(P) = a⇔ |D(a,P)| ≥ 2
Games 2024,15, 44 6 o 9
is a sGSP sc ha is no con lic -independen .
We a e now eady o cha ac e ize s ong g oup s a egy-p oo ness in he case o a
socie y wi h mo e han wo agen s.
Theo em 2. I
|V|>
2, hen a sc
ϕ:P→ {a
,
b}
is sGSP i and only i i is Pa e ian and
con lic -independen , i.e., i and only i i e i ies (1), (2) and (4).
P oo .
Assume by con adic ion ha a Pa e ian and con lic -independen sc
ϕ
can be
weakly manipula ed by a coali ion
D
a a p o ile
P
. Wi hou any loss o gene ali y, we e e
o he case
ϕ(P) = a
. This means ha o a ce ain p o ile
Q= (QD
,
P−D)
, i is
ϕ(Q) = b
,
and o a leas one agen
∈D
, i is
b≻P a
. The ac ha
D(b
,
P)
is nonemp y and ha
ϕ(P) = a
, oge he wi h Condi ion (2) o P oposi ion 2, imply
D(a
,
P)=∅
. Hence,
P∈P′
.
The ela ion
Pu=Qu∀u∈D(a
,
P)
ensu es ha
D(a
,
Q)=∅
. A his poin , ei he
D(b
,
Q)
is emp y, o i con ains a leas one agen . In he i s case, Condi ion (1) o
P oposi ion 2implies
ϕ(Q) = a
. In he second case, i is
Q∈P′
. Thus, wi h
ϕ
being
con lic -independen , i is ϕ(Q) = a. In bo h cases, we ge a con adic ion.
The con e se implica ion ollows om P oposi ions 3and 5.
We summa ize he wo p e ious Theo ems 1and 2in one s a emen :
Theo em 3. Le ϕ:P→ {a,b}be a sc .
I |V|=2, hen ϕis sGSP i and only i i is Pa e ian and almos -iia.
I |V|>2, hen ϕis sGSP i and only i i is Pa e ian and con lic -independen .
No e ha in bo h cases,
|V|=
2 and
|V|>
2, he alues a social choice unc ion a ains
on he se P0a e no ele an o es ablish whe he he unc ion is sGSP o no .
4. Func ional Fo m o S ongly G oup S a egy-P oo Social Choice Func ions
We now ecall he de ini ion o some social choice unc ions om [
7
] and [
5
] ha gi e
an explici desc ip ion o sGSP unc ions.
De ini ion 7. A unc ion ϕis said o be a e o ule o a i i sa is ies
(P) =
b i D(b,P)=∅
a i D(b,P) = ∅=D(a,P)
Symme ically, ϕis said o be a e o ule o b i i sa is ies
(P) =
a i D(a,P)=∅
b i D(a,P) = ∅=D(b,P)
No e ha a e o ule can assume any alue a a p o ile o unanimous indi e ence. So,
e o ules on he same al e na i e may di e only on p o iles o unanimous indi e ence.
I is ob ious ha any e o ule sa is ies (1), (2) and (4). On he o he hand, i is easy
o check ha any unc ion e i ying (1) and (2) ha a ains he same alue, say
a
( esp.
b
),
a all con lic p o iles is a e o ule o
b
( esp. a e o ule o
a
). These wo obse a ions,
oge he wi h Theo em 2, imply ha
Co olla y 1. In he case |V|>2, he e o ules a e all and only he sGSP sc s.
To ob ain he desc ip ion o sGSP unc ions o he case
|V|=
2, le us in oduce a
u he social choice unc ion.
Games 2024,15, 44 7 o 9
De ini ion 8. Le
π
be an o de (a pe mu a ion) on he se
V
o agen s, assumed o be ini e. A
unc ion
ϕ
is said o be a se ial dic a o wi h o de
π
i i sa is ies, o any p o ile
P∈P P0
,
he ela ion
ϕ(P) =
a i h ∈D(a,P),
b i h ∈D(b,P),
whe e h :=min{π( ): /∈I(P)}.
No e ha , as in he case o e o ules, a se ial dic a o wi h any o de can assume any
alue a a p o ile o unanimous indi e ence.
When
|V|=
2, se ial dic a o s sa is y (1), (2) and (3). This obse a ion, oge he wi h
Theo em 1, implies ha when he socie y consis s o only wo agen s, e o ules and se ial
dic a o s wi h any o de a e sGSP.
Le us e i y ha , con e sely, any sGSP is necessa ily o his kind.
When a sGSP social choice unc ion is no a e o ule, i assumes bo h alues on he
se o con lic p o iles. Since he e a e only wo agen s, say
V={
1, 2
}
, con lic p o iles a e
all and only p o iles acco ding o which one o he wo agen s s ic ly p e e s
a
o
b
, and
he o he agen s ic ly p e e s
b
o
a
. Gi en P oposi ion 4, such a social choice unc ion is
cons an on each o he se s
P12 :={P∈P:D(a,P) = {1}and D(b,P) = {2}}
and
P21 :={P∈P:D(a,P) = {2}and D(b,P) = {1}}.
I
ϕ(P12) = {a}
and
ϕ(P21) = {b}
, he unc ion is a se ial dic a o wi h o de he iden i y
on
V
(
π(
1
) =
1 and
π(
2
) =
2). I
ϕ(P12) = {b}
and
ϕ(P21) = {a}
, he unc ion is a se ial
dic a o wi h he “ e e sing” o de on V(π(1) = 2 and π(2) = 1). Hence,
Co olla y 2. In he case
|V|=
2, he e o ules and he se ial dic a o s a e all and only he
sGSP sc s.
Co olla ies 1and 2 oge he gi e [
7
] (Theo em 3). In [
7
], he p oo o Theo em 3
consis s o a ce ain numbe o s eps. Among hese, S ep 2 uses a cha ac e iza ion o weakly
g oup s a egy-p oo unc ions. Such a cha ac e iza ion has been p o ed, making use o
he ini eness o
V
(see [
7
] (Foo no e 9)). Di e en ly om [
7
], we do no need o assume he
se V o be ini e.
Be o e concluding, we make a compa ison o ou Co olla y 1, in he pa icula case o
|A|=2 and P=WV, wi h a esul in [5].
When he se
A
consis s o exac ly wo al e na i es, he e is only one p o ile o unan-
imous indi e ence, hence in his case he se
P0
collapses in o a single on. The cha ac-
e iza ion o sGSP social choice unc ions s a ed in Theo em 2says ha when he e a e
a leas h ee agen s in he socie y, o a Pa e ian social choice unc ion o be sGSP i is
necessa y and su icien o ix he alue, say
x∈ {a
,
b}
, i a ains a any o he con lic
p o iles (hence a all o hem), and he alue, say
y∈ {a
,
b}
, i a ains a he (unique) p o ile
o unanimous indi e ence. Any o hese wo can be ei he
a
o
b
( hey may also coincide).
These a e exac ly he consensus ules in oduced in [
5
]. Mo e p ecisely, consensus ule
wi h disag eemen -de aul
x
and indi e ence-de aul
y
. Then in his pa icula case ou
Theo em 2gi es back he ollowing esul
Theo em 4 ([
5
], Theo em 2).Fo
|V|>
2,
|A|=
2and
P=WV
, only consensus ules
a e sGSP.
This means ha in his case, he se o consensus ules coincides wi h he se o e o
ules. Le us desc ibe all hese unc ions in de ail as ollows:
Games 2024,15, 44 8 o 9
When
|A|=
2, i is
A={a
,
b}
, and he e a e only h ee p e e ences on
A
:
a
is be e
han
b
(we w i e
a
),
b
is be e han
a
(we w i e
b
), and
a
and
b
a e indi e en o each o he
(we w i e ∼). Hence,
W={a,b,∼},
and he e is only one p o ile o unanimous indi e ence. We deno e i by
U
. Fix any con lic
p o ile, say
C
. Gi en Theo em 2, o comple ely desc ibe a sGSP unc ion, i is su icien o
know i s alues a Uand a C. The e a e exac ly ou sGSP unc ions:
p o iles →C U
unc ions ↓
ψ1a a
ψ2a b
ψ3b a
ψ4b b
Acco ding o he e minology o [
7
], we ecognize ha
ψ1
and
ψ2
( esp.
ψ3
and
ψ4
) a e
he e o ules o b( esp e o ules o a).
On he o he hand, e e ing o [
5
], we obse e ha , as expec ed, hey a e all he consensus
ules (CR o b e i y). P ecisely, hey a e
ψ1CR wi h disag eemen -de aul aand indi e ence-de aul a;
ψ2CR wi h disag eemen -de aul aand indi e ence-de aul b;
ψ3CR wi h disag eemen -de aul band indi e ence-de aul a;
ψ4CR wi h disag eemen -de aul band indi e ence-de aul b.
Rema k: We ecall ha a sc is said o be anonymous when no pe mu a ion o he
agen s can e ec i s alues (“all he agen s a e equal”).
I he se
A
o al e na i es consis s o only wo elemen s, hen he e is only one
p e e ence acco ding o which he wo al e na i es a e indi e en , and, o cou se, only one
p o ile o unanimous indi e ence. In his case, any e o ule is anonymous, which means
ha o he case o a se Vconsis ing o a leas h ee agen s, any sGSP sc is anonymous.
Fo he case
|A|>
2, he si ua ion is di e en : a sGSP unc ion may a ain any alue
a each p o ile on unanimous indi e ence. Hence, e en i only he e o ules a e sGSP
( his happens, as we al eady obse ed, only in he case
|V|>
2), he possibili y o such
a unc ion o be anonymous depends on he alues i a ains a he (many) p o iles o
unanimous indi e ence.
5. Conclusions
When designing mechanisms ha agg ega es p e e ences, one o he main eques s
is he p ope y o obus ness wi h espec o manipula ion (s a egy-p oo ness). The
mechanisms we conside in his pape a e he wo- alued social choice unc ions, i.e.,
ules ha , based on how he agen s in he socie y o de he al e na i es, selec one o
wo al e na i es. We ocused on he p oblem o cha ac e izing wo- alued social choice
unc ions ha esis o weak manipula ions by coali ions: s ong g oup s a egy-p oo social
choice unc ions.
We i s e i y ha each s ong g oup s a egy-p oo social choice unc ion enjoys wo
p ope ies: a Pa e o e iciency wi h espec o i s ange and a mild o m o independence o
i ele an al e na i es. These wo p ope ies cha ac e ize such unc ions i he e a e only
wo agen s in he socie y. In la ge socie ies, his cha ac e iza ion is no mo e ue, bu he
unc ions happen o e i y a much mo e in e es ing p ope y: hey gi e ise o he same
ou come in a e y la ge se o p o iles whe e he con lic be ween wo al e na i es appea s
( hey a e con lic -independen ). This p ope y, oge he wi h he Pa e o e iciency, allows o
cha ac e ize s ong g oup s a egy-p oo ness when he e a e a leas h ee agen s.
A e cha ac e izing he s ong g oup s a egy-p oo sc s, bo h in he wo o mo e han
wo agen s’ cases, we can explici ly desc ibe hei o m using wo well-known agg ega ion
ules: e o ules and se ial dic a o s.
