Approval-based voting with mixed goods

Lu, Xinhang; Pe e s, Jannik; Aziz, Ha is; Bei, Xiaohui; Suksompong, Wa u
A icle — Published Ve sion
App o al-based o ing wi h mixed goods
Social Choice and Wel a e
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Lu, Xinhang; Pe e s, Jannik; Aziz, Ha is; Bei, Xiaohui; Suksompong, Wa u (2024) :
App o al-based o ing wi h mixed goods, Social Choice and Wel a e, ISSN 1432-217X, Sp inge ,
Be lin, Heidelbe g, Vol. 62, Iss. 4, pp. 643-677,
h ps://doi.o g/10.1007/s00355-024-01511-8
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/314984
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 p://c ea i ecommons.o g/licenses/by/4.0/
Social Choice and Wel a e (2024) 62:643–677
h ps://doi.o g/10.1007/s00355-024-01511-8
ORIGINAL PAPER
App o al-based o ing wi h mixed goods
Xinhang Lu1·Jannik Pe e s2·Ha is Aziz1·Xiaohui Bei3·
Wa u Suksompong4
Recei ed: 21 Ap il 2023 / Accep ed: 29 Janua y 2024 / Published online: 27 Feb ua y 2024
© The Au ho (s) 2024, co ec ed publica ion 2024
Abs ac
We conside a o ing scena io in which he esou ce o be o ed upon may consis
o bo h indi isible and di isible goods. This se ing gene alizes bo h he well-s udied
model o mul iwinne o ing and he ecen ly in oduced model o cake sha ing. Unde
app o al o es, we p opose wo a ian s o he ex ended jus i ied ep esen a ion (EJR)
no ion om mul iwinne o ing, a s onge one called EJR o mixed goods (EJR-M)
and a weake one called EJR up o 1(EJR-1). We ex end h ee mul iwinne o ing
ules o ou se ing—G eedyEJR, he me hod o equal sha es (MES), and p opo ional
app o al o ing (PAV)—and show ha while all h ee gene aliza ions sa is y EJR-1,
only he i s one p o ides EJR-M. In addi ion, we de i e igh bounds on he p o-
po ionali y deg ee implied by EJR-M and EJR-1, and in es iga e he p opo ionali y
deg ee o ou p oposed ules.
1 In oduc ion
In mul iwinne o ing—a “new challenge o social choice heo y”, as Faliszewski
e al. (2017) pu i — he goal is o selec a subse o candida es o ixed size om a
gi en se based on he o e s’ p e e ences. The candida es could be poli icians ying
o sea s in he pa liamen , p oduc s o be shown on a company websi e, o places
o isi on a school ip. A common way o elici p e e ences om he o e s is ia
A p elimina y e sion o his pape appea s in P oceedings o he 37 h AAAI Con e ence on A i icial
In elligence (AAAI 2023). This e sion con ains addi ional esul s on a new no ion called “s ong EJR-1”
(Sec . 3.2), a igh bound on a e age sa is ac ion (Theo em B.2), as well as all p oo s omi ed om he
con e ence e sion.
BWa u Suksompong
[email p o ec ed]
1Uni e si y o New Sou h Wales, Sydney, Aus alia
2Technische Uni e si ä Be lin, Be lin, Ge many
3Nanyang Technological Uni e si y, Singapo e, Singapo e
4Na ional Uni e si y o Singapo e, Singapo e, Singapo e
123
644 X. Lu e al.
he app o al model, whe ein each o e simply speci ies he subse o candida es ha
he o she app o es (Kilgou 2010; Lackne and Skow on 2023). While (app o al-
based) mul iwinne o ing has ecei ed subs an ial a en ion om (compu a ional)
social choice esea che s in he pas ew yea s, a di isible analog called cake sha ing
was ecen ly in oduced by Bei e al. (2024). In cake sha ing, he candida es co espond
o a di isible esou ce such as ime pe iods o using a acili y o iles o be s o ed
in cache memo y. Following he amous esou ce alloca ion p oblem o cake cu ing
(Robe son and Webb 1998; P ocaccia 2016), his di isible esou ce is e e ed o as a
“cake”, and cake sha ing is he collec i e choice p oblem o selec ing a subse o his
esou ce.
In his pape , we s udy a se ing ha simul aneously gene alizes bo h mul iwinne
o ing and cake sha ing, which we call (app o al-based) o ing wi h mixed goods.
Speci ically, in ou se ing, he esou ce may consis o bo h indi isible and di isible
goods.1This gene ali y allows ou model o cap u e mo e scena ios han ei he o
he p e ious models. Fo example, when ese ing ime slo s, i is possible ha some
hou ly slo s mus be ese ed as a whole, while o he slo s can be booked ac ionally.
Likewise, in cache memo y s o age, ce ain iles may need o be s o ed in hei en i e y,
whe eas o he iles can be b oken in o smalle po ions. Combina ions o di isible and
indi isible goods ha e been examined in he con ex o ai di ision, whe e he esou ce
is o be di ided among in e es ed agen s and he en i e esou ce can be alloca ed (Bei
e al. 2021a,b; Bhaska e al. 2021;Kawasee al.2023; Nishimu a and Sumi a 2023).
By con as , we in es iga e mixed goods in a collec i e choice con ex , whe e only a
subse o he esou ce can be alloca ed bu he alloca ed esou ce is collec i ely sha ed
by all agen s.2
The e a e mul iple c i e ia ha one can use o selec a collec i e subse o esou ce
based on he app o al o es. Fo example, one could y o op imize he social wel-
a e— he sum o he agen s’ u ili ies—o he co e age— he numbe o agen s who
ecei e nonze o u ili y. A ep esen a ion c i e ion ha has a ac ed g owing in e es
is jus i ied ep esen a ion (JR) (Aziz e al. 2017). In mul iwinne o ing, i he e a e
nagen s and k(indi isible) goods can be chosen, hen JR equi es ha whene e
a g oup o a leas n/kagen s app o e a common good, some agen in ha g oup
mus ha e an app o ed good in he selec ed se . A well-s udied s eng hening o JR is
ex ended jus i ied ep esen a ion (EJR), which says ha o each posi i e in ege ,i
a g oup o a leas ·n/kagen s app o e no ewe han common goods (such a g oup
is said o be -cohesi e), some agen in ha g oup mus ha e no ewe han app o ed
goods in he selec ed se . Aziz e al. (2017) showed ha he p opo ional app o al
o ing (PAV) ule always ou pu s a se o goods ha sa is ies EJR. In cake sha ing,
Bei e al. (2024, Sec. 7) adap ed EJR by imposing he condi ion o e e y posi i e
eal numbe ,and p o ed ha he esul ing no ion is sa is ied by he maximum Nash
1Since a “candida e” usually e e s o an indi isible en i y, we use he e m “good” ins ead om he e on.
2We hence o h use he e m “agen ” ins ead o “ o e ”.
123
App o al-based o ing wi h mixed goods 645
wel a e (MNW) ule.3Can we uni y he wo e sions o EJR o ou gene alized se ing
in such a way ha he gua an eed exis ence is main ained?4
1.1 Ou con ibu ions
In Sec . 3, we in oduce wo a ian s o EJR sui able o he mixed-goods se ing. The
s onge a ian , EJR o mixed goods (EJR-M), imposes he EJR condi ion o any
posi i e eal numbe whene e a -cohesi e g oup commonly app o es a esou ce o
size exac ly .The weake a ian , EJR up o 1(EJR-1), again conside s he condi ion
o e e y posi i e eal numbe bu only equi es ha some membe o a -cohesi e
g oup ecei es u ili y g ea e han −1.While EJR-M educes o he co esponding
no ion o EJR in bo h mul iwinne o ing and cake sha ing, and he e o e o e s a
uni ica ion o bo h e sions, EJR-1 does so only o mul iwinne o ing. We hen
ex end h ee mul iwinne o ing ules o ou se ing: G eedyEJR, he me hod o equal
sha es (MES), and p opo ional app o al o ing (PAV). We show ha G eedyEJR-M,
ou gene aliza ion o G eedyEJR, sa is ies EJR-M (and he e o e EJR-1), which also
means ha an EJR-M alloca ion always exis s. On he o he hand, we p o e ha ou
gene aliza ions o he o he wo me hods p o ide EJR-1 bu no EJR-M. Fu he mo e,
while G eedyEJR-M and Gene alized MES gua an ee he cake e sion o EJR in cake
sha ing, Gene alized PAV does no .
In Sec . 4, we u n ou a en ion o he concep o p opo ionali y deg ee, which
measu es he a e age u ili y o he agen s in a cohesi e g oup (Skow on 2021). We
de i e igh bounds on he p opo ionali y deg ee implied by bo h EJR-M and EJR-1,
wi h he EJR-M bound being sligh ly highe . We also in es iga e he p opo ionali y
deg ee o he h ee ules om Sec . 3; in pa icula , we ind ha Gene alized PAV has a
signi ican ly highe p opo ionali y deg ee han bo h G eedyEJR-M and Gene alized
MES.
An o e iew o ou esul s can be ound in Table 1.
2 P elimina ies
Le N={1,2,...,n}be he se o agen s. In he mixed-goods se ing, he esou ce R
consis s o a cake C=[0,c] o some eal numbe c≥0 and a se o indi isible
goods G={g1,...,gm} o some in ege m≥0.Assume wi hou loss o gene ali y
ha max(c,m)>0.Apiece o cake is a union o ini ely many disjoin (closed)
subin e als o C.Deno e by (I) he leng h o an in e al I, ha is, ([x,y]):=
y−x.Fo a piece o cake Cconsis ing o a se o disjoin in e als IC,we le
(C):=I∈IC(I). Abundle Rconsis s o a (possibly emp y) piece o cake
C⊆Cand a (possibly emp y) se o indi isible goods G⊆G; he size o such a
3They also no ed ha JR does no admi a na u al analog o cake sha ing, since he e is no disc e e uni
o cake.
4As u he e idence o he gene ali y o ou se ing, we ema k ha , as Bei e al. (2024, Sec. 1.2) poin ed
ou , cake sha ing i sel gene alizes ano he collec i e choice se ing called ai mixing (Aziz e al. 2020).
123
646 X. Lu e al.
Table 1 O e iew o ou esul s. The check ma k (✓) indica es ha he ule sa is ies he p ope y; he c oss
ma k (✗) indica es ha i does no
G eedyEJR-M Gen. MES Gen. PAV
EJR-M ✓✗✗
EJR-1 ✓✓ ✓
P opo ionali y deg ee  ·1− +1
2 ≈
2 −2+1/
2, +1
2≈
2> −1
Indi isible-goods EJR ✓∗✓∗✓∗
Cake EJR ✓✓ ✗
Polynomial- ime compu a ion ? ✓✗∗
En ies ma ked by an as e isk ollow om known esul s in mul iwinne o ing; he en y on he compu a ion
o Gene alized PAV elies on he assump ion ha P = NP. We also show ha he p opo ionali y deg ee
implied by EJR-M and EJR-1 is  ·1− +1
2 and −2+1/
2,which a e bo h app oxima ely /2,
espec i ely
Fig. 1 A mixed-goods ins ance
wi h wo agen s N={1,2}, wo
indi isible goods G={g1,g2},
a cake Co leng h 0.9,and
α=2.Agen 1 app o es
R1={g1}∪C,while agen 2
app o es R2={g2}∪C.I he
alloca ion A={g1,g2}is
chosen, bo h agen s ecei e a
u ili y o 1
GC
g1g2
00.9
R
R1
R2
bundle Ris s(R):=(C)+|G|.We some imes w i e R=(C,G)ins ead o
R=C∪G.
We assume ha he agen s ha e app o al p e e ences (also known as dicho omous
o bina y), i.e., each agen i∈Napp o es a bundle Ri=(Ci,Gi)o he esou ce.5
The u ili y o agen i o a bundle Ris gi en by ui(R):=s(Ri∩R)=(Ci∩C)+
|Gi∩G|.Le α∈(0,c+m]be a gi en pa ame e , and assume ha a bundle Awi h
s(A)≤αcan be chosen and collec i ely alloca ed o he agen s6; we also e e o an
alloca ed bundle as an alloca ion. (No e ha we allow s(A)≤α a he han equi ing
s(A)=α; his is a sligh de ia ion om he s anda d mul iwinne o ing model.) An
ins ance consis s o he esou ce R, he agen s Nand hei app o ed bundles (Ri)i∈N,
and he pa ame e α. We say ha an ins ance is a cake ins ance i i does no con ain
indi isible goods (i.e., m=0), and an indi isible-goods ins ance i i does no con ain
cake (i.e., c=0).7An example ins ance is shown in Fig. 1.
Amechanism o ule Mmaps any ins ance o an alloca ion o he esou ce. Fo
any p ope y Po alloca ions, we say ha a ule Msa is ies p ope y Pi o e e y
5App o al p e e ences can be gi en explici ly as pa o he inpu o algo i hms, so we do no need
he cake-cu ing que y model o Robe son and Webb (1998). In pa icula , he cake p e e ences can be
desc ibed by he endpoin s o he cake in e als app o ed by each agen .
6Ins ead o he a iable kas in mul iwinne o ing, we use α, as his a iable may no be an in ege in ou
se ing. This is consis en wi h he no a ion used by Bei e al. (2024) o cake sha ing.
7When c=0 he cake consis s o a single poin , which yields u ili y 0 o e e y agen , so we may igno e i .
123

App o al-based o ing wi h mixed goods 647
ins ance, he alloca ion ou pu by Msa is ies P.An example o a ule is he maximum
Nash wel a e (MNW) ule, which e u ns an alloca ion A ha maximizes he p oduc
i∈Nui(A)o he agen s’ u ili ies.8
3 EJR no ions and ules
In o de o eason abou ex ended jus i ied ep esen a ion (EJR), an impo an concep
is ha o a cohesi e g oup. Fo any posi i e eal numbe ,a se o agen s N∗⊆N
is said o be -cohesi e i |N∗|≥ ·n/α and s(i∈N∗Ri)≥ .Fo an indi isible-
goods ins ance, Aziz e al. (2017) de ined EJR as ollows: an alloca ion Asa is ies
EJR i o e e y posi i e in ege and e e y -cohesi e g oup o agen s N∗,a leas
one agen in N∗ ecei es u ili y a leas .Bei e al. (2024) adap ed his axiom o cake
sha ing by conside ing e e y posi i e eal numbe ins ead o only posi i e in ege s.9
To dis inguish be ween hese wo e sions o EJR, as well as om e sions o mixed
goods ha we will de ine nex , we e e o he wo e sions as indi isible-goods EJR
and cake EJR, espec i ely.
A i s a emp o de ine EJR o mixed goods is o simply use he cake e sion.
Howe e , as we will see sho ly, he esul ing no ion is oo s ong. Hence, we elax i
by lowe ing he u ili y h eshold.
De ini ion 3.1 (EJR-β)Le β≥0.Gi en an ins ance, an alloca ion Awi h s(A)≤α
is said o sa is y ex ended jus i ied ep esen a ion up o β(EJR-β)i o e e y posi i e
eal numbe and e e y -cohesi e g oup o agen s N∗,i holds ha uj(A)> −β
o some j∈N∗.10
P oposi ion 3.2 Fo each cons an β∈[0,1), he e exis s an indi isible-goods
ins ance in which no alloca ion sa is ies EJR-β. This emains ue e en i we elax he
inequali y u j(A)> −βin De ini ion 3.1 o u j(A)≥ −β.
P oo We wo k wi h he weake condi ion uj(A)≥ −β. Fix β∈[0,1), and choose
a a ional cons an β∈(β, 1). Conside an indi isible-goods ins ance wi h in ege s
nand αsuch ha α=β·n,and assume ha all agen s app o e disjoin nonemp y
subse s Gio goods. Each indi idual agen o ms a β-cohesi e g oup, so in an EJR-β
alloca ion, e e y agen mus ecei e u ili y a leas β−β>0.Hence, any EJR-β
alloca ion necessa ily includes a leas one good om each app o al se Gi,and mus
he e o e con ain a leas ngoods in o al. Howe e , since α=β·n<n,no alloca ion
can sa is y EJR-β. 
P oposi ion 3.2 aises he ques ion o whe he EJR-1 can always be sa is ied. We
will answe his ques ion in he a i ma i e in Sec . 3.1. Be o e ha , we in oduce
8Ties can be b oken a bi a ily excep when he highes possible p oduc is 0.In his excep ional case, he
MNW ule i s gi es posi i e u ili y o a se o agen s o maximal size and hen maximizes he p oduc o
u ili ies o he agen s in his se .
9No e ha he indi isible-goods e sion wi h posi i e in ege s may be meaningless in he cake se ing,
e.g., i he en i e cake has leng h less han 1.Mo e gene ally, he es ic ion o posi i e in ege s is unna u al
o cake, as he e is no disc e e uni o cake.
10 Fo β=1,Pe e s e al. (2021) conside ed a somewha simila no ion called “EJR up o one p ojec ” in
he se ing o pa icipa o y budge ing wi h indi isible p ojec s.
123
648 X. Lu e al.
EJR-M, ano he a ian o EJR ailo ed o mixed goods. The in ui ion behind EJR-M
is ha a -cohesi e g oup o agen s should be able o claim a u ili y o o some
membe only when he e exis s a commonly app o ed esou ce o size exac ly .This
ules ou such cases as in he p oo o P oposi ion 3.2, whe e a g oup can e ec i ely
claim u ili y highe han due o he indi isibili y o he goods.
De ini ion 3.3 (EJR-M) Gi en an ins ance, an alloca ion Awi h s(A)≤αis said
o sa is y ex ended jus i ied ep esen a ion o mixed goods (EJR-M) i he ollowing
holds:
Fo e e y posi i e eal numbe and e e y -cohesi e g oup o agen s N∗ o which
he e exis s R∗⊆Rsuch ha s(R∗)= and R∗⊆Ri o all i∈N∗,i holds ha
uj(A)≥ o some j∈N∗.
No e ha o indi isible-goods ins ances, he condi ion s(R∗)= can only hold o
in ege s ,so EJR-M educes o indi isible-goods EJR. Likewise, o cake ins ances,
i a g oup is -cohesi e hen a commonly app o ed subse o size exac ly always
exis s, so EJR-M educes o cake EJR. Hence, EJR-M uni ies EJR om bo h se ings.
P oposi ion 3.4 Le be a posi i e eal numbe . Fo an EJR-M alloca ion A and a
-cohesi e g oup o agen s N∗,i holds ha u j(A)≥  o some j ∈N∗.
P oo Le R∗=i∈N∗Ri,so s(R∗)≥ ,and le m∗be he numbe o indi isible
goods in R∗.I m∗≥ , hen by De ini ion 3.3, he e exis s j∈N∗such ha
uj(A)≥ .Else, m∗< ,which means ha R∗con ains a piece o cake o leng h
a leas −m∗.In his case, by conside ing he m∗indi isible goods and a piece o
cake o leng h exac ly −m∗commonly app o ed by all agen s in N∗,De ini ion 3.3
implies he exis ence o j∈N∗such ha uj(A)≥ ≥ .
Since  > −1 o e e y eal numbe ,we ha e he ollowing co olla y.
Co olla y 3.5 EJR-M implies EJR-1.
Fo indi isible-goods ins ances, EJR-1 educes o indi isible-goods EJR, since o
e e y posi i e eal numbe , he smalles in ege g ea e han −1is .On he o he
hand, o cake ins ances, EJR-1 is weake han cake EJR.
In he cake se ing, Bei e al. (2024) p o ed ha he MNW ule sa is ies cake EJR.
Howe e , in he indi isible-goods se ing, he ac ha MNW ies o a oid gi ing
u ili y 0 o any agen a all cos s means ha i some imes a emp s o help indi idual
agen s a he expense o la ge dese ing g oups. This is o malized in he ollowing
p oposi ion.
P oposi ion 3.6 Fo any cons an β≥0, he e exis s an indi isible-goods ins ance in
which no MNW alloca ion sa is ies EJR-β.
P oo I su ices o p o e he s a emen o e e y posi i e in ege β. Indeed, once we
ha e his, hen o any nonnega i e eal numbe β, he e exis s a posi i e in ege
β>β
.Since EJR-βimplies EJR-β, in an ins ance in which no MNW alloca ion
sa is ies EJR-β, he e also does no exis an MNW alloca ion sa is ying EJR-β.
123
App o al-based o ing wi h mixed goods 649
Fix a posi i e in ege β, and le γ=β+2.Conside an indi isible-goods ins ance
wi h n=γ2+γagen s, m=2γgoods, and α=γ+1.The i s γ2agen s all
app o e goods g1,...,gγ,while agen γ2+ionly app o es good gγ+i o 1 ≤i≤γ.
No ice ha he i s γ2agen s o m a γ-cohesi e g oup, so a leas one o hem mus
ecei e u ili y no less han γ−β=2inanEJR-βalloca ion. In pa icula , a leas wo
goods among g1,...,gγmus be chosen. Howe e , e e y MNW alloca ion con ains
gγ+1,gγ+2,...,g2γalong wi h exac ly one o g1,...,gγ.I ollows ha no MNW
alloca ion sa is ies EJR-β. 
3.1 G eedyEJR-M
P oposi ion 3.6 implies ha he MNW ule canno gua an ee EJR-M o EJR-1 in he
indi isible-goods se ing, le alone in he mixed-goods se ing. We show nex ha a
g eedy app oach can be used o achie e hese gua an ees. The ule ha we use is an
adap a ion o he G eedyEJR ule om he indi isible-goods se ing (B ede eck e al.
2019; Pe e s e al. 2021; Elkind e al. 2022); we he e o e call i G eedyEJR-M and
desc ibe i below.
G eedyEJR-M
S ep 1: Ini ialize N=Nand R=∅.
S ep 2: Le ∗be he la ges nonnega i e eal numbe o which he e exis
∅ = N∗⊆Nand R∗⊆Rsuch ha N∗is a ∗-cohesi e g oup, R∗⊆Ri o all
i∈N∗,and s(R∗)= ∗.Conside any such pai (N∗,R∗). Remo e N∗ om N
and add he pa o R∗ ha is no al eady in R o R.
S ep 3: I N=∅, e u n R.Else, go back o S ep 2.
Example 3.7 Conside he ins ance in Fig. 1.Weha en/α =1,and S ep 2 o
G eedyEJR-M chooses ∗=1,along wi h (as one possibili y) N∗={1}and
R∗={g1}.We a e le wi h N={2},and he nex i e a ion o S ep 2 chooses
∗=1,N∗={2},and R∗={g2}.Finally, he ule e u ns R={g1,g2}.
Theo em 3.8 The G eedyEJR-M ule sa is ies EJR-M (and he e o e EJR-1).
P oo By Co olla y 3.5, i su ices o p o e he claim o EJR-M. We b eak he p oo
in o he ollowing ou pa s.
•The p ocedu e is well-de ined. To his end, we mus show ha he la ges nonnega-
i e eal numbe ∗in S ep 2 always exis s. Obse e ha o each nonemp y g oup
o agen s X⊆N, he se
TX:= ≥0|X|≥ ·n
αand he e exis s Y⊆
i∈X
Riwi h s(Y)= 
123
650 X. Lu e al.
is a union o a ini e numbe o (possibly degene a e) closed in e als, and is
nonemp y because 0 ∈TX.The e o e, TXhas a maximum. The alue ∗chosen in
S ep 2 is hen he la ges among he maxima o TXac oss all nonemp y X⊆N.
•The p ocedu e always e mina es. This is because each i e a ion o S ep 2 emo es
a leas one agen om N.
•The p ocedu e e u ns an alloca ion Rwi h s(R)≤α. Indeed, i an i e a ion
o S ep 2 uses alue ∗,i emo es11 a leas ∗·n/α agen s om Nand adds a
esou ce o size a mos ∗ o R.Since only nagen s can be emo ed in o al, he
added esou ce has size a mos α.
•The e u ned alloca ion Rsa is ies EJR-M. Assume o con adic ion ha o
some g oup X,De ini ion 3.3 ails o Xand pa ame e .Conside he momen
a e he p ocedu e emo ed he las g oup wi h pa ame e ∗≥ .I no agen
in Xhas been emo ed, he p ocedu e should ha e emo ed Xwi h pa ame e
,a con adic ion. Else, some agen j∈Xhas been emo ed. In his case, he
p ocedu e gua an ees ha uj(R)≥ ,which means ha Xsa is ies De ini ion 3.3
wi h pa ame e ,again a con adic ion. 
3.2 Gene alized Me hod o Equal Sha es
Despi e he s ong ep esen a ion gua an ee p o ided by G eedyEJR-M, he ule does
no admi an ob ious polynomial- ime implemen a ion.12 In he indi isible-goods
se ing, Pe e s and Skow on (2020) in oduced he Me hod o Equal Sha es (MES),
o iginally known as Rule X, and showed ha i sa is ies indi isible-goods EJR and uns
in polynomial ime. We now ex end hei ule o ou mixed-goods se ing. A a high
le el, in Gene alized MES, each agen is gi en a budge o α/n,which can be spen
on buying he esou ce—each piece o cake has cos equal o i s leng h whe eas each
indi isible good cos s 1.In each s ep, a piece o cake o an indi isible good ha incu s
he smalles cos pe u ili y o agen s who app o e i is chosen, and hese agen s pay
as equally as possible o co e he cos o he chosen esou ce. The ule s ops once no
mo e cake o indi isible good is a o dable. No e ha when he esou ce consis s only
o indi isible goods, Gene alized MES is equi alen o he o iginal MES o Pe e s and
Skow on (2020).
11 I ∗=0, he i e a ion s ill emo es a leas one agen om N,bu we do no need his ac he e.
12 Indeed, de e mining ∗in S ep 2 o G eedyEJR-M po en ially equi es inspec ing an exponen ial numbe
o subse s N∗⊆N.
123
App o al-based o ing wi h mixed goods 657
=
i∈N+1
ui(R)ui(G)+ui(C)≤
i∈N
1=n.(3)
He e, we ha e Cui([x,x+1])dx=ui(C)because
C
ui([x,x+1])dx=C
(Ci∩[x,x+1])dx
=Ci∩C
([y−1,y])dy=Ci∩C
1dy=(Ci∩C)=ui(C),
whe e he second equali y holds because a poin y∈Cibelongs o he in e al [x,x+1]
i and only i x∈[y−1,y].
I i we e he case ha H(R)−H(R [x,x+1])≥n/α o e e y x∈C,we
would ha e

g∈G
(H(R)−H(R {g})) +C
(H(R)−H(R [x,x+1])) dx
≥|G|· n
α+c·n
α=(α +1)·n
α>n,
a con adic ion wi h (3). Thus, i mus be ha H(R)−H(R [x,x+1])<n/α o
some x∈C.By eplacing he cake [x,x+1]in Rwi h he good g∗,we he e o e
ob ain a highe GPAV-sco e han ha o R.This yields he inal con adic ion and
comple es he p oo . 
In con as o Gene alized MES, Gene alized PAV does no sa is y EJR in cake
sha ing.
P oposi ion 3.19 Fo cake ins ances, Gene alized PAV does no sa is y cake EJR.
To p o e his s a emen , we use he ollowing p oposi ion.
P oposi ion 3.20 (Bei e al. 2024)Le :R≥0→[−∞,∞)be a s ic ly inc easing
unc ion which is di e en iable in (0,∞). Fo cake sha ing,i a ule ha always
chooses an alloca ion Rmaximizing i∈N (ui(R)) sa is ies cake EJR, hen he e
exis s a cons an c such ha (x)=c/x o all x ∈(0,∞).16
P oo o P oposi ion 3.19 Fo a posi i e in ege ,one can check ha he de i a i e
wi h espec o xo 
k=1
x
k(x+k)is 
k=1
1
(x+k)2,which con e ges as →∞.This
means ha Hx=∞
k=1
x
k(x+k)is di e en iable as a unc ion o x,and i s de i a i e
is ∞
k=1
1
(x+k)2.In pa icula , he e is no cons an csuch ha H
x=c/x o all
x∈(0,∞)— o example, his can be seen by obse ing ha , as xapp oaches 0
om abo e, H
xapp oaches ∞
k=11/k2=π2/6 a he han ∞.By P oposi ion 3.20,
Gene alized PAV does no sa is y cake EJR. 
16 This is Theo em 7.8 in hei wo k. Bei e al. no malized he leng h o he cake o 1,bu he same p oo
wo ks in ou se ing.
123

658 X. Lu e al.
4 P opo ionali y deg ee
In addi ion o he axioma ic s udy o ep esen a ion in e ms o c i e ia like EJR-M
and EJR-1, ano he ele an concep o cohesi e g oups is he p opo ionali y deg ee,
which measu es he a e age u ili y o he agen s in each such g oup (Skow on 2021).
In his sec ion, we i s de i e igh bounds on he p opo ionali y deg ee implied by
EJR-M and EJR-1, and hen in es iga e he p opo ionali y deg ee o he ules ha we
s udied in Sec . 3.
De ini ion 4.1 (A e age sa is ac ion) Gi en an ins ance and an alloca ion A, he a e -
age sa is ac ion o a g oup o agen s N⊆Nwi h espec o Ais 1
|N|·i∈Nui(A).
De ini ion 4.2 (P opo ionali y deg ee) Fix a unc ion :R>0→R≥0.A uleM
has a p opo ionali y deg ee o i o each ins ance I,each alloca ion A ha M
ou pu s on I,and each -cohesi e g oup o agen s N∗, he a e age sa is ac ion o N∗
wi h espec o Ais a leas ( ), i.e.,
1
|N∗|·
i∈N∗
ui(A)≥ ( ).
Fo indi isible goods, Sánchez-Fe nández e al. (2017) showed ha EJR implies a
p opo ionali y deg ee o −1
2.We will show ha in ou se ing, bo h EJR-M and EJR-1
imply a p opo ionali y deg ee o oughly /2,wi h he gua an ee o EJR-M being
sligh ly highe . In addi ion, we will es ablish ha bo h G eedyEJR-M and Gene alized
MES ha e a p opo ionali y deg ee o app oxima ely /2,while he p opo ionali y
deg ee o Gene alized PAV is highe han −1.
4.1 P opo ionali y deg ee implied by EJR-M and EJR-1
Ou ocus in his subsec ion is o es ablish igh bounds on he p opo ionali y deg ee
implied by EJR-M and EJR-1. Obse e ha o <1,a -cohesi e g oup may ha e
an a e age sa is ac ion o 0 in an EJR-M o EJR-1 alloca ion. Indeed, i α= and he
esou ce consis s only o a single indi isible good, which is app o ed by all nagen s,
hen he se o all agen s is -cohesi e, bu he emp y alloca ion is EJR-M and EJR-1.
We he e o e assume ≥1 o ou esul s om he e on.
We i s show ha he p opo ionali y deg ee implied by EJR-M is  ·1− +1
2 ,
beginning wi h he lowe bound. No e ha his quan i y is oughly /2.
Theo em 4.3 Gi en any ins ance and any eal numbe ≥1,le N∗⊆Nbea -
cohesi e g oup and A be an EJR-M alloca ion. The a e age sa is ac ion o N∗wi h
espec o A is a leas  ·1− +1
2 .
The high-le el idea behind he p oo o Theo em 4.3 is ha , gi en a -cohesi e
g oup N∗and an EJR-M alloca ion, a − 
ac ion o he agen s in N∗a e gua an eed
a u ili y o a leas  .The emaining agen s can hen be pa i ioned in o  disjoin
subse s so ha each subse consis s o a 1/ ac ion o he agen s in N∗and he
gua an eed u ili ies o hese subse s d op a i hme ically om  −1 o0.
123
App o al-based o ing wi h mixed goods 659
P oo o Theo em 4.3 Fo ease o no a ion, le :=n/α, and no e ha |N∗|≥ .
Since N∗is -cohesi e, by P oposi ion 3.4, some agen i1∈N∗ge s u ili y a leas  
om he alloca ion A.I |N∗ {i1}|≥ · , hen since N∗ {i1}is  -cohesi e,
P oposi ion 3.4 implies ha ano he agen i2= i1ge s u ili y a leas   om A.
Applying his a gumen epea edly, as long as he e a e a leas  · agen s le ,
P oposi ion 3.4 implies ha one o hem ge s u ili y a leas  .Le N
 consis
o he agen s wi h gua an eed u ili y   om his a gumen , and no e ha |N
 |=
|N∗|− · +1≥ − · +1.Le 
N:=N∗ N
 ;we ha e |
N|= · −1.
Deno e by N an a bi a y subse o N
 o size exac ly  − · +1.
Now, le us conside he agen s in 
N.Applying an a gumen simila o he one in he
p e ious pa ag aph bu using ( −1)-cohesi eness, we ind ha 
Ncon ains a leas
 · −( −1)· agen s wi h a u ili y o a leas  −1 each; le hese agen s
o m N −1.Con inuing induc i ely, we can pa i ion 
Nin o  pai wise disjoin se s
N −1,N −2,...,N1,N0such ha o each j∈{0,1,..., −1},e e y agen
in Njge s u ili y a leas j om he alloca ion A.
Fo each j∈{1,2,..., },i holds ha j−1
k=0Nk=j −1.Fu he mo e,
we ha e
j· ≥ j· · = ·(j +1)− ≥ ·j − = ·(j −1),
which implies ha
j−1
k=0Nk
 =j −1
 ≤j
.
Since  
k=0Nk= ,i ollows ha
 
k=jNk
 ≥ −j
= − 
+ − j
= − 
+
 −1

k=j
1
.(4)
Wi h his ela ionship in hand, we can bound he a e age sa is ac ion o N ∪
N=
 
k=0Nkas
1
 
k=0Nk
·
i∈ 
k=0Nk
ui(A)≥1
 ·⎛
⎝
 

k=0
|Nk|·k⎞
⎠
=
 

k=0
|Nk|
 ·k
=
 

d=1
 

k=d
|Nk|
 
123
660 X. Lu e al.
≥
 

d=1⎛
⎝ − 
+
 −1

k=d
1
⎞
⎠
= − 
· +
 

d=1
 −1

k=d
1
= − 
· +1
· ·( −1)
2
= 
·2 − −1
2
= ·1− +1
2 ,
whe e he i s inequali y holds because each agen in Nkge s u ili y a leas kand he
second inequali y ollows om (4).
Since e e y agen in N
  N ge s u ili y a leas  , he a e age sa is ac ion o
N
  N is a leas  ≥ ·1− +1
2 .As he a e age sa is ac ion o N∗is a
con ex combina ion o he co esponding quan i ies o N
  N and N ∪
N,i is
a leas  ·1− +1
2 ,as desi ed. 
We nex gi e a ma ching uppe bound.
Theo em 4.4 Fo any eal numbe s ≥1and ε>0, he e exis s an ins ance,a
-cohesi e g oup N∗,and an EJR-M alloca ion A such ha he a e age sa is ac ion
o N∗wi h espec o A is a mos  ·1− +1
2 +ε.
We do no p o e Theo em 4.4 di ec ly, as we will es ablish a s onge s a emen
la e in Theo em 4.7.
Nex , we show ha he p opo ionali y deg ee implied by EJR-1 is −2+1/
2=
( −1)2
2 ,which is sligh ly lowe han ha implied by EJR-M o e e y >1.Fo
he lowe bound, we use a simila idea as in Theo em 4.3, bu we need o be mo e
ca e ul abou agen s wi h low u ili y gua an ees. In pa icula , e en when he gua an ee
p o ided by he EJR-1 condi ion is nega i e, he ac ual u ili y is always nonnega i e,
so we need o “ ound up” he EJR-1 gua an ee app op ia ely.
Theo em 4.5 Gi en any ins ance and any eal numbe ≥1,le N∗⊆Nbea -
cohesi e g oup and A be an EJR-1alloca ion. The a e age sa is ac ion o N∗wi h
espec o A is g ea e han −2+1/
2.
To p o e his heo em, we will use he ollowing claim, which p o ides a lowe
bound o he a e age o a noninc easing and nonnega i e sequence wi h a pa icula
s uc u e.
Claim 1 Le >0 and ≥1 be eal numbe s. Conside any noninc easing and
nonnega i e sequence
−1,a1,a2,...,a − ,b1,b2,...,b −1,
123
App o al-based o ing wi h mixed goods 661
in which a1,a2,...,a −  o ms an a i hme ic subsequence wi h common di e -
ence −1/ .I −1−a1≤1/ , hen he a e age o he en i e sequence is a leas
−2+1/
2.
P oo We s a by showing ha he a e age o he subsequence −1,a1,a2,...,a − 
is a leas −1
2.The bound holds i ially i  − =0;we he e o e assume ha
 − ≥1.Le us con inually dec ease each o he numbe s a1,a2,...,a − 
by he same amoun un il (a leas ) one o he ollowing wo cases occu s:
•Case 1: The di e ence be ween −1 and a1becomes 1/ ,i.e., a1= −1−1/ .
No e ha a − is s ill nonnega i e in his case.
•Case 2:a − becomes 0.No e ha he di e ence be ween −1 and a1is s ill
a mos 1/ .
Clea ly, he a e age o he subsequence in ques ion −1,a1,a2,...,a − does
no inc ease du ing his p ocess. Thus, i su ices o show ha in each o he abo e wo
cases, his a e age is a leas −1
2a e he p ocess.
•In Case 1, he subsequence −1,a1,a2,...,a − is now an a i hme ic
sequence, so i s a e age is ( −1)+a − 
2≥ −1
2,whe e he inequali y ollows
om he ac ha a − ≥0 in his case.
•In Case 2, conside he a i hme ic sequence (dk) − 
k=0wi h d0= −1 and
d − =0.Le −βbe i s common di e ence, so βis nonnega i e. On he one
hand, we ha e
−1=d0=d − +β·( − )=β·( − ).
On he o he hand, we ha e
−1=( −1−a1)+a1
=( −1−a1)+( − −1)·1/ ≤( − )·1/ ,
whe e he inequali y holds because −1−a1≤1/ in Case 2. As a esul ,
we ha e β·( − )≤( − )·1/ , ha is, β≤1/ .Hence, each
e m o he sequence −1,a1,a2,...,a − is a leas as la ge as he co -
esponding e m o he sequence (dk) − 
k=0.We conclude ha he a e age o
−1,a1,a2,...,a − is a leas ha o (dk) − 
k=0,which is d0+d − 
2=
−1
2.
In bo h cases, we ha e p o en ha he a e age o he sequence −1,a1,a2,...,a − 
is a leas −1
2.
Nex , we show ha he a e age o he en i e sequence
−1,a1,a2,...,a − ,b1,b2,...,b −1
123
662 X. Lu e al.
is a leas −2+1/
2.This can be done by aking all bi’s o be 0 and applying he lowe
bound on he a e age o −1,a1,a2,...,a −  ha we p e iously compu ed:
1
1+( − )+( −1)· −1
2·(1+( − ))
=1+ − 
 · −1
2
=1+1− 
 · −1
2
≥1+1−( +1)
 · −1
2
=1−
 · −1
2
≥1−
· −1
2
=( −1)2
2
= −2+1/
2.
The claim is hus p o en. 
We a e now eady o es ablish Theo em 4.5.
P oo o Theo em 4.5 Fo no a ional con enience, le :=n/α. We ha e |N∗|≥ ,
whe e he inequali y holds because N∗is -cohesi e. EJR-1 implies ha some
agen i1∈N∗ge s u ili y g ea e han −1 om he alloca ion A.I |N∗ {i1}| ≥ ,
hen since he e s ill exis s a subse o he esou ce o size a leas commonly app o ed
by he agen s in N∗ {i1},EJR-1 implies ha ano he agen i2= i1ge s u ili y g ea e
han −1 om A.Applying his a gumen epea edly, as long as he e a e a leas ·
agen s le , EJR-1 implies ha one o hem ge s u ili y g ea e han −1.Le N −1
consis o he agen s wi h gua an eed u ili y g ea e han −1 om his a gumen . Le

N:=N∗ N −1and n:=|

N|,and no e ha n= −1.
Now, le us conside he agen s in 
N.Since |
N|=n≥n
· and si∈
NRi≥ >
n
, he agen s in 
N o m an n
-cohesi e g oup. By EJR-1, some agen in 
Nge s u ili y
g ea e han n
−1.Con inuing induc i ely, he gua an eed u ili y d ops a i hme ically
wi h a common di e ence o 1/ .No e also ha an agen ’s ac ual u ili y is always
nonnega i e.
To calcula e he a e age sa is ac ion o he -cohesi e g oup N∗,we i s ocus
on he agen s in 
Nalong wi h agen i1discussed ea lie in he p oo . The a e age
sa is ac ion o hese agen s is
1
1+n·⎛
⎝ui1(A)+
i∈
N
ui(A)⎞
⎠>1
1+n·⎛
⎝ −1+
i∈
N
ui(A)⎞
⎠
123

App o al-based o ing wi h mixed goods 663
≥1
1+n·⎛
⎝ −1+n

j= j
−1+
 −1

j=1
0⎞
⎠
≥ −2+1/
2.
The las inequali y is due o Claim 1: We ha e a noninc easing and nonnega i e
sequence wi h −1 as he i s elemen , ollowed by a dec easing a i hme ic sequence
wi h  −  e ms whose common di e ence is −1/ and whose i s e m,
 −1
−1,is a mos 1/ away om −1,and hen ollowed by  −1 ze os.
The a e age sa is ac ion o N −1 {i1},i his se is no emp y, is g ea e han −1.As
he a e age sa is ac ion o N∗is a con ex combina ion o he co esponding quan i ies
o N −1 {i1}and 
N∪{i1},i is g ea e han −2+1/
2,as desi ed. 
We now de i e a ma ching uppe bound.
Theo em 4.6 Fo any eal numbe s ≥1and ε>0, he e exis s an ins ance,a
-cohesi e g oup N∗,and an EJR-1alloca ion A such ha he a e age sa is ac ion o
N∗wi h espec o A is a mos −2+1/
2+ε.
P oo Conside a cake ins ance wi h a su icien ly la ge numbe o agen s n( o be
speci ied la e ). Le α= .Thus, we ha e |N|= ·n/ ≥ ·n/α. The cake is gi en
by he in e al [0,2 ],and he agen s’ p e e ences a e as ollows.
•Each agen i∈{1,2,...,n/α−1}app o es he in e al [0, ].
•Each agen i∈{n/α,n/α+1,...,n}app o es he in e al 0, +i−n/α
n/α +δ,
whe e δ∈(0,1)is su icien ly small ( o be speci ied la e ).
Since all nagen s app o e he in e al [0, ], hey o m a -cohesi e g oup N.
We claim ha alloca ion A=[ ,2 ],which has size =α, sa is ies EJR-1.
Conside a -cohesi e g oup o some alue o >0.I ∈(0,1), he equi emen o
EJR-1 is i ially ul illed. Since n= ·n/α, we may he e o e assume ha ∈[1, ].
Conside agen  ·n/α∈N,who app o es he in e al 0, + ·n/α−n/α
n/α +δ;
his agen ge s u ili y a leas  ·n/α−n/α
n/α +δ≥ ·n/α−n/α
n/α +δ> −1 om he
alloca ion A.Since e e y -cohesi e g oup con ains a leas  ·n/αagen s, i mus
con ain an agen who ge s u ili y g ea e han −1 om A.This means ha Asa is ies
EJR-1, as claimed.
The a e age sa is ac ion o he -cohesi e g oup Nwi h espec o he EJR-1 allo-
ca ion Ais
1
|N|·
i∈N
ui(A)=1
n·
n

i=n/αi−n/α
n/α +δ
=α
n2·
n

i=n/α
(i−n/α) +1
n·
n

i=n/α
δ
=α
n2·(n/α−n/α) +(n−n/α)
2·(n−n/α+1)
123
664 X. Lu e al.
+δ
n·(n−n/α+1)
≤α
n2·(n−n/α +1)2
2+δ
n·(n−n/α +1)
=α−2+1/α
2+δ·(α −1)
α+α
2n2+α−1+δ
n
= −2+1/
2+δ·( −1)
+
2n2+ −1+δ
n,
whe e he inequali y holds because n/α−n/α ≤1 and −n/α≤−n/α. Finally,
we choose a su icien ly la ge nand a su icien ly small δso ha δ·( −1)
+
2n2+ −1+δ
n≤
ε; his ensu es ha he a e age sa is ac ion o Nis a mos −2+1/
2+ε, as desi ed. 
4.2 P opo ionali y deg ee o speci ic ules
In his subsec ion, we in es iga e he p opo ionali y deg ee o he ules ha we s udied
in Sec . 3.
We begin wi h G eedyEJR-M. Since G eedyEJR-M sa is ies EJR-M, Theo em 4.3
immedia ely yields a lowe bound. We de i e a ma ching uppe bound, which implies
ha he p opo ionali y deg ee o G eedyEJR-M is  ·1− +1
2 .
Theo em 4.7 Fo any eal numbe s ≥1and ε>0, he e exis s an ins ance,a -
cohesi e g oup N∗,and an alloca ion A ou pu by G eedyEJR-M such ha he a e age
sa is ac ion o N∗wi h espec o A is a mos  ·1− +1
2 +ε.
We i s p o ide an in ui ion behind he p oo o Theo em 4.7. We cons uc an
indi isible-goods ins ance, make αan in ege , and choose n o be a mul iple o α.
Ou goal is o cons uc a a ge -cohesi e g oup o agen s N∗wi h as small u ili ies
as possible. Since G eedyEJR-M ou pu s an EJR-M alloca ion, he la ges numbe o
agen s in N∗ ha ecei e u ili y 0—deno e he se o hese agen s by N0—is n/α −1;
o he wise, hese agen s would o m a 1-cohesi e g oup and canno all ecei e u ili y 0.
Simila ly, among he agen s in N∗ N0, he la ges numbe o agen s ha ecei e
u ili y 1—deno e he se o hese agen s by N1—is n/α, as we do no wan N0∪N1
o o m a 2-cohesi e g oup. Con inuing induc i ely, we wan o pa i ion N∗in o
N0∪N1∪···∪ N ,wi h he agen s in Nk ecei ing u ili y exac ly k o each k.
We add dummy agen s and goods in o de o make su e ha , ins ead o all agen s in
N∗being sa is ied a once by he G eedyEJR-M execu ion, he agen s in N a e i s
sa is ied along wi h some dummy agen s ia some dummy goods, hen hose in N −1
a e sa is ied along wi h o he dummy agen s ia o he dummy goods, and so on. The
dummy agen s and goods need o be ca e ully cons uc ed o make his a gumen wo k.
P oo o Theo em 4.7 Le α= ·( +1)
2+1= 2+ +2
2,and no e ha αis an in ege .
We will cons uc an indi isible-goods ins ance wi h a su icien ly la ge numbe o
agen s n( o be speci ied la e ), whe e nis a mul iple o α ha is a leas 2α. Obse e
123
App o al-based o ing wi h mixed goods 665
ha
·n
α!=  · n
α+( − )·n
α!= · n
α+ ( − )·n
α!.
Since − <1,we can choose nla ge enough so ha ( − )·n
α≤n
α−1.
When his holds, we ha e
·n
α≤ ·n
α!≤ · n
α+n
α−1=( +1)·n
α−1.(5)
This inequali y will help ensu e ha we can cons uc a -cohesi e g oup ha is no
( +1)-cohesi e. No e ha in an indi isible-goods ins ance, a -cohesi e g oup mus
commonly app o e a leas  indi isible goods.
We now desc ibe ou ins ance. Le G={g1,g2,...,g }∪ 
k=1DG
kbe he
se o indi isible goods, whe e o each k∈{1,2,..., },DG
kcon ains exac ly k
indi isible goods. In pa icula , he se s
{g1,g2,...,g },DG
1,DG
2,...,DG
 
a e all disjoin . Ou speci ica ions o he agen s a e sligh ly di e en depending on
whe he ≥2o ∈[1,2);we dis inguish be ween he wo cases below.
Case 1: ≥2 Recalling ha n/α is an in ege , we pa i ion he se o all agen s N
in o he ollowing pai wise disjoin se s:
N0="1,2,..., n
α−1#,
N1="n
α,n
α+1,...,2·n
α−1#,
.
.
.
Nk="k·n
α,k·n
α+1,...,(k+1)·n
α−1#,
.
.
.
N −1="( −1)·n
α,( −1)·n
α+1,..., · n
α−1#,
N =" · n
α, · n
α+1,..., ·n
α!#,
D1,D2,...,D −1,D ,
whe e N∗:= 
k=0Nk=$1,2,..., ·n
α%is ou a ge -cohesi e g oup and
 
k=1Dkconsis s o “dummy agen s”. Mo e speci ically:
•D1con ains a single agen ;
•Fo each k∈{2,..., −1},Dkcon ains (k−1)·n
αagen s;
123
666 X. Lu e al.
•D con ains  · n
α− ·n
α− · n
α+1=2 · n
α− ·n
α−1 agen s.
Obse e ha N ∪D = · n
α.
No e ha D1and D a e di e en se s because ≥2.We e i y ha he o al numbe
o agen s is indeed n:
|N|=⎛
⎝
 
&
k=0
Nk⎞
⎠∪⎛
⎝
 
&
k=1
Dk⎞
⎠
=⎛
⎝
 −1
&
k=0
Nk⎞
⎠∪D1∪⎛
⎝
 −1
&
k=2
Dk⎞
⎠∪N ∪D 
= · n
α−1+1+
 −1

k=2
(k−1)·n
α+ · n
α
=2 · n
α+n
α·(2−1)+(( −1)−1)
2·(( −1)−2+1)
=n
α·2 +( −1)·( −2)
2
=n
α· 2+ +2
2
=n.
The agen s’ p e e ences a e as ollows.
•The agen s in N0app o e he goods in {g1,g2,...,g }.
•Fo each k∈{1,2,..., }, he agen s in Nkapp o e he goods in
{g1,g2,...,g }∪DG
k,and he agen s in Dkapp o e he goods in DG
k.
This comple es he desc ip ion o ou ins ance. Since |N∗|= ·n
α,inequali y (5)
implies ha N∗is no ( +1)-cohesi e. On he o he hand, since he agen s in N∗
commonly app o e he goods g1,g2,...,g ,N∗is -cohesi e. Also, no ice ha
∗= is he la ges in ege such ha a ∗-cohesi e g oup exis s in ou ins ance.
We now conside he execu ion o G eedyEJR-M on he abo e ins ance. Since ou
ins ance consis s exclusi ely o indi isible goods, only in ege s ∗a e ele an o
he EJR-M condi ion in each ound o G eedyEJR-M. We claim ha G eedyEJR-M
can e u n he alloca ion A= 
k=1DG
k,which has size  ·( +1)
2≤α. Gi en he
ins ance, a he beginning, ∗= is he la ges numbe such ha he EJR-M condi ion
is sa is ied: i is sa is ied wi h N ∪D ,DG
 ,because N ∪D = · n
α
and he agen s in N ∪D commonly app o e all goods in DG
 ,which has size
exac ly  .17 G eedyEJR-M emo es he agen s in N ∪D and adds he goods
in DG
  o he alloca ion A.Now, he e is no mo e  -cohesi e g oup, and ∗= −1
becomes he la ges numbe such ha he EJR-M condi ion is sa is ied: i is sa is ied
17 A his s age, he EJR-M condi ion wi h ∗= also holds wi h (N∗,{g1,g2,...,g }).
123
App o al-based o ing wi h mixed goods 673
Finally, assume ha is i a ional. Le > and ε<εbe a ional numbe s such
ha  = and +z(1−z)
+ε< +z(1−z)
+ε, whe e z= − ; he exis ence
o such a pai ( ,ε
)is gua an eed by he ac ha , as we inc ease sligh ly, he alue o
+z(1−z)
changes con inuously. F om ou p e ious a gumen , he e exis s an ins ance
in which no alloca ion p o ides an a e age sa is ac ion o a leas −1+z(1−z)
+ε
o all -cohesi e g oups. Suppose o con adic ion ha he e is an alloca ion ha
p o ides an a e age sa is ac ion o a leas −1+z(1−z)
+ε o all -cohesi e g oups
in his ins ance. Because any -cohesi e g oup is also -cohesi e, his alloca ion would
also p o ide an a e age sa is ac ion o a leas −1+z(1−z)
+ε> −1+z(1−z)
+ε
o all -cohesi e g oups, a con adic ion. 
We also show ha he bound p o ed in Theo em B.1 is—pe haps su p isingly—
igh .
Theo em B.2 Fo any eal numbe ≥1,le z = − deno e he ac ional pa o .
Gi en any ins ance, he e exis s an alloca ion ha p o ides an a e age sa is ac ion o
a leas −1+z(1−z)
o all -cohesi e g oups.
P oo Le I=N,R,(Ri)i∈N,αbe an ins ance, and le k= (so =k+z). Le
T={T1,T2,...,Tp}be he se o all -cohesi e g oups in ins ance I.By de ini ion,
o each i∈{1,2,...,p},i holds ha |Ti|≥ ·n/α and s(j∈TiRj)≥ .
We c ea e ano he ins ance 
I=N,
R,(
Ri)i∈N,αwi h he same se o agen s N
and a modi ied esou ce 
R=p
i=1
RTisuch ha
• o anypai o dis inc i,j∈{1,...,p},
RTi∩
RTj=∅;
• o each i∈{1,...,p},
RTiconsis s o k indi isible goods ha a e commonly
app o ed (only) by he agen s in Ti.
Pu di e en ly, he esou ce 
RTiin ins ance 
Ico esponds o he esou ce j∈TiRjin
ins ance I,bu has a weakly smalle size. The idea he e is ha we a e “wo sening” he
ins ance in e ms o he a e age sa is ac ion o all -cohesi e g oups. Mo e speci ically,
gi en an alloca ion 
R o ins ance 
I,we can selec an alloca ion R o ins ance I
as ollows: o each 
RTi,i ≤k(indi isible) goods om 
RTia e included in 
R,
hen we include a esou ce o size  om j∈TiRjin R.(E en i some esou ce ge s
included in Rmul iple imes du ing his p ocess, i is e ec i ely only included once.)
Clea ly, s(R)≤s(
R)≤α. Mo eo e , i can be seen ha o each i∈{1,...,p},
1
|Ti|·
j∈Ti
uj(R)≥1
|Ti|·
j∈Ti
uj(
R).
I is wo h no ing ha in ins ance 
I,each agen g oup Timay no longe be a -cohesi e
g oup, because hei se o commonly app o ed goods is now 
RTi,whose size is only
k= .Ne e heless, ou goal is o ind an alloca ion 
R o ins ance 
Isuch ha o
e e y i∈{1,...,p}, he a e age sa is ac ion o Tiwi h espec o 
Rin ins ance 
Iis
a leas −1+z(1−z)
,e en i Tiis no a -cohesi e g oup in ins ance 
I.As a esul ,
as we a gued abo e, he e exis s a co esponding alloca ion R o ins ance I ha has
he same o be e a e age sa is ac ion o all -cohesi e g oups in ins ance I.
123

674 X. Lu e al.
We apply he classic PAV ule o ind he alloca ion 
R o ins ance 
I(which
is an indi isible-goods ins ance). Tha is, we choose 
R ha maximizes H(
R)=
i∈NHui(
R),whe e Hx:=1+1
2+ ··· + 1
xis he x- h ha monic numbe . The
ollowing analysis is simila o ha o Theo em 3.18, bu mo e e ined. By adding an
indi isible good app o ed by no agen o he esou ce 
Ras well as 
Ri necessa y, we
may assume wi hou loss o gene ali y ha s(
R)=α.
To show ha 
Rsa is ies he a ge a e age sa is ac ion alue o each Ti∈T,we
assume o con adic ion ha he e exis s T∗∈Tsuch ha
1
|T∗|·
i∈T∗
ui(
R)< −1+z(1−z)
= −z−1+z( −z+1)
=k−1+(k+1)z
.(6)
Since (k+1)z
<k+z
=1,we ha e
k−1≤k−1+(k+1)z
<k,(7)
which means ha he e exis s a good g∗∈
RT∗ ha is no selec ed in 
R.Le 
R :=

R∪{g∗}; so |
R|=α+1.We ha e
H(
R)−H(
R)≥
i∈T∗Hui(
R)+1−Hui(
R)=
i∈T∗
1
ui(
R)+1.
In wha ollows, we p o ide a lowe bound on i∈T∗
1
ui(
R)+1.Fi s , o each i∈T∗,
le yi=ui(
R). We hus ha e i∈T∗
1
ui(
R)+1=i∈T∗
1
yi+1.I he e exis s a pai
i,j∈T∗wi h yi≥yj+2,le y
i=yi−1 and y
j=yj+1.I is easy o e i y ha
1
yi+1+1
yj+1>1
y
i+1+1
y
j+1.
By eplacing yi( esp., yj) wi h y
i( esp., y
j), we dec ease b∈T∗
1
yb+1.Repea his
p ocess un il, o e e y pai i,j∈T∗,i holds ha |yi−yj|≤1.We now ha e

i∈T∗
1
ui(
R)+1≥
i∈T∗
1
yi+1.
No e ha all yi’s a e in ege s and he ollowing equa ion s ill holds:

i∈T∗
ui(
R)=
i∈T∗
yi.(8)
123
App o al-based o ing wi h mixed goods 675
Toge he wi h (6) and (7), we ha e ha yi≤k−1 o somei∈T∗,and he e o e
yi≤k o all i∈T∗.
I i∈T∗yi≤|T∗|·(k−1), hen

i∈T∗
1
yi+1≥|T∗|2
i∈T∗(yi+1)
=|T∗|2
i∈T∗yi+|T∗|≥|T∗|2
|T∗|·(k−1)+|T∗|≥|T∗|
≥n
α,
whe e he i s ansi ion ollows om he inequali y o a i hme ic and ha monic means
and he second- o-las ansi ion om he ac ha ≥k.
Else, i∈T∗yi>|T∗|·(k−1). This means ha he e exis s i∈T∗such ha yi=k.
Le '
T∗:={i∈T∗|yi=k}; we ha e |'
T∗|>0.As a gued ea lie , o all i∈T∗ '
T∗,
i holds ha yi=k−1.Recall om (6) and (8) ha
|'
T∗|·k+(|T∗|−|
'
T∗|)·(k−1)=
i∈'
T∗
k+
i∈T∗ '
T∗
(k−1)
=
i∈T∗
yi
=
i∈T∗
ui(
R)<|T∗|·k−1+(k+1)z
,
which implies ha |'
T∗|<|T∗|·(k+1)z
.As a esul , we ha e

i∈T∗
1
yi+1=
i∈'
T∗
1
k+1+
i∈T∗ '
T∗
1
k=|'
T∗|
k+1+|T∗|−|
'
T∗|
k=(k+1)·|T∗|−|
'
T∗|
k(k+1)
>(k+1)·|T∗|−|T∗|·(k+1)z
k(k+1)
=|T∗|·1−z

k=|T∗|
≥n
α.
The e o e, in ei he case, adding g∗inc eases he PAV-sco e o 
Rby a leas n/α.
Finally, he es o he p oo p oceeds in he same way as ha o Theo em 3.18
when a guing abou he ma ginal con ibu ion o an indi isible good in R (which
co esponds o 
R in ou p oo he e). Fo each good g∈
R,deno e by Ng⊆N he
se o agen s who app o e i . Fo each g∈
R,we ha e
H(
R)−H(
R {g})=
i∈NgHui(
R)−Hui(
R)−1=
i∈Ng
1
ui(
R).
123
676 X. Lu e al.
Le ing N+consis o he agen s i∈Nwi h ui(
R)>0,we ge

g∈
R
(H(
R)−H(
R {g}))
=
g∈
R 
i∈Ng
1
ui(
R)=
i∈N+
g∈
R∩
Ri
1
ui(
R)=|N+|≤n.
I he e is a good g∈
R such ha H(
R)−H(
R {g})<n/α (clea ly, g= g∗), we
can eplace gwi h g∗in 
Rand ob ain a highe PAV-sco e, con adic ing he de ini ion
o 
R.Hence, we may assume ha H(
R)−H(
R {g})≥n/α o e e y g∈
R.I
ollows ha
n≥
g∈
R
(H(
R)−H(
R {g})) ≥|

R|· n
α.
The e o e, we ha e ha |
R|≤α, con adic ing he ac ha |
R|=α+1.This
comple es he p oo . 
The p oo o Theo em B.2, howe e , does no show ha he e exis s an alloca ion
wi h he claimed a e age sa is ac ion gua an ee o all simul aneously, as he c e-
a ion o he new ins ance 
Idepends on .While i is concei able ha Gene alized
PAV achie es his simul aneous gua an ee, p o ing (o disp o ing) his seems o be a
challenging ask.
Acknowledgemen s This wo k was suppo ed by ARC Lau ea e P ojec FL200100204 on “T us wo hy
AI”, by he Singapo e Minis y o Educa ion unde g an numbe MOE-T2EP20221-0001, by he Deu sche
Fo schungsgemeinscha unde g an BR 4744/2-1 and he G aduie enkolleg “Face s o Complexi y” (GRK
2434), and by an NUS S a -up G an . We would like o hank he anonymous e iewe s o hei aluable
commen s.
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included
in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I
ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed
by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he
copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
Ab amowi z M, S egun IA (eds) (1972) Handbook o ma hema ical unc ions wi h o mulas, g aphs, and
ma hema ical ables, 10 h edn. Na ional Bu eau o S anda ds, Washing on D.C.
Aziz H, B ill M, Coni ze V, Elkind E, F eeman R, Walsh T (2017) Jus i ied ep esen a ion in app o al-based
commi ee o ing. Soc Choice Wel 48(2):461–485
Aziz H, Elkind E, Huang S, Lackne M, Sánchez-Fe nández L, Skow on P (2018) On he complexi y o
ex ended and p opo ional jus i ied ep esen a ion. In: P oceedings o he 32nd AAAI con e ence on
a i icial in elligence (AAAI), pp 902–909
123
App o al-based o ing wi h mixed goods 677
Aziz H, Bogomolnaia A, Moulin H (2020) Fai mixing: he case o dicho omous p e e ences. ACM T ans
Econ Compu 8(4):18:1-18:27
Bei X, Li Z, Liu J, Liu S, Lu X (2021a) Fai di ision o mixed di isible and indi isible goods. A i In ell
293:103436
Bei X, Liu S, Lu X, Wang H (2021b) Maximin ai ness wi h mixed di isible and indi isible goods. Au on
Agen s Mul i-Agen Sys 35(2):34:1–34:21
Bei X, Lu X, Suksompong W (2024) T u h ul cake sha ing. Soc Choice Wel ( o hcoming)
Bhaska U, S icha an AR, Vaish R (2021) On app oxima e en y- eeness o indi isible cho es and mixed
esou ces. In: P oceedings o he 24 h in e na ional con e ence on app oxima ion algo i hms o com-
bina o ial op imiza ion p oblems (APPROX), pp 1:1–1:23
B ede eck R, Faliszewski P, Kaczma czyk A, Niede meie R (2019) An expe imen al iew on commi ees
p o iding jus i ied ep esen a ion. In: P oceedings o he 28 h in e na ional join con e ence on a i icial
in elligence (IJCAI), pp 109–115
Elkind E, Faliszewski P, Iga ashi A, Manu angsi P, Schmid -K aepelin U, Suksompong W (2022) The p ice
o jus i ied ep esen a ion. In: P oceedings o he 36 h AAAI con e ence on a i icial in elligence
(AAAI), pp 4983–4990
Faliszewski P, Skow on P, Slinko A, Talmon N (2017) Mul iwinne o ing: a new challenge o social choice
heo y. In: End iss U (ed) T ends in compu a ional social choice, chap e 2. AI Access, pp 27–47
Kawase Y, Nishimu a K, Sumi a H (2023) Fai alloca ion wi h bina y alua ions o mixed di isible and
indi isible goods. a Xi p ep in . a Xi :2306.05986
Kilgou DM (2010) App o al ballo ing o mul i-winne elec ions. In: Laslie J-F, San e MR (eds) Hand-
book on app o al o ing. Sp inge , Be lin, pp 105–124
Lackne M, Skow on P (2023) Mul i-winne o ing wi h app o al p e e ences. Sp inge , Be lin
Nishimu a K, Sumi a H (2023) En y- eeness and maximum Nash wel a e o mixed di isible and indi isible
goods. a Xi p ep in . a Xi :2302.13342
Pe e s D, Skow on P (2020) P opo ionali y and he limi s o wel a ism. In: P oceedings o he 21s
ACM con e ence on economics and compu a ion (EC), pp 793–794. Ex ended e sion a ailable a
a Xi :1911.11747 2
Pe e s D, Pie czy´nski G, Skow on P (2021) P opo ional pa icipa o y budge ing wi h addi i e u ili ies. In:
P oceedings o he 35 h con e ence on neu al in o ma ion p ocessing sys ems (Neu IPS), pp 12726–
12737
P ocaccia AD (2016) Cake cu ing algo i hms. In: B and F, Coni ze V, End iss U, Lang J, P ocaccia AD
(eds) Handbook o compu a ional social choice, chap e 13. Camb idge Uni e si y P ess, Camb idge,
pp 311–329
Robe son J, Webb W (1998) Cake-cu ing algo i hms: be ai i you can. Pe e s/CRC P ess, Na ick
Sánchez-Fe nández L, Elkind E, Lackne M, Fe nández N, Fis eus JA, Basan a-Val P, Skow on P (2017)
P opo ional jus i ied ep esen a ion. In: P oceedings o he 31s AAAI con e ence on a i icial in el-
ligence (AAAI), pp 670–676
Skow on P (2021) P opo ionali y deg ee o mul iwinne ules. In: P oceedings o he 22nd ACM con e ence
on economics and compu a ion (EC), pp 820–840
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps
and ins i u ional a ilia ions.
123