A Magyar Tudományos Akadémia folyóirata. Alapítva: 1840
 

KEZDŐLAP    ARCHÍVUM    IMPRESSZUM    KERESÉS


 KÖZGAZDASÁGI NOBEL-EMLÉKDÍJ 2012 •

    ALVIN E. ROTH ÉS LLOYD S. SHAPLEY

X

Bíró Péter

egyetemi docens, tudományos munkatárs, MTA Közgazdaság- és Regionális Tudományi Kutatóközpont,

Budapesti Corvinus Egyetem Operációkutatás és Aktuáriustudományok Tanszék • biro.peter(kukac)krtk.mta.hu

Csóka Péter

egyetemi docens, tudományos munkatárs, Budapesti Corvinus Egyetem Befektetések és Vállalati Pénzügy Tanszék,

MTA Közgazdaság- és Regionális Tudományi Kutatóközpont • peter.csoka(kukac)uni-corvinus.hu

Kóczy Á. László

tudományos főmunkatárs, egyetemi docens, MTA Közgazdaság- és Regionális Tudományi Kutatóközpont,

Óbudai Egyetem Keleti Károly Gazdasági Kar • koczy(kukac)krtk.mta.hu

Radványi Anna Ráhel

tudományos segédmunkatárs, MTA Közgazdaság- és Regionális Tudományi Kutatóközpont, Budapesti Corvinus Egyetem Matematika Tanszék • radvanyi.anna(kukac)krtk.mta.hu

Sziklai Balázs

tudományos segédmunkatárs, MTA Közgazdaság- és Regionális Tudományi Kutatóközpont

sziklai.balazs(kukac)krtk.mta.hu

 

 

A játékelmélet fiatal és szerteágazó tudományág. Születését hagyományosan Neumann János és Oskar Morgenstern híres monográfiájának 1944-es megjelenésétől szokták datálni (Neumann – Morgenstern, 1944). A játékelmélet olyan többszereplős döntési helyzeteket vizsgál, ahol a játékosok ellenérdekeltek, vagy szűkös erőforráson osztozkodnak. A játékosok figyelemmel kísérik a többi szereplő viselkedését, és ez alapján határozzák meg saját stratégiájukat. Az ilyen szituációk a gazdaságban hétköznapinak számítanak. Talán ez az oka, hogy a játékelmélet – amely az alkalmazott matematika egy ágának mondható – leginkább a közgazdaságtanban vert gyökeret, és az első kiemelkedő eredmények is innen származnak. Mára ez a kizárólagosság eltűnt: a játékelmélet teret hódított a biológiában (populációdinamika [Szabó – Szolnoki, 2012], hálózatok [Csermely, 2004]), a fizikában (anyagtudomány [Szabó – Borsos, 1994]), a számítástudományban (forgalomirányítás [Feldmann et al., 2003]) és még számos más területen. Az elért sikerek nem maradtak elismerés nélkül: a játékelmélet születése óta eltelt nem egész hetven év alatt a Nobel-díj Bizottság nyolc alkalommal díjazott erről a területről szakembereket. Az utóbbi tíz évben immár harmadszor, ami egyfelől azt jelzi, hogy az elvégzett elméleti munka gyümölcse kezd beérni, az eredmények a közgazdasági kánon részévé váltak, másfelől talán azt is mutatja, hogy a szakma fókusza eltolódott a matematikai eszközökkel jobban leírható modellek irányába. Ennek részben az a magyarázata, hogy a közgazdaságtan egyértelműen az egzaktan leírható összefüggésekben való gondolkodás tudománya lett, ha úgy tetszik, végképp eldőlt, hogy a közgazdaságtannak is a matematika a nyelve.

A mostani díjazottak, Alvin E. Roth és Lloyd S. Shapley a stabil allokációk elméletének és a piactervezés gyakorlatának kidolgozásáért kapták a neves kitüntetést. Nézzük, mit is takarnak ezek a kifejezések!


Párosításelmélet


A sokszereplős piaci rendszerek – hasonlóan a fizikai rendszerekhez – egyensúlyra törekszenek. A kereslet és kínálat összeegyeztetése rendszerint valamilyen ármechanizmus szerint történik. A tökéletes verseny keretfeltételei azonban (mindenki jól informált, a javak nem, vagy nem nagyon különböztethetőek meg, nincsenek időbeli és helybeli különbségek stb.) szinte soha nem teljesülnek egyszerre. A legtöbb piacon megfigyelhető valamilyen deformitás, ami a kínált termék vagy szolgáltatás jellegéből, vagy a kereslet típusából ered. A vasúti közlekedés vagy a közművek tipikus példái a természetes monopóliumnak, amikor a kínálati oldalon egyszerűen értelmetlen volna több szereplőnek megjelennie. A való életben megfigyelhető monopóliumok és oligopóliumok esetében az ár, a szereplők haszna és a társadalmi hatékonyság mind-mind más értéket vesz fel a kialakuló piaci egyensúlyban, mint tökéletes verseny esetén. Vannak azonban olyan piacok is, ahol az egyensúly külső beavatkozás nélkül nem, vagy csak nehezen jöhetne létre. A termék inhomogenitása vagy a jól informáltság követelményének sérülése ilyen esetekhez vezethet. Olyan gazdasági, társadalmi helyzetek is előfordulnak, ahol a pénzkifizetés nem megengedett (például: iskolaválasztás, szervdonáció). A piactervezés olyan mechanizmusok tervezésével és elemzésével foglalkozik, amelyek ilyen esetekben is képesek stabil, azaz egyensúlyi megoldást létrehozni.

Az elméleti alapokat David Gale és Lloyd S. Shapley 1962-es úttörő munkája fektette le (Gale – Shapley, 1962). Az alig hétoldalas cikkükben egy olyan eljárást mutattak be, amely a keresleti és kínálati oldal szereplőit stabil módon párosítja össze. Képzeljünk el egy piacot, ahol a „termékek” egyediek, például a diákok az egyetemi felvételi versenyben, vagy munkavállalók egy magas tudásigényű szakmában. Minthogy nincs két egyforma képességű és tudású ember, így nem is helyettesíthetőek tökéletesen egymással. Éppen ezért a keresleti oldal szereplői – ha az említett példáknál maradunk, akkor az egyetemek vagy munkaadók – csupán egy preferenciasorrendet tudnak felállítani a jelentkezők között. Gale és Shapley múlhatatlan érdeme, hogy időtálló módon definiálták a stabilitás fogalmát egy ilyen rendszerben. Megeshet ugyanis, hogy munkaadóknak és munkavállalóknak egy olyan párosítása alakul ki, hogy egy X dolgozó az Y cégnek dolgozik (esetleg munkanélküli), miközben jobban szeretne Z cégnél elhelyezkedni. Ezzel egy időben pedig a Z cégnél van üres pozíció, vagy pedig a posztot olyasvalaki tölti be, akit az X dolgozónál kevesebbre értékel. Ilyenkor mindkét félnek érdeke váltani. Stabil az a párosítás, ahol ilyen anomália nem figyelhető meg, vagyis nincsenek blokkoló párok. Nem nyilvánvaló, hogy milyen feltételek szükségesek ahhoz, hogy egyáltalán létezzen egy rendszerben stabil párosítás, ahogy az sem, hogy ha létezik, milyen eljárással lehetne meghatározni egy ilyen egyensúlyra vezető megoldást.

A Gale és Shapley által javasolt ún. késleltetett elfogadási algoritmus során a piac egyik oldalának szereplői (például a munkaadók) ajánlatokat tesznek a másik oldal szereplőinek, amelyek bizonyos – alább részletesen ismertetett – szabályokat követve elfogadják, illetve elutasítják azokat. Amennyiben minden szereplőnek teljes a preferenciarendezése, azaz bármely jelentkező meg tudja mondani, hogy az Y vagy a Z céget szereti-e jobban, úgy a Gale–Shapley-algoritmus stabil párosítást eredményez. Külön irodalma alakult ki annak a problémakörnek, hogy milyen piacokon és milyen feltételek mellett alkalmazható a Gale–Shapley-algoritmus. Alvin E. Roth empirikus kutatásaiban rámutatott, hogy a jól és rosszul működő piacok alapvetően stabilitási szempontból különböznek. A kórházak és rezidensek párosításáról szóló tanulmányának (Roth, 1984) kulcsszerepe volt a technika elterjedésében. Roth ugyancsak behatóan elemezte a mechanizmus egyik legfontosabb játékelméleti aspektusát: az ún. igazmondásra ösztönzést. A következő pár oldalon bemutatjuk a Gale–Shapley-algoritmust, és egy példán keresztül szemléltetjük a működését és tulajdonságait. Cikkünk második felében pedig Shapley kooperatív játékelméleti munkásságáról adunk rövid áttekintést.


A Gale–Shapley-algoritmus


A késleltetett elfogadási algoritmus működését legegyszerűbb egy példán bemutatni. Képzeljük el, hogy egy végzős osztály a szalagavató báljára készül. A fiúk és a lányok is azon törik a fejüket, kivel táncoljanak. A fiúk először a nekik leginkább tetsző lányt kérik föl, hogy legyen a partnerük. A lányok azonban csalafinták. Mivel nem tudják, hogy a jövőben lesz-e a jelenlegi kérőknél jobb parti, ezért a nekik legjobban tetsző fiúnak azt mondják, „talán”, a többit elküldik. A következő körben minden kosarat kapott fiú felkéri a neki második legjobban tetsző lányt. A lányok most megint választanak. Ha az új kérők közt van olyan, akit a jelenlegi párjuknál jobban kedvelnek, akkor váltanak. Az eljárás így folyik tovább, amíg minden fiú ki nem fogy a jelöltekből. Mindkét oldalon megengedjük, hogy legyenek elfogadhatatlan partnerek. Azaz lehetséges, hogy egy fiú sosem kér föl egy adott lányt, illetve hogy egy lány akkor sem táncol egy fiúval, ha más kérője nincs. A késleltetett elfogadás elnevezés onnan származik, hogy a lányok nem fogadják el azonnal az épp aktuális jelöltek közül a legjobbat, csak miután minden fiú megállapodik, és így újabb partneri ajánlatot már nem kaphatnak.

Nézzünk egy példát! A lányok legyenek név szerint: Anna (A), Bea (B), Csilla (C) és Dóri (D), a fiúk pedig Endre (E), Feri (F), Gábor (G) és Henrik (H). Jelölje X <M Y, hogy M jobban kedveli X-et, mint Y-t, szakszóval M preferálja X-et Y-hoz képest. Az elfogadható jelöltek listáját név szerint az 1. táblázat foglalja össze.

Az első körben Endre, Feri és Gábor felkérik Dórit, Henrik pedig Beát. Dóri Gábornak, Bea pedig Henriknek mondja, hogy talán táncol vele. Endre és Feri kosarat kaptak, így ők tovább próbálkoznak. Endre Annát kéri fel, de most sincs szerencséje. Feri pedig Csillát, akitől azt a választ kapja, hogy talán. A harmadik körben már csak Endre van pár nélkül, így ő megkéri a sorban következő lányt, aki történetesen Bea. Beának Endre jobban tetszik, mint Henrik, ezért Henrik kosarat kap. A negyedik körben Henrik felkéri a preferencialistáján szereplő következő lányt, Annát és ezzel az utolsó fiú is párra lel. Mivel minden fiú megállapodott, a lányok elfogadják a jelenlegi partnerüket és a párok megalakulnak. A táblázatban félkövér betűvel jelöltük a végső párosításban szereplő nevek kezdőbetűjét.

Könnyen látható, hogy a késleltetett elfogadási algoritmus stabil megoldást eredményez. A fiúk, mivel sorrendben haladtak, úgy jutottak el végső partnerükhöz, hogy minden nála szimpatikusabb lány kikosarazta őket. Így tehát minden olyan lány, akivel szívesebben lennének, jobb párra lelt, mint ők. A lányoknál ugyan előfordulhat, hogy van olyan fiú, akivel szívesebben lennének, mint a jelenlegi párjuk, de ezek a fiúk nem kérték fel őket. Fontos következménye az algoritmusnak, hogy a fenti feltételek teljesülése esetén mindig létezik stabil párosítás, hiszen az algoritmus ilyet eredményez.

A táblázatot tovább vizsgálva kitűnik, hogy a fiúk valamivel jobban jártak. A lányok inkább a preferencialistájuk végéről szereztek párt, a fiúk inkább az elejéről. Ennél több is igaz. Nincs olyan stabil párosítás, amelyben bármelyik fiú is jobban járhatna. A késleltetett elfogadási algoritmus, amennyiben a fiúk a kezdeményezők, fiú-optimális stabil megoldást ad. Amennyiben a lányok kérték volna fel a fiúkat, úgy lány-optimális végeredményt kaptunk volna (a fenti példában Bea Endre helyett Ferit, Csilla Feri helyett Endrét kapta volna párnak, amellyel mindkét lány boldogabb lett volna). A Gale–Shapley-algoritmus módosításával olyan stabil megoldásokat is előállíthatunk, amelyek e két szélsőség között helyezkednek el. A való életben azonban inkább a jelentkező-optimális eljárások terjedtek el. Maga Gale és Shapley is amellett érveltek a cikkben, az egyetemi felvételi rendszert felhozva példaként, hogy a diák-optimális megoldás célravezetőbb, hiszen az egyetemek vannak a diákokért és nem fordítva.

Bár a szalagavató tánc is igen fontos az ember életében, a gazdaságban ennél fajsúlyosabb esetekben is szükség lehet stabil párosítások létrehozására. Éppen ezért elengedhetetlen megvizsgálni azt a kérdést, hogy stratégiailag mennyire kikezdhető a késleltetett elfogadási algoritmus. Azaz tudnak-e javítani a szereplők a helyzetükön azzal, hogy hazudnak a saját preferenciájukról?

A valóságban a gazdasági szereplők párosítását általában valamilyen független intézmény végzi el. Mindkét oldal szereplői átadják a preferencialistájukat ennek az intézménynek, amely végrehajtja az algoritmus lépéseit úgy, mintha a beadott listák mindenki számára nyilvánosak lennének. Itt példaként megint csak gondolhatunk az egyetemi felvételi rendszerre, ahol a diákok és egyetemek párosítását egy független szervezet (Magyarországon az Educatio Társadalmi Szolgáltató Nonprofit Kft.) hajtja végre. Egy ilyen nyilvános eljárás igazmondásra ösztönző, ha az igazmondás mindenkinek a domináns stratégiája. Azaz, ha mindenki akkor jár a legjobban, ha a valódi preferenciáit közli. A fiú-kezdeményező algoritmus taktikázásbiztos a fiúk részéről. Egy fiú sem járhat jobban azáltal, hogy nem az értékítéletének megfelelő sorrendben kéri fel a lányokat. A másik oldalról viszont nincs így! A fiú-kezdeményező algoritmus nem taktikázásbiztos a lányok részéről. A fenti példát felhasználva könnyen ellenőrizhetjük, hogy ha Bea a valódi preferenciái helyett a G ˂B F <B H <B E sorrendet közli, akkor a végső – az eredeti preferencialistákra nézve stabil – párosításban Ferivel kerül össze (akit jobban kedvel) és nem Endrével. Nyilvánvaló, hogy az új, 2013-as egyetemi felvételi rendszer sem ösztönöz igazmondásra, hiszen ritkán célszerű a legjobb iskolákat beírni az öt lehetséges helyre – a legtöbb jelentkező ezeken a helyeken esélytelen. Roth bebizonyította, hogy nincs olyan stabil párosítási mechanizmus, amelyben az igazmondás minden szereplő számára domináns stratégia (Roth, 1984). Ugyanakkor ha a szereplők nem ismerik a többiek preferenciáit, akkor nem tudják előre megmondani, hogyan kéne módosítani a sorrendjükön, hogy számukra kedvező módon tudják manipulálni a végeredményt. Roth elméleti megfontolások és számítógép-szimulációs tesztek alapján is arra jutott, hogy sokszereplős piacon lényegében lehetetlen megjósolni, és ezáltal manipulálni a kimeneteket.


Rezidensi felvételi az Egyesült Államokban


Roth munkásságának jelentősége elsősorban a gyakorlati alkalmazásokban mutatkozik meg. Az 1940-es években az Egyesült Államokban a végzett orvosok rezidensi felvételije nem központosított rendszeren keresztül történt. A jelentkezők közvetlenül a kórházakat keresték fel, ennek számos negatívuma volt. Előfordultak olyan esetek, amikor a leendő rezidenseknek időben annyira korán kellett jelentkezniük, amikor még nem is voltak feltétlenül tisztában azzal, hogy milyen szakirányon szeretnének elhelyezkedni. Más esetben olyan későn kaptak visszautasító választ, hogy másik kórházba már nem tudtak jelentkezni, vagy olyan korán kellett választ adniuk egy ajánlatra, amikor más kórházaktól esetleg nem kaphattak még visszajelzést. Így nem feltétlenül alakultak ki optimális, azaz stabil rezidens-kórház párosok. Roth 1984-ben megjelent tanulmányaiban ír erről a problémáról, illetve a Gale–Shapley-algoritmussal lényegében azonos, de azt tíz évvel megelőző új eljárás 1952-es bevezetéséről. A rezidensi felvételi azóta is ezen módszer szerint, központosított, bár választható intézményi rendszeren keresztül zajlik, ami lehetővé teszi a rezidensek számára elérhető lehető legjobb állásajánlat elfogadását. Az algoritmus módosítására csak évtizedekkel később volt szükség, köszönhetően annak, hogy az 1960-as évektől kezdve egyre több lett a fiatal orvos házaspár. Számukra elsősorban az a fontos, hogy egy városban kapjanak állást, ezt pedig az algoritmus nem tudta biztosítani. Roth és csapata dolgozta ki a 90-es évek végén azt a módosított algoritmust, ami immáron a házaspárok szempontjait is figyelembe veszi. Az erről szóló leírás Alvin E. Roth és Elliott Peranson cikkében (1999) található.


További alkalmazások


A Gale–Shapley-algoritmust napjainkban is egyre több alkalmazásban vezetik be. Roth és társai érdeme, hogy ez lett az alapjuk a New York-i és bostoni középiskolai felvételi eljárásoknak (Abdulkadiroglu et al., 2005a, 2005b). Európában is számos országban használják ezt az eljárást középiskolai és felsőoktatási felvételik, illetve gyakornokok elhelyezése esetén. Átfogó képet kaphatunk erről a Matching in Practice európai kutatói hálózat weboldalán (URL1). Hazánkban a középiskolai és felsőoktatási felvételi eljárások szintén a Gale–Shapley-algoritmuson alapszanak.

Szintén kiemelt érdeme volt Rothnak és társainak a vesecsereprogramok beindításában. Ezen központilag koordinált párosító programokban inkompatibilis beteg-donor párokat próbálnak összehozni más hasonló párokkal, hogy aztán a donorok elcserélésével minél több beteg juthasson kompatibilis veséhez. Az úttörő elméleti tanulmányok mellett Roth és társai tevőlegesen is részt vettek az első amerikai vesecsereprogram (NEPKE) létrehozásában (Roth et al., 2004).

 

 

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, Bro­nislav – Vojtáš, Peter (eds.): Mathematical Foun­dations 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 Mono­graph 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

 


 

név preferenciasorrend név preferenciasorrend

Anna

G >A H

Endre

D >E A >E B >E C

Bea

G >B F >B E >B H

Feri

D >F C >F A >F B

Csilla

G > H > E > F

Gábor

D >G C >G B >G A

Dóri

H >D G

Henrik

B >H A >H C


1. táblázat <

 



 

ország kvóta Shapley-érték

Németország

4 23,2%

Olaszország

4 23,2%

Franciaország

4 23,2%

Hollandia

2 15%

Belgium

2 15%

Luxemburg

1 0%


2. táblázat
<