Előadó:  Solymosi Tamás  BCE Operációkutatás és Aktuáriustudományok Tanszék

Súlyozott nukleoluszok kiszámítása kiegyensúlyozott játékokban

Absztrakt: A kooperatív játékok egyik központi megoldása, a nukleolusz azt az elosztási elvet testesíti meg, hogy először a legrosszabb helyzetben lévő koalíciókat hozzuk a lehető legjobb helyzetbe, majd azokat, amelyek helyzete még javítható anélkül, hogy a rosszabb helyzetben lévők helyzetén rontanánk, és így tovább, ameddig a javítás még lehetséges. A nukleolusz esetén egy koalíció elégedettségét a többletével, azaz a tagjainak jutó összkifizetésnek és a koalíció értékének a különbségével mérjük. Ez az egyszerű különbség azonban nem veszi figyelembe a koalíció egyéb olyan jellemzőit, amelyek fontosak lehetnek az alkalmazások szempontjából. Amennyiben egy koalíció elégedettségét például jobban jellemzi az egy főre jutó többlet, a nukleolusz alapját jelentő elosztási elv a per-capita a nukleoluszt adja, ami tehát az az elosztás, amelyik lexikografikusan maximalizálja a koalíciók egy főre eső többletének nemcsökkenő sorrendbe rendezett vektorát.

Előadásunkban a nukleolusz lineárisan súlyozott változatainak (mint például a per-capita nukleolusz) kiszámításakor felhasználható egyszerűsítési lehetőségekkel foglalkozunk. Megmutatjuk, hogy amennyiben a játék magja (a stabil elosztások halmaza) nem üres, a lineárisan súlyozott nukleoluszok meghatározásakor figyelmen kívül hagyhatók azok a koalíciók, amelyek nem lényegesek a duális játékban. Fontos következményként kapjuk, hogy például a hozzárendelési játékok osztályán a lineárisan súlyozott nukleoluszok polinom időben kiszámíthatók.