Density estimation using game theory

Densi y es ima ion using game heo y1 Ignacio Ga c´ıa-Ju ado Depa men o S a is ics and OR, Facul y o Ma hema ics, Uni e sidad de San iago de Compos ela, 15782 San iago de Compos ela, Spain. Luciano M´endez-Naya Depa men o Econome ics, Facul y o Economics, Uni e sidad de San iago de Compos ela, 15782 San iago de Compos ela, Spain. C´esa S´anchez-Selle o Depa men o S a is ics and OR, Facul y o Ma hema ics, Uni e sidad de San iago de Compos ela, 15782 San iago de Compos ela, Spain. Abs ac : In his no e we show ha he ma hema ical ools o coope a- i e game heo y allow a success ul app oach o he s a is ical p oblem o es ima ing a densi y unc ion. Speci ically, any andom sample o an abso- lu ely con inuous andom a iable de e mines a ans e able u ili y game, he Shapley alue o which p o es o be an es ima o o he densi y unc ion o binned ke nel and WARPing ypes, wi h good compu a ional and s a is ical p ope ies. Key Wo ds: Coope a i e Games, Densi y Es ima ion, Shapley Value. Mailing Au ho : Ignacio Ga c´ıa-Ju ado (ig[email p o ec ed]). Running Ti le: Densi y Es ima ion. 1Au ho s acknowledge he inancial suppo o Spanish Minis y o Science and Tech- nology and FEDER h ough p ojec s BFM2002-03213 and BEC2002-04102-C02-02 and o Xun a de Galicia h ough p ojec s PGIDT00PXI20104PR and PGIDT03PXIC20701PN. They also hank he commen s o wo anonymous e e ees. 1 1 In oduc ion The ela ionship be ween game heo y and s a is ics is gene ally seen as e y one-sided: whe eas he in luence o p obabili y heo y and bayesian s a is ics on game heo y is e iden , he only well-known con ibu ion o game he- o y o s a is ical hough is he minimax p inciple. Noncoope a i e games had a ce ain in luence on s a is ical heo y (Blackwell and Gi shick (1953); Schwa z (1994)), bu coope a i e game heo y has been applied o s a is ics e y a ely (Land and Ge elle ’s (1997) and (2000) ea men o an epidemi- ological p oblem as a cos alloca ion game is one o hose applica ions). This is o some ex en su p ising i one bea s in mind ha ai ness, one o he cen al hemes o coope a i e game heo y, is clea ly desi able in s a is ics in he sense ha a good s a is ical es ima o should in some sense p o ide an es ima e ha is ai , gi en he a ailable da a. The aim o his no e is o p o ide a new illus a ion o he connec ion be ween coope a i e game heo y and s a is ics. We show ha he ma he- ma ical ools o coope a i e game heo y allow a success ul app oach o he s a is ical p oblem o es ima ing a densi y unc ion. Speci ically, we show ha any andom sample o an absolu ely con inuous andom a iable can be used o cons uc a TU ( ans e able u ili y) game, he Shapley alue o which (Shapley (1953)) is an es ima o o he densi y unc ion o binned ke nel ype (Hall and Wand (1996)) and WARPing ype (H¨a dle (1991)). Densi y es ima ion is an impo an p oblem in s a is ics ha has gene a ed a la ge li e a u e in he las decades. I s pu pose is o p o ide an accu a e es ima ion o he densi y unc ion o a andom a iable on he basis o a andom sample. Nowadays, densi y es ima ion is a basic ool o explo a o y da a analysis and o o he impo an ields wi hin s a is ics. Fo a comple e in oduc ion o densi y es ima ion, Sil e man (1986) can be consul ed. In sec ion 2 below we desc ibe he densi y es ima ion p oblem, model i as a coope a i e game whose Shapley alue is he equi ed densi y es ima- o , and ob ain a mo e con enien exp ession o his es ima o . In sec ion 3 we p o ide an axioma ic cha ac e iza ion o he Shapley densi y es ima- o . Finally, in sec ion 4 we make some commen s on he s a is ical and compu a ional p ope ies o he Shapley densi y es ima o . 2 2 Densi y es ima ion as a game- heo e ical p oblem In a densi y es ima ion p oblem we ha e a andom sample X1, ..., Xmo m independen and iden ically dis ibu ed obse a ions o an absolu ely con in- uous andom a iable wi h densi y unc ion . is unknown and he p oblem is o es ima e using he andom sample. A a ie y o nonpa ame ic den- si y es ima o s ha e been p oposed and s udied since he publica ion o he pionee wo ks by Pa zen (1962) and Rosenbla (1956) on he so-called ke nel me hods. Fo a su ey on densi y es ima ion see Sil e man (1986). A ke nel es ima o is any eal unc ion ˆ o he o m ˆ (x) = 1 mh m X j=1 Kx−Xj h whe e Kis a densi y unc ion symme ic a ound ze o and his he so-called bandwid h o smoo hing pa ame e . No e ha , de ined in his way, ˆ is a densi y unc ion (a non-nega i e eal unc ion which in eg a es o one). The necessi y o he smoo hing pa ame e comes om he ac ha e e y obse a ion Xiin he sample no only shows ha he e is a posi i e densi y on he eal numbe Xibu also ha he e is a posi i e densi y on a neighbo hood o he eal numbe Xi(no e ha he o iginal a iable is con inuous and we ha e a ini e sample o es ima e i s densi y). The selec ion o his an impo an , hough di icul , issue. The e is a la ge numbe o pape s on he selec ion o he bandwid h pa ame e o gi en classes o es ima o s. Fo a su ey on his opic see Cao e al (1994). Ve y o en, he s a is ical li e a u e has ea ed his p oblem as a di e en one. One issue is o iden i y amilies o densi y es ima o s wi h good s a is ical and compu a ional p ope ies. Ano he di e en issue, which is usually analyzed in a second s age, is o ind a good selec o o he smoo hing pa ame e o a gi en amily o densi y es ima o s. In his pape we ocus on he i s o hese issues and ob ain a densi y es ima o based on he Shapley alue. Ou main a ge is o illus a e a connec ion be ween coope a i e game heo y and s a is ics by showing ha his new es ima o is a compe i i e one om a s a is ical poin o iew. Mo eo e , we p o ide an axioma ic cha ac e iza ion o i . Axioma ic cha ac e iza ions migh be use ul o s a is icians, who 3 ha e some imes se e al p ocedu es o sol e a p oblem and no clea easons o choose one among hose p ocedu es. To model he densi y es ima ion p oblem in game- heo e ical e ms, we p oceed essen ially as ollows: we conside he eal line Ras an in ini e se o playe s o a coope a i e game wi h cha ac e is ic unc ion such ha o any coali ion A(i.e. any subse Ao R), (A) is de e mined by X1, .., Xmand A i sel ; we hen de ine ou es ima o ˆ o as he payo ec o alloca ed by an app op ia e game- heo e ical solu ion concep . The p ecise na u e o ˆ e iden ly depends on bo h he solu ion concep used and he way in which (A) is de e mined by X1, .., Xmand A. In his pape we adop a simple app oach o he la e ques ion, aking (A) p opo ional o he ca dinali y o {X1, .., Xm}∩A0, whe e A0is a se con aining A. To a oid game- heo e ical complica ions, and in he in e es s o compu a ional e iciency (see sec ion 4), we ac ually g oup he poin s o Rin a coun able numbe o “indi isible coali ions“ Ji ha ac as he e ec i e playe s. As no ed abo e, we s a by di iding Rin in e als o he same leng h δ, i.e. R=∪i∈Z[δi, δ(i+ 1)). We deno e [δi, δ(i+ 1)) by Ji( o all i∈Z). Now, o e e y S⊂Z, de ine ¯ (S) = 1 mδ m X j=1 I∪i∈S¯ Ji(Xj) whe e, o all i∈Z,¯ Jiis he se ∪{J | | −i| ≤ k},kbeing a non-nega i e in ege , and IAdeno es he indica o unc ion o A, o any se A⊂R (IA(x) = 1 i x∈A,IA(x) = 0 i x∈R A). Abou ¯ no e ha : 1. ¯ (Z) = 1 δ. In ac , we wan o alloca e 1 δ o he in e als o {Ji|i∈Z} because in his way we can de ine ˆ (x) as he sha e o 1 δ ha Jiob ains (x∈Ji) and, hen, R+∞ −∞ ˆ (x)dx = 1. 2. Fo e e y S⊂Z, ¯ (S) is 1 mδ imes he numbe o obse a ions belonging o an in e al k-close o an in e al in {Ji|i∈S}. This can be in e - p e ed as he maximum densi y ha can be alloca ed o S. Obse e ha kplays he e he ole o he smoo hing pa ame e . Now we can make a TU-game (N, ) ou o he densi y es ima ion p oblem cha ac e ized by he sample X1, ..., Xm: 4 •N={i∈Z|¯ (i)>0}(no e ha N, which is a ini e se , can also be w i en as N={i∈Z|¯ (S∪ {i})−¯ (S)>0 o some S⊂Z}). • is he es ic ion o ¯ o {S|S⊂N}. Abou his game we can make he ollowing commen s: 1. I k= 0 he game is addi i e. I k≥1 he game is subaddi i e and, mo eo e , (N)<Pi∈N (i). As kinc eases, he Jiin e als sha e hei obse a ions wi h mo e neighbo ing in e als, p oducing a smoo hing e ec in he game. 2. I is easy o see ha is a conca e game. 3. can be seen as a cos game. Since (S) can be in e p e ed as he maximum densi y ha should be alloca ed o S, a ai alloca ion x mus belong o he co e o , i.e. X i∈S xi≤ (S) o all S⊂N. Since is a conca e game, i s Shapley alue φ( ) lies in i s co e (see Shapley (1971)). Thus, a p omising es ima o o he densi y unc ion is ha based on φ( ). Fo mally, he Shapley es ima o we p opose is gi en by: ˆ S(x) = φi( ) i x∈Ji,i∈N 0 i x∈Ji,i6∈ N. Since he numbe o playe s in he game may be la ge, calcula ion o ˆ di ec ly om i s de ini ion and ha o he Shapley alue can be e y one ous. The ollowing heo em p o ides a mo e con enien exp ession. Theo em 1 Le (N, )be he TU-game associa ed wi h he densi y es ima- ion p oblem cha ac e ized by he sample X1, ..., Xm. Then, o any i∈N, φi( ) = 1 mδ X ∈Nk(i) n( ) 2k+ 1 whe e n( )deno es he numbe o obse a ions belonging o he in e al J and Nk(i)is he se { ∈N| | −i| ≤ k}. 5 P oo . F om he de ini ion o he Shapley alue, φi( ) = 1 n!X π∈Π(N) 1 mδ X ∈Pk(i,π) n( ) whe e Π(N) is he se o pe mu a ions o N,nis he ca dinali y o he se Nand Pk(i, π) = { ∈Nk(i)|π(i)≤π(s) o all s∈Nk( )}. Now, aking in o accoun ha , o each ∈Nk(i), he ca dinali y o he se {π∈Π(N)|π(i)≤π(s) o all s∈Nk( )} is n!/(2k+ 1), hen X π∈Π(N)X ∈Pk(i,π) n( ) = X ∈Nk(i) n! 2k+ 1n( ) and he heo em ollows.2 3 An axioma ic cha ac e iza ion o he Shap- ley es ima o Taking in o accoun he p ope ies o he Shapley alue, i is possible o p o ide axioma ic cha ac e iza ions o he Shapley es ima o . We p esen one in his sec ion which ollows he ideas in Mye son (1977). Assume ha δ > 0 is ixed. A δ-es ima o is a map which assigns o e e y andom sample X=X1, . . . , Xma densi y unc ion2ˆ Xwhich sa is ies ˆ X(x) = ˆ X(y) o all x, y ∈Jiand all i∈Z. Fo simplici y, we deno e by ˆ X(i) he e alua ion o ˆ Xin any x∈Ji. Obse e ha , since ˆ Xis a densi y unc ion, i holds ha ˆ X(x)≥0 o all x∈Rand ha Pi∈Zˆ X(i) = 1/δ. No e also ha he Shapley es ima o is, in ac , a amily o δ-es ima o s (one o each k∈N; emembe ha kdeno es he smoo hing pa ame e ). 2Fo no a ional con enience, in his sec ion we deno e by ˆ X he densi y es ima ion o a gi en sample X. 6 Le us see some in e es ing p ope ies o he δ-es ima o s. Le X= X1, . . . , Xmbe a andom sample and suppose ha he smoo hing pa ame e k is ixed. We say ha i, j ∈Za e di ec ly connec ed i he e exis s an elemen o he sample Xlsuch ha Xl∈¯ Ji∩¯ Jj. We say ha C⊂Zis a connec ed se i , o e e y i, j ∈C he e exis s a ini e sequence {i1, . . . , i } ⊂ Csuch ha i1=i,i =jand is, is+1 a e di ec ly connec ed o e e y s∈ {1, . . . , −1}. We say ha Cis a connec ed componen o Zi Cis a maximal connec ed subse o Z. The i s p ope y ha we conside is componen e iciency, which s a es ha he densi y ha he δ-es ima o assigns o he in e als in a connec ed componen is he one co esponding o he obse a ions belonging o hose in e als. CE (Componen E iciency). A δ-es ima o is said o sa is y componen e iciency o ki , o e e y andom sample Xand e e y connec ed componen C, X i∈C ˆ X(i) = mC m 1 δ whe e mCis he numbe o obse a ions lying in ∪i∈CJi. No e ha i a δ-es ima o sa is ies CE o k, hen i alloca es densi y equal o ze o o he in e als in whose neighbo hoods he e a e no obse a ions o he sample, mo e p ecisely o hose Jisuch ha P ∈Nk(i)n( ) = 0. The second p ope y ha we in oduce is he ai ness p ope y. In o - mally, his p ope y s a es ha , when es ima ing a densi y unc ion, he inc emen o he densi y due o a pa icula obse a ion is he same o all in e als in he neighbo hood o his obse a ion. F (Fai ness). A δ-es ima o is said o sa is y ai ness o ki , o e e y andom sample X, e e y i, j ∈Zdi ec ly connec ed and e e y Xl∈¯ Ji∩¯ Jj, i holds ha ˆ X(i)−ˆ X Xl(i) = ˆ X(j)−ˆ X Xl(j), whe e X Xlis he sample iden ical o Xexcep o he ac ha Xlhas been shi ed a om he obse a ions o X(mo e p ecisely, i has been shi ed o an in e al J such ha ¯ J ∩¯ Js=∅ o all Jscon aining some obse a ion o X). A s a is ical a gumen o u he explain hese p ope ies is he ollow- ing. As i was ema ked, e e y sample obse a ion Xishows ha he e is a 7 posi i e densi y no only on he eal numbe Xibu also on a neighbo hood o i (gi en by he smoo hing pa ame e ). Ha ing his in mind, CE can be in e p e ed as ha he posi i e densi y gi en by he sample is alloca ed o he igh in e als. F means ha he densi y co esponding o an obse a ion Xiis alloca ed equally o all hose in e als o which i mus be alloca ed. These wo p ope ies a e, in ou opinion, qui e na u al and appealing. Mo e- o e , hey cha ac e ize he amily o he Shapley es ima o s, as he ollowing heo em shows. Theo em 2 Take δ > 0. Fo e e y alue o he smoo hing pa ame e k, he co esponding Shapley es ima o is he unique δ-es ima o sa is ying CE and F. P oo . Clea ly, he Shapley es ima o sa is ies CE and F. In o de o p o e uniqueness, assume ha he e exis wo di e en δ-es ima o s sa is ying CE and F (le us call hem es ima o s 1 and 2). Since hey a e di e en , he e mus exis a sample Xo size msuch ha ˆ 1 X6=ˆ 2 Xand such ha i has a maximal numbe o connec ed componen s among hose samples o size m o which he wo es ima o s p o ide di e en es ima ions. Fo his X, ake a connec ed componen Cand i, j ∈Csuch ha iand ja e di ec ly connec ed. Since bo h es ima o s sa is y F, ˆ X(i)−ˆ X(j) = ˆ X Xl(i)−ˆ X Xl(j) (1) o all ∈ {1,2}and all Xl∈¯ Ji∩¯ Jj. No e now ha ˆ 1 X Xl(i)−ˆ 1 X Xl(j) = ˆ 2 X Xl(i)−ˆ 2 X Xl(j) (2) because, i Xlis he unique obse a ion in ∪k∈CJk, hen all he elemen s in equa ion (2) a e ze os and, o he wise, X Xlhas, a leas , one connec ed componen mo e han Xand hen (2) ollows om maximali y o X. Hence, in iew o (1) and (2), i holds ha ˆ 1 X(i)−ˆ 2 X(i) = ˆ 1 X(j)−ˆ 2 X(j). I is clea ha epea ing his a gumen a ini e numbe o imes, one concludes ha ˆ 1 X(i)−ˆ 2 X(i) is cons an o all i∈C. Since bo h es ima o s sa is y CE ha cons an mus be ze o. This clea ly implies ha ˆ 1 X=ˆ 2 X, which is a con adic ion. 2 8 4 P ope ies o he Shapley es ima o In he sequel, he s a is ical and compu a ional p ope ies o his es ima o will be s udied in compa ison wi h a ke nel es ima o . The Shapley es ima o esul s o be wi hin well-known amilies o densi y es ima o s: i is a binned ke nel densi y es ima o and i is a WARPing- ype densi y es ima o . Binned ke nel densi y es ima o s use some se o binning unc ions wδ i(x) (whe e Pi∈Zwδ i(x) = 1 o all x∈Rand δ > 0) o dis ibu e he weigh o each sample poin Xjamong he in e als Ji( he bins); concen a e he accu- mula ed weigh o each bin a i s cen e , gi; and hen apply a ke nel es ima o o he esul ing weigh ed “sample“ {(gi, Ni)}, whe e Ni=Pm j=1 wδ i(Xj): ˆ B(x) = 1 mh X i∈Z NiK(x−gi h). The Shapley es ima o is a binned ke nel es ima o wi h wδ i(x) = IJi(x), Ni=n(i), K=1 2I[−1,1) and h=δ(k+1 2). WARPing (Weigh ed A e aging o Rounded Poin s) es ima o s use a dis- c e e unc ion w( , i) ( , i ∈Z;Pi∈Zw( , i) = 1 ∀ ∈Z) o dis ibu e he o al weigh o he sample poin s in each bin among he neighbo ing bins: ˆ W(x) = 1 mδ X ∈Z w( , i)n( )∀x∈Ji. I δis small enough, smoo hing is mainly e ec ed by he unc ion w( , i), which is o en de ined in e ms o a smoo hing pa ame e . The Shapley es ima o is a WARPing es ima o wi h w( , i) = 1 (2k+1) i ∈Nk(i), w( , i) = 0 o he wise. Sco (1985) showed ha one pa icula ype o WARPing es ima o , he a e aged shi ed his og am, is simila o he his og am in compu a ional e iciency and o ke nel es ima o s in s a is ical e iciency. By compu a ional e iciency we simply mean li le compu a ional cos s, whe eas s a is ical e iciency e e s o he accu acy o he es ima ion. Resul s on he e iciency o binned ke nel es ima o s ha e been ob ained by Hall and Wand (1996). The objec i e o binning is o educe compu a ional cos s. Compu a ion- ally, he mos e icien es ima o is he his og am, which uses bins wi hou 9