A Shapley-megoldás airport játékokon

A Shapley-megoldás airport játékokon

Szakdolgozat

Készítette: Márkus Judit

Alkalmazott közgazdaságtan alapszak

Közgazdaságtudományi Kar

Szakszemináriumvezet®:

Pintér Miklós Péter, egyetemi docens Matematika Tanszék Budapesti Corvinus Egyetem, Közgazdaságtudományi Kar

Budapesti Corvinus Egyetem Közgazdaságtudományi Kar 2011

Tartalomjegyzék

1. Bevezetés

1

2. TU játékok

3

3. Az airport játékok osztálya

11

4. A Shapley-érték két axiomatizálása

16

5. Airport probléma és airport játék

21

5.1.

A modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.2.

Tulajdonságok megfeleltetése . . . . . . . . . . . . . . . . . . . . . . .

24

5.3.

Dubey(1982) valamint Moulin és Shenker(1992) eredménye . . . . . .

26

6. Összefoglalás

28

Irodalomjegyzék

29

II

1. fejezet Bevezetés

A dolgozatban egy költségelosztási problémát szeretnénk megoldani. A költségelosztási problémák a gazdasági élet számos területén el®fordulnak. Ahol egy adott szolgáltatást együttesen több ember vesz igénybe, rögtön felmerül a kérdés, hogy az adott szolgáltatás költségét milyen arányban osszák el az igénybevev®k között. A költségelosztási probléma indukál egy költségjátékot. Ha az egyes játékosok összefogásából megszület® koalíció költsége az ®t alkotó játékosok költségének maximuma, akkor airport játékról beszélhetünk. Dolgozatunk középpontjában az airport játékok osztálya áll. A dolgozatot egy elméleti áttekintéssel kezdjük, amelyben bemutatjuk az átruházható hasznosságú kooperatív játékokat, röviden TU játékokat. Ebben a fejezetben a kés®bbi vizsgálatokhoz elengedhetetlenül szükséges fogalmakat, állításokat tárgyaljuk. Bemutatásra kerül egy fontos fogalom, a Shapley-érték és ehhez kapcsolódóan a Shapley-megoldás. A költségek elosztásának kérdésekor fontos szerep jut a Shapley-megoldásnak. Valamint igyekszünk gyakorlati példával rávilágítani arra, hogy a költségek elosztásánál használt axiómák jogosan elvárt tulajdonságokat fogalmaznak meg az elosztásra nézve. Ezután részletesen bemutatásra kerülnek az airport játékok, valamint ezen játékok fontosabb tulajdonságai. Majd igazoljuk, hogy a Shapley (1953) és Young (1985) tételek teljesülnek az airport játékok osztályán is. A Shapley-érték Youngféle axiomatizálásának igazolásához az eredeti Young-féle bizonyítást alkalmazzuk. Az állítást, hogy a fent említett tételek teljesülnek az airport játékok osztályán, el®ször Dubey (1982) illetve Moulin és Shenker (1992) igazolták. A Thomson (2007) cikk egy áttekintést ad az airport játékok osztályán elért eredményekr®l. Dolgozatunkban feldolgozzuk az említett cikk egyes fejezeteit. A cikkre támaszkodva igazoljuk Dubey (1982) illetve Moulin és Shenker (1992) eredményeit. A bizonyítás menete során megmutatjuk, hogy a Thomson (2007) cikk axiómái

1

megfeleltethet®k a szokásos játékelméleti axiómáknak és mivel a Shapley-érték eredeti Shapley-féle és Young-féle axiomatizációját belátjuk airport játékokra az el®z® fejezetben, így Dubey illetve Moulin és Shenker eredményei könnyen igazolhatóak. Ezzel a bizonyítással új igazolást adunk a Dubey (1982) illetve Moulin és Shenker (1992) eredményekre. A témakörben több alkalmazás, eredmény megtalálható magyar nyelven is a következ® munkákban: Csóka (2003), Balog et al. (2010), Pintér (2007), Pintér (2009) és Solymosi (2007). A dolgozatban az airport játékok osztályán a Shapley-érték Shapley-féle és Youngféle axiomatizációjának igazolásakor megmutatjuk, hogy ha az airport játék megoldása rendelkezik bizonyos tulajdonságokkal, akkor a megoldás csak a Shapleymegoldás lehet. A Forgó és Olajos (1991) cikk eredménye szerint pedig nem a Shapley-megoldás az egyetlen ilyen megoldás. Az eltér® eredmény a tulajdonságok deniálásából adódik. Jelen dolgozatban az egyenl®en kezel® (ami ebben a környezetben ekvivalens a szimmetriával) tulajdonsággal dolgozunk, míg az említett cikk egy olyan szimmetria tulajdonságot használ, amely az ETP-nél gyengébb.

2

2. fejezet TU játékok

Ebben a fejezetben célunk a TU játékok bemutatása, a dolgozat kés®bbi fejezeteiben el®forduló fogalmak bevezetése és a fontosabb eredmények áttekintése. Ebben segítségünkre volt a Peleg és Sudhölter (2003) könyv, valamint a következ® cikk és elektronikus jegyzet: Pintér (2009) és Solymosi (2007). Legyen

N

a játékosok egy nemüres, véges halmaza. A játékosok egy

S ⊆ N

∅

pedig az

részhalmazát koalíciónak nevezzük. Speciálisan, az üres koalíció. Az

N

2.1. Deníció.

Legyen

P(N ) → R

N

a nagykoalíció, az

halmaz összes részhalmazainak osztályát

N 6= ∅, |N | < ∞

olyan függvény, melyre

P(N )

jelöli.

a játékosok egy halmaza. Legyen

v(∅) = 0.

Ekkor a

v -t

v :

átruházható hasznosságú

kooperatív játéknak ( coalitional game with transferable utility, röviden TU game) nevezzük. Valamint jelölje

GN

az N játékoshalmazzal rendelkez® TU játékok osztályát.

Az átruházható hasznosságú játékok leggyakoribb reprezentációja a következ®: a koalíciók emberek csoportját jelentik, a kizetések pedig pénzben értend®k, amit a koalíció tagjai tetsz®legesen feloszthatnak maguk között. A denícióban szerepl®

v

függvény a különböz® koalíciókhoz rendel más-más kizetést. (A kizetést mér-

hetjük pénzben vagy bármilyen tetsz®leges mértékegységben, vagy pedig jelenthet hasznosságot is.)

2.2. Deníció. S⊆N

v ∈ GN

koalíció esetén, hogy

2.3. Deníció. minden

Egy

Egy

S, T ⊆ N

2.4. Példa.

játék duálisa az a

v¯ ∈ G N

játék, amelyre teljesül minden

v¯(S) = v(N ) − v(N \ S).

v ∈ GN

játék monoton, ha

S ⊆ T ⇒ v(S) ≤ v(T )

teljesül

koalíció esetén.

Legyen

N = {1, 2, 3}

és legyen

v

a következ®:

v({1}) = 1, v({2}) = 2,

v({3}) = 1, v({1, 2}) = 3, v({1, 3}) = 3, v({2, 3}) = 4, v({1, 2, 3}) = 4.

Látható,

hogy a nagykoalíció értékénél (4) nem nagyobb az egyes játékosok kizetése (rendre

1,2,1),

valamint a kétszemélyes koalíciók kizetése (rendre

3

3,3,4)

is kisebb vagy

egyenl®, mint a nagykoalíció kizetése. Valamint a kétszemélyes koalíciók kizetése (rendre

3,3,4)

nem kisebb, mint az egy f®s koalíciók értéke (rendre

2.5. Deníció. amire

Egy

S∩T =∅

2.6. Példa.

v ∈ GN

játék szubadditív, ha minden

igaz, teljesül, hogy

Legyen

N = {1, 2, 3}

1,2,1).

S, T ⊆ N

koalícióra,

v(S) + v(T ) ≥ v(S ∪ T ). v

és legyen

a következ®:

v({1}) = 1, v({2}) = 2,

v({3}) = 1, v({1, 2}) = 3, v({1, 3}) = 2, v({2, 3}) = 2, v({1, 2, 3}) = 3.

Itt hat

esetet kell vizsgálni (az üres halmaz esetében mindig teljesül a feltétel), ugyanis az

S, T

részhalmazok metszetének üresnek kell lennie, ami az

{3}-{1, 2}, {1}-{2}, {1}-{3}

és

{2}-{3}

{1}-{2, 3}, {2}-{1, 3},

részhalmazpárokra teljesül. Az els® három

részhalmazpár esetében az unió a nagykoalíció. Az egyéni kizetés (rendre és a hozzátartozó kétszemélyes koalíció kizetésének (rendre

2,2,3)

1,2,1)

összege mind-

egyik esetben nem kisebb a nagykoalíció kizetésénél (3). A második és a harmadik esetben szigorú egyenl®tlenséggel, az els® esetben egyenl®séggel teljesül a megadott feltétel. A második három halmazpár esetében az unió a kétszemélyes koalíciókat jelenti. A két f®s koalíciók értéke (rendre

3,2,2) nem nagyobb a hozzátartozó két egy

f®s koalíció kizetéseinek összegénél (rendre

3,2,3).

Látható, hogy az els® két eset-

ben egyenl®séggel, az utolsó esetben szigorú egyenl®tlenséggel teljesül a megadott feltétel.

2.7. Deníció. hogy

Egy

v ∈ GN

játék konkáv, ha minden

S, T ⊆ N

koalícióra teljesül,

v(S) + v(T ) ≥ v(S ∪ T ) + v(S ∩ T ).

2.8. Állítás.

Minden konkáv játék szubadditív.

Bizonyítás. Szubadditív játékok esetén csak ez esetben

v(S ∩ T ) = 0,

2.9. Deníció.

Egy

S ∩T = ∅ halmazokat kell nézni, viszont

amib®l az állítás adódik.

c ∈ GN

játék költségjáték, ha nemnegatív, monoton és szubad-

ditív. (A nemnegatív tulajdonság azt jelenti, hogy Tehát költségjáték alatt egy olyan

c : P(N ) → R+ ∪ {0})

c függvényt értünk, ami a különböz® koalíciók-

hoz nemnegatív értéket rendel. Ez az érték szimbolizálja, hogy az egyes koalícióknak mennyibe kerül egy adott szolgáltatást igénybe venni. Beszélhetünk még költségelosztási problémáról is (cost allocation problem), amikor adottak az egyes játékosok költségei és ekkor a feladat a nagykoalíció költségének, vagyis az összköltségnek az elosztása a játékosok között.

2.10. Deníció.

A

ψ : A ⇒ RN

függvényt, ahol

megoldásnak nevezzük.

4

A ⊆ G N , az A halmazon értelmezett

⇒

Megjegyzés: A

jelölést halmazérték¶ függvény megadására alkalmazzuk.

2.11. Deníció (Gillies (1959)). S⊆N

a játékosok egy az

c∈G

N

Legyen

N = {1, 2, . . . , n} a játékosok egy halmaza,

részhalmaza pedig koalíció. A költségfüggvényt jelölje

költségjáték magján a következ®t értjük:

( n

x∈R :

Core(c) =

n X

) xi = c(N ), minden S

-re

i=1

2.12. Példa.

Legyen

X

xi ≤ c(S)

i∈S

N = {1, 2, 3}

c

és legyen

a következ®:

c({1}) = c({2}) =

c({3}) = 1, c({1, 2}) = 1, c({1, 3}) = c({2, 3}) = 2, c({1, 2, 3}) = 2.

Ekkor a követ-

kez® egyenl®ségnek és egyenl®tlenségeknek kell teljesülni ahhoz, hogy az a játék magja legyen: (1)

x1 + x3 ≤ 2, hogy

x3 ≥ 1.

x1 ≤ 1,

x2 + x3 ≤ 2,

(6)

(7)

x2 ≤ 1,

(2)

(3)

x1 + x2 + x3 = 2.

Ezt összevetve (3)-mal adódik, hogy

vetkez® adódik: (8)

x1 + x2 = 1.

Mivel

megegyeznek (1)-gyel és (2)-vel. Vagyis

x3 = 1, x1

és

x3 ≤ 1,

(4)

x

vektor

x1 + x2 ≤ 1,

(5)

(4) és (7) alapján az következik,

x3 = 1.

Ez alapján (7)-b®l a kö-

ezért (5) és (6) összefüggések rendre

x2

áll még (1), (2), (4) és (8). Az ezeket teljesít® igaz:

c. Ekkor

meghatározásához rendelkezésünkre

x1

és

x2

komponensekre a következ®

x1 = 1 − x2 , ahol x1 , x2 ≥ 0. Tehát a játék magját azok az x = (x1 , x2 , x3 ) vek-

torok alkotják, melyek komponenseire a fent említett összefüggések igazak, vagyis:

x1 = 1 − x2 ,

ahol

x1 , x2 ≥ 0

és

x3 = 1.

Látható, hogy a példában szerepl® játék

magja nemüres, vektorok egy halmazából áll. Megjegyzés: El®fordulhat, hogy egyetlen vektor sem elégíti ki a feltételeket, vagyis olyankor a mag üres.

2.13. Deníció. tett. Ekkor az

i

Tekintsünk egy

játékos

deniálhatjuk: minden Vagyis

vi 0 (S)

v

v ∈ GN

S ⊆ N -re

az i játékos a

v

legyen

vi 0 (S) := v(S ∪ {i}) − v(S).

játékbeli határhozzájárulása az

Legyen

X

v ∈ GN

vi 0 (S)

S⊆N \{i}

jelölje

tetsz®legesen rögzí-

S

koalícióhoz.

tetsz®legesen rögzített, és minden

legyen

φi (v) := Ekkor

i∈N

játékbeli határhozzájárulási függvényét a következ®képpen

2.14. Deníció (Shapley (1953)). i ∈ N -re

játékot és legyen

φi (v)-t

az i játékos

v

φ(v) = (φi (v))i∈N ∈ RN

játékbeli Shapley-értékének nevezzük. A továbbiakban a Shapley-megoldást.

Az összegzésben azért csak azok az nem szerepel, mert a

0

vi (S)

|S|!(|N \ S| − 1)! . |N |!

S

koalíciók szerepelnek, amiben az

i

játékos

határhozzájárulás 0 azokban az esetekben, amikor az

5

i

játékos tagja az

S

koalíciónak, valamint

i

a számlálóban. Ha az

S =N

játékos nem tagja az

koalícióba való belépéssel

S

esetén -1 faktoriális jelenne meg koalíciónak, akkor az

i

játékos a

vi 0 (S) töblettel járul hozzá a koalíció értékéhez ceteris pa-

ribus. Tegyük fel, hogy a koalíciók az egyes játékosok véletlenszer¶ (például érkezési) sorrendjéb®l alakulnak ki, vagyis az azonos számú koalíciók bekövetkezésének valószín¶sége megegyezik. Az összes játékos sz®leges koalíció. Az van, míg az

i-t

|N |!

féleképpen érkezhet. Legyen

S

egy tet-

i el®tt megérkez® S koalíció tagjainak |S|!-féle érkezési sorrendje N \ (S ∪ i)-beli

követ®

játékosok

(|N \ S| − 1)!-féleképpen

érkezhet-

. nek. Ekkor ha i ∈ / S , akkor az S koalíció megalakulásának valószín¶sége |S|!(|N|N\S|−1)! |! |S|!(|N \S|−1)! 0 Így az i játékos hozzájárulása az S koalícióhoz várhatóan vi (S) , vagyis |N |! a

φi (v)

Shapley-érték valójában nem más, mint várhatóérték.

2.15. Példa.

Legyen

N = {1, 2, 3}

és legyen

c

a következ®:

c({1}) = 1, c({2}) = 2,

c({3}) = 3, c({1, 2}) = 2, c({1, 3}) = 3, c({2, 3}) = 4, c({1, 2, 3}) = 5. A három játékos összes lehetséges sorrendje: 1. játékos

1 1 2 2 3 3

2. játékos

2 3 1 3 1 2

3. játékos

3 2 3 1 2 1

Játékosonkénti határhozzájárulások: 1. játékos

1 1 0 0 1 1

2. játékos

1 2 2 2 2 1

3. játékos

3 2 3 3 2 3

A Shapley-értékek:

1 2 φ1 (c) = (1 + 1 + 0 + 0 + 1 + 1) = 6 3 1 φ2 (c) = (1 + 2 + 2 + 2 + 2 + 1) = 6 1 φ3 (c) = (3 + 2 + 3 + 3 + 2 + 3) = 6

5 3 8 3

Látható, hogy a Shapley-érték egyenl® súlyt rendel minden játékoshoz, ezt nevezzük a Shapley-érték normatív tulajdonságának.

2.16. Állítás.

A konkáv költségjátékok magja tartalmazza a Shapley-megoldást.

Bizonyítás. Az Ichiishi (1981) és Shapley (1971) tételek szerint konvex játékok magja tartalmazza a Shapley-megoldást. A játék magjának illetve a költségjáték magjának deníciójából és az el®bb említett tételekb®l következik az állítás.

6

2.17. Deníció.

Legyen a

v ∈ GN

S ⊆ N -re,

játékosok ekvivalensek a v játékban, ha minden igaz, hogy

vi 0 (S) = vj 0 (S).

i, j ∈ S -re i a

v

és

j

Jelölés:

i, j ∈ N

játék tetsz®legesen rögzített. Ekkor az

i ∼v j .

Valamint, ha

ekvivalensek a v játékban (i

v

∼ j ),

amelyre

S⊆N

akkor az

i, j ∈ /S

teljesül,

olyan, hogy minden

S

ekvivalenciahalmaz

játékban.

2.18. Deníció. ψ , •

P

P O),

ha minden

i∈N

játékra és

v∈A

játékra tel-

ψi (v) = v(N ),

i∈N

játékosra teljesül, hogy

N P ),

ha tetsz®leges

(vi 0 = 0) ⇒ (ψi (v) = 0),

egyenl®en kezel® (equal treatment property, röviden játékra teljesül, hogy

•

játékosztályon értelmezett megoldás

nulla játékos tulajdonságú (null player property, röviden

v∈A •

A ⊆ GN

Pareto-optimális (Pareto optimal, röviden jesül, hogy

•

az

ET P ),

ha minden

v∈A

v

(i ∼ j) ⇒ (ψi (v) = ψj (v)),

additív (additive, röviden

ADD),

v, w ∈ A

ha minden

játékra, amelyre

v + w ∈ A : ψ(v + w) = ψ(v) + ψ(w), •

marginális (marginal, röviden játékra teljesül, hogy

0

M ),

ha minden

i ∈ N

játékosra és

v, w ∈ A

0

(vi = wi ) ⇒ (ψi (v) = ψi (w)).

Vagyis a denícióban említett

ψ

megoldás

P O,

ha minden játék esetén teljesül

az, hogy a megoldás által az egyes játékosokhoz rendelt értékek összege kiadja a nagykoalíció értékét. A

ψ

megoldás

NP ,

ha minden játékban minden olyan játékos

esetén, akinek a játékban a határhozzájárulása

0

kizetést rendel. A

ψ

megoldás

ET P ,

sokhoz ugyanakkora értéket rendel. A

ψ

0,

a megoldás ehhez a játékoshoz

ha minden játékban az ekvivalens játékomegoldás

ADD,

ha két olyan játék esetén,

melyek összege is benne van a megoldás értelmezési tartományában, a két játék összegének megoldása megegyezik a két játék megoldásának összegével. A dás

M,

ψ

megol-

ha minden játékosra, akinek a határhozzájárulása megegyezik két játékban,

a megoldás egyenl® értéket rendel mindkét játékban az adott játékoshoz. A fenti tulajdonságok közül a

P O, N P

és az

ET P

a játékosok közötti viszonyt írják le, míg az

tulajdonságok egy adott játékon belül

ADD

és a

M

tulajdonságok két játék

között teremtenek összefüggést. Az alábbiakban egy gyakorlati példán keresztül igyekszünk rávilágítani arra, hogy mennyire jogos elvárás, hogy egy költségelosztási problémára épül® költségjáték megoldása rendelkezzen a fenti tulajdonságokkal.

7

2.19. Példa.

Egy társasház rendezni szeretné egy adott id®szaki számláját, amit a

szolgáltató a szemét elszállításáért számolt fel, és a szemétszállítás díját fel szeretné osztani a tulajdonosok között. Tegyük fel, hogy az elszállított hulladék mennyisége után kell a háznak zetnie.

• P O tulajdonság: A lakóktól beszedett pénz nem lehet kevesebb, mint a számla értéke, mert akkor nem tudják azt kiegyenlíteni. Viszont a számla összegénél többet nem szednek be, mert csak ennek az adott szolgáltatásnak a költségét osztják szét ebben a szituációban.

• NP

tulajdonság: Tegyük fel, hogy az el®bbi társasháznak van olyan lakástulaj-

donosa, akinek a lakása üresen áll az adott id®szakban. Ekkor feltehetjük, hogy a tulajdonosnak nem is keletkezett elszállítandó szemete a vizsgált id®szakban. A költségek elosztásánál ez esetben jogos elvárás, hogy ennek a tulajdonosnak ne kelljen zetnie, ugyanis nem vesz igénybe szolgáltatást.

• ET P

tulajdonság: A szemétszállítás költségeinek elosztásánál vannak ekvi-

valensnek tekinthet® játékosok, akik nagyjából azonos mennyiség¶ szemetet termelnek. Egy lakásban keletkez® szemét mennyiségét befolyásolja, hogy hányan laknak az ingatlanban, milyen korúak az egy háztartásban él®k, milyen gyakran van náluk nagyobb összejövetel és ehhez hasonló szempontok. Ennek megfelel®en, ha lakik a házban két atal házaspár egy-egy csecsem®vel, ahol a házaspárok ritkán fogadnak vendégeket, akkor ez a két házaspár tekinthet® ekvivalens játékosoknak. Ez esetben elvárható, hogy a két család ugyanannyit zessen a szemétszállításért. A következ® két tulajdonság esetében tegyük fel, hogy a szemétszállítás költségeinek elosztási problémáját két id®szakon keresztül vizsgáljuk, és azt, hogy a szolgáltatás díja a vizsgált két id®szakban megegyezik.

• ADD tulajdonság: Ha az egyes tulajdonosok által zetend® összegeket összeadjuk a két id®szakra, jogosan várható el, hogy így ugyanannyit kelljen zetniük, mintha egy id®szakként vizsgáltuk volna a két id®tartamot.

• M

tulajdonság: Ahogy fentebb említettük, tekintsük a szemétszállítás költsé-

geinek elosztását két id®szakra azonos szolgáltatási díj mellett és egy adott tulajdonosra nézve. Ha azt tapasztaljuk, hogy a lakó a két id®szakban ugyanannyival járult hozzá a ház által felhalmozott hulladék mennyiségéhez, akkor jogos elvárás, hogy a tulajdonosnak ugyanannyit kelljen zetnie mindkét id®szakban.

8

A következ® eredmény jól ismert az irodalomban, így igazolásától eltekintünk.

2.20. Állítás.

A Shapley-megoldás

P O, N P , ET P , ADD

és

M.

Az airport játékok osztályának vizsgálatához elengedhetetlen az egyetértési játék fogalmának ismerete. Ezért a következ®kben bemutatjuk az említett fogalmat, valamint egy ehhez kapcsolódó lemmát is tárgyalunk.

2.21. Deníció.

Legyen

N, T ⊆ N, T 6= ∅ tetsz®legesen rögzített, és minden S ⊆ N -

re

( uT (S) :=

Az

uT

T

játékot a

T ⊆S

1,

ha

0

különben

.

koalíción értelmezett egyetértési játéknak nevezzük.

T

A deníció szemléletesen: ha például a

koalíció tagjai közül van olyan tag, aki

nem ért valamivel egyet egy szavazási szituációban, akkor nem lehet megvalósítani a tervet; a

T

tagjainak mintegy vétójoga van a kérdésben.

A következ® lemma jól ismert az irodalomban. (Lásd például Peleg és Sudhölter (2003).) A teljesség kedvéért a lemmát bizonyítással együtt közöljük.

2.22. Lemma.

Az

{uT : ∅ = 6 T ⊆ N}

halmaz egy bázisa

G N -nek,

az

N

játékoshal-

mazzal rendelkez® TU játékok osztályának. Bizonyítás. Ha van. Az

n

nincs, ez

2n

számára a

N = {1, 2, . . . , n} a játékosok halmaza, akkor 2n −1 egyetértési játék

játékos közül mindegyik játékos vagy benne van a

T

koalícióban, vagy

lehet®ség. Ebb®l levonva az üres koalíciót, adódik az egyetértési játékok

n

2 − 1.

A bizonyításhoz elég megmutatni, hogy ez a

2n − 1

egyetértési já-

{uT }T 6=∅ egy lineárisan független vektorrendszert P ∅6=T ⊆N αT uT = 0 és {T : αT 6= 0} 6= ∅, azaz nem

ték lineárisan független, vagyis az alkot. Indirekt tegyük fel, hogy minden

αT ∈ R

eleme. Ekkor azonban Tehát

P

T0

egyenl® nullával. Legyen

(

P

∅6=T ⊆N

a

{T : αT 6= 0}

halmaz egy minimális

αT uT )(T0 ) = αT0 6= 0, ami ellentmond a feltevésnek.

αT uT 6= 0, azaz az {uT }T 6=∅ valóban egy lineárisan független vektorP ( ∅6=T ⊆N αT uT )(T0 ) = αT0 egyenl®ség teljesül, mert az uT egyetértési

∅6=T ⊆N

rendszer. (A

játék minden esetben nullát vesz fel, kivéve, ha

T = T0

a

T0

minimális tulajdonsága

miatt.) A következ® két tétel a Shapley-érték egy-egy axiomatizálását adja. Az els® az eredeti Shapley-féle axiomatizáció 1953-ból, míg a második Young 1985-ös eredménye a Shapley-érték axiomatizálására.

2.23. Tétel

.

(Shapley (1953))

pontosan akkor

P O, N P , ET P

Legyen és

ψ

egy

G N -en

értelmezett megoldás. Ekkor

ha

ψ = φ,

azaz ha

ADD, 9

ψ

ψ

a Shapley-megoldás.

2.24. Tétel

(Young (1985))

pontosan akkor

P O, ET P

.

és

Legyen

M,

ha

ψ

egy

ψ = φ,

10

G N -en azaz ha

értelmezett megoldás. Ekkor

ψ

a Shapley-megoldás.

ψ

3. fejezet Az airport játékok osztálya

Az airport játékok reprezentációja a következ®: adott egy repül®tér egyetlen kifutóval. A repül®tér kifutóját céljából. Jelölje

m

db különböz® típusú repül®gép veszi igénybe leszállás

ck (1 ≤ k ≤ m)

nek költségét. Például lehet

m

a

k

típusú repül®gépnek megfelel® kifutó építésé-

típus az alapján, hogy milyen hosszú kifutóra van

szüksége az adott típusú repül®gépnek.

3.1. Deníció.

Legyen

Tk

egy adott id®szakban landoló

ekkor az összes repül®gépet magában foglaló halmaz: költségfüggvénye pedig a következ®képpen alakul:

ca (∅) = 0.

Valamint jelölje

GaN

az

N

N

ca (S) =

k

típusú gépek halmaza, m S = Tk . Az S koalíció k=1 max {ck : S ∩ Tk 6= ∅}S és

játékoshalmazzal rendelkez® airport játékok

osztályát.

3.2. Példa.

Tegyük fel, hogy a repül®teret három típusú repül®gép veszi igény-

be, ahol a típusok költsége rendre

2, 5

és

10 (c1 = 2,c2 = 5

és

c3 = 10).

Ha egy

koalícióban mindhárom géptípusból szerepelnek repül®gépek, akkor szükség van a leghosszabb kifutóra, vagyis a koalíció költsége

10

egység lesz. Viszont ha egy koalí-

cióban csak az els® és második típusú gépek halmazába tartozó repül®gépek vesznek részt, akkor a leghosszabb kifutóra nincs szükség, tehát a koalíció költsége a közepes kifutó építésének költségével egyezik meg, vagyis

5

egység lesz.

Az airport játékok további tárgyalásában fontos szerepet játszik az egyetértési játék duálisa. Az egyetértési játék és egy játék duálisának a fogalmából adódik a következ® deníció:

3.3. Deníció.

Legyen

N, T ⊆ N, T 6= ∅

tetsz®legesen rögzített, és minden

re

( u¯T (S) :=

S ∩ T 6= ∅

1,

ha

0

különben 11

.

S ⊆ N-

Az

u¯T

játékot a

T

koalíción értelmezett egyetértési játék duálisának nevezzük.

A deníció szemléletesen: tekintsük egy vállalatnál a szerz®dések aláírására jogosultakat a

T

koalíció tagjainak. Ha feltételezzük, hogy egyetlen aláírás is elegend® az

iratok érvényesítésére, akkor csak azok az

S

koalíciók tudnak érvényes szerz®déseket

kötni a cég nevében, amelyben legalább egy aláírásra jogosult személy is szerepel.

3.4. Állítás.

u¯T1 , u¯T2 , . . . , u¯Tm

Az

játékok airport játékok.

Bizonyítás. Egy adott i-re teljesül a következ®: nemüres halmaz, azaz van szerint, ha az

u¯Ti (S) = 0. ( ci

= 1),

S

i

Ti ⊆ N ,

Ti

valamint feltehet®, hogy

típusú gép. Az egyetértési játék duálisának deníciója

i

koalíciónak van

típusú tagja, akkor

Ez egy olyan airport játék, ahol az

minden más típusú játékosnak pedig

i

u¯Ti (S) = 1,

ha nincs, akkor

1

típusú játékosoknak

0 (cj = 0,

ha

j 6= i).

a költsége

Airport játék

esetén minden koalíció költsége a különböz® típusú tagjai költségének a maximuma. Jelen esetben ez azt jelenti, hogy ha egy koalíciónak van koalíció költsége

1

lesz, mert

max {0, 1} = 1

koalíció, akkor minden tag költsége

3.5. Állítás. GaN ,

vagyis az

N

1,

i típusú tagja is, akkor ezen

(ha kizárólag

i

típusú tagokból áll a

így a koalícióé is).

játékoshalmazzal rendelkez® airport játékok osztálya

kúp. Bizonyítás. Azt kell belátni, hogy ha minden

α > 0

esetén. Mivel az

hogy egy pozitív

α

αca

ca

airport játék, akkor

αca

is airport játék

ca

airport játéktól,

játék abban különbözik a

számmal meg van szorozva minden költség, ezért az

airport játék. Mégpedig olyan airport játék, amelyben minden költség

ca

αca

játék is

α-szorosa

a

airport játékbeli költségeknek.

3.6. Állítás.

Az

{¯ uT }T ⊆N

játékok által kifeszített konvex kúp tartalmazza az

játékoshalmazzal rendelkez® airport játékok osztályát, vagyis

N

GaN ⊆ cone({¯ uT }T ⊆N ).

Bizonyítás. A bizonyításhoz tekintsük az airport játékok egy másik felírását, amely hasonlít az öntözési játékokra. A konstrukció a következ®képpen néz ki: a játékosokat egy láncra f¶zzük fel aszerint, hogy mekkora a költségük. A költségeket típusunként növekv® sorrendbe állíthatjuk;

0 ≤ c1 ≤ c2 ≤ c3 ≤ · · · ≤ cm ,

amennyiben

m

db

típusú játékos szerepel a játékban. A lánc egy gyökérb®l indul, ezután az els® csúcs a legkisebb költség¶ típusból jelent egy tetsz®leges játékost. Ekkor a gyökér és az els® csúcs közötti szakasz költsége

c1 ,

ami a két csúcs költségének különbségeként adódik:

c1 − 0 = c1 .

csúcsok azok közül a játékosok közül kerülnek ki, akik szintén a tartoznak. Két

c1

c1

A következ®

költségú típusba

költség¶ játékos által képviselt csúcs közötti szakasz költsége

12

0 lesz

(c1

− c1 = 0).

Ezután a lánc következ® csúcsa a

c2

költség¶ játékosok valamelyike

lesz. A közte és a láncban ®t közvetlenül megel®z® csúcs közötti szakasz költsége

c2 − c1

lesz. Ezután a

c2

költség¶ játékosok következnek tetsz®leges sorrendben,

0

mely csúcsok közötti szakaszok költsége

lesz, ahogyan azt láthattuk a

c1

költség¶

játékosok esetében is. A leírt logika szerint folytatjuk a lánc építését, míg el nem érkezünk a séggel rendelkez® játékosokig. A láncban jelenleg az utolsó helyen a

cm−1

cm

költ-

költséggel

rendelkez® típusból szerepel egy játékos, majd utána következik egy tetsz®leges

cm

költség¶ játékos. A két játékos által reprezentált két csúcs közötti szakasz költsége ebben az esetben is úgy alakul, mint az el®z®ekben, vagyis a költség lánc soron következ® tagjai a

cm

cm − cm−1 .

A

költség¶ játékosok, akik által reprezentált csúcsok

közötti szakaszok költsége szintén

0

lesz.

Ekkor az airport játék felírható a következ® alakban a 3.1 deníció jelöléseivel:

ca = c1 u¯N + (c2 − c1 )¯ uN \T1 + (c3 − c2 )¯ uN \(T1 ∪T2 ) + . . . +

(3.1)

+ (cm−1 − cm−2 )¯ u(Tm−1 ∪Tm ) + (cm − cm−1 )¯ uTm . Ez a felírás akalmas a játék leírására. Ugyanis nézzük meg, hogy az ilyen formában adott airport játék milyen költségeket rendel az egyes koalíciókhoz! Az összeg els® tagja alapján mindenkinek kell zetni

c1

nagyságú összeget. A kizárólag

jaiból álló koalíciók esetében a fenti összeg többi tagja

0

T2

tag-

lesz, mert az egyetértési

játékok duálisai nullát vesznek fel, így az ilyen koalíciók költsége esetében, amelynek tagjai között szerepelnek

T1

c1 .

Azon koalíciók

típusú játékosok is, az összeg els® és

második tagja kivételével a többi tag nullát vesz fel. Vagyis ezekhez a koalíciókhoz rendelt költség

c1 + (c2 − c1 ) = c2 .

Azon koalíciók esetében, amiben szerepelnek

T3

típusú játékosok, az összeg els® három tagja lesz nullától különböz®. Minden ilyen koalíció költsége tehát

c1 + (c2 − c1 ) + (c3 − c2 ) = c3

lesz.

Következésképpen az eddig vizsgált esetekben a csak

T3

típusú tagokból álló koalíciók költsége rendre

tagokat egyaránt tartalmazó koalíciók költsége Ehhez hasonlóan adódik, hogy a

T1

talmazó koalíciók költsége egyaránt szerepelnek

T1 ,T2

és

T3

és

c3 .

T3 ,

c2 ,

csak

és

c3 .

A

T2 , T1

illetve a csak és

T2

típusú

vagyis a két költség maximuma.

valamint a

T2

és

T3

típusú tagokat tar-

Annak a koalíciónak az esetében, amelyben

típusú játékosok is, szintén

A gondolatmenetet folytatva a

c1 , c2

T1 ,

T4 ,T5 , . . . , Tm

c3

lesz a koalíció költsége.

típusú játékosokra, látható, hogy a

fenti felírás valóban airport játékot ad. Ugyanis egy koalíció költsége a benne szerepl® játékosok költségeinek maximumaként adódik, ami deníció szerint airport játék. A

ca

fenti felírása egyértelm¶en meghatároz egy airport játékot. Az állítás igazolására azt kell megmutatni, hogy minden airport játék el®áll egyet-

13

értési játékok duálisainak kúp kombinációjaként. Vagyis minden airport játékhoz található olyan

α ,β , . . . , ω ,

hogy

ca = α¯ uT 1 ⊆N + β u¯T 2 ⊆N + . . . + ω¯ uT k ⊆N . Ha súlyoknak a

c1 , c2 − c1 , c3 − c2 , . . . , cm − cm−1

N \T1 , N \(T1 ∪T2 ), . . ., (Tm−1 ∪Tm ), Tm

súlyokat, koalícióknak pedig a

ca

koalíciókat választjuk és a

N,

játékot a fenti

módon írjuk fel, akkor minden airport játékot egyértelm¶en felírhatunk egy ilyen formában adott

ca

játékként. Ha a felírandó airport játékban megnézzük az egyes

típusú játékosok költségét, és erre megkonstruáljuk a fenti összegképlet segítségével

ca -t, akkor a fenti felírás ca -ra egyértelm¶ lesz. Vagyis minden airport játék felírható egyetértési játékok duálisainak kúp kombinációjaként. (Mégpedig ha típusú játékos van, akkor

3.7. Példa. A

d

m

m

különböz®

db egytértési játék duálisának kúp kombinációjaként.)

A fenti állítás illusztrálására:

játékban négy játékos vesz részt (A,

pusba sorolhatóak a következ®képpen:

a := c1 u¯{A,B,C,D} , b := (c2 − c1 )¯ u{C,D}

B , C , D)

és a játékosok három tí-

cA = cB = c1 , cC = c2 és

és

cD = c3 .

Legyen

c := (c3 − c2 )¯ u{D} .

a

b

c

a+b

a+c

b+c

a+b+c

∅

0

0

0

0

0

0

0

{A}

c1

0

0

c1

c1

0

c1

{B}

c1

0

0

c1

c1

0

c1

{C}

c1 c2 − c1

0

c2

c1

c2 − c1

c2

{D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{A, B}

c1

0

c1

c1

0

c1

{A, C}

c1 c2 − c1

0

c2

c1

c2 − c1

c2

{A, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{B, C}

c1 c2 − c1

c2

c2 − c1

c2

{B, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{C, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{A, B, C}

c1 c2 − c1

c2

c2 − c1

c2

{A, B, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{A, C, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{B, C, D}

c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

{A, B, C, D} c1 c2 − c1 c3 − c2

c2

c3 − c2 + c1 c3 − c1

c3

0

0

0

c1

c1

Látható, hogy mindegyik oszlop airport játék, vagyis bármely airport játék el®áll egyetértési játékok duálisainak kúp kombinációjaként. Az utolsó oszlop adja meg a

14

példa elején bemutatott

d játékot, amely a következ® alakban áll el®: d = a + b + c =

c1 u¯{A,B,C,D} + (c2 − c1 )¯ u{C,D} + (c3 − c2 )¯ u{D} .

De ehhez hasonlóan a többi oszlop is

megad egy-egy airport játékot. Nézzük például az utolsó el®tti oszlop által megadott

e

játékot. A következ® formában áll el® az

e

játék:

e = b + c = (c2 − c1 )¯ u{C,D} +

(c3 − c2 )¯ u{D} . A d játékhoz hasonlóan az e játékban is négy játékos vesz részt (A, B , C , D)

és a játékosok három típusba sorolhatóak a következ®képpen:

cC = c2 − c1

és

cD = c3 − c1 .

Tehát a

d

és az

e

cA = cB = 0,

játékok abban különböznek csak

egymástól, hogy más az egyes típusok költsége a két játékban.

3.8. Lemma.

Ha tekintünk egy (3.1) alakban adott

ca

airport játékot és az összeg

tagjai közül letörlünk tetsz®leges számú játékot, akkor az így kapott játék szintén airport játék lesz. Bizonyítás. Vegyük például azt a játékot, ami a

(c2 − c1 )¯ uN \T1

játék letörlésével

keletkezik:

c˜a = c1 u¯N + (c3 − c2 )¯ uN \(T1 ∪T2 ) + . . . +

(3.2)

+ (cm−1 − cm−2 )¯ u(Tm−1 ∪Tm ) + (cm − cm−1 )¯ uTm . Ha a

(c2 − c1 )¯ uN \T1

játékot letöröljük, akkor ez megfelel annak, hogy az

egyetértési játék duálisának együtthatója 0, vagyis hogy a

T2

c2 = c1 .

u¯N \T1

Ez pedig azt jelenti,

típusú játékosok ugyanolyan költséggel rendelkeznek mint a

T1

típusú

játékosok. Így a 3.2 a következ® alakot ölti:

c˜a = c1 u¯N + (c3 − c1 )¯ uN \(T1 ∪T2 ) + . . . +

(3.3)

+ (cm−1 − cm−2 )¯ u(Tm−1 ∪Tm ) + (cm − cm−1 )¯ uTm . A következ®kben még szebb alakra hozzuk a 3.3 összefüggéssel adott játékot. Legyen

T˙1 = T1 ∪ T2 , T˙2 = T3 , T˙3 = T4 , . . . , T˙m−1 = Tm .

c˙1 = c1 = c2 , c˙2 = c3 , . . . , c˙m−1 = cm .

Ekkor

c˜a -ra

c˜a

airport

Valamint legyen

a következ® adódik:

c˜a = c˙1 u¯N + (c˙2 − c˙1 )¯ uN \T˙1 + (c˙3 − c˙2 )¯ uN \(T˙1 ∪T˙2 ) + . . . +

(3.4)

+ (c˙m−2 − c˙m−3 )¯ u(T˙m−2 ∪T˙m−1 ) + (c˙m−1 − c˙m−2 )¯ uT˙m−1 . Láthatjuk, hogy a (3.4) egyenlet pontosan olyan alakú, mint a (3.1) egyenlet, tehát a

c˜a

játék is airport játék. Ugyanez a gondolatmenet m¶ködik arra az esetre

is, amikor több játékot törlünk le. Ha például

k számú játékot törlünk le, akkor k -val

kevesebb típusú játékos lesz, de ugyanúgy airport játékot kapunk. Ezzel igazoltuk, hogy (3.1) alakban adott airport játékból törléssel is airport játékot kapunk.

15

4. fejezet A Shapley-érték két axiomatizálása

Ebben a fejezetben megmutatjuk, hogy a 2.23 és a 2.24 tételek teljesülnek az airport játékok osztályán. A következ®kben az említett tételek airport játékokra való kimondása, majd a tételek bizonyítása szerepel.

4.1. Tétel. akkor

ψ

egy

P O, N P , ET P

és

Legyen

Bizonyítás. Ha a oldás

ψ

ψ

ADD,

ha

ψ = φ,

megoldás megegyezik a

P O, N P , ET P

Ha a a

ψ

GaN -en értelmezett pontérték¶ megoldás. Ekkor ψ

és

ADD.

φ

φ

ψ

a Shapley-megoldás.

Shapley-megoldással, akkor a

ψ

meg-

Ez teljesül a 2.20 állítás miatt.

megoldásra teljesül, hogy

megoldás megegyezik a

azaz ha

pontosan

P O, N P , ET P

és

ADD

tulajdonságú, akkor

Shapley-megoldással. Ezt az állítást bizonyítom az

alábbiakban. Tekintsük a Ha

T

koalíción értelmezett egyetértési játék duálisát, az

i∈ / T , akkor ez az i játékos nulla játékos, ugyanis az u¯T

zájárulása

0

((¯ uT )0i

S

értéke

i

S

az

NP

i

játékban a határhoz-

koalícióhoz csatlakozik, amelyre

csatlakozása el®tt és után is

koalícióhoz csatlakozik, amelyre igaz az, hogy koalíció értéke

játékot.

= 0). Az i játékos bármilyen koalícióhoz csatlakozik is, nem tudja

növelni annak értékét. Hiszen ha olyan teljesül, akkor az

u¯T

csatlakozása után is

0

S ∩ T = ∅,

lesz. Mivel

i

1

S ∩ T 6= ∅

lesz. Ha pedig olyan

akkor mivel

i∈ / T,

S

nulla játékos, ezért a megoldás

tulajdonság alapján a következ® értéket rendeli hozzá:

ψi (¯ uT ) = 0. Ha

az

S

i, j ∈ T ,

akkor ez a két játékos ekvivalens a játékban, vagyis

gáljunk egy tetsz®leges határhozzájárulása az legalább egy

S ∩ T = ∅,

(4.1)

T -beli

S

S

koalíciót, amelyre

i, j ∈ / S

i ∼u¯T j .

teljesül. Ez esetben

i

Vizsés

j

koalícióhoz megegyezik, hiszen bármelyikük csatlakozik is,

tag szerepel a koalícióban a csatlakozás után, vagyis ha eddig

akkor ezután

S ∩ T 6= ∅,

tehát a koalíció értéke

16

0-ról 1-re

emelkedett.

S ∩ T 6= ∅,

Viszont ha a csatlakozás el®tt

S

nem növeli a koalíció értékét:

akkor egy

értéke ugyanúgy

1

T -beli

lesz, tehát a határhozzájárulá-

sok is nullával egyenl®ek mindkét játékos esetében ((¯ uT )0i (S) csatlakozás el®tt a következ® teljesült:

S ∩ T 6= ∅).

játékos csatlakozása

Az

ET P

= (¯ uT )0j (S) = 0,

ha a

tulajdonság alapján a

játékban a két játékoshoz ugyanakkora értéket rendel a megoldás:

ψi (¯ uT ) = ψj (¯ uT ). A nagykoalíció értéke ebben a játékban

1, vagyis u¯T (N ) = 1. Ha a megoldás P O

tulajdonságú, akkor teljesül a következ® az

X

(4.2)

u¯T

játékban:

ψi (¯ uT ) = u¯T (N ) = 1.

(4.3)

i∈N A (4.1) egyenletb®l összesen nem

T -beli

az

darab van, ami úgy adódik, hogy az összes

játékosra felírjuk az adott összefüggést. A (4.2) összefüggés alkalmazá-

|T | − 1

sából összesen

T

|N \ T |

lineárisan független egyenlet adódik a következ®képpen: a

tagjai közül kiválasztunk egy tetsz®leges

i

játékos és minden

T -beli

i

játékost és a (4.2) egyenletet felírjuk

tag közötti összefüggésre. (Ebb®l a

egyenletb®l kiderül, hogy bármely két

T -beli

egyetlen

ψ

|N \ T | + (|T | − 1) + 1 = |N |

da-

számú játékos van. Ebb®l következik, hogy

megoldás van, ami kielégíti az összes egyenletet. Mivel a 2.20 állítás alap-

ján a Shapley-érték tetsz®leges

|N |

számú

játékos ekvivalens egymással.) Végül

felírhatjuk a (4.3) egyenletet is. Tehát összesen rab lineárisan független egyenlet és

|T | − 1

u¯T

N P , ET P

és

PO

játékra teljesül, hogy

A 3.4 állítás alapján az

u¯T

tulajdonságokkal rendelkez® megoldás, ezért

ψ(¯ uT ) = φ(¯ uT ).

játék airport játék. Emellett az

αT u¯T (αT ≥ 0) játék is

airport játék a 3.5 állítás alapján. Ez a játék csak a koalíciók értékében különbözik az

u¯T

játéktól: azon

αT ,

S

koalíciók esetében, melyekre

a többi koalíció értéke pedig

•

Ha

0.

S ∩ T 6= ∅ teljesül, a koalíció értéke

Ebben az esetben is teljesülnek a következ®k:

i∈ / T , akkor i nulla játékos. Ekkor a megoldás az N P

egyenlet szerint a következ® értéket rendeli az

•

Ha

i

tulajdonság és a (4.1)

játékoshoz:

i, j ∈ T , akkor ez a két játékos ekvivalens a játékban, tehát i ∼αT u¯T j . Ekkor

a megoldás egyforma értéket rendel a két játékoshoz az miatt. Ez az érték a (4.2) összefüggés alapján:

•

A nagykoalíció értéke ebben a játékban

αT ,

ET P

tulajdonság

ψi (αT u¯T ) = ψj (αT u¯T ). vagyis

αT u¯T (N ) = αT .

Ha a

P O tulajdonságú, akkor a (4.3) egyenlet alapján teljesül a következ® P αT u¯T játékban: i∈N ψi (αT u¯T ) = αT u¯T (N ) = αT .

megoldás az

ψi (αT u¯T ) = 0.

17

Ekkor az

u¯T

játékhoz hasonlóan az

lineárisan független egyenlet és

ψ

len

αT u¯T

játékban is teljesül, hogy

|N |

darab

|N | számú játékos van. Ebb®l következik, hogy egyet-

megoldás van, ami kielégíti az összes egyenletet. Mivel a 2.20 állítás alapján

N P ,ET P

a Shapley-megoldás tetsz®leges

αT u¯T

Tekintsük a

PO

és

tulajdonságokkal rendelkez® megoldás, ezért

játékra teljesül, hogy

c

ψ(αT u¯T ) = φ(αT u¯T ).

airport játékot. Mivel minden airport játék felírható egyetértési

játékok duálisainak kúp kombinációjaként a 3.6 állítás szerint, ezért c a következ® formában írható fel:

P

c :=

T ⊆N

még azt kell megmutatni, hogy

T ⊆N

Minden

koalícióra az

ψ

megoldással és mivel a a

c =

P

T ⊆N

αT u¯T

αT u¯T ,

ahol

αT ≥ 0.

Tehát a tétel bizonyításához

ψ(c) = φ(c). αT u¯T

φ megoldás megegyezik a Shapley-

játékban a

megoldásról tudjuk, hogy

ADD

tulajdonságú is, ezért

játékban is teljesül az említett egyenl®ség. Ezzel beláttuk a

tételt.

4.2. Tétel. akkor

P O, ET P

Bizonyítás. Ha a oldás

P O, ET P

Ha a a

φ

ψ

ψ

Legyen

egy

GaN -en értelmezett pontérték¶ megoldás. Ekkor ψ

és

M,

ψ

megoldás megegyezik a

és

M.

megoldás

ha

ψ = φ,

azaz ha

ψ φ

pontosan

a Shapley-megoldás. Shapley-megoldással, akkor a

ψ

meg-

Ez teljesül a 2.20 állítás miatt.

P O, ET P

és

M

tulajdonságú, akkor a

ψ

megoldás megegyezik

Shapley-megoldással. Ezt az állítást igazoljuk az alábbiakban Young (1985)

bizonyítását alkalmazva. Minden

c ∈ GaN

airport játék egyértelm¶en el®áll

{¯ uT }T ⊆N

játékok kúp kombiná-

ciójaként a 3.6 állítás alapján. Az egyértelm¶séget biztosítja, hogy az

u¯T

vektorok

függetlenek. Deniáljuk a

c



airport játékhoz

D(c) := | αT : c = az

αT

{¯ uT }T ⊆N

P

T ⊆N

αT u¯T

és

D(c)-t

a következ®képpen:

αT 6= 0 | 1 . Vagyis ha a c airport játékot felírjuk

játékok kúp kombinációjaként, akkor

D(c) azt a számot jelöli, amennyi

súly pozitív a kombinációban. A bizonyítás menete a továbbiakban Ha

D(c) = 0,

D(c)-re

vonatkozó indukció lesz.

akkor nulla játékot kapunk. A

PO

koalíció értékét kell szétosztani, ami a nulla játékban zájárulása a nulla játékban

0,

tulajdonság alapján a nagy-

0.

Minden játékos határhoz-

tehát minden játékos nulla játékos. Mivel minden

játékos határhozzájárulása megyegyezik, ezért ®k ekvivalens játékosok, tehát a megoldás ugyanakkora értéket rendel mindenkihez az

1A

ET P

tulajdonság alapján. Mivel

2.22 lemma teljesül egyetértési játékok duálisaira is. Emiatt igaz, hogy {¯ uT } bázisa G N -nek. Ebb®l adódóan D(c) jól deniált.

18

0 költséget kell szétosztani és mindenkihez ugyanakkora összeget kell rendelni, ezért a megoldás minden játékoshoz

0

Tegyük fel, hogy tetsz®leges

ψ

hogy a játék

ψ

megoldás

c

és

D(c) = n

Ha van olyan

i

M

D(c) ≤ n − 1,

játékra, melyre igaz, hogy

megoldása egyértelm¶ és megegyezik a

P O, ET P

Tekintsük a

költséget rendel.

φ

Shapley-megoldással, ha a

tulajdonságú.

esetet!

játékos, hogy valamelyik

T -re,

αT > 0, i

ahol

nulla játékos az

játékban, akkor töröljük le ezt a játékot, majd vizsgáljuk az így kapott amire

D(d) = n − 1

vetkez®re jutunk: ezért

c0i = d0i .

egyezik a

A

ψ

i

d

u¯T

játékot,

teljesül. Az egyik komponens letörlésével is airport játékot

kapunk a 3.8 lemma alapján, vagyis Ha vizsgáljuk az

teljesül,

d

is airport játék.

játékos határhozzájárulásait az egyes játékokban, akkor a kö-

c0i = d0i + (¯ uT )0i . megoldás

M

Az

i

játékos nulla játékos volta miatt

tulajdonsága miatt az

i

(¯ uT )0i = 0,

játékosra rótt költség meg-

c és a d játékban, tehát egyértelm¶en meghatározott az az érték, amelyet a

megoldás az

i

játékoshoz rendel. Ez igaz minden olyan játékosra, aki valamelyik

játékban nulla játékos. (Ha valamely játékos egynél több ilyen játékos, akkor az adott játékok letörlésével kapott

u¯T

u¯T

játékban is nulla

e játékra igaz, hogy D(e) < n − 1,

de erre az esetre ugyanúgy alkalmazható az indukciós feltétel.)

u¯T

Most tekintsünk azokat a játékosokat, akik egyik olyan játékosok, ahol

αT > 0.

megoldás ehhez az

i

Ha csak egy ilyen

i

játékban sem nulla

játékos van, akkor az az érték, amit a

játékoshoz rendel, egyértelm¶en meghatározott. Ugyanis az

i

játékos kivételével minden játékosra igaz, hogy valamelyik játékban nulla játékosok, tehát a fentebb leírt módszerrel meghatározható a hozzájuk rendelt összeg. Mivel a nagykoalíció összege adott és a

ψ PO

tulajdonsága miatt a nagykoalíció értékét

kell szétosztani a játékosok között, a megoldás által az

i

játékoshoz rendelt érték

egyértelm¶en meghatározható. Ha több olyan játékos is van, aki egyik olyan

αT > 0,

akkor ezek minden

sok minden

u¯T

u¯T

u¯T

játékban sem nulla játékos, ahol

játékban ekvivalens játékosok. Mivel ezek a játéko-

játékban ekvivalensek, ezért ezek kúp kombinációjában, vagyis a

játékban is ekvivalens játékosok. A

ψ

megoldás

ET P

c

tulajdonsága alapján minden

ekvivalens játékoshoz ugyanakkora értéket rendel a megoldás. A nulla játékosokról már tudjuk, hogy mekkora értéket rendel hozzájuk a megoldás, a nagykoalíció értéke adott és a

PO

tulajdonság alapján ezt az értéket kell szétosztani a játékosok között,

az ekvivalens játékosokról pedig tudjuk, hogy egyenl® összeget rendel hozzájuk a megoldás. Ebb®l következik, hogy a

ψ

megoldás egyértelm¶.

Mivel a Shapley-megoldásra igaz a 2.20 állítás alapján, hogy tulajdonságú, ezért a

D(c) = n

esetben is teljesül, hogy a

19

ψ

P O, ET P

és

M

megoldás megegyezik a

Shapley-megoldással, vagyis

ψ = φ.

Ezzel a végére értünk az indukciós bizonyítás-

nak, igazoltuk a tételt.

20

5. fejezet Airport probléma és airport játék

Az ebben a fejezetben bemutatásra kerül® modellt, fogalmakat és eredményeket a Thomson (2007) cikk alapján tárgyaljuk. Jelölésekben alapvet®en a cikket követjük, viszont néhol változtatásokat eszközölünk az ott leírtakhoz képest.

5.1. A modell Legyen

N

a játékosok egy halmaza, akik igénybe szeretnének venni egy adott szol-

gáltatást, de azt el®bb ki kell építeni. (Például egy adott utcában lakók szeretnék a kábeltévé szolgáltatást igénybe venni, de ahhoz el®bb be kell vezetni az utcába a kábeltévéhez szükséges vezetékeket.) Minden játékosnak különböz® szükséglete van a szolgáltatásra nézve. Úgy kell kiépíteni a szolgáltatáshoz szükséges rendszert, hogy az minden játékos szükségletét kielégítse. Minden kerül az

i

i∈N

játékos jellemezhet® egy

ci költséggel. A ci az a költség, amennyibe

játékosnak, ha egyedül építi ki a szolgáltatáshoz szükséges rendszert.

Ha olyan rendszer épült ki, amely kielégíti az

i

következik, hogy ez a rendszer kielégíti mindazon a

cj

költsége legfeljebb akkora, mint az

játékos szükségletét, akkor ebb®l

j

játékosok szükségletét, akiknek

i játékos ci költsége. Olyan rendszer kiépítése,

amely minden játékos szükségletét kielégíti,

maxj∈N cj

költség¶. A kérdés az, hogy

ehhez az egyes játékosoknak mennyivel kell hozzájárulni. A dolgozat els®dleges alkalmazásában a játékosok repül®gépek és a az a költség, amely annak a kifutónak az építési költsége, amelyre az szüksége van. Airport probléma alatt egy

c ∈ RN +

vektort értünk. Jelölje

i

ci

költség

játékosnak

CN

az összes

airport probléma halmazát.

5.1. Deníció.

Egy elosztási szabály (röviden szabály) olyan leképezés, amely az

összes probléma halmazán van deniálva és minden

21

c ∈ CN

problémához hozzárendel

egy

x ∈ RN

vektort. A szabályt jelöljük

χ-vel.

Ekkor a

χ

szabályra a következ® igaz:

χ : C N → RN . Megjegyzés: Az így deniált szabályok pontérték¶ek.

5.2. Deníció.

Az egymást követ® egyenl® hozzájárulás szabályán (sequential equal

contributions rule, jelöljük minden

i∈N

ξ -vel)

Nézzünk egy példát a

ξ

szabály alkalmazására!

ξ3 = 53 + 12 + 41 =

ξ szabály az egyes játékosokhoz: ξ1 =

és legyen a

c

5 3

=

10 , 6

ξ2 = 53 + 12 =

13 6

37 . Az airport probléma deníciója alapján a nagykoalíció költsége 6

az egyes játékosok költségeinek maximuma (c(N ) problémában

N = {1, 2, 3}

R3 -beli vektor: c = (5, 6, 10). Ekkor a deníció alapján a követ-

kez® értékeket rendeli a

c

problémára és

c1 c2 − c1 ci − ci−1 + + ... + . n n−1 n−i+1

Legyen a játékosok halmaza a következ®:

probléma a következ®

és

c ∈ CN

játékosra legyen

ξi :=

5.3. Példa.

a következ®t értjük: minden

c(N ) = c({1, 2, 3}) = 10.

= maxi∈N ci ). A példában szerepl®

Ha összeadjuk azokat az értékeket, amit a

szabály rendelt az egyes a játékosokhoz, azt kapjuk, hogy az összeg megegyezik a

P3

i=1 ξi

nagykoalíció értékével:

= 10.

Ezt a tulajdonságot elvárjuk egy szabálytól,

hiszen a szabály segítségével szeretnénk szétosztani a nagykoalíció költségét az egyes játékosok között. A következ®kben deniálom a Thomson (2007) cikkben szerepl® tulajdonságokat.

5.4. Deníció.

A

χ

szabály, ami az összes airport probléma halmazán van értel-

mezve

•

nemnegatív (non-negativity, röviden jesül, hogy

•

korlátos költség¶ (cost boundedness, röviden

i∈N

c ∈ CN

problémára tel-

CB ),

ha minden

c ∈ CN

problé-

χ(c) ≤ c,

hatékony (eciency, röviden

P •

ha minden

0 ≤ χ(c),

mára teljesül, hogy

•

N N ),

E ),

ha minden

c ∈ CN

problémára teljesül, hogy

χi = maxi∈N ci ,

egyforma játékosokat egyformán kezel® (equal treatment of equals, röviden ha minden ha

ci = cj ,

c ∈ CN akkor

problémára és minden

χi (c) = χj (c),

22

{i, j} ⊆ N

ET E ),

játékospárra teljesül, hogy

•

feltételesen költség additív (conditional cost additivity, röviden den

{c, c˜} ∈ C N

pelnek a

•

c

és

CCA),

ha min-

problémapárra, amelyre a játékosok azonos sorrendben szere-

c˜ problémában,

teljesül, hogy

χ(c + c˜) = χ(c) + χ(˜ c) ,

rendelkezik a legalább akkora költségek függetlenségének tulajdonságával (independence of at-least-as-large costs, röviden problémapárra és minden

(i) c˜i = ci (ii)

ha minden

{c, c˜} ∈ C N

játékosra teljesül, hogy ha

és

minden olyan

akkor

i

IALC ),

j ∈ N \ {i}

játékosra, amelyre

cj < ci ,

teljesül, hogy

c˜j = cj

χi (c) = χi (˜ c) .

A következ®kben a 2.19 példához hasonló illusztráció segítségével igyekszünk megmutatni, hogy mennyire jogos elvárás, hogy egy költségelosztási probléma szabálya a denícióban említett tulajdonságokkal rendelkezzen.

5.5. Példa.

Egy társasház rendezni szeretné egy adott id®szaki számláját, amit a

szolgáltató a szemét elszállításáért számolt fel, és a szemétszállítás díját fel szeretné osztani a tulajdonosok között. Minden lakóhoz tartozik egy költség, ami azt mutatja meg, hogy mennyit kéne zetnie az adott lakónak, ha a házból egyedül venné igénybe a szolgáltatást.

• NN

tulajdonság: Egyetlen lakó által bezetend® összeg sem lehet negatív.

Valakinek vagy kell zetnie egy pozitív nagyságú összeget, vagy semmit nem kell zetnie, de egyetlen lakónak sem zetünk a többi lakó által bezetett összegb®l a költségelosztás során.

• CB

tulajdonság: Egy lakónak sem kell többet zetnie a költségeltosztás során

az egyéni költségénél. Ugyanis ha ez el®fordulna, akkor a lakó nem a házon keresztül intézné a szemét elszállítását, hanem egyénileg.

• E

tulajdonság: A lakóktól beszedett pénz nem lehet kevesebb, mint a számla

értéke, mert akkor nem tudják azt kiegyenlíteni. Viszont a számla összegénél többet nem szednek be, mert csak ennek az adott szolgáltatásnak a költségét osztják szét ezen költségelosztási problémában.

• ET E

tulajdonság: Ha két lakástulajdonosnak megegyezik az egyéni költsége,

akkor jogosan várható el, hogy ugyanannyit kelljen zetniük, amikor a ház szemétszállítási költségét osztják fel a lakók. Hiszen a szolgáltatást azonos módon veszik igénybe, mivel az egyéni költségük megegyezik.

23

• CCA

tulajdonság: Tegyük fel, hogy a szemétszállítás költségeinek elosztási

problémáját két id®szakon keresztül vizsgáljuk. Ha az egyes tulajdonosok által zetend® összegeket összeadjuk a két id®szakra, jogosan várható el, hogy így ugyanannyit kelljen zetniük, mintha egy id®szakként vizsgáltuk volna a két id®tartamot.

• IALC

tulajdonság: Az

IALC

tulajdonság szemléltetésére tekintsünk egy má-

sik szituációt! Néhány vásárló egy áruház raktárához szeretne egy gépjárm¶beállót építeni, hogy egyszer¶bb legyen az áru rakodása. A vásárlók között van, aki kis tételben vásáról, ® személygépkocsit használ, valaki kisteherautóval szeretné igénybevenni a beállót, míg a nagytételben vásárlók teherautóval érkeznek. A különböz® méret¶ járm¶veknek különböz® hosszúságú beálló kell, emiatt a beálló megépítésének egyéni költségei is eltér®ek. Mivel van a járm¶vek között teherautó, így a beállót ennek megfelel® nagyságúra kell építeni. A vásárlók között ezt a költséget szeretnénk elosztani. Ugyanezek a vásárlók szeretnének a szomszéd áruházhoz is egy beállót építeni. (A két esetben az egyéni költségek eltérhetnek, hiszen más területen, más körülmények között, esetleg más kivitelez®vel építkeznek.) Tekintsük az építés költségének elosztását a két építkezésre, valamint egy adott

i

vásárlóra nézve.

Ha azt tapasztaljuk, hogy



az



minden olyan

i

vásárló egyéni költsége a két építés esetében azonos,

j

vásárló esetében, akinek az els® beálló építésekor kisebb

az egyéni költsége az

i

vásárlóénál, teljesül, hogy a

j

vásárló egyéni költ-

sége megegyezik mindkét esetben, (Ez a feltétel azért várható el, mert tegyük fel, hogy kezdetben csak a majd csatlakozik hozzá az

i

j

vásárló igényli a beálló megépítését,

vásárló is. Ekkor ha az

sége megegyezik a két vizsgált esetben, és a

j

i

vásárló egyéni költ-

vásárló egyéni költsége is

azonos mindkét építési szituációban, akkor mondhatjuk, hogy az

i vásárló

ugyanannyival járult hozzá mindkét építkezés költségeihez.) akkor jogos elvárás, hogy a vásárlónak ugyanannyit kelljen zetnie mindkét beálló építésekor.

5.2. Tulajdonságok megfeleltetése A következ®kben jelölje

c

a

ca

problémán értelmezett szabály és

airport játék mögötti airport problémát. Ha

ψ

a

ca

χ

a

c

játékon értelmezett megoldás, akkor legyen

24

ψ

olyan megoldás, amelyre a következ® teljesül:

5.6. Állítás. akkor a

c ∈ CN

Ha a

ca ∈ GaN

ψ(ca ) := χ(c). χ

airport problémán értelmezett

airport játékon értelmezett

ψ

megoldás

szabály

i∈N

tartozó komponense a költségvektornak

0, vagyis ci = 0. Az N N

χ

i

χ

szabály által az

szabály az

CB ,

CB

játékoshoz

tulajdonság alapján tulajdonság miatt a

játékoshoz rendelt érték nem nagyobb, mint a költségvektor

játékoshoz tartozó komponense, vagyis a

i

nulla játékost. Ekkor az

játékoshoz nemnegatív értéket rendel. A

i

és

NP .

Bizonyítás. Tekintsünk egy tetsz®leges

a

NN

i

ci , ami 0. Tehát az i játékoshoz nullát rendel

χ szabály a c airport problémában: χi (c) = 0. Mivel ψ(ca ) := χ(c), ezért ψi (ca ) = 0.

Látható, hogy a

ψ NP

tulajdonságú.

5.7. Állítás. ca ∈ GaN

Ha a

c ∈ CN

airport problémán értelmezett

airport játékon értelmezett

Bizonyítás.

P O.

ψ megoldás a nulla játékoshoz 0-t rendel a ca airport játékban, tehát

P

i∈N

ψi (ca ) =

Az els® egyenl®ség a

P

ca

megoldás

ca

E,

akkor a

Tehát a

ψ

megoldás

összefüggésb®l, a második egyenl®ség az

maxi∈N ci = ca (N )

airport játékban és a

szabály

P O.

χi (c) = maxi∈N ci = ca (N ).

ψ(ca ) := χ(c)

tulajdonságból következik. A hogy a

i∈N

ψ

χ

mögötti

c

E

összefüggés pedig amiatt teljesül,

airport problémában ugyanazok a

költségek tartoznak az egyes játékosokhoz. Megjegyzés: Az állítás megfordítása is teljesül, tehát ha a értelmezett

ψ megoldás P O, akkor a c ∈ C

rendelkezik az

5.8. Állítás. ca ∈ GaN

E

N

ca ∈ GaN

airport játékon

airport problémán értelmezett

tulajdonsággal.

Ha a

c ∈ CN

airport problémán értelmezett

airport játékon értelmezett

ψ

megoldás

Bizonyítás. Tekintsünk két ekvivalens játékost:

χ

szabály

ET E ,

Ebb®l következik, hogy

i ∼ ca j ,

ahol

i, j ∈ N .

5.9. Állítás. ca ∈ GaN

(ca )i = (ca )j .

Tehát a

c ∈ CN

i és j játékosokhoz: χi (c) = χj (c). Mivel ψ(ca ) := χ(c), ψ

megoldás rendelkezik az

ET P

airport problémán értelmezett

airport játékon értelmezett

Bizonyítás.

ADD.

Ha a

Airport já-

ci = cj . Mivel a χ szabály ET E tulajdonságú, ezért a szabály

ugyanakkora értéket rendel az

ψi (ca ) = ψj (ca ).

akkor a

ET P .

tékok esetén az ekvivalens játékosokhoz ugyanakkora költség tartozik:

ezért

χ szabály

ψ

megoldás

χ

tulajdonsággal.

szabály

CCA,

ADD.

ψ(ca + c˜a ) = χ(c + c˜) = χ(c) + χ(˜ c) = ψ(ca ) + ψ(c˜a ). Tehát a ψ

Az els® és a harmadik egyenl®ség a

míg a második egyenl®ség a

CCA

ψ(ca ) := χ(c)

megoldás

összefüggés miatt teljesül,

tulajdonságból következik. A

25

akkor a

CCA

tulajdonság

csak azokra a

c, c˜ ∈ C N

airport problémapárokra teljesül, amikben a játékosok azo-

nos sorrendben szerepelnek. A

ca , c˜a ∈ GaN

airport játékokban is azonos sorrendben

szerepelnek a játékosok, ugyanis a sorrendet

GaN ,

N

az

játékoshalmazzal rendelkez®

airport játékok osztálya egyértelm¶en meghatározza.

5.10. Állítás. a

ca ∈ GaN

Ha a

c ∈ CN

χ

airport problémán értelmezett

ψ

airport játékon értelmezett

megoldás

ca , c˜a ∈ GaN

Bizonyítás. Vegyünk két tetsz®leges

i

Ha az

i

játékosnak két airport

(ca )i = (˜ ca )i .

i

teljesül, igaz a következ®:

hogy

j

j ∈ N \ {i} játékosra, amelyre (ca )j < (ca )i

(ca )j = (˜ ca )j . (Itt azt gyeljük, amikor az i játékos az egy-

koalícióhoz csatlakozik mindkét játékban.) Ebb®l következ®en teljesül,

cj = c˜j .

Ekkor teljesül az értéket rendel az

ψ(ca ) := χ(c),

5.11. Állítás.

i

ezért

A

IALC

tulajdonság két feltétele, emiatt a

ca ∈ GaN

azaz

χ szabály ugyanakkora

játékoshoz mindkét airport problémában:

ψi (ca ) = ψi (˜ ca ) .

c ∈ CN

Tehát a

ψ

megoldás

airport problémán értelmezett

mást követ® egyenl® hozzájárulás szabályával, vagyis a

ci = c˜i .

játékosnak két airport játékban megegyezik a határhozzájáru-

lása, akkor igaz az is, hogy minden olyan

személyes

(Itt azt

játékoshoz tartozó komponense a költségvektornak a

két airport játék mögötti két airport problémában megegyezik:

i

i

játékos az üres koalícióhoz csatlakozik mindkét játékban.)

Ebb®l következik, hogy az

Valamint ha az

akkor

airport játékot és egy tetsz®leges

játékban megegyezik a határhozzájárulása, akkor igaz, hogy gyeljük, amikor az

IALC ,

M.

(ca )0i = (˜ ca )0i .

játékost, melyre teljesül a következ®:

szabály

airport játékon értelmezett

ψ

χ

M

χi (c) = χi (˜ c) .

Mivel

tulajdonságú.

szabály megegyezik az egy-

χ(c) = ξ(c), pontosan akkor, ha

megoldás megegyezik a Shapley-megoldással,

ψ = φ.

Az állítás bizonyításától eltekintünk, az állítás igazolása megtalálható a Littlechild és Owen (1973) cikkben.

5.3. Dubey(1982) valamint Moulin és Shenker(1992) eredménye 5.12. Tétel

.

(Dubey (1982))

szabály. Ekkor

χ

Legyen

pontosan akkor

χ

egy

c ∈ CN

N N , CB , E , ET E

az egymást követ® egyenl® hozzájárulás szabálya.

26

airport problémán értelmezett és

CCA,

ha

χ = ξ,

azaz ha

χ

χ

Bizonyítás. Ha a

szabályával, akkor a

ξ

szabály megegyezik a

χ

szabály

egymást követ® egyenl® hozzájárulás

N N , CB , E , ET E

CCA.

és

Ez az állítás igazolásra

került a Thomson (2007) cikkben. Ha a a

χ

szabályra teljesül, hogy

N N , CB , E , ET E

és

CCA

tulajdonságú, akkor

χ szabály megegyezik a ξ -vel, az egymást követ® egyenl® hozzájárulás szabályával.

Ezt az állítást igazoljuk az alábbiakban. Mivel alapján a

χ szabály a fenti tulajdonságokkal bír, ezért az 5.6, 5.7, 5.8 és 5.9 állítások c ∈ CN

N P , P O, ET P oldása a

és

ADD

N P , P O, ET P

airport játék

tulajdonságokkal rendelkezik. Ha viszont a

ADD,

és

akkor a 4.1 tétel szerint a

c

ca

airport játék

ψ

megoldása megegyezik a

airport problémán értelmezett

χ

ψ

ca

ψ

megoldása

játék

ψ

meg-

megoldás megegyezik

φ

Shapley-megoldással, akkor

szabály megegyezik az egymást követ® egyenl®

hozzájárulás

ξ

5.13. Tétel

(Moulin és Shenker (1992))

szabályával. Ezzel igazoltuk a tételt.

értelmezett szabály. Ekkor

χ

ca ∈ GaN

φ Shapley-megoldással. Az 5.11 állítás szerint pedig, ha a c airport probléma által

generált a

airport probléma által generált

χ

.

Legyen

pontosan akkor

χ

egy

E , ET E

és

c ∈ CN

airport problémán

IALC ,

ha

χ = ξ,

azaz ha

az egymást követ® egyenl® hozzájárulás szabálya. A tétel bizonyítása a 5.12 tétel bizonyításának analógiájára történik.

Bizonyítás. Ha a

χ

szabályával, akkor a

szabály megegyezik a

ξ

χ

IALC .

szabály

E , ET E

és

egymást követ® egyenl® hozzájárulás Ez az állítás igazolásra került a

Thomson (2007) cikkben. Ha a

χ

szabályra teljesül, hogy

szabály megegyezik a

ξ -vel,

E , ET E

és

IALC

tulajdonságú, akkor a

χ

az egymást követ® egyenl® hozzájárulás szabályával.

Ezt az állítást igazoljuk az alábbiakban. Mivel alapján a

χ

szabály a fenti tulajdonságokkal bír, ezért az 5.7, 5.8 és 5.10 állítások

c ∈ CN

P O, ET P

és

M

P O, ET P

és

M,

airport probléma által generált

ψ

akkor a 4.2 tétel szerint a

megoldása megegyezik a

problémán értelmezett

ξ

airport játék

tulajdonságokkal rendelkezik. Ha viszont a

ψ

megoldással. Az 5.11 állítás szerint pedig, ha a airport játék

ca ∈ GaN

φ

ca

játék

ψ

megoldása

ψ

megoldása

megoldás megegyezik a

c

φ

Shapley-

airport probléma által generált

Shapley-megoldással, akkor a

c

ca

airport

χ szabály megegyezik az egymást követ® egyenl® hozzájárulás

szabályával. Ezzel igazoltuk a tételt. A fenti bizonyításokkal új igazolását adtuk a Dubey (1982) és a Moulin és Shenker

(1992) tételeknek, valamint összekapcsoltuk az airport játékok esetében és az airport problémák területén elért eredményeket.

27

6. fejezet Összefoglalás

A dolgozatot egy elméleti áttekintéssel kezdtük, amelyben az átruházható hasznosságú kooperatív játékok, röviden TU játékok osztályán el®forduló legfontosabb fogalmak, állítások, tételek kerültek bemutatásra. Egy-egy fogalmat általában példa követett, amely a könnyebb érthet®ség és a szemléletesség célját szolgálta. A bevezet®b®l külön kiemelnénk a Shapley-érték és ehhez kapcsolódóan a Shapley-megoldás fogalmát. A dolgozatban a Shapley-megoldást tanulmányoztuk a TU játékok egy részosztályán, az airport játékok osztályán. Ezután következett a dolgozat középpontjában álló airport játékok osztályának vizsgálata. El®ször bemutattuk az airport játék fogalmát, majd a játékosztály f®bb tulajdonságait tekintettük át. A következ® szakaszban pedig megmutattuk, hogy a Shapley-érték két karakterizációja, az 1953-as Shapley-féle(Shapley (1953)) és az 1985-ös Young-féle(Young (1985)) axiomatizáció teljesül a vizsgált játékosztályon. A Young-féle axiomatizáció igazolása esetében az eredeti Young-féle bizonyítást alkalmaztuk. A dolgozat záró fejezetének kiindulópontjaként a Thomson (2007) cikk szolgált. A cikk áttekintést ad az airport játékok osztályáról, az eddig elért eredményekr®l. A tételeket, hogy a fent említett Shapley-féle valamint Young-féle axiomatizáció teljesül az airport játékok osztályán, el®ször Dubey (1982) valamint Moulin és Shenker (1992) igazolták. A Thomson (2007) cikkre támaszkodva igazoltuk Dubey (1982) illetve Moulin és Shenker (1992) eredményeit. Az igazolás menete a következ®képpen alakult: el®ször a Thomson (2007) cikk axiómáit megfeleltettük a szokásos játékelméleti axiómáknak. Mivel a Shapley-érték eredeti Shapley-féle és Young-féle axiomatizációját airport játékokra beláttuk az el®z® fejezetben, így Dubey illetve Moulin és Shenker eredményeit könnyen igazoltuk. Ezzel a bizonyítással új igazolást adtunk a Dubey (1982) illetve Moulin és Shenker (1992) eredményekre. Költségelosztási problémák a gazdasági életben is gyakran el®fordulnak. Ez a

28

tény indokolja a kooperatív játékelméleten belül a költségjátékok alaposabb vizsgálatát. Az airport játékok széleskör¶ irodalma pedig alátámasztja, hogy a kooperatív játékelmélet fontos részét alkotják az airport játékok. A 4. fejezetben vizsgált probléma, hogy a Shapley-érték fenti Shapley-féle és Young-féle axiomatizálása érvényes-e az airport játékok osztályán, relevánsnak bizonyul, hiszen a TU játékok osztályán teljesül® tulajdonságok nem feltétlenül igazak annak részosztályain. Jelen dolgozatban a Shapley-érték karakterizációját vizsgáltuk az airport játékok osztályán. Emellett azonban számos érdekes kérdés, probléma merülhet fel az említett játékosztállyal kapcsolatban. Egyike ezeknek a nukleolusz vizsgálata airport játékokon. A Thomson (2007) cikk végén található egy táblázat, hogy melyik szabály melyik TU játékokon értelmezett megoldásnak feleltethet® meg. Valamint fel vannak sorolva azok a tulajdonságok, axiómák is, amelyek teljesülnek az adott szabályok esetén. Ebben a táblázatban megtalálható a nukleolusz is. Úgy gondoljuk, hogy ennek vizsgálata képezheti egy következ® kutatás alapját.

29

Irodalomjegyzék

Balog D, Csóka P, Pintér M (2010) T®keallokáció nem likvid portfóliók esetén. Hitelintézeti Szemle 6:604616 Csóka P (2003) Koherens kockázatmérés és t®keallokáció. Közgazdasági Szemle L(10):855880 Dubey P (1982) The shapley value as aircraft landing feesrevisited. Management Science 28:869874 Forgó F, Olajos M (1991) A family of cost allocations methods for a tree. PU.M.A. Pure Mathematics and Applications 1:513 Gillies DB (1959) Solutions to general non-zero-sum games. Contributions to the Theory of Games IV. Princeton University Press Ichiishi T (1981) Super-modularity: Applications to convex games and the greedy algorithm for LP. Journal of Economic Theory 25:283286 Littlechild SC, Owen G (1973) A simple expression for the Shapley value in a special case. Management Science 20:370372 Moulin H, Shenker S (1992) Serial cost sharing. Econometrica 60:10091037 Peleg B, Sudhölter P (2003) Introduction to the theory of cooperative games Kluwer Pintér M (2007) Regressziós játékok. Szigma XXXVIII:131147 Pintér M (2009) A Shapley-érték axiomatizálásai. Alkalmazott Matematikai Lapok 26:289315 Shapley LS (1953) A value for

n-person

games. In: Kuhn HW, Tucker AW (eds.)

Contributions to the theory of games II, Annals of Mathematics Studies 28. Princeton University Press, Princeton pp. 307317 Shapley LS (1971) Cores of convex games. International Journal of Game Theory 1:1126

30

Solymosi T (2007) Kooperatv játékelmélet (elektronikus jegyzet).

http://web.

uni-corvinus.hu/~pmiklos/Works/PDF/solymosi_jatekelmelet.pdf Thomson W (2007) Cost allocation and airport problems. Rochester Center for Economic Research, Working Paper No. 538 Young HP (1985) Monotonic solutions of cooperative games. International Journal of Game Theory 14:6572

31