Stabil halmazok hozzárendelési játékokban = Stable sets in assignment games

Abstract

A dolgozatban a kooperatív játékelmélet egyik legrégebbi megoldáskoncepcióját a (Neumann-Morgenstern) stabil halmazokat vizsgáljuk egy speciális játékosztályon a hozzárendelési játékokon. A stabil halmaz az elosztásoknak egy olyan részhalmaza, amelynek elemei egymást nem dominálják (belső stabilitás), viszont minden a halmazon kívüli elosztást dominál valamelyik (külső stabilitás). Ez így egy elég egyszerű és természetes megoldáskoncepció, azonban később kiderült, hogy matematikailag elég rosszul kezelhető. Sokáig az is kérdés volt, hogy egyáltalán létezik-e minden játékban stabil halmaz. Később megmutatták, hogy minden 4 személyes játékban létezik, és találtak 10 személyes játékot, amelyben nem, a kettő közti esetekről azonban továbbra sem tudunk semmit. Ezt a megoldáskoncepciót vizsgáljuk a hozzárendelési játékok osztályán. Shapley és Shubik is több cikkben foglalkozott ezzel a témával, megadtak egy halmazt, amelyről az volt a sejtésük, hogy stabil, ezáltal minden hozzárendelési játékban létezik stabil halmaz, de ezt a sejtésüket nem tudták bizonyítani. Később egy 2013-as cikkükben Núñez és Rafels bebizonyították ennek a halmaznak a stabilitását. A dolgozat legfontosabb eredménye a stabil halmazoknak egy új karakterizációja ezen a játékosztályon. Megmutatjuk, hogy az elosztáshalmaznak egy részhalmaza pontosan akkor stabil, ha belső stabil (ez ugyanaz mint az eredeti definícióban), összefüggő, van egy olyan pontja, ahol minden eladó- és egy olyan ahol minden vevő kifizetése 0, és tartalmazza bizonyos redukált játékok magjait. A karakterizációt felhasználva szinte egyből megkapjuk, hogy a Shapley és Shubik által javasolt halmaz stabil, sőt ennél többet is megmutatunk. Abban az esetben, ha a játék magja nem stabil megadunk végtelen sok stabil halmazt. A létezésen kívül több, a stabil halmazok szerkezetére vonatkozó állítást is megfogalmazunk. A karakterizációnak egy nemkooperatív játékelméleti felhasználását is bemutatjuk. Harsányi János megfogalmazott egy kritikát a stabil halmazokkal kapcsolatban. Szerinte az eredeti definíció nem szerencsés, mert nem veszi figyelembe a közvetett, több lépésen keresztüli dominanciát, ezért javasolt egy alkujátékot, amelynek szerinte az egyensúlyában szereplő fixpontjait kellene stabil halmaznak nevezni. A karakterizáció segítségével megmutatjuk, hogy a hozzárendelési játékoknál ez a kettő ugyanaz. A dolgozat végén a hozzárendelési játékok egy általánosításával, a többoldalú hozzárendelési játékokkal foglalkozunk. Megmutatjuk, hogy a mag akkor és csak akkor stabil, ha a generáló (poli)mátrix főátlódomináns. Ez csak a legkisebb nemtriviális esetben volt ismert, és még a speciális eset bizonyítása is sokkal bonyolultabb, mint a mienk.