Párosítási játékok kifizetésekkel

Abstract

Ebben a dolgozatban a kooperatív játékelmélet témakörbe tartozó párosítási játékokat vizsgáljuk meg. Ennek legjobb szemléltetése egy súlyozott páros gráf, melyben a maximális párosítást keressük, és hozzá egy stabil kifizetést, azaz a maximális párosítás értékének egy olyan elosztását a csúcsok közt, melyet egy pár sem tud blokkolni. Négy különböző esetet különböztetünk meg az alapján, hogy a gráf páros-e vagy sem, illetve, hogy a játékosok egy adott párosításban benne lehetnek-e egyszerre több párban. Egy rövid, az alapfogalmakat bemutató fejezet után a két kapacitás nélküli esetet nézzük át. Megadjuk a legfontosabb fogalmaikat, tulajdonságaikat és tételeiket. Ezek azért is fontosak, mert a harmadik fejezetben egy olyan alternatív kapacitás nélküli gráfot adunk meg az eredeti kapacitásos játék alapján, melynek megoldásaiból megadhatjuk az eredeti problémára vonatkozó megoldásokat. Ezzel a módszerrel könnyedén megmutathatjuk, hogy milyen tulajdonságokkal rendelkeznek az eredeti modelljeink. A negyedik fejezetben tanulmányozott esetben érdemes külön kihangsúlyozni, hogy egy eddig még nem tanulmányozott esetet mutatunk be, mikor a kapacitásos modellt egy nempáros gráfon adjuk meg. Ezért ebben a fejezetben már a modell fogalmainak, problémáinak megfogalmazása is új eredménynek számít.