Regressziós játékok. Pintér Miklós. XXVII. OPKUT Konferencia 2007, június 7-9. Balatonöszöd. Budapesti Corvinus Egyetem Matematika Tanszék

Felépítés Statisztikus játékok A statisztikus Shapley-érték axiomatizációja Regressziós játékok

Regressziós játékok Pintér Miklós Budapesti Corvinus Egyetem Matematika Tanszék

XXVII. OPKUT Konferencia 2007, június 7-9. Balatonöszöd

Pintér Miklós

Regressziós játékok


Tartalomjegyzék

1

Statisztikus játékok

2

A statisztikus Shapley-érték axiomatizációja

3


Pintér Miklós



Statisztikus játék

Definíció Legyen (Ω, M, P) valószínűségi mező rögzítet, v : Ω × P(N) → R egy függvény, hogy ∀S ∈ P(N)-re, v (·, S) egy valószínűségi változó aminek van várhatórétéke, és ∀ω ∈ Ω-ra, v (ω, ∅) = 0, ahol N = {1, . . . , n} a játékosok véges halmaza. Ekkor a v függvényt statisztikus játéknak nevezzük.

Pintér Miklós



Példa

Példa Legyen Ω = {ω1 , ω2 }, M = P(Ω), P({ω1 }) = v (ω1 , {1}) = 0 1 v (ω1 , {2}) = 4 1 v (ω1 , {3}) = 3 1 v (ω1 , {1, 2}) = 3 1 v (ω1 , {1, 3}) = 3 3 v (ω1 , {2, 3}) = 8 2 v (ω1 , {1, 2, 3}) = 5

Pintér Miklós

1 , N = 3. 3

v (ω2 , {1}) = 0 1 v (ω2 , {2}) = 4 1 v (ω2 , {3}) = 2 1 v (ω2 , {1, 2}) = 3 1 v (ω2 , {1, 3}) = 2 5714 v (ω2 , {2, 3}) = 10000 3 v (ω2 , {1, 2, 3}) = 5



A statisztikus játékok részosztályai

Definíció A v ∈ G N statisztikus játék (S, T ∈ P(N)) monoton, ha (S ⊆ T ) ⇒ (v (S) ≤P-m.m. v (T )),

Pintér Miklós




Definíció A v ∈ G N statisztikus játék (S, T ∈ P(N)) monoton, ha (S ⊆ T ) ⇒ (v (S) ≤P-m.m. v (T )), additív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) =P-m.m. v (S ∪ T )),

Pintér Miklós




Definíció A v ∈ G N statisztikus játék (S, T ∈ P(N)) monoton, ha (S ⊆ T ) ⇒ (v (S) ≤P-m.m. v (T )), additív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) =P-m.m. v (S ∪ T )), szuperadditív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) ≤P-m.m. v (S ∪ T )),

Pintér Miklós




Definíció A v ∈ G N statisztikus játék (S, T ∈ P(N)) monoton, ha (S ⊆ T ) ⇒ (v (S) ≤P-m.m. v (T )), additív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) =P-m.m. v (S ∪ T )), szuperadditív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) ≤P-m.m. v (S ∪ T )), szubadditív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) ≥P-m.m. v (S ∪ T )),

Pintér Miklós




Definíció A v ∈ G N statisztikus játék (S, T ∈ P(N)) monoton, ha (S ⊆ T ) ⇒ (v (S) ≤P-m.m. v (T )), additív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) =P-m.m. v (S ∪ T )), szuperadditív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) ≤P-m.m. v (S ∪ T )), szubadditív, ha (S ∩ T = ∅) ⇒ (v (S) + v (T ) ≥P-m.m. v (S ∪ T )), P lényeges, ha v (N) >P-m.m. v ({i}). i∈N

Pintér Miklós



Statisztikus Shapley-érték

Definíció Legyen i ∈ N tetszőlegesen rögzített, és legyen vi0 (S) = v (S ∪ {i}) − v (S), ahol S ⊆ N. Definíció i i Legyen P8 Sh = P × fSh szorzatmérték, ahol < |S|!(|N| − |S| − 1)! , ha i ∈ /S i fSh (S) = . |N|! : 0 különben

Pintér Miklós



Statisztikus Shapley-érték

Definíció Legyen v ∈ G N tetszőleges statisztikus játék rögzített. Ekkor az i játékos statisztikus Shapley-értéke φSi a következő Z

φSi (v ) =

i vi0 dPSh

(Ω×N,M⊗P(N))

X |S|!(|N| − |S| − 1)! = |N|! S∈P(N)

Z

vi0 (S) dP ,

(Ω,M)

Pintér Miklós



Megoldás

Definíció Legyen B ⊆ G N rögzített. A ψ : B → RN függvényt a B halmazon értelmezett megoldásnak nevezzük. Definíció ψ, a B ⊆ G N halmazon értelmezett megoldás a statisztikus Shapley-érték megoldás (φS ), ha ∀v ∈ B-re, ψ(v ) a v játék statisztikus Shapley-értékeinek vektora. Definíció Legyen v ∈ G N tetszőlegesen rögzített. Ekkor i ∼vP-m.m. j (i, j ∈ N), ha vi0 (S) =P-m.m vj0 (S) ∀S ⊆ N-re, hogy i, j ∈ / S.

Pintér Miklós



Tulajdonságok Definíció Legyen B ⊆ G N tetszőlegesen rögzített, és legyen ψ a B halmazon értelmezett megoldás. A ψ megoldás P statisztikusan Pareto-optimális (SPO), ha ∀v ∈ B-re, ψi (v ) i∈N R = v (N) dP, Ω

Pintér Miklós




statisztikusan nulla játékos tulajdonságú (SNP), ha ∀v ∈ B-re, (vi0 = P-m.m. 0) ⇒ (ψi (v ) = 0),

Pintér Miklós




statisztikusan nulla játékos tulajdonságú (SNP), ha ∀v ∈ B-re, (vi0 = P-m.m. 0) ⇒ (ψi (v ) = 0), statisztikusan egyenlően kezelő (SETP), ha ∀v ∈ B-re, (i ∼vP-m.m. j) ⇒ (ψi (v ) = ψj (v )),

Pintér Miklós




statisztikusan nulla játékos tulajdonságú (SNP), ha ∀v ∈ B-re, (vi0 = P-m.m. 0) ⇒ (ψi (v ) = 0), statisztikusan egyenlően kezelő (SETP), ha ∀v ∈ B-re, (i ∼vP-m.m. j) ⇒ (ψi (v ) = ψj (v )), statisztikusan additív (SADD), ha ∀v , w ∈ B-re, hogy ∃z ∈ B, z =P-m.m. v + w , ψ(z) = ψ(v ) + ψ(w ).

Pintér Miklós




statisztikusan nulla játékos tulajdonságú (SNP), ha ∀v ∈ B-re, (vi0 = P-m.m. 0) ⇒ (ψi (v ) = 0), statisztikusan egyenlően kezelő (SETP), ha ∀v ∈ B-re, (i ∼vP-m.m. j) ⇒ (ψi (v ) = ψj (v )), statisztikusan additív (SADD), ha ∀v , w ∈ B-re, hogy ∃z ∈ B, z =P-m.m. v + w , ψ(z) = ψ(v ) + ψ(w ). statisztikusan monoton (SM) / statisztikusan egyenlőség monoton (SEM), ha ∀v , w ∈ B-re, (vi0 ≤P-m.m. / =P-m.m. wi0 , i ∈ N) ⇒ (ψi (v ) ≤ / = ψi (w )). Pintér Miklós



Statisztikus alapjátékok

Definíció v ∈ G N statisztikus alapjáték, ha (i, j ∈ / SNP(v )) ⇒ (i ∼vP-m.m. j), ahol 0 SNP(v ) = {h ∈ N | vh =P-m.m. 0}. Következmény Ha v ∈ G N statisztikus alapjáték, akkor tetszőleges α ∈ R-ra, αv szintén statisztikus alapjáték. Definíció (Ω, M, P) reprezentálja R ⊆ ∆(A, B(A))-t, ahol A ⊆ Rn , ha tetszőleges µ ∈ R-ra, ∃v : Ω → A, hogy ∀C ∈ B(A)-ra µ(C ) = P(v −1 (C )).

Pintér Miklós



A Shapley-féle axiomatizálás

Tétel Legyen M ∈ N és B ⊆ G N olyan, hogy (Ω, M, P) reprezentálja ∆M A -t, és tetszőleges v ∈ B-re ∃v1 , . . . , vk ∈ B statisztikus alapjátékok k ≤ M, hogy 1

a v1 , . . . , vk generálta kúp B-ben van,

2

∃α1 , . . . , αk ∈ R súlyok, hogy v =P-m.m.

k P

αi vi .

i=1

Ekkor ψ a B halamzon értelmezett megoldás pontosan akkor SPO, SNP, SETP és SADD, ha ψ = φS .

Pintér Miklós



A Young-féle axiomatizálás

Tétel Legyen M ∈ N és B ⊆ G N olyan, hogy (Ω, M, P) reprezentálja ∆M A -t, és tetszőleges v ∈ B-re ∃v1 , . . . , vk ∈ B statisztikus alapjátékok k ≤ M, hogy 1

a v1 , . . . , vk generálta kúp B-ben van,

2

∃α1 , . . . , αk ∈ R+ súlyok, hogy v =P-m.m.

k P

αi vi .

i=1

Ekkor ψ a B halamzon értelmezett megoldás pontosan akkor SPO, SETP és SEM, ha ψ = φS .

Pintér Miklós



Alapfogalom

Definíció Legyen N = {ξ1 , . . . , ξn } a játékosok halmaza, ahol ξi olyan valószínűségi változó amelynek létezik a varianciája i = 1, . . . , n. var(η) − var(η −

P

βi ξi )

→

max (1)

i∈S

βi ∈ R, i ∈ S Definíció Legyen ω ∈ Ω tetszőlegesen rögzített, ahol ω a magyarázott (η) és a magyarázó változók (ξ1 , . . . , ξn ) körét. ∀S ∈ P(N)-re legyen v (ω, S) az (1) feladat megoldása.

Pintér Miklós



Példa

Példa 1 Legyen Ω = {ω1 , ω2 }, M = P(Ω), P({ω1 }) = , N = 3. A kovarianciamátrix 3 az ω1 világállapotban 1 0 1 0 1 1 B 0 1 −1 0 C C , B @ 1 −1 4 2 A 1 0 2 3 és az ω2 világállapotban 0

2 B 0 B @ 1 1

0 1 −1 0

Pintér Miklós

1 −1 4 1

1 1 0 C C . 1 A 2



Axiomatizálások

Tétel Legyen (Ω, M, P) = ([0, 1], B([0, 1]), λ). Ekkor ψ a GRN halmazon értelmezett megoldás pontosan akkor SPO, SNP, SETP és SADD, ha ψ = φS . Tétel Legyen (Ω, M, P) = ([0, 1], B([0, 1]), λ). Ekkor ψ a GRN halmazon értelmezett megoldás pontosan akkor SPO, SETP és SM, ha ψ = φS .

Pintér Miklós


Regressziós játékok. Pintér Miklós. XXVII. OPKUT Konferencia 2007, június 7-9. Balatonöszöd. Budapesti Corvinus Egyetem Matematika Tanszék

Recommend Documents