En opy 2014,16, 1586-1631; doi:10.3390/e16031586
OPEN ACCESS
en opy
ISSN 1099-4300
www.mdpi.com/jou nal/en opy
A icle
Op imal Fo ge y and Supp ession o Ra ings o
P i acy Enhancemen in Recommenda ion Sys ems ∗
Ja ie Pa a-A nau *, Da id Rebollo-Monede o and Jo di Fo n´
e
Depa men o Telema ics Enginee ing, Uni e si a Poli `
ecnica de Ca alunya (UPC), C. Jo di
Gi ona 1-3, Ba celona 08034, Spain; E-Mails: da[email p o ec ed] (D.R.-M.);
[email p o ec ed] (J.F.)
*Au ho o whom co espondence should be add essed; E-Mail: ja ie [email p o ec ed];
Tel.: +34-93-401-7041.
Recei ed: 9 Janua y 2014; in e ised o m: 7 Feb ua y 2014 / Accep ed: 12 Ma ch 2014 /
Published: 21 Ma ch 2014
Abs ac : Recommenda ion sys ems a e in o ma ion- il e ing sys ems ha ailo
in o ma ion o use s on he basis o knowledge abou hei p e e ences. The abili y o hese
sys ems o p o ile use s is wha enables such in elligen unc ionali y, bu a he same ime,
i is he sou ce o se ious p i acy conce ns. In his pape we in es iga e a p i acy-enhancing
echnology ha aims a hinde ing an a acke in i s e o s o accu a ely p o ile use s based
on he i ems hey a e. Ou app oach capi alizes on he combina ion o wo pe u ba i e
mechanisms— he o ge y and he supp ession o a ings. While his echnique enhances use
p i acy o a ce ain ex en , i ine i ably comes a he cos o a loss in da a u ili y, namely a
deg ada ion o he ecommenda ion’s accu acy. In sho , i poses a ade-o be ween p i acy
and u ili y. The heo e ical analysis o such ade-o is he objec o his wo k. We measu e
p i acy as he Kullback-Leible di e gence be ween he use ’s and he popula ion’s i em
dis ibu ions, and quan i y u ili y as he p opo ion o a ings use s consen o o ge and
elimina e. Equipped wi h hese quan i a i e measu es, we ind a closed- o m solu ion o
he p oblem o op imal o ge y and supp ession o a ings, an op imiza ion p oblem ha
includes, as a pa icula case, he maximiza ion o he en opy o he pe u bed p o ile. We
cha ac e ize he op imal ade-o su ace among p i acy, o ge y a e and supp ession a e,
∗Some pa s o his pape (a educed e sion o Sec ions 1and 2) we e p esen ed a he In e na ional Wo kshop on Da a
P i acy Managemen , Leu en, Belgium, Sep embe 2011 [1]. The o mula ion o he ade-o be ween p i acy and u ili y
(Sec ion 3), he cu en heo e ical analysis (Sec ion 4), he expe imen al wo k (Sec ion 5), he conclusions (Sec ion 6) and
he p oo s gi en in he Appendices a e all new wo k.
En opy 2014,16 1587
and expe imen ally e alua e how ou app oach could con ibu e o p i acy p o ec ion in a
eal-wo ld ecommenda ion sys em.
Keywo ds: in o ma ion p i acy; Kullback-Leible di e gence; Shannon’s en opy; use
p o iling; p i acy-enhancing echnologies; da a pe u ba ion; ecommenda ion sys ems
1. In oduc ion
F om he ad en o he In e ne and he Wo ld Wide Web, he amoun o in o ma ion a ailable o
use s has g own exponen ially. As a esul , he abili y o ind in o ma ion ele an o hei in e es s has
become a cen al issue in ecen yea s. In his con ex o in o ma ion o e load, ecommenda ion sys ems
a ise o p o ide in o ma ion ailo ed o use s on he basis o knowledge abou hei p e e ences [2].
In essence, a ecommenda ion sys em may be ega ded as a ype o in o ma ion- il e ing sys em ha
sugges s in o ma ion i ems use s may be in e es ed in. Examples o such sys ems include ecommending
music a Las . m and Pando a Radio, mo ies by Mo ieLens and Ne lix, ideos a YouTube, news a Digg
and Google News, and books and o he p oduc s a Amazon.
Mos o hese sys ems capi alize on he c ea ion o p o iles ha ep esen in e es s and p e e ences o
use s. Such p o iles a e he esul o he collec ion and analysis o he da a ha use s communica e o
hose sys ems. A dis inc ion is equen ly made be ween explici and implici o ms o da a collec ion.
The mos popula o m o explici da a collec ion is ha use s communica e hei p e e ences by a ing
i ems. This is he case o many o he applica ions men ioned abo e, whe e use s assign a ings o songs,
mo ies o news hey ha e al eady lis ened, wa ched o ead. O he s a egies o cap u e use s’ in e es s
include asking hem o so a numbe o i ems by o de o p edilec ion, o sugges ing ha hey ma k
he i ems hey like. On he o he hand, ecommenda ion sys ems may collec da a om use s wi hou
equi ing hem o explici ly con ey hei p e e ences [3]. These p ac ices comp ise obse ing he i ems
clicked by use s in an online s o e, analyzing he ime i akes use s o examine an i em, o simply
keeping a eco d o he pu chased i ems.
The p olonged collec ion o hese pe sonal da a allows he sys em o ex ac an accu a e snapsho o
use in e es s, i.e., hei p o iles. Wi h his in aluable sou ce o in o ma ion, he ecommenda ion sys em
applies some echnique [4] o gene a e a p edic ion o use s’ in e es s o hose i ems hey ha e no
ye conside ed. Fo example, Mo ielens and Digg use collabo a i e- il e ing echniques [5] o p edic
he a ing ha a use would gi e o a mo ie and o c ea e a pe sonalized lis o ecommended news,
espec i ely. In a nu shell, he abili y o p o iling use s based on such pe sonal in o ma ion is p ecisely
wha enables he in elligen unc ionali y o hose sys ems.
Despi e he many ad an ages ecommenda ion sys ems a e b inging o use s, he in o ma ion
collec ed, p ocessed and s o ed by hese sys ems p omp s se ious p i acy conce ns. One o he main
p i acy isks pe cei ed by use s is ha o a compu e “ igu ing hings ou ” abou hem [6]. Many use s
a e wo ied abou he idea ha hei p o iles may e eal sensi i e in o ma ion such as heal h- ela ed
issues, poli ical p e e ences, sala y o eligion. Such p i acy isk is exace ba ed especially when hese
En opy 2014,16 1588
p o iles a e combined ac oss se e al in o ma ion se ices o en iched wi h da a om social ne wo ks.
An illus a i e example is [7], which demons a es ha i is possible o un eil sensi i e in o ma ion
abou a pe son om hei mo ie a ing his o y by c oss- e e encing da a om o he sou ces. The au ho s
analyzed he Ne lix P ize da a se [8], which con ained anonymous mo ie a ings o a ound hal a million
use s o Ne lix, and we e able o unco e he iden i y, poli ical leaning and e en sexual o ien a ion o
some o hose use s, by simply co ela ing hei a ings wi h e iews hey pos ed on he popula mo ie
Web si e IMDb. Apa om he isk o c oss- e e encing, use s a e also conce ned ha he sys em’s
p edic ions may be o ally e oneous and be la e used o de ame hem. This la e si ua ion is examined
in [9], whe e he accu acy o he p edic ions p o ided by TiVo digi al ideo eco de and Amazon is
ques ioned. Las ly, o he p i acy isks emb ace unsolici ed ma ke ing, in o ma ion leaked o o he use s
o he same compu e , cou subpoenas, and go e nmen su eillance [6].
Some o he p i acy isks desc ibed abo e a ise om a lack o con idence in ecommenda ion sys ems.
Knowing how use s’ da a a e ea ed and p o ec ed would ce ainly help engende us . Howe e , e en
in hose cases whe e use s could comple ely us a ecommenda ion sys em, such sys em could also
be subjec o secu i y b eaches esul ing in he o disclosu e o sensi i e in o ma ion. Some examples
include Sony’s secu i y b each [10] and E e no e’s [11]. So whe he p i acy is p ese ed o no depends
no only on he us wo hiness o he da a con olle bu also on i s capaci y o e ec i ely manage he
en us ed da a.
Sys ems like Amazon o Delicious p o ec use s’ da a du ing ansmission by using secu e socke s
laye so wa e, which in essence enc yp s he in o ma ion use s submi . Howe e , beyond his, mos
ecommenda ion sys ems do no speci y which secu i y measu es a e adop ed once hose da a ha e been
collec ed. Enc yp ing hose da a and using numbe s ins ead o names migh be a common s a egy o gi e
hei use s anonymi y. Howe e , his s a egy may no always be e ec i e. AOL use No. 4417749 ound
his ou he ha d way in 2006, when AOL eleased a ex ile in ended o esea ch pu poses con aining
wen y million sea ch keywo ds including he s. Repo e s we e able o na ow down he 62-yea -old
widow in Lilbu n, Ga., by examining he con en o he sea ch que ies [12].
On he o he hand, sys ems such as Las . m and Mo ielens claim o use i ewalls and o s o e use s’
da a on e minals which equi e passwo d access. Howe e , as hese sys ems know such le el o
p o ec ion may be insu icien , hey explici ly claim ha hose measu es could no s op an a acke
om “ge ing a ound he p i acy o secu i y se ings on he Web si e h ough un o eseen and/o illegal
ac i i y” [13]. In he unlikely e en o an absolu ely secu e ecommenda ion sys em, we mus also
bea in mind ha he sys em could be legally en o ced o e eal he in o ma ion hey ha e access o.
In 2008, o example, as pa o a copy igh in ingemen lawsui agains YouTube, a US judge o de ed
he popula online ideo-sha ing se ice o hand o e a da abase linking use s wi h e e y ideo clip hey
had wa ched [14].
As a esul o all hese p i acy and secu i y conce ns, i is he e o e no su p ising ha some use s a e
e icen o e eal hei in e es s. In ac , [15] epo s ha he 24% o In e ne use s su eyed p o ided
alse in o ma ion in o de o a oid gi ing p i a e in o ma ion o a Web si e. Al e na i ely, ano he
s udy [16] inds ha 95% o he esponden s e used, a some poin , o p o ide pe sonal in o ma ion
when eques ed by a Web si e. In closing, hese s udies seem o indica e ha submi ing alse in o ma ion
and e using o gi e p i a e in o ma ion a e s a egies accep ed by use s conce ned wi h hei p i acy.
En opy 2014,16 1589
1.1. Con ibu ion and Plan o his Pape
In his pape , we app oach he p oblem o p o ec ing use p i acy in hose ecommenda ion sys ems
ha p o ile use s on he basis o he i ems hey a e. Ou se o po en ial p i acy a acke s comp ises
any en i y who may asce ain he in e es s o use s om hei a ings. Ob iously, his se includes he
ecommende i sel , bu also he ne wo k ope a o and any passi e ea esd oppe .
Gi en he willingness o use s o p o ide ake in o ma ion and elude disclosing p i a e da a, we
in es iga e a p i acy-enhancing echnology (PET) ha combines hese wo o ms o da a pe u ba ion,
namely, he o ge y and he supp ession o a ings. Conco dan ly, in ou scena io use s a e hose i ems
hey ha e an opinion on. Howe e , in o de o a oid being accu a ely p o iled by an a acke , use s
may wish o e ain om a ing some o hose i ems and/o a e i ems ha do no e lec hei ac ual
p e e ences. Ou app oach hus p o ec s use p i acy o a ce ain deg ee, wi hou ha ing o us he
ecommenda ion sys em o he ne wo k ope a o , bu a he cos o a loss in u ili y, a deg ada ion o he
quali y o he ecommenda ion. In o he wo ds, ou PET poses a ade-o be ween p i acy and u ili y.
The heo e ical analysis o he ade-o be ween hese wo con as ing aspec s is he objec o his
wo k. We ackle he issue in a sys ema ic ashion, d awing upon he me hodology o mul iobjec i e
op imiza ion. Be o e p oceeding, hough, we adop a quan i iable measu e o use p i acy— he
Kullback-Leible (KL) di e gence o ela i e en opy be ween he p obabili y dis ibu ion o he
use ’s i ems and he popula ion’s dis ibu ion, a c i e ion ha we jus i ied and in e p e ed in p e ious
wo k [17,18] by le e aging on he a ionale behind en opy-maximiza ion me hods. Equipped wi h
a measu e o bo h p i acy and u ili y, we o mula e an op imiza ion p oblem modeling he ade-o
be ween p i acy on he one hand, and on he o he o ge y a e and supp ession a e as u ili y me ics.
The p oposed o mula ion con empla es, as a special case, he maximiza ion o he en opy o he
use ’s pe u bed p o ile. Ou heo e ical analysis inds a closed- o m solu ion o he p oblem o op imal
o ge y and supp ession o a ings, and cha ac e izes he op imal ade-o be ween he aspec s o p i acy
and u ili y.
In addi ion, we p o ide an empi ical e alua ion o ou da a-pe u ba i e app oach. Speci ically, we
apply he o ge y and he supp ession o a ings in he popula mo ie ecommenda ion sys em Mo ielens,
and show how hese wo s a egies may p ese e he p i acy o i s use s.
Sec ion 2 e iews se e al da a-pe u ba i e app oaches aimed a enhancing use p i acy in he
con ex o ecommende sys ems. Sec ion 3in oduces ou p i acy-enhancing echnology, p oposes
a quan i a i e measu e o he p i acy o use p o iles, and o mula es he ade-o be ween p i acy
and u ili y. Sec ion 4p esen s a heo e ical analysis o he op imiza ion p oblem cha ac e izing he
p i acy- o ge y-supp ession ade-o . In his same sec ion we also p o ide a nume ical example ha
illus a es ou o mula ion and heo e ical esul s. Sec ion 5e alua es ou p i acy-p o ec ing mechanism
in a eal ecommenda ion sys em. Conclusions a e d awn in Sec ion 6. Finally, Appendices A–Dp o ide
he p oo s o he esul s included in Sec ion 4.
En opy 2014,16 1590
2. S a e o he A
Nume ous app oaches ha e been p oposed o p o ec use p i acy in he con ex o ecommenda ion
sys ems. These app oaches undamen ally sugges ei he pe u bing he in o ma ion p o ided by use s
o using c yp og aphic echniques.
In he case o pe u ba i e me hods o ecommenda ion sys ems, [19] p oposes ha use s add andom
alues o hei a ings and hen submi hese pe u bed a ings o he ecommende . A e ecei ing hese
a ings, he sys em execu es an algo i hm and sends he use s some in o ma ion ha allows hem o
compu e he p edic ion. When he numbe o pa icipa ing use s is su icien ly la ge, he au ho s ind
ha use p i acy is p o ec ed o a ce ain ex en and he sys em eaches a decen le el o accu acy.
Howe e , e en hough a use disguises all hei a ings, i is e iden ha he i ems hemsel es may
unco e sensi i e in o ma ion. Simply pu , he me e ac o showing in e es in a ce ain i em may be
mo e e ealing han he a ing assigned o ha i em. Fo ins ance, a use a ing a book called “How o
O e come Dep ession” indica es a clea in e es in dep ession, ega dless o he sco e assigned o his
book. Apa om his c i ique, o he wo ks [20,21] s ess ha he use o andomized da a dis o ion
echniques migh no be able o p ese e p i acy.
The au ho s o [19] p opose in [22] he same da a-pe u ba i e echnique bu applied o
collabo a i e- il e ing algo i hms based on singula - alue decomposi ion. An impo an di e ence
be ween bo h wo ks is ha he null en ies, i.e., hose i ems he use has no a ed, a e now eplaced
wi h he mean alue o hei a ings. In addi ion, he au ho s measu e he le el o p i acy achie ed by
using he me ic p oposed in [23], which is essen ially equi alen o di e en ial en opy. Expe imen al
esul s in Mo ielens and Jes e show he ade-o cu e be ween accu acy in ecommenda ions and
p i acy. In pa icula , hey assess accu acy as he mean absolu e e o be ween he p edic ed alues om
he o iginal a ings and he p edic ions ob ained om he pe u bed a ings.
Al hough his la e app oach p e en s he ecommenda ion sys em om lea ning abou which i ems
a use has a ed and which no , i s ill su e s om a a ie y o d awbacks ha limi i s adop ion. One
o hese limi a ions is ha bo h [19,22] equi e he se e o coope a e and pa icipa e in he execu ion
o a p o ocol. Bu i is he use who is in e es ed in hei own p i acy. The mo i a ion o he sys em
may be dubious, especially because p i acy p o ec ion comes a he cos o a deg ada ion o he quali y
o i s ecommenda ion algo i hm. Besides, i is he ecommenda ion sys em who decides how use s will
pe u b hei a ings. In pa icula , he sys em i s chooses whe he he andom alues o be added o
he use ’s a ings will be dis ibu ed acco ding o ei he a uni o m dis ibu ion o a Gaussian dis ibu ion;
and hen, he pa ame e s o he dis ibu ion chosen a e communica ed o all use s. Simply pu , use s do
no decide o which ex en hei a ings will be al e ed, and canno speci y he le el o p i acy hey wish
o achie e wi h such pe u ba ion. All his depends on he ecommenda ion sys em.
As we shall see in he coming sec ions, ou p i acy-enhancing mechanism di e s signi ican ly om
hese wo a ing-pe u ba i e schemes. Speci ically, he p oposed PET does no equi e in as uc u e, i
allows each use o con igu e he poin o ope a ion o he mechanism wi hin he op imal p i acy-u ili y
ade-o su ace, in he sense o maximizing p i acy o a desi ed u ili y, o ice e sa; i con empla es
no only he submission o alse a ings, bu also he possibili y o elimina ing genuine da a; and las
En opy 2014,16 1591
bu no leas , a om being mu ually exclusi e, ou PET may be combined syne gically wi h o he
app oaches based on use collabo a ion [24–26], anonymize s o pseudonymize s.
A his poin , we would like o ema k ha he use o pe u ba i e echniques is by no means new in
o he scena ios such as p i a e in o ma ion e ie al and he seman ic Web. In he o me scena io, use s
send gene al-pu pose que ies o an in o ma ion se ice p o ide . A pe u ba i e app oach o p o ec
use p o iles in his con ex consis s in combining genuine wi h alse que ies. P ecisely, [27] p oposes
anon andomized me hod o que y o ge y and in es iga es he ade-o be ween p i acy and he
addi ional a ic o e head. In he seman ic Web scena io, use s anno a e esou ces wi h he pu pose
o classi ying hem. In his applica ion domain, he pe u ba ion o use p o iles o p i acy p ese a ion
may be ca ied ou by d opping ce ain anno a ions o ags. An example o his kind o pe u ba ion may
be ound in [28–30], whe e he au ho s p opose he elimina ion o ags as a p i acy-enhancing s a egy.
Rega ding he use o c yp og aphic echniques, [31,32] p opose a me hod ha enables a communi y
o use s o calcula e a public agg ega e o hei p o iles wi hou e ealing hem on an indi idual basis.
In pa icula , he au ho s use a homomo phic enc yp ion scheme and a pee - o-pee communica ion
p o ocol o he ecommende o pe o m his calcula ion. Once he agg ega ed p o ile is compu ed, he
sys em sends i o use s, who inally use local compu a ion o ob ain pe sonalized ecommenda ions.
This p oposal p e en s he sys em o any ex e nal a acke om asce aining he indi idual use p o iles.
Howe e , i s main handicap is assuming ha an accep able numbe o use s is online and willing o
pa icipa e in he p o ocol. In line wi h his, [33] uses a a ian o Paillie s’ homomo phic c yp osys em
which imp o es he e iciency in he communica ion p o ocol. Ano he solu ion [34] p esen s an
algo i hm aimed a p o iding mo e e iciency by using he scala p oduc p o ocol.
3. P i acy P o ec ion ia Fo ge y and Supp ession o Ra ings
In his sec ion, i s we p esen he o ge y and he supp ession o a ings as a p i acy-enhancing
echnology. The desc ip ion o ou app oach is p e aced by a b ie in oduc ion o he concep s o so
p i acy and ha d p i acy. Secondly, we p opose a model o use p o ile and se o h ou assump ions
abou he ad e sa y capabili ies. Finally, we p o ide a quan i a i e measu e o bo h p i acy and u ili y,
and p esen a o mula ion o he ade-o be ween hese wo con as ing aspec s.
3.1. So P i acy s. Ha d P i acy
The p i acy esea ch li e a u e [35] ecognizes he dis inc ion be ween he concep s o so p i acy
and ha d p i acy. A p i acy-enhancing mechanism p o iding so p i acy assumes ha use s
en us hei p i a e da a o an en i y, which is he ea e esponsible o he p o ec ion o hei
da a. In he li e a u e, nume ous a emp s o p o ec p i acy ha e ollowed he adi ional me hod o
anonymous communica ions [36–45], which is undamen ally based on he supposi ions o so p i acy.
En opy 2014,16 1592
Un o una ely, anonymous-communica ion sys ems a e no comple ely e ec i e [46–49], hey no mally
come a he cos o in as uc u e, and assume ha use s a e willing o us o he pa ies (a).
Ou p i acy-p o ec ing echnique, pe con a, le e ages on he p inciple o ha d p i acy, which
assumes ha use s mis us communica ing en i ies and he e o e s i e o e eal as li le p i a e
in o ma ion as possible. In he mo i a ing scena io o his wo k, ha d p i acy means ha use s need
no us an ex e nal en i y such as he ecommende o he ne wo k ope a o . Consequen ly, because
use s jus us hemsel es, i is hei own esponsibili y o p o ec hei p i acy. In his s a e o a ai s,
he o ge y and he supp ession o a ings appea as a echnique ha may hinde p i acy a acke s in
hei e o s o accu a ely p o ile use s on he basis o he i ems hey a e. Speci ically, when use s a e
adhe ed o his echnique, hey ha e he possibili y o submi a ings o i ems ha do no e lec hei
genuine p e e ences, and/o e ain om a ing some i ems o hei in e es — his is wha we e e o as
he o ge y and he supp ession o a ings, espec i ely.
3.2. Use P o ile and Ad e sa y Model
In he scena io o ecommenda ion sys ems, use s a e i ems o a e y di e en na u e, e.g., music,
pic u es, ideos o news, acco ding o hei pe sonal p e e ences. The in o ma ion con eyed allows
hose sys ems o ex ac a p o ile o in e es s o use p o ile, which u ns o be essen ial in he p o ision
o pe sonalized ecommenda ions.
We men ioned in Sec ion 1 ha Mo ielens ep esen s use p o iles by using some kind o his og am.
O he sys ems such as Jinni and Las . m show his in o ma ion by means o a ag cloud, which in essence
may be ega ded as ano he kind o his og am. In his same spi i , ecen p i acy-p o ec ing app oaches
in he scena io o ecommenda ion sys ems also p opose using his og ams o absolu e equencies o
modeling use p o iles [51,52].
Acco ding o hese examples and inspi ed by o he wo ks in he ield [1,28–30,53,54], we model
he i ems a ed by use s as andom a iables ( . .’s) aking on alues in a common ini e alphabe o
ca ego ies, namely he se {1, . . . , n} o some in ege n⩾2. Conco dan ly, we model he p o ile o a
use as a p obabili y mass unc ion (PMF) q= (q1, . . . , qn), ha is, a his og am o ela i e equencies
o i ems wi hin a p ede ined se o ca ego ies o in e es .
Al hough o simplici y ou use -p o ile model cap u es only he i ems a ed by use s, we would
like o ema k ha his same model could also include in o ma ion o implici na u e. In o he wo ds,
ou use -p o ile model could e y well be applied o hose ecommenda ion sys ems which collec no
only he a ings explici ly con eyed by use s, bu also he Web pages hey explo e, he ime i akes
hem o examine hose pages o he i ems pu chased. Examples o such sys ems include Amazon and
Google News.
We would also like o emphasize ha , unde ou use -p o ile model based on explici a ings, p o iles
do no cap u e he pa icula sco es gi en o i ems, bu wha we conside o be mo e sensi i e: he
ca ego ies hese i ems belong o. This is exac ly he case o Mo ielens and nume ous con en -based
(a) A ecen su ey [50] epo s ha 69% o he esponden s jus us hemsel es when i comes o p o ec ing hei own
pe sonal in o ma ion online.
En opy 2014,16 1593
ecommenda ion sys ems. Figu e 1p o ides an example ha illus a es how use p o iles a e cons uc ed
in Mo ielens. In his pa icula example, a use assigns wo s a s o a mo ie, meaning ha hey conside
i o be “ ai ly bad”. Howe e , he ecommende upda es hei p o ile based only on he ca ego ies his
mo ie belongs o.
Acco ding o his model, a p i acy a acke supposedly obse es a pe u bed e sion o his p o ile,
esul ing om he o ge y and he supp ession o ce ain a ings, and is unawa e o igno es he ac ha
he obse ed use p o ile, also in he o m o a his og am, does no e lec he ac ual p o ile o in e es s
o he use in ques ion. In p inciple, ou passi e a acke could be he ecommende i sel o he ne wo k
ope a o . Howe e , he se o po en ial a acke s is no es ic ed me ely o hese wo en i ies. Since
a ings a e o en publicly a ailable o o he use s o he ecommenda ion sys em, any o he a acke able
o c awl h ough his in o ma ion is aken in o conside a ion in ou ad e sa y model.
When use s adhe e o he o ge y and he supp ession o a ings, hey speci y a o ge y a e ρ∈[0,∞)
and a supp ession a e σ∈[0,1). The o me is he a io o o ged a ings o o al genuine a ings ha
a use consen s o submi . The la e a io is he ac ion o genuine a ings ha he use ag ees o
elimina e (b). No e ha , in ou app oach, he numbe o alse a ings submi ed by he use can exceed
he numbe o genuine a ings, ha is, ρcan be g ea e han 1. Ne e heless, he numbe o supp essed
a ings is always lowe han he numbe o genuine a ings.
Figu e 1. The p o ile o a use is modeled in Mo ielens as a his og am o absolu e
equencies o a ings wi hin a se o mo ie gen es (bo om). Based on his p o ile, he
ecommende p edic s he a ing ha he use would p obably gi e o a mo ie ( op). A e
ha ing wa ched he mo ie, he use a es i and hei p o ile is upda ed.
P edic ion
o Ra ing
You
Ra ing
Mo ie
In o ma ion
No seen 2001: A Space Odyssey (1968)
Ad en u e, Sci-Fi
80
76
71 71
67
62
54
51
38
34
25 25
16
12
7 7 7
3 3
D ama
Th ille
Comedy
Ac ion
Ad en u e
C ime
Romance
Sci-Fi
Wa
Mis e y
Documen a y
Anima ion
Fan asy
Ho o
Child en
Musical
Wes e n
Film-Noi
IMAX
Use ’s Ra ing
+1
+1
By o ging and supp essing a ings, he ac ual p o ile o in e es s qis hen pe cei ed om he ou side
as he appa en PMF =q+ −s
1+ρ−σ, acco ding o a o ge y s a egy = ( 1, . . . , n)and a supp ession
(b) The desc ip ion o an a chi ec u e implemen ing his da a-pe u ba i e app oach may be ound in [1].
En opy 2014,16 1594
s a egy s= (s1, . . . , sn). Such s a egies ep esen he p opo ion o a ings ha he use should o ge
and elimina e in each o he nca ego ies. Na u ally, hese s a egies mus sa is y, on he one hand, ha
i⩾0,si⩾0and qi+ i−si⩾0 o i= 1, . . . , n, and on he o he , ha Pn
i=1 i=ρand Pn
i=1 si=σ.
In conclusion, he appa en p o ile is he esul o he addi ion and he subs ac ion o ce ain i ems
o/ om he ac ual p o ile, and he pos e io no maliza ion by 1
1+ρ−σso ha Pn
i=1 i= 1.
3.3. Measu ing he P i acy o Use P o iles
Inspi ed by he p i acy measu es p oposed in [17,27,28,55], and acco ding o he model o use p o ile
assumed in Sec ion 3.2, we de ine ini ial p i acy isk as he KL di e gence [56] be ween he use ’s
genuine p o ile and he popula ion’s dis ibu ion, ha is,
R0= D(qkp).(1)
Simila ly, we de ine ( inal) p i acy isk Ras he KL di e gence be ween he use ’s appa en p o ile and
he popula ion’s dis ibu ion,
R= D( kp) = D q+ −s
1 + ρ−σ
p.(2)
In ou a emp o quan i y p i acy isk, we ha e he e o e assumed ha he use knows, o is able
o es ima e, he dis ibu ion p ep esen ing he a e age in e es . We conside his is a easonable
assump ion, in pa because many ecommenda ion sys ems p o ide he ca ego ies hei i ems belong
o as well as de ailed s a is ics abou he a ings assigned by use s. I his in o ma ion we e no enough
o build he popula ion’s p o ile, use s could al e na i ely eso o da abases con aining his kind o da a.
An example o such da abases is Google AdWo ds Display Planne [57], which p o ides es ima es o he
numbe o imes ha ads, classi ied acco ding o a p ede ined se o opics, a e shown on a sea ch esul
page o o he si e on he Google Display Ne wo k [58]. Since ads o his ne wo k a e displayed based on
he sea ch que ies submi ed by use s and he con en o he Web pages b owsed, hose es ima es p o ide
a means o compu e he popula ion’s p o ile. P ecisely, his is he me hodology ollowed by [59,60] o
es ima e p.
Once we ha e de ined ou measu e o p i acy, nex we p oceed o jus i y i . An in ui i e jus i ica ion
o ou p i acy me ic s ems om he obse a ion ha , whene e he use ’s appa en i em dis ibu ion
di e ges oo much om he popula ion’s, a p i acy a acke will ha e ac ually gained some in o ma ion
abou he use , in con as o he s a is ics o he gene al popula ion.
A iche in e p e a ion a ises om he ac ha Shannon’s en opy may be ega ded as a special case
o KL di e gence. P ecisely, le udeno e he uni o m dis ibu ion on {1, . . . , n}, ha is, ui= 1/n.
In he special case when p=u, he p i acy isk becomes
D( ku) = log n−H( ).(3)
In o he wo ds, minimizing he KL di e gence is equi alen o maximizing he en opy o he use ’s
appa en i em dis ibu ion. Acco dingly, ins ead o using he measu e o p i acy isk ep esen ed by he
KL di e gence, ela i e o he popula ion’s dis ibu ion, we would use he en opy H( )as an absolu e
measu e o p i acy gain.
En opy 2014,16 1601
In he ollowing subsec ions, we shall analyze a numbe o impo an consequences o Theo em 3.
4.2. O hogonali y, Con inui y and P opo ionali y
In his subsec ion we s udy some in e es ing p ope ies o he closed- o m solu ion ob ained in
Sec ion 4.1. Speci ically, we in es iga e he o hogonali y and con inui y o he op imal o ge y and
supp ession s a egies, and hen es ablish a p opo ionali y ela ionship be ween he op imal appa en
use p o ile and he popula ion’s dis ibu ion.
Co olla y 4 (O hogonali y and Con inui y).
(i) Fo any (ρ, σ)∈cl ¯
C, he op imal o ge y and supp ession s a egies sa is y ∗
ks∗
k= 0 o
k= 1, . . . , n.
(ii) The componen s o ∗and s∗, in e p e ed as unc ions o ρand σ espec i ely, a e con inuous on
cl ¯
C.
P oo : The p oo is p o ided in Appendix B.
The o hogonali y o he op imal o ge y and supp ession s a egies, in he sense indica ed by
Co olla y 4(i), con o ms o in ui ion—i would no make any sense o submi alse a ings o i ems o
a pa icula ca ego y and, a he same ime, elimina e genuine a ings om his ca ego y. This in ui i e
esul is illus a ed in Figu e 2. The second pa o his co olla y is applied o show ou nex esul ,
P oposi ion 5.
P oposi ion 5 (P opo ionali y).De ine he piecewise unc ions φ(ρ, σ) = Qi+ρ
(1+ρ−σ)Piand
χ(ρ, σ) = ¯
Qj−σ
(1+ρ−σ)¯
Pjon he in e als [σj, σj−1] o j= 2, . . . , n and [ρi, ρi+1] o i= 1, . . . , j −1.
(i) Fo any j= 2, . . . , n and i= 1, . . . , j −1, and o any σ∈[σj, σj−1]and ρ∈[ρi, ρi+1], he
op imal appa en p o ile ∗and he popula ion’s dis ibu ion psa is y
∗
1
p1
=· · · = ∗
i
pi
=φ(ρ, σ),(18)
∗
j
pj
=· · · = ∗
n
pn
=χ(ρ, σ),(19)
and
φ(ρ, σ)⩽ ∗
i+1
pi+1
⩽· · · ⩽ ∗
j−1
pj−1
⩽χ(ρ, σ).(20)
(ii) The unc ion φis con inuous and s ic ly inc easing in each o i s a gumen s, and sa is ies
φ(ρ, σ)⩽1, wi h equali y i , and only i , (ρ, σ)=(ρj(σ), σ).
(iii) The unc ion χis con inuous and s ic ly dec easing in each o i s a gumen s, and sa is ies
χ(ρ, σ)⩾1, wi h equali y i , and only i , (ρ, σ) = (ρj(σ), σ).
En opy 2014,16 1602
P oo : The p oo is p esen ed in Appendix B.
Ou p e ious esul ells us how pe u ba ion ope a es. Acco ding o P oposi ion 5, he op imal
s a egies pe u b he use p o ile in such a manne ha , in hose ca ego ies wi h he lowes and highes
a ios qk
pk, he appa en p o ile becomes p opo ional o he popula ion’s dis ibu ion. Mo e p ecisely, he
common a io ∗
k
pkinc eases wi h bo h ρand σin hose ca ego ies a ec ed by o ge y, ha is, k= 1, . . . , i.
Exac ly he opposi e happens in hose ca ego ies a ec ed by supp ession, whe e he common a io ∗
j
pj
dec eases wi h bo h a es. This endency con inues un il ρ=ρc i (σ), a which poin ∗=p. Figu e 3
illus a es his p opo ionali y p ope y in he case o he example depic ed in Figu e 2.
Figu e 3. P opo ionali y ela ionship be ween he op imal use ’s appa en i em dis ibu ion
and he popula ion’s p o ile. In his igu e we show he a ios ∗
k
pko he example illus a ed in
Figu e 2, whe e he numbe o ca ego ies is n= 5,ρ∈[ρ2, ρ3]and σ∈[σ4, σ3].
*
/p
1
*
/p
*
k
/p
k
4.3. C i ical-P i acy Region
One o he esul s o Theo em 3is ha he bounda y o he c i ical-p i acy egion is de e mined
by he c i ical o ge y-supp ession h eshold ρj(σ), which we also deno e by ρc i (σ) o highligh his
ac . The ollowing p oposi ion le e ages on his esul and cha ac e izes said egion. In pa icula ,
P oposi ion 6 i s examines some p ope ies o his h eshold and hen in es iga es he con exi y o he
c i ical-p i acy egion.
P oposi ion 6 (Con exi y o he C i ical-P i acy Region).
(i) ρjis a con ex, piecewise linea unc ion o σ∈[σj, σj−1] o j= 2, . . . , n.
(ii) Cis con ex.
P oo : The p oo is p esen ed in Appendix C.
The conclusions d awn om his heo e ical esul a e illus a ed in Figu e 4. In his igu e we
ep esen he c i ical and nonc i ical-p i acy egions o n= 5 ca ego ies o in e es ; he dis ibu ions
qand passumed in his concep ual example a e di e en om hose conside ed in Figu es 2and 3.
Tha said, he igu e in ques ion shows a s aigh o wa d consequence o ou p e ious p oposi ion— he
nonc i ical-p i acy egion is noncon ex.
En opy 2014,16 1603
Figu e 4. Concep ual plo o he c i ical and nonc i ical p i acy egions o n= 5 ca ego ies.
c i ical-p i acy
egion
½1
½2
½3
½4
¾5
½5
¾4
¾3
¾2
¾1
nonc i ical-p i acy
egion
c i ical–p i acy
egion
½j(¾)
In his illus a i e example, he sequences o o ge y h esholds {ρ1...,ρ5}and supp ession
h esholds {σ5, . . . , σ1}a e s ic ly inc easing. By P oposi ion 2, we can conclude hen ha he
inequali ies o he labeling assump ion (6) hold s ic ly. Rela ed o hese h esholds is also he numbe
o nonze o componen s o he op imal s a egies, as ollows om Theo em 3. Figu e 4shows he se s o
pai s (ρ, σ)whe e he numbe o nonze o componen s o ∗and s∗is ixed. Thus, in he iangula a ea
shown da ke , co esponding o he Ca esian p oduc o he in e als [ρ3, ρ4]and [σ4, σ3], he solu ions
∗and s∗ha e i= 3 and n−j+ 1 = 2 nonze o componen s, espec i ely.
4.4. Case o Low Fo ge y and Supp ession
This subsec ion cha ac e izes he p i acy- o ge y-supp ession unc ion in he special case when
ρ, σ ≃0.
P oposi ion 7 (Low Ra es o Fo ge y and Supp ession).Assume he non i ial case in which q6=p.
Then, he e exis wo indexes i, j such ha 0 = ρ1=· · · =ρi< ρi+1 and 0 = σn=· · · =σj< σj−1.
Fo any ρ∈[0, ρi+1]and σ∈[0, σj−1], he numbe o nonze o componen s o he op imal o ge y and
supp ession s a egies is iand n−j+ 1, espec i ely. Fu he , he g adien o he p i acy- o ge y-
supp ession unc ion a he o igin is
∇R(0,0) =
∂R(0,0)
∂ρ
∂R(0,0)
∂σ
=
log q1
p1−D(qkp)
D(qkp)−log qn
pn
.(21)
P oo : The p oo is p esen ed in Appendix D.
Nex , we shall de i e an exp ession o he ela i e dec emen o he p i acy- isk unc ion a ρ, σ ≃0.
To his end, we de ine he o ge y ela i e dec emen ac o
δρ=−
∂R(0,0)
∂ρ
R(0,0) = 1 −log q1
p1
D(qkp),(22)
En opy 2014,16 1604
and he supp ession ela i e dec emen ac o
δσ=−
∂R(0,0)
∂σ
R(0,0) =log qn
pn
D(qkp)−1.(23)
By din o P oposi ion 7, he i s -o de Taylo app oxima ion o unc ion (4) a ound ρ=σ= 0 yields
R(ρ, σ)≃D(qkp) + ρlog q1
p1
−D(qkp)+σD(qkp)−log qn
pn,(24)
o mo e compac ly, in e ms o he dec emen ac o s,
D(qkp)− R(ρ, σ)
D(qkp)≃δρρ+δσσ. (25)
In wo ds, he minimum and maximum a ios qk
pkcha ac e ize he ela i e educ ion in p i acy isk. The
ollowing esul , P oposi ion 8, es ablishes a bound on hese ela i e dec emen ac o s.
P oposi ion 8 (Rela i e Dec emen Fac o s).In he non i ial case when q6=p, he ela i e dec emen
ac o s sa is y δρ>1and δσ>0.
P oo : The p oo is shown in Appendix D.
Concep ually, he bound on δρ ells us ha he ela i e dec emen in p i acy isk is g ea e han
he o ge y a e in oduced. This is unde he assump ion ha q6=pand a low a es o o ge y and
supp ession. The bound on δσ, howe e , is loose han he p e ious one and jus ensu es ha an inc ease
in he supp ession a e always leads o a dec ease in p i acy isk, as one would expec .
4.5. Pu e S a egies
In he p e ious subsec ions we in es iga ed he o ge y and he supp ession o a ings as a mixed
s a egy ha use s may adop o enhance hei p i acy. In his subsec ion we con empla e he case in
which use s may be eluc an o use hese wo mechanisms in conjunc ion; and as a consequence, hey
may op o a pu e s a egy consis ing in he applica ion o ei he o ge y o supp ession. In his case,
i would be use ul o de e mine which is he mos app op ia e echnique in e ms o he p i acy-u ili y
ade-o posed. Ou nex esul , Co olla y 9, p o ides some insigh on his, unde he assump ion ha ,
om he use ’s pe spec i e, he impac on u ili y due o o ge y is equi alen o ha caused by he e ec
o supp ession.
Be o e showing his esul , obse e om Theo em 3 ha ρn=qn
pn−1is he minimum o ge y a e such
ha R(ρ, 0) = 0. Analogously, σ1= 1 −q1
p1is he minimum supp ession a e sa is ying R(0, σ)=0.
In o he wo ds, ρnand σ1a e he c i ical a es o he pu e o ge y and supp ession s a egies, espec i ely.
Fu he , no e ha σ1< σ0= 1, on accoun o he posi i i y assump ion (5). Howe e , ρn>1i , and
only i , qn
pn>2.
Co olla y 9 (Pu e S a egies).Conside he non i ial case when q6=p.
(i) The c i ical a es o he pu e o ge y and supp ession s a egies sa is y ρn< σ1i , and only i ,
q1
/p1+qn
/pn
2<1.(26)
En opy 2014,16 1605
(ii) The o ge y and he supp ession ela i e dec emen ac o s sa is y δρ> δσi , and only i ,
q1
p1
qn
pn
<2D(qkp).(27)
P oo : Bo h s a emen s a e immedia e om he de ini ions o ρnand σ1on he one hand, and δρand
δσon he o he .
In concep ual e ms, he condi ion ρn< σ1means ha he pu e o ge y s a egy is he mos app op ia e
mechanism in e ms o causing he minimum dis o ion o a ain he c i ical-p i acy egion. On he
o he hand, he condi ion δρ> δσimplies ha , a low a es, he pu e o ge y s a egy o e s be e
p i acy p o ec ion han he pu e supp ession s a egy does. The e o e, he conclusion ha ollows
om Co olla y 9is ha , oge he wi h he quan i y D(qkp), he a i hme ic and geome ic mean o he
a ios q1
p1and qn
pnde e mine which s a egy o choose. Since he choice o he pu e s a egy depends on
each pa icula use and each pa icula applica ion, ob iously i is no possible o d aw u he gene al
conclusions on which one is mo e con enien . La e on in Sec ion 5, howe e , we shall in es iga e his
issue in a eal-wo ld applica ion and examine he pe cen age o use s ha would op o ei he o ge y o
supp ession as pu e s a egies.
Ano he in e es ing ema k is he duali y o hese wo a ios q1
p1and qn
pn. The o me cha ac e izes he
minimum a e o he pu e supp ession s a egy o each he c i ical-p i acy egion and, a he same ime,
i es ablishes he p i acy gain a low o ge y a es. Con e sely, he la e a io de ines he c i ical a e o
he pu e o ge y s a egy and de e mines he ela i e dec emen in p i acy isk a low supp ession a es.
Las ly, we would like o es ablish a connec ion be ween ou wo k and ha o [27,29], whe e he
pu e o ge y and supp ession s a egies a e in es iga ed. Deno e by RF he unc ion de i ed in [27]
modeling he ade-o be ween o ge y a e and p i acy isk, he la e being measu ed as he KL
di e gence be ween he use ’s appa en p o ile and he popula ion’s dis ibu ion. De ine ρ0as he a io o
o ged a ings o o al numbe o a ings. Acco dingly, i can be shown ha ρ0=ρ
1+ρand ha
R(ρ, 0) = 1
ln 2 RF(ρ0).On he o he hand, deno e by PS he unc ion in [29] cha ac e izing he ade-o
be ween supp ession a e and p i acy gain. In his case, p i acy is measu ed as he Shannon’s en opy
o he use ’s appa en p o ile. Unde he assump ion ha he popula ion’s p o ile is uni o m, i can be
p o en ha R(0, σ) = log n−1
ln 2 PS(σ).In sho , ou o mula ion o he p oblem o op imal o ge y and
supp ession o a ings encompasses, as pa icula cases, he ci ed wo ks.
4.6. Nume ical Example
This subsec ion p esen s a nume ical example ha illus a es he heo e ical analysis conduc ed in he
p e ious subsec ions. La e on in Sec ion 5we shall e alua e he e ec i eness o ou app oach in a eal
scena io, namely in he mo ie ecommenda ion sys em Mo ielens. In ou nume ical example we assume
n= 3 ca ego ies o in e es s. Al hough he example shown he e is syn he ic, hese h ee ca ego ies
could e y well ep esen in e es s ac oss opics such as echnology, spo s and beau y. Acco dingly, we
suppose ha he use ’s a ing dis ibu ion is
q= (0.130,0.440,0.430),(28)
En opy 2014,16 1606
and he popula ion’s,
p= (0.380,0.390,0.230).(29)
No e ha hese dis ibu ions sa is y he posi i i y and labeling assump ions (5) and (6).
F om Sec ion 4.1, we easily ob ain he o ge y h esholds ρ1= 0,ρ2≃0.299 and ρ3≃0.870 on
he one hand, and on he o he he supp ession h esholds σ3= 0,σ2≃0.171 and σ1≃0.658. The
h esholds ρ3and σ1a e he c i ical a es o he pu e s a egies. I we a e o each he c i ical-p i acy
egion and do no ha e any p e e ence o ei he o ge y o supp ession, he ac ha ρ3> σ1leads us o
op o supp ession as pu e s a egy. Howe e , he geome ic mean o q1
p1and q3
p3is app oxima ely 0.799,
which is lowe han 2D(qkp)≃1.20. On accoun o Co olla y 9, his means ha he pu e o ge y s a egy
con ibu es o a g ea e educ ion in p i acy isk a low a es han supp ession does. In ac , he g adien
o he p i acy- o ge y-supp ession unc ion a he o igin is ∇R(0,0)T≃(−1.81,−0.639), by i ue o
P oposi ion 7.
Figu e 5. Con ou lines o he p i acy- o ge y-supp ession unc ion, he co esponding
o ge y and supp ession h esholds, and he c i ical and nonc i ical p i acy egions.
σ
ρ
ρ=σ
ρ2≃0.299
σ2≃0.171
c i ical−p i acy
egion
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9 Theo e ical
Nume ical
R
0
0.05
0.10
0.15
0.20
0.25
σ1≃0.658
ρ3≃0.870
ρc i (σ)
Figu e 5shows he con ou lines o his unc ion, compu ed analy ically om Theo em 3and
nume ically (c). The egion plo ed in g ay shades co esponds o he nonc i ical-p i acy egion ¯
C.
The ini ial p i acy isk is R(0,0) ≃0.263. The whi e a ea ep esen s he c i ical-p i acy egion C,
whe e he appa en use p o ile coincides wi h he popula ion’s dis ibu ion and hus he p i acy isk
anishes. An in e es ing obse a ion a ising om Figu e 5is he syne gis ic e ec o combining o ge y
and supp ession. Jus as an example, in he case when ρ=ρ2and σ=σ2, we no e ha R(ρ, σ)is lowe
han R(ρ+σ, 0) and R(0, ρ +σ). Pu di e en ly, o ge y and supp ession p o ide be e p i acy o
he same o al a e han jus o ge y o supp ession alone. This is ue o his pa icula example, bu
i is no a gene al ule. Wha is always ue, howe e , is ha he mixed s a egy canno be wo se han
he pu e s a egies. This is because he easible se o he p oblem minimizing R(ρ, σ)subjec o he
(c) The nume ical me hod chosen is he in e io -poin algo i hm [62] implemen ed by he Ma lab R2012b unc ion mincon.
En opy 2014,16 1607
cons ain ρ+σ=τincludes he ex eme alues ρ=τand σ=τ, ha is, he cases co esponding o
he pu e s a egies.
Figu e 6. P obabili y simplices showing, o se e al in e es ing alues o ρand
σ, he use ’s ac ual p o ile q= (0.130,0.440,0.430), he popula ion’s dis ibu ion
p= (0.380,0.390,0.230), he op imal appa en dis ibu ion ∗and he se o easible appa en
dis ibu ions. (a)ρ= 0.050,σ= 0.100,ρ/ρc i (σ)≃0.093,R(ρ, σ)/R0≃0.498,
∗= (0.050,0,0),s∗= (0,0,0.100), ∗≃(0.189,0.463,0.347); (b)ρ= 0.100,σ= 0.200,
ρ/ρc i (σ)≃0.356,R(ρ, σ)/R0≃0.190, ∗= (0.100,0,0),s∗≃(0,0.019,0.181),
∗≃(0.256,0.468,0.276); (c)ρ≃0.219,σ= 0.300,ρ/ρc i (σ) = 1,R(ρ, σ)/R0= 0,
∗≃(0.219,0,0),s∗≃(0,0.081,0.219), ∗=p; (d)ρ= 0.300,σ= 0.300,
ρ/ρc i (σ)≃1.368,R(ρ, σ)/R0= 0, ∗≃(0.260,0.021,0.019),s∗≃(0.010,0.071,0.219),
∗=p.
q
∗
p
(100) (010)
(001)
(a)
q
∗
p
(100) (010)
(001)
(b)
q
∗p
(100) (010)
(001)
(c)
q
∗p
(100) (010)
(001)
(d)
Nex , we examine he op imal appa en a ing dis ibu ion o di e en alues o ρand σ. Fo his
pu pose, he use ’s genuine dis ibu ion q, he popula ion’s dis ibu ion pand he op imal appa en
dis ibu ion ∗a e depic ed in he p obabili y simplices shown in Figu e 6. In each simplex, we also
ep esen he con ou lines o he KL di e gence D(· k p)be ween e e y dis ibu ion in he simplex and
p. Fu he , we plo he se o easible appa en use dis ibu ions, no necessa ily op imal, o ou
di e en combina ions o ρand σ; in any o hese cases, he se akes he o m o a hexagon. Ha ing said
his, now we u n ou a en ion o Figu e 6a. In his case, he op imal o ge y and supp ession s a egies
ha e i=n−j+ 1 = 1 nonze o componen , since ρ∈[0, ρ2]and σ∈[0, σ2]. This places he solu ion ∗
a one e ex o he hexagon. A ema kable ac is ha , o hese a es, he p i acy isk is app oxima ely
En opy 2014,16 1608
hal ed. In he end, consis en ly wi h P oposi ion 8, he o ge y and he supp ession ela i e dec emen
ac o s a e δρ≃6.87 >1and δσ≃2.42 >0.
In he case shown in Figu e 6b, ∗s ill has i= 1 nonze o componen s, while s∗con ains n−j+1 = 2
nonze o componen s. Geome ically, he op imal appa en dis ibu ion lies a one edge o he easible
egion. This lowe s p i acy isk o a 19% o i s ini ial alue. The case in which (ρ, σ)=(ρc i (σ), σ)is
depic ed in Figu e 6c. He e, he numbe o nonze o componen s o ∗and s∗ emains he same as in he
p e ious case, bu he p i acy isk becomes ze o. The las case, illus a ed in Figu e 6d, does no ha e
any p ac ical applica ion, as R(ρ, σ) = 0 o any (ρ, σ)∈∂C. In his igu e we can obse e ha he
solu ion ∗is placed in he in e io o he hexagon, and ha he o hogonali y p inciple o he s a egies
∗and s∗s a ed in Co olla y 4is no sa is ied.
5. Expe imen al E alua ion
In his sec ion we e alua e he ex en o which he o ge y and he supp ession o a ings could enhance
use p i acy in a eal-wo ld ecommenda ion sys em. The sys em chosen o conduc his e alua ion
is Mo ielens, a popula mo ie ecommende de eloped by he G oupLens Resea ch Lab [63] a he
Uni e si y o Minneso a. As many o he ecommende s, Mo ielens allows use s o bo h a e and ag
mo ies acco ding o hei p e e ences. These p e e ences a e hen exploi ed by he ecommende o
sugges mo ies ha use s ha e no wa ched ye .
5.1. Da a Se
The da a se ha we used o assess ou da a-pe u ba i e mechanism is he Mo ielens 10M da a
se [64], which con ains 10,000,054 a ings and 95,580 ags. The a ings and ags included in his da a
se we e assigned o 10,681 mo ies by 71,567 use s. The da a a e o ganized in he o m o quad uples
(use name,mo ie, a ing, ime), each one ep esen ing he ac ion o a use a ing a mo ie a a ce ain
ime. Use names ha e been eplaced wi h numbe s in an a emp o anonymize he da a se .
Fo ou pu poses o expe imen a ion, we jus needed he da a ields use name and mo ie, oge he wi h
he ca ego ies each mo ie belongs o. Mo ielens con empla es n= 19 ca ego ies o mo ies gen es, lis ed
in alphabe ical o de as ollows: ac ion,ad en u e,anima ion,child en’s,comedy,c ime,documen a y,
d ama, an asy, ilm-noi ,ho o ,IMAX,musical,mys e y, omance,sci- i, h ille ,wa and wes e n. As
we shall see la e in Sec ion 5.2, o each pa icula use , we shall ha e o ea ange hose ca ego ies in
such a way ha he labeling assump ion (6) is sa is ied.
In ou da a se , all use s a ed, a leas , 20 mo ies. This was he minimum numbe o a ings o
he ecommende o s a wo king (d). A e he elimina ion o hose use s who exclusi ely agged
mo ies, he o al numbe o use s educed o 69,878. We ound ha only 4,099 o hose use s sa is ied
he posi i i y assump ion (5). Al hough we commen ed in Sec ion 4 ha ou analysis is also alid o
nons ic ly posi i e dis ibu ions, ou expe imen al analysis was conduc ed wi h p o iles which do sa is y
he a o emen ioned assump ion, in pa icula wi h hose 4,099 use s. We decided o use s ic ly posi i e
(d) Nowadays, he algo i hm implemen ed by Mo ielens equi es only 15 a ings o s a gene a ing p edic ions.
En opy 2014,16 1609
p o iles as a p ocedu e o elimina ing ou lie s, since, in p ac ice, o an app op ia ely ep esen a i e
choice o opic ca ego ies and a la ge olume o da a, nea ly all use s should ha e a minimal in e es in
all hose ca ego ies.
Conside ing ha his small g oup o use s ep esen s jus he 5.8% o he o al numbe o use s, we can
assume ha he applica ion o ou echnique will ha e a negligible e ec on he popula ion’s p o ile p,
as supposed in Sec ion 3.4.
5.2. Resul s
In his subsec ion we examine how he o ge y and he supp ession o a ings may help use s o
Mo ielens o enhance hei p i acy. Wi h his aim, i s , we analyze he e ec o he pe u ba ion o
a ings on he p i acy p o ec ion o wo pa icula use s om ou da a se . Secondly, we conside he
en i e se o 4,099 use s and assess he ela i e educ ion in p i acy isk when hese use s apply he
same o ge y and supp ession a es. Las ly, we in es iga e he o ge y and he supp ession s a egies
sepa a ely, and d aw some conclusions abou hese wo pu e s a egies.
To conduc ou i s expe imen s, we choose wo use s wi h a he di e en p o iles, in pa icula hose
iden i ied by he numbe s 3301 and 26589 in [64]. Fo he sake o b e i y, we shall deno e hese use s
by υ1and υ2, espec i ely. Be o e pe u bing he mo ie a ing his o y o hese wo use s, i is necessa y
ha he componen s o hei ac ual p o iles and he popula ion’s dis ibu ion be ea anged o sa is y he
labeling assump ion (6). Table 1shows how mo ie ca ego ies ha e been so ed, and hen indexed om
1 o n, o ul ill he assump ion abo e.
Table 1. Ca ego y indexes o he wo speci ic use s examined in ou i s se ies o
expe imen s. The ca ego ies o Mo ielens ha e been so ed and indexed in o de o sa is y he
labeling assump ion (6). The indexes 1 and 2 co espond o he use s υ1and υ2, espec i ely.
Ca ego y name Index 1 Index 2 Ca ego y
name
Index 1 Index 2 Ca ego y name Index 1 Index 2
ac ion 2 15 documen a y 19 9 musical 15 1
ad en u e 5 18 d ama 18 5 mys e y 14 8
anima ion 1 16 an asy 10 17 omance 16 6
child en’s 4 12 ilm-noi 3 3 sci- i 7 13
comedy 8 14 ho o 11 4 h ille 9 10
c ime 6 11 IMAX 17 19 wa 13 7
wes e n 12 2
Figu e 7a depic s he ac ual p o ile o υ1as well as he popula ion’s dis ibu ion, he la e being
compu ed by a e aging ac oss he 69,878 use s. F om his igu e we no e ha he in e es s o his use
a exceeds he popula ion’s in ca ego ies such as musical, omance,IMAX,d ama and documen a y.
Mo e p ecisely, such a ios qk
pkyield
qk
pkk=15,...,19
≃(1.300,1.306,1.451,1.728,2.292).(30)
In his igu e, we also obse e ha he use ’s in e es and he popula ion’s in he ca ego y 17 a e nea ly
ze o, namely q17 ≃0.0005 and p17 ≃0.0003. On he o he hand, Figu e 7a indica es ha υ1shows li le
En opy 2014,16 1610
in e es , compa ed o he popula ion’s p e e ences, in ca ego ies such as anima ion,ac ion, ilm-noi o
child en’s, o name jus a ew. Speci ically, he i s i e smalles a ios qk
pkyield
qk
pkk=1,...,5
≃(0.444,0.599,0.651,0.691,0.705).(31)
Figu e 7. In his igu e we ep esen (a) he i em dis ibu ion qo he pa icula use υ1,
and he popula ion’s i em dis ibu ion p. In addi ion, we plo (b) he op imal o ge y s a egy
∗and (c) he op imal supp ession s a egy s∗ ha his use should adop when hey speci y
σ= 0.150 and ρ=ρc i (σ)≃0.180.
Ca ego ies
Rela i e equency o a ings [%]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0
6
12
18
24
30 q
p
(a)
Ca ego ies
Rela i e equency o a ings [%]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0
6
12
18
24
30
(b)
Ca ego ies
Rela i e equency o a ings [%]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0
6
12
18
24
30
(c)
Figu e 7b and 7c show he op imal o ge y and supp ession s a egies ha his pa icula use should
apply, in he case when σ= 0.150 and ρc i (σ)≃0.180. The solu ions plo ed in hese igu es a e
consis en wi h ou wo p e ious obse a ions— he op imal o ge y s a egy ecommends ha he use
submi alse a ings o mo ies alling in o he ca ego ies whe e he a io qk
pkis low; and he op imal
supp ession s a egy sugges s ha he use e ain om a ing mo ies belonging o ca ego ies whe e he
a io qk
pkis high. Jus as an example, he ac ha s∗
17 ≃0.0001 means ha he use a hand should
elimina e one in i e a ings o mo ies classi ied as IMAX.
En opy 2014,16 1617
o he p i acy-u ili y ade-o unc ion, om which we conclude ha he a ios q1
p1and qn
pnde e mine,
oge he wi h he quan i y D(qkp), he p i acy isk a low a es. An eye-opening ac is ha he ela i e
dec emen in p i acy isk is g ea e han he o ge y a e in oduced.
Fu he , we conside he special case when o ge y and supp ession a e no used in combina ion.
Unde his conside a ion, we in es iga e which one is he mos app op ia e echnique, i s , in e ms o
causing he minimum dis o ion o each he c i ical-p i acy egion, and secondly, in e ms o o e ing
be e p i acy p o ec ion a low a es. Ou indings show ha he a i hme ic and geome ic mean o
he maximum and minimum a ios qk
pkplay a undamen al ole in deciding he bes echnique o use.
A e wa ds, ou o mula ion and heo e ical analysis a e illus a ed wi h a nume ical example.
In he end, he las sec ion is de o ed o he expe imen al e alua ion o ou da a-pe u ba i e
mechanism in a eal-wo ld ecommenda ion sys em. In pa icula , we examine how he applica ion o
he o ge y and he supp ession o a ings may p ese e use p i acy in Mo ielens. Among o he esul s,
we ind ha a la ge majo i y o use s signi ican ly educe p i acy isk o o ge y and supp ession a es
o jus 13%. Mo eo e , we obse e ha he mixed s a egy may p o ide s onge p i acy p o ec ion o
he same o al a e han he pu e s a egies. In ou da a se , he p obabili y dis ibu ions o he ela i e
dec emen ac o s indica e ha , a low a es, o ge y p o ides a highe educ ion in p i acy isk han
supp ession does. By con as , we no ice ha he supp ession ela i e dec emen ac o is g ea e han
ha o o ge y in 56.55% o use s. Las ly, we conside he case when use s mus op o ei he o ge y
o supp ession; and ind ha he la e is he bes s a egy o use in 95.3% o use s who wish o anish
p i acy isk while causing he minimum dis o ion.
Appendix
A. Closed-Fo m Solu ion
In his appendix, we p o ide he p oo s o he heo e ical esul s included in Sec ion 4.1, namely,
Lemma 1, P oposi ion 2and Theo em 3.
P oo o Lemma 1:The p oo o s a emen (i) consis s o wo s eps. In he i s s ep, we show ha
he op imiza ion p oblem s a ed in he lemma is con ex; hen we apply Ka ush-Kuhn-Tucke (KKT)
condi ions o said p oblem, and inally e o mula e hese condi ions in o a educed numbe o equa ions.
The bulk o his p oo comes la e , in he second s ep, whe e we p oceed o sol e he sys em o equa ions
o he wo cases conside ed in he lemma, ψ < ω and ψ=ω. Las ly, s a emen s (ii) and (iii) ollow
om (i).
To see ha he p oblem is con ex, simply obse e ha he objec i e unc ion is con ex on accoun o
H( k)0, and ha he inequali y and equali y cons ain unc ions a e a ine. Since he objec i e and
cons ain unc ions a e also di e en iable and Sla e ’s cons ain quali ica ion holds, KKT condi ions
a e necessa y and su icien condi ions o op imali y [62]. Sys ema ic applica ion o hese op imali y
condi ions leads o he Lag angian cos ,
L=X k(xk, yk)−Xλkxk−Xµkyk+Xνk(yk−κk−xk)−ψXxk−η+ωXyk−θ,
(34)
En opy 2014,16 1618
and inally o he condi ions
xk⩾0, yk⩾0, κk+xk−yk⩾0,
Pxk=η, Pyk=θ, (p imal easibili y)
λk⩾0, µk⩾0, νk⩾0,(dual easibili y)
λkxk= 0, µkyk= 0,
νk(yk−κk−xk)=0,(complemen a y slackness)
∂L
∂xk=hk(xk, yk)−λk−νk−ψ= 0,
∂L
∂yk=hk(xk, yk) + µk−νk−ω= 0.(dual op imali y)
Because lim
xk↓yk−κk
hk(xk, yk) = −∞, i ollows om he dual op imali y condi ions ha κk+xk−yk>
0, which implies, by complemen a y slackness, ha νk= 0. Subsequen ly, we may ew i e he dual
op imali y condi ions as λk=hk(xk, yk)−ψand µk=ω−hk(xk, yk). By elimina ing he slack
a iables λk, µk, we ob ain he simpli ied condi ions hk(xk, yk)⩾ψand hk(xk, yk)⩽ω. Las ly, we
subs i u e he abo e exp essions o λkand µkin o he complemen a y slackness condi ions, so ha we
can o mula e he dual op imali y and complemen a y slackness condi ions equi alen ly as
hk(xk, yk)⩾ψ, (35)
hk(xk, yk)⩽ω, (36)
(hk(xk, yk)−ψ)xk= 0,(37)
(hk(xk, yk)−ω)yk= 0.(38)
In he ollowing, we shall p oceed o sol e hese equa ions which, oge he wi h he p imal and dual
easibili y condi ions, a e necessa y and su icien condi ions o op imali y. To his end, i s no e ha ,
i ψ > ω, hen he e exis s no (xk, yk) ha sa is ies Equa ions (35) and (36) a he same ime, and
consequen ly, as s a ed in pa (i) o he lemma, he e is no solu ion. Conco dan ly, nex we shall s udy
he case when ψ < ω; a e wa ds we shall ackle he o he case when ψ=ω.
Be o e plunging in o he analysis o he o me case, ecall ha he unc ion hkis s ic ly inc easing
in xkand s ic ly dec easing in yk. Ha ing said his, obse e ha , unde he assump ion ψ < ω, he
a iables xkand ykcanno be posi i e simul aneously by i ue o Equa ions (37) and (38). Bea ing his
in mind, conside hese h ee possibili ies o each k:hk(0,0) < ψ,ψ⩽hk(0,0) ⩽ωand ω < hk(0,0).
When hk(0,0) < ψ, he only conclusion consis en wi h (35) and wi h he ac ha hkis s ic ly
inc easing in xkis ha xk>0. Since xkmus be posi i e, he complemen a y slackness condi ion (37)
implies ha hk(xk, yk) = ψand, because o (38), ha yk= 0. As a esul , xkmus sa is y hk(xk,0) = ψ,
o equi alen ly, xk=h−1
k(ψ). Nex , we show ha he solu ion (xk,0) is unique. Fo his pu pose,
suppose ha yk>0and, in consequence, ha xk= 0. I ollows om (38), howe e , ha hk(0, yk) = ω,
which con adic s he ac ha hkis a s ic ly dec easing unc ion o yk. In he end, we e i y ha
xk=yk= 0 does no sa is y (35) and hus p o e ha (xk, yk)=(h−1
k(ψ),0) is he unique minimize o
he objec i e unc ion when hk(0,0) < ψ.
Now conside he case when ψ⩽hk(0,0) ⩽ω. Fi s , suppose ha xk>0, and he e o e ha yk= 0.
By complemen a y slackness, i ollows ha hk(xk,0) = ψ, which is no consis en wi h he ac ha
hkis s ic ly inc easing in xk. Consequen ly, xkcanno be posi i e. Secondly, assume ha xkis ze o
En opy 2014,16 1619
and ykposi i e. Unde his assump ion, Equa ion (38) implies ha hk(0, yk) = ω, a con adic ion since
hkis a s ic ly dec easing unc ion o yk. Acco dingly, ykcanno be posi i e ei he . Finally, check ha
xk=yk= 0 sa is ies he op imali y condi ions and hence i is he unique solu ion.
The las possibili y co esponds o he case when ω < hk(0,0). No e ha , in his case, he only
conclusion consis en wi h (36) and wi h he ac ha hkis s ic ly dec easing in ykis ha yk>0.
Thus, because o (38), ykmus sa is y hk(0, yk) = ω. Recalling om he lemma ha hk(xk, yk) =
hk(xk−yk,0), we may exp ess he condi ion hk(0, yk) = ωequi alen ly as yk=−h−1
k(ω). Las ly,
we check ha his solu ion is unique in he case unde s udy. To his end, no e ha a solu ion such ha
xk>0and yk= 0 con adic s he ac ha hkis s ic ly inc easing in xk. As a esul , xkcanno be
posi i e. Finally, we con i m ha Equa ion (36) does no hold o xk=yk= 0 and he e o e p o e ha
(xk, yk) = (0,−h−1
k(ω)) is he unique solu ion when ω < hk(0,0).
In summa y, xk=h−1
k(ψ)i hk(0,0) < ψ, o equi alen ly, h−1
k(ψ)>0; o he wise xk= 0. Fu he ,
yk=−h−1
k(ω)i hk(0,0) > ω, o equi alen ly, h−1
k(ω)<0; o he wise yk= 0. Acco dingly, we may
w i e he solu ion compac ly as
(xk, yk) = max 0, h−1
k(ψ),max 0,−h−1
k(ω),(39)
whe e ψ, ω mus sa is y he p imal equali y cons ain s Pkxk=ηand Pkyk=θ.
Ha ing examined he case when ψ < ω, nex we p oceed o sol e he op imali y condi ions a hand
o ψ=ω. Obse e ha , in his new case, Equa ions (35) and (36) ans o m in o he equa ion
hk(xk, yk) = ψ. (40)
Mo eo e , no e ha any pai (xk, yk)sa is ying (40) also mee s he complemen a y slackness
condi ions (37) and (38). Howe e , no ice ha his does no mean ha all hose pai s a e op imal. To
elabo a e on his poin , conside he ollowing h ee possibili ies o each k:hk(0,0) < ψ,hk(0,0) = ψ
and ψ < hk(0,0).
In he case when hk(0,0) < ψ, he only condi ion consis en wi h (40) and wi h he ac ha hkis
s ic ly inc easing in xkis ha xk>0. F om he lemma, i is immedia e ha ∂hk
∂xk=−∂hk
∂yk, which implies
ha xkmus also be g ea e han yk. Hence, he se o solu ions is
{(xk, yk): hk(xk, yk) = ψ, xk> yk},(41)
whe e e e y pai in his se mus also ul ill he p imal equali y condi ions. Le x0
ksa is y hk(x0
k,0) = ψ,
o equi alen ly, x0
k=h−1
k(ψ). Then, because hk(x0
k+αk, αk) = ψ o any α⩾0, his se may be ecas
equi alen ly as
{(xk, yk): xk=x0
k+αk, yk=αk}.(42)
Fo he wo emaining cases, i.e., hk(0,0) = ψand ψ < hk(0,0), he se o solu ions is ob ained in a
comple ely analogous way as abo e. In he o me case, he pai s (xk, yk)mus sa is y xk=yk, and he
se o solu ions may be exp essed as
{(xk, yk): xk=αk, yk=αk}.(43)
In he la e case, i ollows ha yk> xkand, consequen ly, ha he se o solu ions is
{(xk, yk): xk=αk, yk=y0
k+αk},(44)
En opy 2014,16 1620
whe e y0
kmus sa is y hk(0, y0
k) = ψ.
To sum up, he case ψ=ωleads o he ollowing solu ions: xk=h−1
k(ψ) + αki hk(0,0) < ψ, o
equi alen ly, h−1
k(ψ)>0; o he wise xk=αk. In addi ion, yk=−h−1
k(ω) + αki hk(0,0) > ω, o
equi alen ly, h−1
k(ω)<0; o he wise yk=αk. Acco dingly, he solu ions (xk, yk)yield
max 0, h−1
k(ψ)+αk,max 0,−h−1
k(ω)+αk,(45)
o some ψ, ω and nonnega i e sequence α1, . . . , αnsuch ha Pkxk=ηand Pkyk=θ. No e ha ,
al hough ψ=ω, we in en ionally w i e ωin he second e m ins ead o ψ o highligh ha he solu ions
o ψ < ω and o ψ=ωjus di e in he e m αk, as we claimed in pa (i) o he lemma.
To comple e he p oo o s a emen (i), i su ices o show ha he numbe o solu ions is in ini e when
ψ=ω. To his end, simply obse e ha he e exis s an in ini e numbe o sequences α1, . . . , αnsuch ha
X
k
xk=X
k
h−1
k(ψ) + X
k
αk=η(46)
and
X
k
yk=−X
k
h−1
k(ψ) + X
k
αk=θ, (47)
which esul s in an in ini e numbe o solu ions o he o m gi en in Equa ion (45).
Now we p oceed o p o e (ii), which is an immedia e consequence o (i). Fo his pu pose, obse e
ha i ψ⩽hi+1(0,0) ⩽· · · ⩽hn(0,0) holds o some i= 0, . . . , n −1, hen h−1
i+1(ψ), . . . , h−1
n(ψ)⩽0,
and acco dingly xi+1 =· · · =xn= 0. Simila ly, i h1(0,0) ⩽· · · ⩽hj−1(0,0) ⩽ωis sa is ied o
some j= 2, . . . , n + 1, hen h−1
1(ω), . . . , h−1
j−1(ω)⩾0, and hus y1=· · · =yj−1= 0.
No e ha he pa icula case when he index i anges om 1 o j−1and he index jgoes om 2 o n
is he case desc ibed in (ii) (a), which co esponds o η, θ > 0. Fu he , obse e ha he case assumed in
(ii) (b), i.e., when j=n+ 1, implies ha θ= 0. He e, he index is a s a 1, he e o e excluding η= 0,
and ends a n, including he possibili y ha xi>0 o all i. In pa (ii) (c), we conside i= 0, which is
equi alen o he condi ion η= 0. In his case, he index js a s a 1, pe mi ing yj>0 o all j, and
ends a n, a oiding θ= 0. Finally, he case desc ibed in (ii) (d), namely when j=n+ 1 and i= 0, is
p ecisely he i ial case x=y= 0.
In o de o e i y s a emen (iii), we p oceed analogously by no ing ha i ψ=hi+1(0,0) = · · · =
hj−1(0,0) holds o some i= 1, . . . , j −2and some j= 3, . . . , n, hen h−1
i+1(ψ) = · · · =h−1
j−1(ψ) = 0,
and consequen ly xk=yk=αk o k=i+ 1, . . . , j −1.
P oo o P oposi ion 2:The i s s a emen can be shown om he de ini ion o he o ge y h esholds
by ou ine algeb aic manipula ion and unde he labeling assump ion (6). To his end, i is help ul o
no e ha
Pi
qi+1
pi+1
−Qi=Pi+1
qi+1
pi+1
−Qi+1.(48)
The second s a emen can be shown analogously, obse ing ha
¯
Qj−¯
Pj
qj−1
pj−1
=¯
Qj−1−¯
Pj−1
qj−1
pj−1
.(49)
Fo he las s a emen , use he de ini ions o he o ge y and he supp ession h esholds o no e ha he
condi ion ρj(σ)⩾ρj−1is equi alen o σ⩽σj−1.
En opy 2014,16 1621
P oo o Theo em 3:The p oo is s uc u ed as ollows. We begin by showing ha he op imiza ion
p oblem (4) may be cons ued as a pa icula case o ha s a ed in Lemma 1. Acco dingly, we apply
his lemma, namely he cases (ii) and (iii), o ob ain he op imal o ge y and supp ession s a egies. The
applica ion o he o me case allows us o de i e he solu ion o (ρ, σ)∈¯
C. The la e case enables us,
i s , o con i m ha his solu ion is also alid on ∂C, and secondly, o p o e s a emen (i). Las ly, we
comple e he p oo o (ii) by exp essing unc ion (4) in e ms o he op imal appa en dis ibu ion.
Use he de ini ion o KL di e gence o w i e he objec i e unc ion o he op imiza ion p oblem as
D( kp) = Pk klog k
pk, wi h =q+ −s
1+ρ−σ. Obse e ha he unc ions k( k, sk) = klog k
pka e wice
di e en iable on {( k, sk): qk+ k−sk>0}. Deno e by hk he de i a i e o kwi h espec o k,
hk( k, sk) = 1
1 + ρ−σlog qk+ k−sk
(1 + ρ−σ)pk
+ 1.(50)
Then, no e ha he unc ions kand hksa is y he assump ions o Lemma 1, and ha he inequali y and
equali y cons ain s o unc ion (4) coincide wi h hose in he lemma. This exposes he s uc u e o he
op imiza ion p oblem as a special case o he esou ce alloca ion lemma.
Be o e p oceeding any u he , no ice om Equa ion (50) ha hk( k,0) is a s ic ly inc easing unc ion
o kand hence in e ible. No e also ha , acco ding o he lemma, he solu ions a e comple ely
de e mined by he in e se o his unc ion, which is deno ed by h−1
kand yields
h−1
k(φ) = pk(1 + ρ−σ)2(1+ρ−σ)φ−1−qk.(51)
Finally, obse e ha he assump ion h1(0,0) ⩽· · · ⩽hn(0,0) in he lemma is equi alen o he labeling
assump ion (6), as hk(0,0) is a s ic ly inc easing unc ion o qk
pk.
Nex we apply Lemma 1(ii), whe e i is assumed he condi ion ψ < ω. We s a wi h case (ii) (a). On
accoun o pa (i) o he lemma, he op imal o ge y s a egy mus sa is y
ρ=
i
X
k=1
h−1
k(ψ) = Pi(1 + ρ−σ)2(1+ρ−σ)ψ−1−Qi,(52)
o equi alen ly,
ψ=1
1 + ρ−σlog Qi+ρ
(1 + ρ−σ)Pi
+ 1.(53)
Analogously o he supp ession s a egy,
σ=−
n
X
k=j
h−1
k(ω) = ¯
Qj−¯
Pj(1 + ρ−σ)2(1+ρ−σ)ω−1,(54)
and he e o e
ω=1
1 + ρ−σlog ¯
Qj−σ
(1 + ρ−σ)¯
Pj
+ 1.(55)
Then i su ices o subs i u e he exp essions o ψand ωin o he unc ion h−1
k, o ob ain he nonze o
op imal solu ions claimed in asse ion (ii) o he heo em.
Now we p oceed o con i m he in e al o alues o ρand σwhe e hese solu ions a e de ined.
In he case unde s udy, ψand ωsa is y hi(0,0) < ψ ⩽hi+1(0,0) o some i= 1, . . . , j −1and
En opy 2014,16 1622
hj−1(0,0) ⩽ω < hj(0,0) o some j= 2, . . . , n. We spli he discussion in o wo cases, namely
i<j−1and i=j−1.
Assume he o me case. Obse e ha he condi ion hi(0,0) < ψ is equi alen o
1
1 + ρ−σlog qi
(1 + ρ−σ)pi
+ 1<1
1 + ρ−σlog Qi+ρ
(1 + ρ−σ)Pi
+ 1(56)
and inally, a e ou ine algeb aic manipula ion, o
ρ>Pi
qi
pi
−Qi.(57)
Simila ly, he uppe -bound condi ion ψ⩽hi+1(0,0) leads o
ρ⩽Pi
qi+1
pi+1
−Qi.(58)
Hence, he in e als esul ing om imposing hi(0,0) < ψ ⩽hi+1(0,0) a e o he o m (ρi, ρi+1].
The mono onici y o he h esholds ρi, demons a ed in P oposi ion 2, gua an ees ha hese in e als
a e con iguous and nono e lapping. In an analogous manne , i can be shown ha he condi ion
hj−1(0,0) ⩽ω < hj(0,0) leads o in e als o he o m (σj, σj−1], also con iguous and nono e lapping
by i ue o P oposi ion 2.
Now assume he la e case, whe e hi(0,0) < ψ < ω < hj(0,0) wi h i=j−1. On he one hand, he
assump ion hj−1(0,0) < ψ is, as shown abo e, equi alen o he condi ion ρ>ρj−1. On he o he hand,
s aigh o wa d manipula ion allows us o w i e he inequali y ψ < ω as
ρ < Pj−1
¯
Pj
(¯
Qj−σ)−Qj−1.(59)
Combining hese wo bounds on ψ, we ob ain he in e al (ρj−1, ρc i (σ)). Wi h his las in e al, we
comple e he ange o alidi y o he solu ion o he case (ii) (a) in he lemma. Ul ima ely, i is easy o
e i y ha , in hose in e als o ρand σ, he op imal appa en p o ile =q+ −s
1+ρ−σdoes no coincide wi h
he popula ion’s p o ile p. In consequence, D( kp)>0.
Nex , we u n o case (ii) (b) o he lemma. He e, he assump ion hn(0,0) ⩽ωleads o σ= 0, o
equi alen ly, o he solu ion s= 0. No e ha , p ecisely, his is he solu ion gi en in he heo em o
σ=σjwi h j=n. On he o he hand, he applica ion o he condi ion Pi
k=1 k=ρ esul s in he
same op imal o ge y s a egy ob ained in case (ii) (a). P oceeding analogously as in his case, om
he assump ions on ψwe de i e he in e als o alues o ρwhe e he solu ion is de ined: (ρi, ρi+1] o
i= 1, . . . , n −1and (ρi, ρi+1) o i=n. Gi en hese in e als, i is hen s aigh o wa d o check ha
R(ρ, 0) = 0 i , and only i , ρ⩾ρn. This p o ides us wi h he pai s (ρ, 0) ha belong o cl ¯
C.
In case (ii) (c), he condi ion ψ⩽h1(0,0) means ha ρ= 0, o equi alen ly, = 0. Obse e ha
his is he solu ion s a ed in he heo em o ρ=ρiwi h i= 1. Then again, he condi ion Pn
k=jsk=σ
leads o he same op imal supp ession s a egy ound in case (ii) (a). F om he assump ions in he lemma
on ω, we ob ain he in e als (σj, σj−1] o j= 2, . . . , n and (σj, σj−1) o j= 1. Then, we e i y ha
R(0, σ)=0i , and only i , σ⩾σ1, om which i ollows he pai s (0, σ) ha belong o cl ¯
C.
Finally, he case (ii) (d) in he lemma, in which hn(0,0) ⩽ωand ψ⩽h1(0,0), co esponds o he
i ial case σ=σj o j=nand ρ=ρi o i= 1, ha is, he solu ion =s= 0.
En opy 2014,16 1623
A e ha ing applied Lemma 1(ii) o unc ion (4), now we p oceed wi h case (iii) (a). In applying i ,
we shall show ha he solu ion claimed in he heo em is also alid o he ex eme alues o he in e als
in case (ii) (a), speci ically he se
{(ρ, σ): ρ=ρc i (σ), σ ∈(σj, σj−1] o j= 3, . . . , n, and σ∈(σj, σj−1) o j= 2}.(60)
Assume he case (iii) (a) in which hi(0,0) < ψ =ω < hj(0,0) o some j= 2, . . . , n and i=j−1.
Unde his assump ion, he equali y cons ain Pi
k=1 k=ρin he lemma is equi alen , a e simple
algeb aic manipula ion, o
ψ=1
1 + ρ−σlog Qj−1+ρ−ζ
(1 + ρ−σ)Pj−1
+ 1,(61)
whe e we de ine ζ=Pn
k=1 αk. Simila ly, he equali y cons ain Pn
k=jsk=σbecomes
ω=1
1 + ρ−σlog ¯
Qj−σ+ζ
(1 + ρ−σ)¯
Pj
+ 1.(62)
Bu ψ=ω, he e o e
Qj−1+ρ−ζ
Pj−1
=¯
Qj−σ+ζ
¯
Pj
,(63)
o equi alen ly,
ρ=ρc i (σ) + ζ
¯
Pj
.(64)
In sho , he assump ion ψ=ωimposes he condi ion (ρ, σ)(ρc i (σ), σ) o some nonnega i e
sequence α1, . . . , αnsa is ying he abo e equali y. Nex we examine, o a gi en σ, hese wo
possibili ies, ρ=ρc i (σ)and ρ>ρc i (σ).
Conside he o me possibili y and obse e ha ρ=ρc i (σ)i , and only i , αk= 0 o k= 1, . . . , n.
Acco ding o he lemma, he nonze o op imal solu ions yield
k=h−1
k(ψ) = pk
Qj−1+ρc i (σ)
Pj−1
−qk
=pk(1 + ρc i (σ)−σ)−qk
(65)
o k= 1, . . . , j −1, and
sk=−h−1
k(ψ) = qk−pk(1 + ρc i (σ)−σ)(66)
o k=j, . . . , n, ha is, he solu ions ob ained a e applying case (ii) (a), bu e alua ed a ρ=ρc i (σ).
F om hese exp ession o and s, i is immedia e o e i y hen ha =pand hus R(ρ, σ) = 0.
Now we assume he la e possibili y, i.e., (ρ, σ)(ρc i (σ), σ), o show ha he p i acy- isk unc ion
also anishes o hese alues o ρand σ. On accoun o pa (iii) (a) o he lemma and (61), we de i e
he op imal o ge y and supp ession s a egies
k=pk(1 + ρc i (σ)−σ) + pkζ
¯
Pj
−qk+αk(67)
and sk=αk o k= 1, . . . , j −1, and
sk=qk−pk(1 + ρc i (σ)−σ)−pkζ
¯
Pj
+αk(68)
En opy 2014,16 1624
and k=αk o k=j, . . . , n. Then, we subs i u e and sback in o he appa en p o ile and check ha
D( kp) = 0. In doing so, we de e mine he pai s (ρ, σ)0 ha belong o cl ¯
C, and inally ob ain he
exp ession o he bounda y o he c i ical-p i acy egion claimed in s a emen (i) o he heo em.
To conclude he p oo , i emains only o w i e he p i acy- isk unc ion R(ρ, σ) = Pn
k=1 klog k
pkin
e ms o he op imal appa en dis ibu ion. Wi h his aim, we spli he summa ion in o h ee pa s. The
i s pa , co esponding o k=pk(Qi+ρ)
Pi(1+ρ−σ), is
i
X
k=1
klog k
pk
=Qi+ρ
1 + ρ−σlog Qi+ρ
(1 + ρ−σ)Pi
,(69)
whe e we le e age on he ac ha k
pkdoes no depend on k. The second pa o he sum, co esponding
o k=qk
1+ρ−σ, yields
j−1
X
k=i+1
klog k
pk
=
j−1
X
k=i+1
qk
1 + ρ−σlog qk
(1 + ρ−σ)pk
.(70)
The las pa , co esponding o k=pk(¯
Qj−σ)
¯
Pj(1+ρ−σ), is
n
X
k=j
klog k
pk
=¯
Qj−σ
1 + ρ−σlog ¯
Qj−σ
(1 + ρ−σ)¯
Pj
,(71)
whe e we also no e ha k
pkdoes no depend on kei he . Now, i is s aigh o wa d o iden i y he e ms
o R(ρ, σ)as he KL di e gence be ween he dis ibu ions
Qi+ρ
1 + ρ−σ,qi+1
1 + ρ−σ,..., qj−1
1 + ρ−σ,¯
Qj−σ
1 + ρ−σ(72)
and
Pi, pi+1, . . . , pj−1,¯
Pj,(73)
p ecisely he dis ibu ions s a ed in he heo em.
B. O hogonali y, Con inui y and P opo ionali y
This appendix p o ides he p oo o he esul s shown in Sec ion 4.2, in pa icula , Co olla y 4and
P oposi ion 5.
P oo o Co olla y 4:The p oo o (i) is i ial om Theo em 3. To p o e s a emen (ii) we also
eso o his heo em. Acco ding o i , each componen ∗
kmay be ega ded as a piecewise unc ion o ρ
de ined on he con iguous, nono e lapping in e als [ρi, ρi+1] o i= 1 and (ρi, ρi+1] o i= 2, . . . , j−1.
A di ec e i ica ion shows ha , o any k=j, . . . , n, he componen ∗
kis iden ically ze o on he whole
in e al [ρ1, ρj]and hence con inuous. Fo any k= 1, . . . , j −1, we immedia ely check he con inui y
o ∗
kon he in e io o each o he in e als pa ame e ized by i. Now we examine he endpoin s o such
in e als. The con inui y a he ex eme poin s ρ1and ρjis e i ied s aigh o wa dly as he in e als a e
closed a hese poin s. Then, we check ha he limi a he emaining endpoin s ρiexis s, since
lim
ρ→ρ−
i
∗
k(ρ) = pk
Pi−1
(Qi−1+ρi)−qk
En opy 2014,16 1625
=pk
Pi
(Qi+ρi)−qk= lim
ρ→ρ+
i
∗
k(ρ),(74)
o i= 2, . . . , j −1. Because each limi coincides wi h he co esponding alue ∗
k(ρi), we p o e
he con inui y o he componen s 1, . . . , j−1. The p oo o he con inui y o he componen s o s∗is
analogous o ha o ∗.
P oo o P oposi ion 5:The con inui y o he componen s o ∗on cl ¯
C ollows om Co olla y 4(ii).
This allows us o w i e he in e als in Theo em 3as [ρi, ρi+1]and [σj, σj−1], in lieu o (ρi, ρi+1]and
(σj, σj−1], espec i ely. F om he exp essions o ∗
kand s∗
kin he heo em, i is immedia e o iden i y
he a ios ∗
k
pkas ei he φ(ρ, σ)o χ(ρ, σ). The inne inequali ies in s a emen (i) o his p oposi ion
also ollow immedia ely om he labeling assump ion (6). Di ec manipula ion shows ha he ou e
inequali ies ∗
i
pi⩽ ∗
i+1
pi+1 and ∗
j−1
pj−1⩽ ∗
j
pja e equi alen o ρ⩽ρi+1 and σ⩽σj−1, espec i ely. This
p o es (i).
Nex , we p oceed o demons a e he s ic mono onici y o φ. A simple calcula ion shows ha
∂φ
∂ρ =¯
Qi+1 −σ
(1 + ρ−σ)2Pi
.(75)
To p o e ha ∂φ
∂ρ >0, i is su icien o e i y ha ¯
Qj> σj−1, o equi alen ly, ha ¯
Pj
qj−1
pj−1>0.Then, by
he posi i i y assump ion (5), we immedia ely see ha his la e inequali y holds o any j= 2, . . . , n.
The s ic mono onici y o φin σalso ollows om assump ion (5).
To comple e (ii), we w i e he condi ion φ(ρ, σ)⩽1as
ρ⩽(1 −σ)Pi−Qi
¯
Pi+1
.(76)
A ou ine compu a ion shows ha he equali y holds o ρj(σ)and any σ∈[σj, σj−1]wi h j= 2, . . . , n.
The e o e, o any ixed σ, he inequali y holds s ic ly o any o he ρ. The con e se, ha is, φ(ρ, σ) = 1
implies (ρ, σ) = (ρj(σ), σ), is immedia e om he s ic mono onici y o φ. The p oo o s a emen (iii)
p oceeds along he same lines o ha o (ii) and is omi ed.
C. C i ical-P i acy Region
Nex , we p o ide he p oo o P oposi ion 6, included in Sec ion 4.3.
P oo o P oposi ion 6:F om Theo em 3, i is ou ine o check he con inui y o ρjon [σn, σ1]. To
show i s con exi y, we con enien ly w i e his unc ion as ρj(σ) = mjσ+bj, whe e mj=−Pj−1
¯
Pjand
bj=Pj−1−Qj−1
¯
Pj. Nex , we p o e ha he slopes sa is y mj< mj−1 o all j= 3, . . . , n. We p oceed by
con adic ion, assuming ha mj⩾mj−1. No e ha his inequali y is equi alen o Pj−1¯
Pj−1⩽¯
Pj−
¯
Pj¯
Pj−1and, a e algeb aic simpli ica ion, o pj−1⩽0. This con adic s he posi i i y assump ion (5),
which, in u n, implies ha mj<0 o all j= 2, . . . , n. The e o e, since ρjis a piecewise linea unc ion
de ined by he s ic ly inc easing sequence o nega i e slopes {mn, . . . , m2}, we can conclude ha ρjis
con ex. This p o es s a emen (i). The second s a emen ollows om he i s one. As ρjis con ex, so
is i s epig aph, i.e., he c i ical-p i acy egion.
En opy 2014,16 1626
D. Case o Low Fo ge y and Supp ession
Finally, his appendix p o ides he p oo s o he heo e ical esul s shown Sec ion 4.4, namely,
P oposi ions 7and 8.
P oo o P oposi ion 7:The exis ence o he indexes iand jis gua an eed by he assump ion ha
q6=p. The numbe o nonze o componen s o ∗and s∗is i ial om Theo em 3. In iew o his
heo em, o any ρ∈[0, ρi+1]and σ∈[0, σj−1], we ha e
R(ρ, σ) = D ˜q+ρ(1,0,...,0) −σ(0,...,0,1)
1 + ρ−σ
˜p.(77)
The con inui y o he componen s o ∗and s∗p o en in Co olla y 4(ii) ensu es he con inui y o he
p i acy- o ge y-supp ession unc ion on ¯
C. I is ou ine o check i s di e en iabili y in his egion and
o ob ain i s de i a i e wi h espec o σa he o igin,
∂R(0,0)
∂σ =Qilog Qi¯
Pj
Pi¯
Qj
+
j−1
X
k=i+1
qklog ¯
Pjqk
¯
Qjpk
.(78)
On accoun o P oposi ion 2, he condi ions ρ1=· · · =ρiand σj=· · · =σnimply
q1
p1
=· · · =qi
pi
=Qi
Pi
(79)
and qj
pj
=· · · =qn
pn
=¯
Qj
¯
Pj
.(80)
The e o e,
∂R(0,0)
∂σ =
j−1
X
k=1
qklog qk
pk
−Qj−1log qn
pn
= D(qkp)−log qn
pn
.
(81)
The de i a i e o Rwi h espec o ρa ρ=σ= 0 ollows analogously.
P oo o P oposi ion 8:Obse e ha he s a emen δρ>1is equi alen o he condi ion q1< p1.
We p o e his by con adic ion. Suppose ha q1> p1. By he labeling assump ion (6), i ollows ha
qk> pk o all k, wha leads o he con adic ion ha 1 = Pqk>Ppk= 1. Now assume ha q1=p1.
Since q6=p, he e mus exis an index isuch ha
q1
p1
=· · · =qi−1
pi−1
<qi
pi
⩽· · · ⩽qn
pn
.(82)
Bu his implies ha
1−
i−1
X
k=1
qk=
n
X
k=i
qk>
n
X
k=i
pk= 1 −
i−1
X
k=1
qk,(83)
a con adic ion. This p o es he i s pa o he p oposi ion.
