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