Néhány szó a kooperatív játékelméletről
Amikor játékelméletről beszélünk, különbséget kell tennünk a
tudományterület két nagy ága, a nem kooperatív, illetve a kooperatív
játékelmélet között. Előbbi esetében olyan többszereplős problémákat
vizsgálunk, amikor az egyes résztvevőknek lehetőségük van különböző
stratégiák alapján cselekedni. Ezek a stratégiák résztvevőnként
eltérőek lehetnek, de az egyének által választott stratégiák végül
hatással vannak egymásra. Így a konkrét egyéni döntés minden esetben
attól függ, hogy a többi egyén összes választható stratégiáira
felkészülve mi a legjobb stratégiánk. Azaz van-e olyan stratégiánk,
ami biztosítja, hogy bárhogyan is cselekednek a többiek, mi egyetlen
másik stratégiánk esetén se jártunk volna jobban. A közismert
Nash-egyensúly a többi játékos aktuális stratégiája melletti „legjobb
választ” adja meg. Vagyis olyan állapotot ad meg, hogy ha a többi
játékos nem változtat az aktuális stratégiáján, akkor nekünk sem
érdemes változtatnunk, mert semelyik másik stratégiánk esetén sem
járnánk jobban.
A kooperatív játékelmélet ezzel szemben a
résztvevők – továbbiakban játékosok – közötti együttműködést,
„kooperációt” hivatott modellezni. A játékosok különböző csoportokat,
ún. koalíciókat alkothatnak, és ezek a koalíciók adott esetben több
mindent elérhetnek együtt, mintha a benne részt vevő játékosok
külön-külön, egyénileg cselekedtek volna. Két kérdésre keressük a
választ: milyen koalíciók jönnek létre, és ezek hogyan osztják el az
együttműködés gyümölcsét a tagjaik között. Ugyanis nem feltétlenül
igaz az, hogy mindenki egyenlőképpen járult hozzá a közös sikerhez,
így az egyenlő osztozkodás nem feltétlenül igazságos is egyben.
Shapley volt egyike azoknak, akik a kooperatív játékelmélet alapjait
lefektették, sőt, a témával kapcsolatos kérdésfelvetései, megoldási
javaslatai teszik ki a tudományterület máig kialakult formájának
jelentős részét; szinte nincs olyan terület a kooperatív
játékelméleten belül, amihez ne tett volna hozzá valamit. Robert J.
Aumann saját, 2005-ös Nobel-díj székfoglaló előadásában is Shapley-t
említi minden idők legnagyobb játékelmélet-kutatójaként. Joggal
tekinthetjük őt tehát – Neumann Jánossal együtt – a kooperatív
játékelmélet atyjának.
A mag és a Shapley-érték
Shapley munkássága olyan sokrétű, hogy ennek ismertetése jócskán
túlmutat e dolgozat keretein. Lehetőségünk legfeljebb arra van, hogy
néhány példa kapcsán megkíséreljük bemutatni az alapokat, és
kitekintést adjunk Shapley további munkáihoz. Vegyünk tehát egy
teljesen hétköznapi szituációt. Adott egy 80 m²-es kétszobás lakás, a
bérlő 110 ezer forintot fizet minden hónapban a tulajdonosnak, bérleti
díjjal, rezsivel együtt. A bérlő egyik barátja maga is bérel egy
lakást, rezsivel együtt havi 80 ezer forintért. Azt gondolják ki, hogy
a lakás kettejüknek is megfelelő, és ha közösen bérelnék, sok pénzt
takarítanának meg. A tulajdonos ezt jóváhagyja, viszont ez esetben 140
ezer forintra emeli a havonta fizetendő díjat, az esetleges
rezsiköltség emelkedése miatt. A bérlő és a barátja együtt egy
kétszereplős játékot határoz meg, amelyben a kooperációval mindkét
bérlő nyer, közösen ugyanis kevesebbet kell fizetniük összesen, mintha
külön-külön bérelnének lakást. Már csak abban kell megegyezniük, hogy
miként osszák fel egymás között a közösen fizetendő 140 ezer forintot.
Világos, hogy egyikőjük sem szeretné, ha az
összeköltözés után többet fizetnének, mint most, ennél többet tehát
egyikük sem lesz hajlandó fizetni. Ketten együtt pedig 140 ezernél
többet nem szeretnének fizetni, annyit viszont ki is kell fizetniük.
Az úgynevezett mag-elosztás azokat a kifizetéseket adja meg, amelyek
egyénileg is elfogadhatóak, és amelyek esetén egyetlen csoport
(koalíció) tagjai sem fizetnek összesen többet, mint amennyi az adott
csoportra vonatkozó költség. Példánk esetében tehát minden olyan
elosztás magbeli lesz, amikor nem fizetnek 110, illetve 80 ezer
forintnál többet, ketten együtt pedig éppen 140 ezret fizetnek. Jó
megoldás ezek alapján például, ha elfelezik a bérleti díjat, esetleg
50–90 ezres felosztás szerint fizetnek stb. Látjuk, hogy számtalan
mag-elosztást megadhatunk, de érezzük, hogy ezek között vannak
„igazságosabb” elosztások. Például kevésbé tartjuk igazságosnak, ha a
jelenleg olcsóbb lakást bérlő albérlő fizet 75 ezret, míg a nagyobb
lakást bérlő csak 65 ezret, mintha ezeket az összegeket fordítva
fizetnék. Érezzük ugyanis, hogy így szinte csak a nagyobb lakással
rendelkező bérlő nyer az összeköltözéssel, övé a megtakarítás döntő
része.
A mag-elosztás fogalmának bevezetéséhez (Donald B.
Gillies mellett) Shapley is hozzájárult; 1953-ban ő vezette be az
azóta róla elnevezett Shapley-értéket is (Shapley, 1953). Itt a
játékosokat a játékbeli szerepük fontossága szerint értékeljük.
Ugyanis minden játékos hozzátesz valamit a koalícióhoz, amihez
csatlakozik. A koalíció értékének (példánkban összköltségének) ilyen
növekedését hívjuk a játékos koalícióhoz való határhozzájárulásának. A
Shapley-érték minden játékoshoz a határhozzájárulásának a várható
értékét rendeli, vagyis azt az értéket, amivel egy játékos átlagosan
hozzá szokott járulni egy-egy koalícióhoz.
A példánkhoz visszatérve: jelen esetben a barát
beköltözése 30 ezer forinttal növeli a bérleti díjat. Ugyanakkor nem
volna igazságos, hogy a bérlő ne részesüljön ötletéből. Fordított
esetben, ha ő költözik be a baráthoz, mindössze 140-80=60 ezer
forintos többletet kellene fizetnie. A 110+30 és a 60+80 között a
85+55 jelenti a félutat, így a két barát 85, illetve 55 ezer forintot
fizet a bérleti díjból, ami épp a Shapley-érték szerinti felosztást
adja.
A Shapley-érték szépsége, hogy a megoldás, amit ad,
sokszor nagyon is intuitív. A fenti példa kapcsán is látszik, hogy
ugyanarra a megoldásra jutottunk volna, ha a józan paraszti eszünkre
hagyatkozunk, játékelméleti elemzésre nem is feltétlen volt szükség. A
Shapley-érték azonban olyan tulajdonságokkal rendelkezik, amelyek
matematikailag igazolják, hogy összetettebb esetekben is „jó”
eredményt szolgáltat. Shapley 1953-ban maga adott egy karakterizációt
a Shapley-értékre (Shapley, 1953) a következő tulajdonságokkal:
• Amennyiben egy játékos nem járul hozzá egyetlen
koalícióhoz sem, az értéke („fontossága”) legyen 0.
• Ha két különböző játékos mindig ugyanannyival
járul hozzá egy koalícióhoz, akkor ezeket értékelje egyformán
(szimmetria).
• A megoldás legyen hatékony, tehát mindig a
játékban összesen elérhető nyereséget ossza szét.
• Illetve, ha két különböző játékot vizsgálunk,
akkor ezeket együttesen értékelje ugyanúgy, mintha a két játékot
külön-külön értékelné, majd ezeket a kiértékeléseket összegezné.
Shapley megmutatta, hogy a Shapley-érték az
egyetlen megoldás, ami ezt a négy feltételt kielégíti. Így
összetettebb problémák esetén is tudhatjuk, hogy a Shapley-értéket
alkalmazva a fenti tulajdonságok értelmében „jó” megoldást kapunk. A
játékelméleti irodalomban azóta többféle karakterizáció is ismertté
vált, melyek a Shapley-érték további hasznos tulajdonságaira hívják
fel a figyelmet.
Tekintsünk még egy rövid példát a Shapley-értékre.
A Miniszterek Tanácsa az Európai Unió egyik legfontosabb döntési
szerve. Az 1958–1972-es periódusban olyan szavazási rendszer volt
érvényben, amely az országoknak különböző kvótákat
adott, és azok a csoportok (koalíciók) voltak döntőképesek, amelyeknek
összesen legalább 12 kvótájuk volt. Érdekes kérdés, hogy mekkora
hatalmuk, befolyásuk volt az egyes országoknak ebben a szavazási
rendszerben. Az országonkénti kvótákat és a Shapley-értéket (amit itt
Shapley–Shubik-indexnek is nevezünk) a 2.
táblázat mutatja.
Egy ország akkor képes befolyásolni egy szavazás
eredményét, ha szavazatának megváltoztatása megváltozatja az eredményt
is. Könnyen belátható, hogy Luxemburg egyetlen szituációban sem képes
a döntés megváltoztatására, teljes jogú tagként is csak kibic. Ezt a
Shapley-érték is jól mutatja, ugyanis befolyását 0-nak értékeli. A
táblázatot tovább vizsgálva a Shapley-érték másik említett
tulajdonsága, a szimmetria is tetten érhető. Például Hollandia és
Belgium kvótája megegyezik, így befolyásuknak is ugyanannyinak kell
lennie, ahogy a Shapley-érték ezt híven tükrözi is.
A Shapley-érték és a mag kapcsán fontos megjegyezni
azonban, hogy nem olyan magától értetődő, hogy létezik magelosztás.
Bizonyos játékokhoz nem tudunk magelosztást megadni. Shapley egyik
leghíresebb eredménye a Shapley–Bondareva-tétel a mag nemürességével
foglalkozik, melyet Shapley Olga Bondarevától függetlenül bizonyított
1967-ben (Shapely, 1967). A Shapley-érték azonban mindig létezik, így
széles körben alkalmazhatóvá teszi. Viszont olyan eset is
előfordulhat, amikor létezik magelosztás, de a Shapley-érték nem
magbeli.
A mag és a Shapley-érték a kooperatív játékelmélet
olyan alapfogalmai, amelyek meghatározóak voltak a tudományterület
további alakulása során. Fontos azonban megjegyezni, hogy kiszámításuk
általában nem könnyű. A számítási bonyolultság a részt vevő játékosok
számának arányában exponenciálisan nő. Egy „alig” háromszáz fős
játékban a lehetséges koalíciók száma több, mint ahány atom van az
univerzumban. Ez azt jelenti, hogy még a mai szuperszámítógépek sem
képesek minden esetben a Shapley-értéket a definíciója szerint
megadott képlettel kiszámolni. A játékelméleti kutatások egy része
azzal foglalkozik, hogy a különböző játékosztályokon megadjon egy
hatékony eljárást, akár az egyik, akár a másik megoldás
meghatározására. Vannak olyan speciális játéktípusok, ahol ilyen
heurisztikák léteznek. Ilyenek például az olyan játékok, ahol a
lehetséges vagy a lényeges koalíciók valamilyen jól körülhatárolható
struktúrával rendelkeznek (lásd fa-gráfokkal reprezentálható játékok).
Sajnos azonban egy általános játék esetén csak a definíciókra
hagyatkozhatunk. Éppen ezért konkrét példák esetén a gyakorlati
alkalmazhatóságuk, elméleti jelentőségük ellenére nem mindig magától
értendő.
Záró gondolatok
Könyveket lehetne megtölteni mindazokkal a területekkel, melyekben
Lloyd S. Shapley maradandót alkotott. A hozzárendelési-,
sztochasztikus- és dinamikus játékokról terjedelmi okokból nem tudtunk
beszélni. A Magyar Tudomány 2009-ben megjelentetett játékelmélettel
foglalkozó számában (Simonovits et al., 2009) részletesebb írásokat
olvashatunk többek között a szavazási játékokról, a
mechanizmustervezésről, a hálózatos játékokról, valamint a kooperatív
játékelméletről általában. Shapley munkássága nyomán a Nobel-díj
Bizottság azt is kiemeli, hogy ez az első alkalom, hogy a kooperatív
játékelmélet területéről díjaztak valakit. Ahogy Shapley, úgy a
Neumann és Shapley által megalapozott tudományterület is már régen
megérdemelte az elismerést.
Alvin E. Rothnak elévülhetetlen érdemei voltak a
Gale–Shapley-algoritmus helyes alkalmazási módjának elterjesztésében.
Laboratóriumi kísérletei nemcsak a párosítás-, de az alkuelméletben is
úttörőek voltak. Munkásságával számos játékelméleti eredmény
fontosságát igazolta azzal, hogy megmutatta, hogyan lehet az elméleti
eredményeket a gyakorlatba átütetni. Kiemelkedő elméleti kutató létére
vette a fáradságot, hogy a témában felkészületlen döntéshozókat is
meggyőzzön az eljárások sikeréről; több piac tervezésében tevékenyen
részt vett. Széles körben olvasott blogja (URL2) a témával foglalkozó
kutatók naprakész hírforrása elsősorban a gyakorlati alkalmazások
tekintetében.
Végezetül emlékezzünk meg David Gale-ről
(1921–2008), aki már nem érhette meg Shapleyvel közösen írt cikkének
ötvenéves évfordulóját. Párosításelméletben elvégzett kutatásai
megkerülhetetlennek számítanak a területen. Ha még élne, minden
bizonnyal most egy hármas-megosztott Nobel-díjról értekeztünk volna.
Kulcsszavak: játékelmélet, párosítások, egyetemi felvételi, stabil
allokációk, piactervezés, preferenciák, őszinteség, kooperatív
játékelmélet, mag, Shapley-érték
IRODALOM
Abdulkadiroglu, Atila – Pathak, P. A. –
Roth, A. E. – Sönmez, T. (2005a): The New York City Public School
Match. American Economic Review. 95, 364–367. •
WEBCÍM
Abdulkadiroglu, A. – Pathak, P. A. – Roth,
A. E. – Sönmez, T. (2005b): The Boston Public School Match. American
Economic Review. 95, 368–371. •
WEBCÍM
Biró Péter (2006): Stabil párosítási
modellek és ezeken alapuló központi párosító programok. Szigma. 37,
3–4, 153–157. •
WEBCÍM
Csermely Péter (2004): A gyenge
kölcsönhatások ereje a stresszfehérjéktől a szociális hálózatokig.
Magyar Tudomány. 111, 12, 1318–1324. •
WEBCÍM
Feldmann, Rainer M. – Gairing, T. –
Lücking, T. – Monien, B. – Rode, M. (2003): Selfish Routing in
Non-cooperative Networks: A Survey. In: Rovan, Bronislav – Vojtáš,
Peter (eds.): Mathematical Foundations of Computer Science 2003.
(Vol. 2747 of Lecture Notes in Computer Science) 21–45. Springer
Berlin / Heidelberg •
WEBCÍM
Gale, David – Shapley, Lloyd S. (1962):
College Admissions and the Stability of Marriage. American
Mathematical Monthly. 69, 1, 9–15. •
WEBCÍM
Kóczy László Á. (2009): Központi felvételi
rendszerek. Taktikázás és stabilitás. Közgazdasági Szemle. 56,
422–442. •
WEBCÍM
Kóczy László Á. (2010): A magyarországi
felvételi rendszerek sajátosságai. Közgazdasági Szemle. 57, 142–164. •
WEBCÍM
Neumann, John von – Morgenstern, Oskar
(1944): Theory of Games and Economic Behavior. Princeton University
Press: Princeton, NJ •
WEBCÍM
Roth, Alvin E. (1984): The Evolution of
the Labor Market for Medical Interns and Residents: A Case Study in
Game Theory. Journal of Political Economy. 92, 991–1016. •
WEBCÍM
Roth, Alvin E. – Peranson, Elliott (1999):
The Redesign of the Matching Market for American Physicians: Some
Engineering Aspects of Economic Design. American Economic Review. 89,
748–780. •
WEBCÍM
Roth, Alvin E. – Sönmez, T. – Ünver, M. U.
(2004): Kidney Exchange. Quarterly Journal of Economics. 119, 457–488.
•
WEBCÍM
Roth, Alvin E. − Sotomayor, Marilda A.
Oliveira (1990): Two-Sided Matching: A Study in Game-Theoretic
Modeling and Analysis. (Econometric Society Monograph Series)
Cambridge University Press, New York •
WEBCÍM
Roth, Alvin E. (2008): Deferred Acceptance
Algorithms: History, Theory, Practice, and Open Questions.
International Journal of Game Theory. 36, 537–569. •
WEBCÍM
Shapley, Lloyd S. (1953): A Value for
n-Person Games. In: Kuhn, Harold W. –Tucker, Albert W. (eds.):
Contributions to the Theory of Games. Vol. 2. Princeton University
Press, Princeton, NJ, 317–318. •
WEBCÍM
Shapley, Lloyd S. (1967): On Balanced Sets
and Cores. Naval Research Logistics Quarterly. 14, 4, 453–460. • DOI:
10.1002/nav.3800140404
Shapley, Lloyd S. − Shubik, M. (1972): The
Assignment Game I: The Core. International Journal of Game Theory. 1,
111–130. •
WEBCÍM
Simonovits András (vendégszerk.) (2009):
Játékelmélet. (Csekő I. – Forgó F. – Mérő L. – Simonovits A. –
Solymosi T. – Tasnádi A. – Vincze J.) Magyar Tudomány. 5, 514–577. •
WEBCÍM
Szabó György – Borsos István (1994):
Evolution and Extinction of Families in a Cellular Automaton. Physical
Review E. 49, 5900–5902. • DOI: 10.1103/PhysRevE.49.5900
Szabó György – Szolnoki Attila (2012):
Selfishness, Fraternity, and Other-Regarding Reference in Spatial
Evolutionary Games. Journal of Theoretical Biology. 299, 81–87. •
WEBCÍM
URL1
URL2
|