Amint az Forgó Ferenc bevezető tanulmányából is kiderül, a játékelméletet szokás két fő (egymástól szigorúan el nem választható) területre osztani attól függően, hogy az érdekeiket és a helyzet adta cselekvési lehetőségeiket felismerni képes racionális döntéshozók közötti konfliktus, avagy a hatékonyabb érdekérvényesítés által motivált együttműködés a vizsgálat tárgya. A másodiknak említett terület, a kooperatív játékok az olyan többszereplős döntési helyzetek matematikai modelljei, amelyekben a szuverén döntéshozók (játékosok) együttműködhetnek egymással, sőt erre vonatkozóan (valamilyen külső erő által számon kérhető) kötelezettséget is vállalhatnak. Ilyenkor a szereplők érdekei között fennálló ellentétek másodlagosak az együttműködésre késztető érdekazonosságokhoz képest. A nemkooperatív játékokban a játékosok közötti (teljes vagy részleges) konfliktuson van a hangsúly, a kooperatív modellekben viszont a kölcsönös előnyök kiaknázása sokkal fontosabb a játékosok számára, mint az együttműködésük hozadékának elosztásakor közöttük fellépő szembenállás.

A kooperatív modellek sajátossága, hogy nem részletezik a játék időbeli lefolyását, a szereplők döntési lehetőségeit, az információk elérhetőségét, az alkufolyamatokat, hanem csak az egyes társulások (koalíciók) által elérhető kimeneteleket adják meg. A játékelméleti modellek közül a kooperatív alaptípus a legkevésbé részletező, ebben tekintünk leginkább „madártávlatból” a döntési helyzetre. Ez gyakran szükségszerű is ahhoz, hogy elemezhető modellt kapjunk. Ha „alább szállnánk”, a nagyobb felbontásban kirajzolódó részletek hamar kezelhetetlenül bonyolulttá tehetnék a modellt, „nem látnánk a fától az erdőt”. Például, ha egyébként konkurens vállalatok egy új technológia közös kifejlesztését fontolgatják, akkor az egyes társulások által és ezeken belül a számukra elérhető előnyök meghatározásán alapuló elemzés még megvalósítható feladat lehet, de a képlékeny helyzet miatt egy részletesebb stratégiát eredményező, strukturáltabb modell felépítése már nehezen elképzelhető.

Az idézett dolgozatban arról is szó esett, hogy a kooperatív modellek két alapkategóriába sorolhatók, aszerint, hogy létezik-e vagy sem egy olyan, az összes szereplő számára közös értékmérő („pénz”), ami lehetővé teszi az egyéni hasznosság-skálák közötti egy az egybeni átválthatóságot, és ezáltal egyrészt egy koalíció „értékének” meghatározhatóságát, másrészt ennek az elérhető összhaszonnak a tagok közötti tetszőleges eloszthatóságát. Amint az a nemkooperatív játékoknál is igaz, a hasznosságok összehasonlíthatósága itt is nagymértékben leegyszerűsíti a modellt, és megkönnyíti az elemzést. Az átváltható hasznosságú (transferable utility) kooperatív játékokban az egyes koalíciók által elérhető kimeneteleket egy-egy számmal jellemezhetjük. Amennyiben viszont nincs egy ilyen értékmérő, a helyzet leírásához az elérhető haszonszint-vektorok halmazának koalíciónkénti megadására van szükség. Itt is igaz tehát, hogy „a pénz nem boldogít, de megkönnyíti az életet”. A továbbiakban csak átváltható hasznosságú kooperatív játékokkal foglalkozunk, és (kooperatív) játék alatt mindig egy ilyen modellt értünk.

Az alapmodell és néhány példa

A Neumann János és Oskar Morgenstern (1944) által bevezetett alapmodell két részből áll: a játékosok nem üres, véges N = {1, 2, …, n} halmazából és egy v karakterisztikus függvényből, amely az N minden S részhalmazához (koalíció) hozzárendel egy v(S) valós szá­mot, és amelyre az egyetlen (a közös hasznosság-skála kezdőpontját rögzítő) kikötés az, hogy az üres koalícióhoz a 0-t rendelje. A v(S) számot az S koalíció értékének nevezzük.

Egy kooperatív játék tehát megadja a különböző lehetséges koalíciók értékét, amit legtöbbször úgy értelmezünk, mint a koalíció tagjai által (a koalícióban részt nem vevő játékosok döntéseitől függetlenül) elérhető hasznosságok összegének legnagyobb értékét, ezáltal mintegy (pénzben) mérve az összefogás lehetőségének hasznosságát. Például, ha egy termelési folyamatban az erőforrások különböző döntéshozók ellenőrzése alatt állnak, egy koalíció értékének tekinthetjük az együttműködésbe bevitt erőforrásokból kitermelhető legnagyobb hasznot.

Nézzünk néhány olyan döntési szituációt, amelyet kooperatív játékként vizsgálhatunk.

Lóvásár (Neumann–Morgenstern, 1944 alapján)

Hárman vannak a vásárban. A-nak van egy eladó lova, amit 200 tallérnál olcsóbban nem hajlandó eladni. B és C mustrálgatja a lovat, B legfeljebb 280 tallért, míg C legfeljebb 300 tallért hajlandó a jószágért adni. Most feltesszük, hogy a tallér tényleg „pénz”, vagyis eggyel több vagy eggyel kevesebb tallér ugyanazt „jelenti” bármelyik szereplőnek. A kezdeti állapotot tallérban kifejezve kapjuk, hogy v(A)=200, míg v(B)=280 és v(C)=300, hiszen az eladónál lévő tényleges pénzmennyiség nyilván éppúgy érdektelen az esetleges üzlet megítélése szempontjából, mint a vevőknél lévő, a vételárplafonjukat meghaladó pénzmennyiség. Ha A és B meg tud egyezni abban, hogy a ló p tallér fejében gazdát cserél, akkor együttműködésük eredménye egy olyan helyzet, amely v(AB)=p+(280+280–p) =560 tallért ér, függetlenül az átadott vételártól. Ha A a C-nek adja el a lovat p tallérért, akkor együtt egy v(AC)=p+(300+300–p) =600 tallért érő helyzetbe jutnak, a koalíción belüli tényleges pénzmozgás megint nem számít. A két vevő viszont legfeljebb pénzt adhat át egymásnak, de abból többletérték nem keletkezik, vagyis v(BC)=280+300=580 tallér a legtöbb, amit elérhetnek. Hárman együttműködve sem tudnak többet kihozni a helyzetből, mint v(ABC)=880 tallér, hiszen többletérték csak a ló eladásából származhat, ez pedig maximálisan 300 tallér (amennyiben a ló a C-é lesz), az üzletre szánt összesen 280+300 tallér újraelosztása ehhez hozzáadni semmit nem tud.

Egyszerűsíthetjük a modellt, ha a kezdeti vagyoni helyzeteket tekintjük azoknak a ki­indulópontoknak, amelyekhez viszonyítják majd a szereplők az egyes kimeneteleket. Ilyenkor a szereplőkhöz hasonlóan minket is csak az érdekel, hogy mennyi az együttműködés hozadéka (tallérban kifejezve), aminek elosztásán aztán lehet majd vitatkozni. Ezért a továbbiakban lóvásár játékon a következő normalizált játékot értjük:
 

Kesztyűpiac (Shapley, 1959 alapján)

A névadó helyzetleírás szerint az ivóban az aranyásók közül egyeseknek egyetlen balkezes kesztyűjük van, míg másoknak egyetlen jobbkezes kesztyűjük. Értéke viszont csak egy pár kesztyűnek van, mégpedig egy üveg whisky. Ha mindegyik aranyásó azonosan értékel eggyel több vagy eggyel kevesebb kupica whiskyt, akkor a nedűt tekinthetjük az általános értékmérő „pénz”-nek. Egy koalíció értékét a tagjai által birtokolt kesztyűkből összeállítható párok száma adja meg, ennyi az összefogásuk által elérhető összhaszon (üveg whiskyben kifejezve). Képlettel, v(S)=min{|S∩B|,|S∩J|}, ahol B jelöli a balkezes, míg J a jobbkezes kesztyűvel rendelkező szereplők halmazát. Egy csupa balkezes kesztyűvel rendelkező társulás értéke például ugyanúgy nulla, mint önmagában bármelyik aranyásóé. Viszont, ha csatlakozik hozzájuk egy jobbkezes kesztyűs társuk, értékük rögtön 1-re ugrik, azon már lehet osztozkodni.

Csődeljárás (Aumann–Maschler, 1985 alapján)

A babilóniai Talmud több mint kétezer éves törvény- és ítéletgyűjteményében található a következő, nagyon is ismerős döntési helyzet annak meglehetősen különös megoldásával együtt. Szét kell osztani E pénzegységnyi va­gyont három hitelező között, akik rendre d₁=100, d₂=200, d₃=300 pénzegységnyi (jogilag egyformán érvényes) követeléssel állnak elő. Gond (csődhelyzet) akkor van, ha E<d₁+d₂+d₃, vagyis a vagyon nem elegendő az összes adósság teljes kiegyenlítésére. A Talmud szerint egy Nathan nevű rabbi ítéletei E=100, E=200, E=300 esetekre a következők:
 

Az első esetben a döntés megfelel az egyenlő elosztás elvének, a harmadik esetben viszont mintha a követelések nagyságával arányos elosztás elvét alkalmazta volna. Már ez a váltás is elgondolkodtató, mert a rabbi vélhetően ugyanazt az „igazságtételi” elvet követve hozta meg döntéseit. Az igazi fejtörést azonban az E=200 eset jelenti már önmagában is, a feltételezett egységes világképbe illesztése pedig különösképpen, hiszen a Talmud ezen döntések magyarázatára vonatkozóan még utalásokat sem tartalmaz. A sok évszázados talányt a játékelmélet két neves „úttörőjének”, Robert Aumann-nak és Michael Maschlernek sikerült megoldania (már amennyire egy ilyen „régészeti” probléma egyáltalán megoldottnak tekinthető) kooperatív játékelméleti eszközök segítségével. Barry O’Neill (1982) ötletét követve a fenti három csődhelyzet mindegyikéhez meghatároztak egy-egy kooperatív játékot, és észrevették, hogy ezeknek a játékoknak a nukleolusz szerinti megoldása mindhárom esetben visszaadja a Talmudban leírt elosztásokat. A nukleolusz játékelméleti tulajdonsá­gait a csődhelyzetre „visszavetítve”, és ezeket a Talmudban egyéb helyeken fellelhető hasonló jellegű helyzetekben hozott döntésekhez, illetve az azokhoz fűzött magyarázatokhoz kapcsolva Aumann és Maschler rögtön három hihető választ is tudott adni arra vonatkozóan, hogy milyen elv vezérelhette Nathan rabbit döntéseiben. Ezekről – hely hiányában – még röviden sem szólunk, csak a modellt ismertetjük. O’Neill (1982) nyomán egy n-szereplős (E; d₁, d₂, …, d_n) csődhelyzetben az {1, 2, …, n}-beli hitelezők egy S csoportjának „értékén” a v(S)=max{0, E–d(N \ S)} számot értjük, ahol d(N \ S) jelöli az S-be nem tartozó adósságok összegét. A modell alapgondolata az, hogy a vagyon értékéből az S-beliek kizárólagosan csak v(S)-nyire tarthatnak igényt, miután a többiek teljes egészében visszakapták hitelük értékét.

Költségmegosztás
(Straffin – Heaney, 1981 alapján)

Az 1930-as évekbeli nagy gazdasági világválság után az USA Kongresszusa létrehozta a Ten­nessee Valley Authorityt (TVA) a Tennes­see-folyó medencéjében végrehajtandó nagyszabású gát- és tározórendszer-építések előkészítésére és lebonyolítására. Az elérendő célokat három fő csoportba sorolták: hajózás (1), árvízvédelem (2), elektromos áram termelése (3). A TVA-t létrehozó törvény előírta, hogy a beruházási költségeket e három célcsoport között kellett felosztani. A feladat nehézsége abban állt, hogy az egyes célok elérésének a költségekre gyakorolt hatása összekeveredik, mivel egy adott vízszabályozási megoldás egyszerre több célkitűzésnek is megfelelt. A TVA munkatársai által kidolgozott elvek és módszerek mintegy előrevetítettek bizonyos kooperatív játékelméleti fogalmakat és megoldásokat. Például, az egyes célcsoportok költségkihatásának számszerűsítése érdekében meghatározták egy sor olyan gátrendszer megépítésének költségét, amelyek a célcsoportok közül maradéktalanul csak egyeseket valósítanak meg. Az egyes kombinációkra a költségek (millió akkori dollárra kerekítve) a következők voltak:
 

A csak hajózási célokat szolgáló gátrendszer tehát C(1)=164 millió dollárba került volna, a hajózásnak és az árvízvédelemnek is megfelelő megoldás C(12)=302 millió dollárba stb. A mindhárom fő cél elérésére alkalmas (a ténylegesen megvalósítandó) gát- és tározórendszer költségét C(123)=414 millió dollárra becsülték, ennek szétosztása volt tehát a feladat. A TVA munkatársai végső javaslatukat a fenti költségfüggvényre alapozták, ami gyakorlatilag egy kooperatív játék, azzal a különbséggel, hogy itt a preferenciák fordítottak (a kisebb a jobb). Ráadásul konkrét javaslatukat olyan elvek mentén határozták meg, amelyek megfelelnek bizonyos kooperatív megoldási koncepciók alapelveinek.

A hasonló költségelosztási problémák kooperatív játékelméleti eszközökkel való elemzésekor a költségek helyett használhatjuk a célcsoportok közötti „összefogás” értékét jobban kifejező költségmegtakarításokat is. Ha C(S) adja meg a célok egy S csoportját kiszolgáló többfunkciós megoldás költségét, akkor a csak egy-egy célra alkalmas egyedi megoldások költségeinek összegéhez képest v(S)=∑iεSC(i)–C(S) pénzegységnyi költségmegtakarítás érhető el. Ilyen módon a TVA fenti költségfüggvényéből az alábbi (normalizált) koalíciós függvényt kapjuk:
 

Erre a játékra a különféle kooperatív megoldási koncepciókat alkalmazva már nemcsak a TVA által kidolgozott megoldásokat kapnánk vissza, hanem egyéb elveket megtestesítő elosztásokat is. Az újabb keletű elemzésekben gyakran élnek ezzel a megközelítéssel. Ez­zel kapcsolatban kezdetnek H. Peyton Young (1994) áttekintő tanulmányát ajánljuk.
Már ebből a néhány példából is látszik a kooperatív alapmodell sokrétű alkalmazási lehetősége. Az utolsó történetben például a „szereplők” már nem is racionálisan cselekvő „hús-vér” döntéshozók, mint az első két esetben (vagy a nemkooperatív modellekre vezető tipikus helyzetekben), hanem „személytelen” célok. A probléma a Talmud-beli csődhelyzetekben és a TVA költségmegosztási feladatában is igazából egy igazságos döntőbíró problémája, aki a konkrét helyzetektől függetlenül megfogalmazott és általánosan elfogadott elvek szerint javasol semleges meg­oldásokat az „ügyfelei” között fennálló részleges konfliktusokra. Ilyen alkalmazásokban a „pénz” minden szereplő általi azonos megítélésére tett feltevésünk nemcsak, hogy nem problematikus, sőt inkább követelmény, hiszen például egy kizárólag a „fogyasztás függ­vényében” megállapítandó költségelosztásnál a pénz egyénenkénti hasznosságát befolyásoló egyéb (például anyagi helyzetre vonatkozó) szempontok nem vehetők figyelembe.

Megoldások

Egy kooperatív játékkal modellezett döntési helyzetben két egymással szervesen összekapcsolódó alapkérdés van:

• milyen koalíciók jönnek létre,

• mennyi lesz az egyes szereplők kifizetése.

Egyrészt egy társulás létrejöttéhez nyilván elengedhetetlen, hogy a részt vevők meg tudjanak egyezni az együtt elérhető össz­haszon mindegyikük számára elfogadható elosztásában. Másrészt egy szereplő kifizetését nyilván befolyásolja, hogy kikkel működik együtt, és mekkora lesz a torta, amelyből ő is részesül.

Az ismertetett kooperatív helyzetek mindegyike olyan, hogy bármely két, közös szereplőt nem tartalmazó koalíció egyesüléséből csak előny származhat. A kapcsolódó játék tehát mindegyik esetben szuperadditív, azaz tetszőleges, diszjunkt S és T koalíciók esetén v(S)+v(T)≤v(SÈT) teljesül. A Lóvásár és a Kesztyűpiac példákban ez nyilvánvaló, a csődjátékokra ezt általánosan sem nehéz igazolni, a TVA költségmegtakarítási játékban pedig azért teljesül, mert az adott költségfüggvény szubadditív, azaz C(S)+C(T)≥C(SÈT) áll fenn bármely két, közös elemet nem tartalmazó S és T célkombináció esetén.

Szuperadditív játékkal modellezhető helyzetekben megvan a késztetés arra, hogy egyre nagyobb koalíciók jöjjenek létre, és végső soron megvalósuljon az összes játékost magában foglaló nagykoalíció. A játékosok koalíciókba szerveződésének modellezése ennél persze jóval összetettebb probléma, mert akár egy egyébként szuperadditív játékként megfogható helyzetben is felmerülhetnek olyan szempontok, amelyek miatt a nagykoalíció esetleg mégsem jön létre. Vegyük észre például, hogy a Lóvásár példában a nagykoalíció értéke már nem több mint az AC koalíció értéke, mégis a gyengébb vételi pozícióban lévő B vevő jelenléte nagyon is befolyásolja a másik két szereplő tárgyalási pozícióját.

Egy szuperadditív koalíciós függvénnyel modellezhető helyzetben tehát bármilyen társuláskonfigurációhoz képest előnyösebb (vagy legalábbis nem előnytelenebb) a nagykoalíció, már ami az elérhető legnagyobb összhasznot illeti. De nézzük annak elosztását. Természetesen mindegyik szereplő a saját részesedését kívánja növelni, ami persze csak a többiek kárára történhet. Ugyanakkor a többi szuverén szereplő együttműködése nélkül nincs miből részesedni, ezt pedig csak kellő önkorlátozással lehet elérni. E két egymással ellentétes cél közül most tehát az együttműködést lehetővé tevő kellő mértékű visszafogottság az elsődleges fontosságú, a relatíve legkedvezőbb részesedés megszerzése pedig csak másodlagos motiváló tényező lehet.

A továbbiakban végig feltesszük, hogy létrejön az N nagykoalíció. Ekkor a fő kérdés már csak az, hogy az N által elérhető v(N)-ből miként részesedjenek az egyes szereplők. Jelölje xi az i játékos kifizetését. Ekkor az (N,v) játék által leírt kooperatív döntési helyzet egy kimenetelét (a játék egy megoldását) egyszerűen a játékosok kifizetéseit tartalmazó (x₁, x₂, ... , x_n) vektorral adjuk meg. (Általánosabb modellekben a létrejövő koalíció-struktúra és a kifizetés-vektor együtt írja le a kimenetelt.)

Nézzünk olyan tulajdonságokat, amelyeket a megoldásoktól a legtöbb esetben „joggal” elvárhatunk. Először is a kimenetelnek megvalósíthatónak kell lennie, azaz a kifizetések összege nem haladhatja meg az elérhető össz­hasznot: x₁+x₂+…+x_n≤_v(N). A teljes összegnél kevesebbet szétosztani viszont nem racionális megoldás, hiszen van olyan megvalósítható megoldás is, ami mindenki számára előnyösebb. Ugyancsak valószerűtlen egy olyan kimenetel, amelyben valamelyik szereplő kevesebbet kap, mint amennyit egyénileg (senkivel sem együttműködve) el tud érni. Ezen érvelések alapján Neumannt és Morgensternt követve az (N,v) (szuperadditív) játék megoldását (megoldásait) eleve csak az alábbi két feltételt teljesítő kifizetés-vektorok között fogjuk keresni:

1. x₁+ x₂+…+ x_n = v(N) (Pareto-hatékonyság)

2. x_i≥v(i) minden i játékosra (egyéni elfogadhatóság).

A Pareto-hatékony kifizetés-vektorokat szétosztásoknak, a minden szereplő számára elfogadható szétosztásokat pedig elosztásoknak fogjuk hívni. Elosztások minden olyan (N,v) játékban léteznek, amelyben v(N)≥v(1)+v(2)+...+v(n). A szuperadditív játékok nyilván ilyenek. Amennyiben a nagykoalíció értéke éppen egyenlő az egyénileg elérhető hasznok összegével, akkor egyetlen elosztás van, mégpedig x_i=v(i) minden i játékosra. Ha az együttműködésnek nincsen hozadéka, a helyzet kimenetele egyértelmű, a modell az elemzés szempontjából érdektelen. Az ún. lényeges játékokban a v₀(N)=v(N)–(v(1)+v(2)+...+v(n)) többlet pozitív, és ilyenkor annyi különböző elosztás van, ahányféleképpen ezt a többletet a szereplők el tudják maguk között osztani. Könnyen belátható: egy lényeges játékban az elosztások pontosan az y₁+y₂+...+y_n=v0(N) egyenlet nemnegatív megoldásainak segítségével képzett x_i=v(i)+y_i alakú kifizetésekből álló vektorok. Például, a Lóvásár játékban az összes elosztás előáll mint az (x_A=100, x_B=0, x_C=0), (x_A=0, x_B=100, x_C=0) és (x_A=0, x_B=0, x_C=100) „diktatórikus” elosztások valamilyen (nemnegatívan) súlyozott átlaga.

A mag

Jóllehet, rögzítettük a nagykoalíció megalakulását, de ennek hatékonysági okai voltak, a kisebb társulások létrejöttének lehetősége ettől még nem szűnt meg. Éppen ezért, ha egy elosztás összességében kevesebbet juttat egy koalíciónak, mint amennyit tagjai együttműködve (a többiektől függetlenül) el tudnak érni, akkor a nagykoalícióból

való kiválásuk reális veszély, ezzel való „fenyegetésüket” a többi szereplőnek komolyan kell vennie. A mag az olyan elosztások halmaza, amelyeknél ilyen megalapozott fenyegetése egyetlen koalíciónak sem lehet. A mag tehát az

1. x₁+ x₂+…+ x_n = v(N) (Pareto-hatékonyság)

2. x(S) ≥ v(S) minden S koalícióra (csoportos elfogadhatóság)
feltételeket kielégítő kifizetés-vektorok halmaza, ahol x(S)=∑_iεSx_i jelöli az x-nél az S-nek jutó összkifizetést. Az összes elképzelhető társulás általi elfogadhatóság jóval szigorúbb követelményt jelent a szétosztandó v(N) nagyságára nézve, mint a csak az egyszemélyes koalíciók általi. A magot meghatározó lineáris feltételrendszer megoldhatósága elvileg könnyen eldönthető (például egy lineáris programozási feladat megoldásával), az egyedüli nehézséget a feltételek nagy száma jelentheti. A mag szuperadditív játékokban is lehet üres, habár konkrét példáink egyikében sem az. Nézzük őket.

A Lóvásár játékban a magot meghatározó feltételek között szereplő x_A+x_B+x_C=100, x_A+x_C≥100, x_B≥0 feltételeknek csak az (x_A=p, x_B=0, x_C=100-p) alakú kifizetések felelnek meg. Az x_A+x_B≥80 miatt az eladási ár p≥80, az xC≥0 miatt pedig p≤100. Az x_B+xC≥0, illetve x_A≥0 feltételek ugyanakkor már semmilyen további megszorítást nem jelentenek. A magbeli elosztások kifejezik a helyzet versenyjellegét. A gyengébbik vételi pozícióban lévő B vevő üres kézzel megy haza, mivel bármilyen legfeljebb 80 talléros ajánlatára C vevő rá tud ígérni. Ugyanakkor éppen B érdeklődé­se miatt tud A eladó legalább 80 talléros árat kialkudni C vevőtől, hiszen C bármilyen 80 tallér alatti vételi ajánlatával szembe tud állítani egy picit magasabb árajánlatot B-től.

A Kesztyűpiac játék magjában ez a jelenség még szembetűnőbb. Ha a balkezes, illetve jobbkezes kesztyűt birtokló aranyásók egyenlő számban vannak jelen (a piac kiegyensúlyozott), akkor a mag az olyan elosztások halmaza, amelyben mindegyik balkezes kesztyűs szereplő kifizetése p, míg mindegyik jobbkezes kesztyűs szereplő kifizetése 1–p, valamilyen 0 és 1 közötti p-vel. A mag tehát egyformán jutalmazza az ugyanolyan típusú kesztyűvel rendelkezőket, de nem mond semmit a két kesztyűtípus egymáshoz viszonyított értékével kapcsolatban. Ugyanakkor ha akár csak eggyel is több balkezes kesztyű van a piacon, mint jobbkezes, a játék magja egyedül a p=0-hoz tartozó előbbi típusú elosztást tartalmazza. A túlkínálatban lévő áru teljesen leértékelődik.

A Talmudból vett csődhelyzetekhez tartozó csődjátékokban sem üres a mag. Könnyen ellenőrizhető, hogy például a rabbi által javasolt elosztás mindhárom esetben a magba tartozik. Hamarosan látjuk majd, hogy ez nem véletlen.

A TVA megtakarítási játék magja sem üres, például az egyenlő (x₁=47, x₂=47, x₃=47) elosztás magbeli. Ez persze egyáltalán nem szükségszerű, ebben a játékban azért teljesül, mert a v(N) értéke kimondottan magas a többi koalíció értékéhez képest. Magbeliek ugyanakkor a (0, 3, 138), (0, 106, 35), (3, 0, 138), (117, 0, 24), (35, 106, 0) és (117, 24, 0) elosztások is. Most a mag pontosan azon elosztások halmaza, amelyek előállnak mint e hat elosztás valamilyen (nem ne­gatívan) súlyozott átlagai. A mag most túl sokféle elosztást tartal­maz, nem nagy segítség a költségmegosztási probléma megoldásában. Megragad ugyanakkor olyan fontos alapelveket, amelyeket már a TVA munkatársai is hangsúlyoztak.

Az egyik a „csináld magad”-elv, amely kimondja, hogy egyetlen célcsoport se fizessen többet annál, mint amennyibe egy az ő céljaikat megvalósító megoldás kerülne. A megtakarításokra átfogalmazva ez éppen a csoportos elfogadhatóság követelménye. Az esetleges különválással való fenyegetés a TVA-esethez hasonlóan sok költségmegosztási problémában puszta gondolatkísérlet, mert eleve rögzített, hogy az összes célra alkalmas megoldást kell megvalósítani. A hatékonyságra apellálni ilyenkor kevéssé meggyőző. Az ilyen helyzetekben az „igazságosság” fontosabb szempont. Egy ilyen jellegű elv a „fizesd magad”, amely kimondja, hogy összességében mindegyik célcsoport fizessen legalább annyit, mint amennyi kizárólag az ő céljaik megvalósítása miatt jelenik meg a teljes költségben. Az S célcsoport igényei nélkül egy C(N \S) költségű megoldás is megfelelne, a C(N) összköltségből tehát kimondottan az S számlájára írandó C(N)–C(N\S). Ha összességében legalább ennyit nem rónak ki az S elemeire, akkor bizonyos fokig a többi cél „szubvencionálja” az S-beli célok elérését. Ha a teljes költséget a célok között kell felosztani (a megtakarításokra átfogalmazva ez éppen a Pareto-hatékonyság), akkor a „csináld magad” és a „fizesd magad” elvek ekvivalensek, a hatékonysági és az igazságossági szempontok tehát erősítik egymást.

A nukleolusz

A mag egy intuitíven nagyon természetes stabilitási követelményeket megfogalmazó megoldási koncepció, de vagy túl sok elosztást tartalmaz, vagy egyet sem. Példáinkhoz hasonlóan sok alkalmazásban a játék magja nem üres, de nem is egyértelmű. Van tér tehát további kívánalmakat támasztani a megoldással szemben anélkül, hogy feladnánk a stabilitást. Egy ilyen koncepció a David Schmeidler (1969) által bevezetett nukleolusz. Ez mindig egy magbeli elosztást ad, ha a mag nem üres. Sőt ilyenkor a nukleolusz a mag „legbelsőbb” pontja, elnevezése is ebből a tulajdonságából származik (a mag magja). A nukleolusz egyébként akkor is létezik, ha a mag üres, ilyen játékokban a nukleolusz a (mag által képviselt) stabilitást „legjobban közelítő” elosztás.

A nukleolusz az egyetlen az elosztások között, amelyik mindegyik koalíciónak olyan összkifizetést biztosít, ami úgy haladja meg a lehető legnagyobb mértékben a koalíció értékét, hogy ezzel egyetlen, az adott koalíciónál kevésbé túlfizetett koalíció túlfizetését sem csökkenti. Ezen elv szerint mindig azoknak a legrosszabb helyzetben lévő koalícióknak a helyzetén akarunk javítani, amelyekén még lehet segíteni úgy, hogy ezzel egyetlen náluk rosszabb helyzetben lévő koalíció helyzetén se rontsunk. Ez a (lexikografikus) optimalitási elv egyben módszert is ad a nukleolusz kiszámítására. Nézzünk egy példát.

A Talmud-beli E=200-as esethez tartozó csődjátékban v(123)=200, v(23)=100, az összes többi koalíció értéke 0. Az x=(0, 0, 200) szétosztás elfogadható mindegyik koalíció számára, tehát magbeli. Igen ám, de az x szerint az (1), (2) és (12) koalíciók éppen csak annyit kapnak, mint amennyit önmaguk is el tudnak érni, míg a többi koalíció túlfizetésben, azaz az értékét meghaladó összkifizetésben részesül. Az x-nél a legkisebb túlfizetésben részesülő (1), (2) és (12) koalíciók helyzetén egyszerre tudunk javítani, például a mag „belsejében” lévő y=(50, 50, 100) elosztással. Ekkor már mindegyik koalíció legalább 50-nel többet kapna, mint az értéke (kivéve persze a minden elosztásban az értékével megegyező összkifizetésben részesülő nagykoalíciót, lásd Pareto-hatékonyság). Az (1) és (2) koalíciók az y-nál is a legkevésbé (a pontosan 50-nel) túlfizetettek közé tartoznak (az (12) koalíció túlfizetése 100-ra nőtt), lecsúszott viszont hozzájuk a (23) koalíció. Mivel az (1) koalíció összkifizetését csak a többi játékost tartalmazó komplementer (23) koalíció össz­kifizetésének terhére tudnánk növelni, és fordítva; látjuk, hogy 50-nél magasabb túlfizetést ennek a két koalíciónak egyszerre semmilyen elosztás sem tud garantálni. A túlfizetésüket (s így az elosztással való „megelégedettségük szintjét”) ezért tovább már nem tudjuk emelni. Rögzítsük tehát, hogy az (1)-nek 50-et, a (23)-nak összesen 150-et, a többi koalíciónak pedig az értéküket legalább 50-nel meghaladó összkifizetést kell kapnia. Az y mellett ezeknek a feltételeknek sok más elosztás is megfelel, a keresés tehát folytatódik, de már a leszűkített elosztáshalmazon. A „versenyben” maradó (2), (3), (12) és (13) koalíciók mindegyikének legalább 75-ös túlfizetést nyújt a leszűkített elosztáshalmaz „belsejében” lévő z=(50, 75, 75) elosztás. Ekkor a második legrosszabb helyzetben lévő (a pontosan 75-tel túlfizetett) koalíciók a (2) és a (3). Tovább már rajtuk sem segíthetünk, mert különben együtt már 150-nél többet kapnának, ami viszont a náluk rosszabb helyzetben lévő (1) helyzetét rontaná. Rögzíteni kell tehát ezeket a követelményeket is. A z-n kívül azonban nincs másik olyan elosztás, amelyik az (1)-nek 50-es, a (2)-nek 75-ös, és a (3)-nak 75-ös túlfizetést biztosítana. A keresésnek vége, a z elosztás a csődjáték nukleolusza. Érdemes ellenőrizni, hogy Nathan rabbi döntései a Talmudban szereplő másik két esetben is meg­egyeznek-e a megfelelő csődjátékok nukleoluszaival.

Lássuk röviden a másik három példánkat is: A Lóvásár játékban a nukleolusz az (x_A=90, x_B=0, x_C=10) elosztás, pontosan a magon belül az eladó számára legkedvezőbb p=100 talléros eladási árhoz tartozó (100, 0, 0) és a tényleges C vevő számára legkedvezőbb p=80 talléros árhoz tartozó (80, 0, 20) elosztások egyenlő súllyal vett átlaga.

A Kesztyűpiac játék nukleoluszában mindegyik B-beli játékos kifizetése p=0, ha |B|>|J|; illetve p=1, ha |B|<|J|, hiszen a kiegyensúlyozatlan esetekben ezek az egyetlen magbeli elosztások. A kiegyensúlyozott kesztyűjátékokban viszont a nukleolusz mindegyik játékosnak p=1/2 kifizetést ad, ami itt is a mag­beli két extrém elosztás egyenlő súllyal vett átlaga.

A TVA költségmegtakarítási játék nukleo­lusza az egyenlő (x₁=47, x₂=47, x₃=47) elosztás. Ez a Talmud-beli E=100 esethez hasonlóan azért van így, mert a kétszereplős koalíciók értéke jóval közelebb van az egyszereplősökéhez, mint a nagykoalíció értékéhez. A megtakarításoknak a nukleolusz alapján történő elosztása esetén a költségek allokációjára tett javaslat tehát a következő lett volna: C(1)–x₁ =117 M $ (hajózás), C(2)–x₂=94 M $ (árvízvédelem) és C(3)–x₃=203 M $ (áramtermelés).

Szembetűnő, hogy a nukleolusz nem veszi figyelembe a koalíciók nagyságát, azonos összegű túlfizetés (költségmegosztási problémákban a megtakarítás) azonos mértékű ösztönzésnek minősül kis- és nagyméretű koalíciókra egyformán. Emiatt egyébként a nukleoluszra nem feltétlenül teljesül egy intuitíven elvárható monotonitási tulajdonság. Nevezetesen, ha változatlan egyéb körülmények között a nagykoalíció értéke megnő, előfordulhat, hogy a nukleolusznál egy játékos kifizetése csökken. Költségmegosztási alkalmazásokban ez azt jelenti, hogy ha a projekt tényleges végösszege meghaladja a tervezettet (amire bizony bőven akad példa), de a költségfüggvény többi értékén nem változtatnak, akkor előfordulhat, hogy a nukleolusz-allokáció bizonyos célokra a tervezettnél kisebb hozzájárulást ró ki. Az egy főre jutó túlfizetést a fenti lexikografikus értelemben maximalizáló per capita nukleolusz már teljesíti az említett monotonitási elvárást. Megsértheti viszont a nukleolusznak azt a tulajdonságát, hogy egy sallangjátékos (aki bármelyik koalícióhoz való csatlakozásával a saját értékével azonos értékváltozást idéz elő) kifizetését mindig a játékos értékével egyenlőnek határozza meg. Ezzel és egyéb nukleolusz vál­tozatok tulajdonságaival is foglalkozik Young (1994) tanulmánya.

A Shapley-érték

A kooperatív játékok egyértelmű megoldását eredményező koncepciók közül kétségkívül a legismertebb a Lloyd Shapley rövid, de nagy hatású PhD-dolgozatában bevezetett (és már róla elnevezett) Shapley-érték. Ebben minden játékos az egyes koalíciókhoz való egyéni hozzájárulásainak átlagát kapja. Ez így első látásra elég esetlegesnek tűnhet, ám Shapley (1953) megmutatta, hogy ha egy megoldási koncepciótól megköveteljük az alábbi négy tulajdonságot, akkor csak az általa javasolt szétosztást alkalmazhatjuk, és ez szuperadditív játékokban biztosan egyénileg elfogadható is lesz.
A Pareto-hatékonyság axiómája előírja, hogy a játékosok kifizetéseinek összege egyezzen meg a nagykoalíció értékével. Az anonimitás axiómája megköveteli, hogy egyetlen játékos kifizetése se függjön a nevétől, „érdemei” megállapításakor csak a játékban betöltött szerepe számítson. A sallangmentesség axiómája szerint bármelyik sallangjátékos pontosan a saját értékével megegyező kifizetésben részesüljön. Az additivitás axiómája előírja, hogy ha szétválasztható komponensekből álló helyzetet vizsgálunk, akkor a játékosok kifizetését is a komponensekben külön-külön, a kölcsönhatást kizárva állapítsák meg.

Shapley (1953) nemcsak azt mutatta meg, hogy e négy axiómának csak egyetlen értékelési függvény felel meg, hanem expliciten meg is adta ezt a függvényt, sőt rögtön két ekvivalens alakban is. Itt csak a könnyebben értelmezhető változatot ismertetjük, bár a kiszámítás szempontjából ez a kevésbé hatékony.

Tegyük fel, hogy a játékosok sorban egymás után érkeznek egy szobába, ahol az együttműködési megbeszélések folynak. Ha mindegyik érkező játékos pontosan akkora kifizetést kap, mint amekkora értéknövekedést előidézett a szobában (azaz a már a szobában lévő koalíció értékéhez való határhozzájárulását), akkor az érkezési sorrend nagyon is számít. Amennyiben a játékosok bármelyik érkezési sorrendje egyformán valószínű, akkor egy játékos várható kifizetése egyenlő az összes lehetséges sorrendre vett határhozzájáru­lásának az átlagával. Éppen ez a várható kifizetés az adott játékos Shapley-értéke.

Lássuk példáinkat:

A Lóvásár játékban a három szereplő hat különböző érkezési sorrendjéhez tartozó határhozzájárulások, illetve azok átlagai, azaz a szereplők Shapley-értékei a következők:
 

Az egyes játékosok Shapley-értékéből álló elosztás nincs a magban, hisz B vevő kifizetése most nem 0, mert ha hamarabb ér a vá­sárba, mint C, és rögtön meg is köti az üzletet A-val, akkor C vevő már csak vele tud üzletet kötni, így B üres kézzel már biztos nem megy haza.

A Shapley-érték anonimitásából következik, hogy tetszőleges méretű Kesztyűpiac játékban az azonos típusú kesztyűvel rendelkezők azonos kifizetést kapnak. Nem számít tehát a testsúly vagy a hangerő, csak az értéknövelő képesség. Kiegyensúlyozott esetben ez az egységes kifizetés mindkét típus esetén 1/2, a Shapley-érték és a nukleolusz szerinti elosztás ilyenkor tehát egybeesik. Nem kiegyensúlyozott esetben viszont a Shapley-elosztás különbözik az egyetlen magbeli elosztástól (azaz a nukleolusztól), mert a túlkínálattal rendelkező aranyásók szerepét is jutalmazza valamennyire. Ha valaki úgy érkezik az ivóba, hogy kesztyűjével rögtön egy újabb pár keletkezik és azt rögtön whiskyre váltva nyomban el is fogyasztja, akkor a nap végén a jutalma már nem lehet 0.

A Talmud-beli E=100-as esethez tartozó csődjátékban a Shapley-érték is az egyenlő (33⅓, 33⅓, 33⅓) elosztást írja elő. Szintén a Talmud-belivel (és a nukleolusszal) megegyező, a követelésekkel arányos (50, 100, 150) elosztást kapjuk az E=300-as esetben. Az E=200-as esetre a Shapley-érték a (33⅓, 83⅓, 83⅓) elosztást adja, amely jellegében ugyancsak hasonlít a Talmud-belihez. A d₂=200 és d₃=300 követelések különbözősége a csődjátékban nem jelenik meg, mert az E=200 feletti követelésrész úgyis reménytelen. A két nagyobb hitelezőnek ezért felcserélhető a szerepe a játékban, az anonimitás miatt tehát kifizetésüknek azonosnak kell lennie. A d₁=100-as hitelező ugyanakkor csak a vagyon felére tart eleve igényt. A másik két hitelezőtől való különbözőségét a Shapley-érték viszont a Talmud-belitől eltérően ítéli meg.

Ebben a három csődjátékban a Shapley-érték szerinti elosztás magbeli. Ez egyébként minden csődjátékra igaz, mert tetszőleges csőd­helyzethez tartozó csődjáték konvex (azaz tetszőleges S és T koalíciók esetén v(S)+v(T) ≤v(SÈT)+v(S∩T) teljesül), és mint Shapley (1971) megmutatta, tetszőleges konvex játékban a Shapley-érték magbeli. O’Neill (1982) vizsgál olyan szintén a Talmudban előforduló eljárásokat, amelyek jellegükben a Shapley-értékhez hasonló elosztást eredményeznek.

A TVA költségmegtakarítási játékra a Shapley-érték a magnál felsorolt hat elosztás átlagát, az (x₁=45,33, x₂=39,83, x₃=55,83) elosztást adja. Ezen elv alapján a költségek allokációjára tett javaslat tehát a következő lett volna: C(1)–x₁=118,67 M $ (hajózás), C(2)–x₂= 101,17 M $ (árvízvédelem) és C(3)–x₃=194,17 M $ (áramtermelés). Ez az allokáció megfelel a „fizesd magad”-elvnek, egyik célcsoport sem szubvencionálja a másikat. Ez egyébként minden olyan esetben igaz, amikor az adott költségfüggvény konkáv (azaz C(S)+C(T) ≥ C(SÈT)+C(S∩T) áll fenn bármely két S és T célkombináció esetén), mivel ilyenkor a megtakarítási játék konvex, és ezért a szereplők bármilyen sorrendjéhez tartozó határhozzájárulás-vektor, valamint ezek átlaga, a Shapley-elosztás is magbeli. Amennyiben a megtakarítási játék nem konvex, a Shapley-értékre alapozott költségallokáció esetleg megsérti a „fizesd magad”-elvet. Ez kétségkívül hátránya lehet bizonyos alkalmazásokban. A Shapley-érték ugyanakkor eleget tesz különféle monotonitási elvárásoknak.

A Shapley-értéknek az ismertetett eredeti jellemzésen kívül számos egyéb axiomatizációja is létezik. Itt csak H. Peyton Young (1985) eredményét említjük, aki az additivitás és a sallangmentesség helyett az ún. erős monotonitást követeli meg a Pareto-hatékonyság és az anonimitás axiómák mellett. Az erős monotonitásból következik például, hogy egy játékos kifizetése csak a határhozzájárulásaitól függ. Young (1985) bizonyította azt is, hogy a legalább öt játékost tartalmazó játékokon nincs olyan megoldási koncepció, amelyik egyrészt mindig magbeli elosztást ad, ha a mag nem üres, másrészt teljesül rá az ún. koa­líciós monotonitás (egy, az erős monotonitás­nál valamivel gyengébb tulajdonság). David Housman és Lori Clark (1998) igazolták, hogy ez már a legalább négyszereplős játékokra is igaz, de a legfeljebb háromszereplős játékokon a magbeliség és a koalíciós monotonitás összebékíthető, például a nukleolusz és különböző variánsai teljesítik mindkét követelményt.

Abban a reményben fejezzük itt be írásunkat, hogy sikerült bepillantást nyújtani a kooperatív játékok „klasszikus” elméletébe, a példákon keresztül pedig az alkalmazási lehetőségeibe.
 

Kulcsszavak: kooperatív játékok, mag, nukleolusz, Shapley-érték
 

IRODALOM

Aumann, R. J. – Maschler, M. (1985): Game Theoretic Analysis of a Bankruptcy Problem from the Talmud. Journal of Economic Theory. 36, 195–213.

Housman, David – Clark, Lori (1998): Core and Monotonic Allocation Methods. International Journal of Game Theory. 27, 611–616.

Neumann, John von – Morgenstern, Oskar (1944): Theory of Games and Economic Behavior. Princeton University Press, Princeton

O’Neill, Barry (1982): A Problem of Rights Arbitration from the Talmud. Mathematical Social Sciences. 36, 195–213.

Schmeidler, David (1969): The Nucleolus of a Characteristic Function Game. SIAM Journal on Applied Mathematics. 17, 1163–1170.

Shapley, Lloyd S. (1953): A Value For N-Person Games. In: Kuhn, Harold William – Tucker, Albert William et al. (eds.): Contributions to the Theory of Games. II. Princeton University Press, Princeton, 307–317. WEBCÍM >

Shapley, Lloyd S. (1959): The Solutions of a Symmetric Market Game. In: Tucker, Albert William – Luce, Robert Duncan (eds.): Contributions to the Theory of Games. IV. Princeton University Press, Princeton, 145–62. WEBCÍM >

Shapley, Lloyd S. (1971): Cores of Convex Games. International Journal of Game Theory. 1, 11–26.

Straffin, Philip D. – Heaney, James P. (1981): Game Theory and the Tennessee Valley Authority. International Journal of Game Theory. 10, 1, 35–43.

Young, H. Peyton (1985): Monotonic Solutions of Cooperative Games. International Journal of Game Theory. 14, 65–72.

Young, H. Peyton (1994): Cost Allocation. In: Aumann, Robert J. – Hart, Sergiu (eds.): Handbook of Game Theory with Economic Applications. II. Elsevier, Amsterdam, 1193–1235.