J´at´ekelm´elet ´es h´al´ozati alkalmaz´asai 4. ea Csercsik D´avid ITK PPKE
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
1 / 21
1
Nash bargaining
2
Kooperat´ıv j´at´ekok A karakterisztikus f¨ uggv´eny defin´ıci´ oja TU CFF j´at´ekok tulajdons´agai A mag
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
2 / 21
Nash bargaining
Nash - bargaining (alku) p´elda Bill’s goods book whip ball bat box Jack’s goods pen toy knife hat
Utility to Bill 2 2 2 2 4
utility to Jack 4 2 1 2 1
10 4 6 2
1 1 2 2
Bargaining situation: Maximaliz´aljuk a hasznoss´agv´altoz´asok szorzat´at: Bill Jack-nek adja: book, whip, ball, bat → B:-8, J: +9 Jack Bill-nek adja: pen, toy, knife → J:-4 B: +20 B: +12, J: +5 → 60 Ha pl. a labd´at nem: B: +14 J: +5 → 56 Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
3 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Kooperat´ıv j´at´ekelm´elet
´ althat´o hasznoss´ag´ Atv´ u (TU) j´at´ekok Adott n j´at´ekos, akik ¨ osszefoghatnak egym´assal. Az a j´at´ekoscsoport, amely egy¨ utt cselekszik u ´n. koal´ıci´ot alkot. K¨ ul¨onb¨oz˝o koal´ıci´ok k¨ ul¨ onb¨ oz˝ o hasznoss´agi szintet ´erhetnek el. A koal´ıci´ok hasznoss´aga egym´assal ¨ osszehasonl´ıthat´o.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
4 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Koal´ıci´o alak´ıt´as P´elda a, b, c ´es d j´atszanak ⇒ 16 f´ele k´eppen alak´ıthatnak koal´ıci´ ot.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
5 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Koal´ıci´o alak´ıt´as P´elda a, b, c ´es d j´atszanak ⇒ 16 f´ele k´eppen alak´ıthatnak koal´ıci´ ot. Lehets´eges koal´ıci´ok
u ¨res halmaz {∅}
{a} {b} {c} {d}
Csercsik D´ avid (ITK PPKE)
{a, b} {a, c} {a, d} {b, c} {b, d} {c, d}
{a, b, c} {a, b, d} {a, c, d} {b, c, d}
nagykoal´ıci´ o {a, b, c, d}
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
5 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Koal´ıci´o alak´ıt´as P´elda a, b, c ´es d j´atszanak ⇒ 16 f´ele k´eppen alak´ıthatnak koal´ıci´ ot. Lehets´eges koal´ıci´ok
u ¨res halmaz {∅}
{a} {b} {c} {d}
{a, b} {a, c} {a, d} {b, c} {b, d} {c, d}
{a, b, c} {a, b, d} {a, c, d} {b, c, d}
nagykoal´ıci´ o {a, b, c, d}
Megfigyel´es Egy n-f˝os j´at´ekban 2n a lehets´eges koal´ıci´ ok sz´ama. Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
5 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
´ althat´o hasznoss´ag´u j´at´ekok defin´ıci´oja Atv´
Matematikai megk¨ozel´ıt´es Egy kooperat´ıv j´at´ek karakterisztikus f¨ uggv´eny form´aban egy rendezett p´ar (N, v ) amely ´all egy j´at´ekoshalmazb´ol N = {1, 2, . . . , n} ´es egy karakterisztikus f¨ uggv´enyb˝ ol v : 2N → R ahol v (∅) = 0.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
6 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
´ althat´o hasznoss´ag´u j´at´ekok defin´ıci´oja Atv´
Matematikai megk¨ozel´ıt´es Egy kooperat´ıv j´at´ek karakterisztikus f¨ uggv´eny form´aban egy rendezett p´ar (N, v ) amely ´all egy j´at´ekoshalmazb´ol N = {1, 2, . . . , n} ´es egy karakterisztikus f¨ uggv´enyb˝ ol v : 2N → R ahol v (∅) = 0. Koal´ıci´ok A v (S) sz´amon az S koal´ıci´ o ´ert´ek´et ´ertj¨ uk. Ezt az S koal´ıci´o minden k¨ uls˝o seg´ıts´eg n´elk¨ ul el tudja ´erni. A v (N) sz´am mutatja teh´at a j´at´ekosok ´altal el´erhet˝o ¨osszhasznoss´agot. Ez a ’torta’ amit a r´esztvev˝ok k¨oz¨ott igazs´ags´agosan sz´et kell osztani.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
6 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Egyszer˝u szavaz´asi j´at´ek
P´elda Legyen N egy parlament k´epvisel˝ oinek a halmaza.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
7 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Egyszer˝u szavaz´asi j´at´ek
P´elda Legyen N egy parlament k´epvisel˝ oinek a halmaza. T¨ obbs´egi szavaz´as Legyen S ⊆ N egy k´epvisel˝ ocsoport ekkor |N| ul¨ onben v (S) = 0 v (S) = 1 ha |S| > 2 m´ask¨ K´erd´es Mekkora ’hatalommal’ b´ır egy k´epvisel˝ o?
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
7 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
S´ulyozott szavaz´asi j´at´ek P´elda A Miniszterek Tan´acsa az EU egyik legfontosabb d¨ ont´esi szerve. Az 1958-72 peri´odusban a k¨ ovetkez˝ o szavaz´asi rendszer volt ´erv´enyben:
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
8 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
S´ulyozott szavaz´asi j´at´ek P´elda A Miniszterek Tan´acsa az EU egyik legfontosabb d¨ ont´esi szerve. Az 1958-72 peri´odusban a k¨ ovetkez˝ o szavaz´asi rendszer volt ´erv´enyben: Orsz´ag N´emetorsz´ag Olaszorsz´ag Franciaorsz´ag Hollandia Belgium Luxemburg Kv´ ota
Csercsik D´ avid (ITK PPKE)
S´ uly 4 4 4 2 2 1 12
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
8 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
S´ulyozott szavaz´asi j´at´ek
Banzhaf-index Egy koal´ıci´ o akkor d¨ont˝ok´epes, ha a s´ ulya legal´abb 12. A Banzhaf index kisz´amol´as´ahoz fel´ırjuk az ¨ osszes lehets´eges koal´ıci´ ot, majd megvizsg´aljuk, hogy egy j´at´ekos kil´ep´es´evel d¨ ont˝ ok´epes marad-e. Egy j´at´ekos befoly´as´at u ´gy kapjuk meg, hogy megsz´amoljuk, hogy h´anyszor volt kritikus, majd elosztjuk azzal, hogy az ¨osszes j´at´ekos ¨ osszesen h´anyszor volt kritikus.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
9 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
S´ulyozott szavaz´asi j´at´ek Banzhaf-index A d¨ ont˝ok´epes koal´ıci´ok (piros sz´ınben a kritikus j´at´ekosok): Koal´ıci´o NOHB NFHB OFHB NOHBL NFHBL OFHBL NOF
Csercsik D´ avid (ITK PPKE)
¨ Osszs´ uly 12 12 12 13 13 13 12
Koal´ıci´ o NOFH NOFB NOFL NOFHB NOFHL NOFBL NOFHBL
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
¨ Osszs´ uly 14 14 13 16 15 15 17
10 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
S´ulyozott szavaz´asi j´at´ek Banzhaf-index ¨ Osszesen 42 alkalommal volt kritikus egy j´at´ekos, ebb˝ ol N´emetorsz´ag 10-szer. Azaz N´emetorsz´ag befoly´asa 10 = 0.238. A kapott 42 Banzhaf-indexeket a k¨ovetkez˝ o t´abl´azat ¨ osszegzi. Orsz´ag N´emetorsz´ag Olaszorsz´ag Franciaorsz´ag Hollandia Belgium Luxemburg
Csercsik D´ avid (ITK PPKE)
S´ uly 4 4 4 2 2 1
βi 0.238 0.238 0.238 0.142 0.142 0
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
11 / 21
Kooperat´ıv j´ at´ ekok
A karakterisztikus f¨ uggv´ eny defin´ıci´ oja
Strat´egiailag ekvivalens j´at´ekok
A j´at´ekosok hasznoss´ag-m´er´esi sk´al´aj´anak kezd˝ opontja ´es sk´alaegys´ege is tetsz˝oleges. Ha az U fv. reprezent´alja egy j´at´ekos preferenci´ait, akkor az αU + β is alkalmas a reprezent´aci´ ora. Defin´ıci´o Az (N, v ) j´at´ek strat´egiailag ekvivalens az (N, w ) j´at´ekkal ha l´ eteznek P olyan α > 0 ´es β1 , ..., βn ∈ R sz´amok, hogy w (S) = αv (S) + i∈S βi ∀S ∈ N
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
12 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
TU CFF j´at´ekok tulajdons´agai Az (N, v ) j´at´ek Defin´ıci´o P Addit´ıv, ha v (S) = i∈S v ({i}) ∀S ∈ N S Szuperaddit´ıv, ha v (S) +Tv (T ) ≤ v (S T ) ´all fenn ∀ olyan S, T ∈ N -re, amelyre S T = ∅
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
13 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
TU CFF j´at´ekok tulajdons´agai Az (N, v ) j´at´ek Defin´ıci´o P Addit´ıv, ha v (S) = i∈S v ({i}) ∀S ∈ N S Szuperaddit´ıv, ha v (S) +Tv (T ) ≤ v (S T ) ´all fenn ∀ olyan S, T ∈ N -re, amelyre S T = ∅ Defin´ıci´o Monoton, ha S ⊆ T ⇒ v (S) ≤ v (T ) ∀S, T ∈ N P 0-monoton, ha S ⊆ T ⇒ v (S) + i∈T \S v ({i}) ≤ v (T ) ∀S, T ∈ N Szimmetrikus, ha |S| = |T | ⇒ v (S) = v (T ) ∀S, T ∈ N Egyszer˝ u, ha v (N) = 1 ´es v (S) ∈ {0, 1} ∀S ∈ N
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
13 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
TU CFF j´at´ekok tulajdons´agai II Az (N, v ) j´at´ek Defin´ıci´o S T Konvex, ha v (S) + v (T ) ≤ v (S T ) + v (S T ) ∀S, T ∈ N
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
14 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
TU CFF j´at´ekok tulajdons´agai II Az (N, v ) j´at´ek Defin´ıci´o S T Konvex, ha v (S) + v (T ) ≤ v (S T ) + v (S T ) ∀S, T ∈ N ´ ıt´asok: All´ A konvex j´at´ekok halmaza z´art a strat´egiai ekvivalenci´ara n´ezve (egy konv. j´at´ekkal strat ekv. minden j´at´ek is konv.). v pontosan akkor konvex, ha v (Q ∪ {i}) − v (Q) ≤ v (R ∪ {i}) − v (R) teljes¨ ul minden i ∈ N-re ´es Q ⊆ R ⊆ N \ {i}-re. v addit´ıv ⇒ v konvex ⇒ v szuperaddit´ıv, de az implik´aci´ok nem megford´ıthat´oak Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
14 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
Bizony´ıt´as
´ ıt´as 2 bizony´ıt´asa All´ ⇒ ir´any S := Q ∪ {i} T := R S ∪ T := R ∪ {i} S ∩ T := Q
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
15 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
Bizony´ıt´as II
´ ıt´as 2 bizony´ıt´asa All´ ⇐ ir´any Legyen S \ T = {i1 , i2 , . . . , is }, ekkor v ((S ∩ T ) ∪ i1 ) − v (S ∩ T ) ≤ v (T ∪ i1 ) − v (T ) v ((S ∩ T ) ∪ i1 ∪ i2 ) − v ((S ∩ T ) ∪ i1 ) ≤ v (T ∪ i1 ∪ i2 ) − v (T ∪ i1 ) .. . v (S) − v ((S ∩ T ) ∪ i1 ∪ · · · ∪ is−1 ) ≤ v (S ∪ T ) − v (T ∪ i1 ∪ · · · ∪ is−1 ) egyenl˝otlens´egeket ¨ osszeadva kapjuk az k´ıv´ant ¨ osszef¨ ugg´est.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
16 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
Kifizet´esek Azt mondjuk hogy az (N, v ) j´at´ekban az x = (x1 , ..., xn ) kifizet´es-vektor P
xi ≤ v (S) P elfogadhat´ o az S koal´ıci´ o sz´am´ara, ha i∈S xi ≥ v (S) el´erhet˝o az S koal´ıci´ o sz´am´ara, ha
i∈S
el˝ ony¨osebb S sz´am´ara mint az y = (y1 , ..., yn ) kifizet´es vektor, ha minden tagja sz´am´ara hat´arozottan jobb, azaz xi > yi ∀i ∈ S Az S koal´ıci´ on kereszt¨ ul domin´alja az y = (y1 , ..., yn ) kifizet´es vektort, ha S sz´am´ara x el´erhet˝ o, ´es el˝ ony¨ osebb mint y (jel¨ ol´es: xdomS y ) Nem domin´alt az S koal´ıci´ on kereszt¨ ul, ha nincs olyan az S sz´am´ara el´erhet˝o z kifizet´es vektor, amire zdomS x domin´alja az y = (y1 , ..., yn ) kifizet´es vektort ha ∃ S xdomS y (jel¨ol´es: xdomy ) nem domin´alt ha egyetlen S koal´ıci´ on kereszt¨ ul sem domin´alt. Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
17 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
Kifizet´esek II
´ ıt´asok All´ Az x ∈ Rn kifizet´es-vektor pontosan akkor elfogadhat´ o az S koal´ıci´o sz´am´ara, ha x S-en kereszt¨ ul nem domin´alt. ∀S ∈ N eset´en a domS egy szigor´ u parci´alis rendez´es (azaz aszimmetrikus ´es tranzit´ıv) a kifizet´es-vektorok Rn halmaz´an A dom rel´aci´ o mindig irreflex´ıv, de m´eg egy szupaeraddit´ıv j´at´ekban sem felt´etlen¨ ul aszimmetrikus vagy tranzit´ıv.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
18 / 21
Kooperat´ıv j´ at´ ekok
TU CFF j´ at´ ekok tulajdons´ agai
Kifizet´esek III
Azt mondjuk hogy az (N, v ) j´at´ekban az x = (x1 , ..., xn ) kifizet´es-vektor P sz´etoszt´as ha i∈N xi = v (N) (N sz´am´ara elfogadhat´o ´es el´erhet˝o) P eloszt´as ha i∈N xi = v (N) ´es xi > v ({i}) ∀i ∈ N (individual rationality) P P mag-eloszt´as Ha i∈N xi = v (N) ´es i∈S xi ≥ v (S) ∀S ∈ N (group rationality)
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
19 / 21
Kooperat´ıv j´ at´ ekok
A mag
A mag (The Core) Egy´eni ´es csoportos racionalit´as: X
xi ≥ v (S) ∀S ∈ N
i∈S
pl. (v (1) = v (2) = v (3) = 0): x(1) ≥ 0 , x(2)
≥ 0 , x(1) ≥ 0
x(12) ≥ v (12) , x(23) ≥ v (23) , x(13) ≥ v (13) x(123) ≥ v (123) x(1) + x(2) + x(3)
= v (123)
Ha pl. v (12) = 90, v (13) = 80, v (23) = 70, v (123) = 135, a mag (az (123) koal´ıci´ ora n´ezve) a kifizet´esek ter´eben egy h´aromsz¨ og az al´abbi cs´ ucsokkal: (66,55,15), (65,25,45), (35,55,45). Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
20 / 21
Kooperat´ıv j´ at´ ekok
A mag
A mag LP
Defin´ıci´o Az e ∈ {0, 1}N vektorra azt mondjuk hogy az S ⊆ N koal´ıci´o tags´agi vektora, ha / S eset´en pedig eSi = 0 i ∈ S eset´en eSi = 1 i ∈ Adott (N, v ) j´at´ek eset´en tekints¨ uk a k¨ ovetkez˝ o LP-t: min eN x eS x x
≥ v (S) S ∈ N ∈ R
A mag (ha nem u ¨res) mindig egy hipers´ıkokkal hat´arolt poli´eder a kifizet´esek ter´eben.
Csercsik D´ avid (ITK PPKE)
J´ at´ ekelm´ elet ´ es h´ al´ ozati alkalmaz´ asai 4. ea
21 / 21
