MEGHÍVÓ

           Szeretettel meghívjuk Benedek Márton előadására

              az Optimalizálási Szeminárium keretében

            2018.10.25-én csütörtökön, 14:15-15:45 óráig

                 Helyszín: BME H épület 306 terem

Előadó: Benedek Márton (Mathematical Sciences, University of Southampton)

A nukleolusz kiszámítása és verifikációja általános játékosztályon

Abstract:

A nukleolusz egy attraktív kifizetésvektort kínál kooperatív játékokban, köszönhetően a rendkívül vonzó tulajdonságainak: létezik és egyértelmű minden játékban (melyben léteznek elosztások), illetve a magban található (ha a mag nem üres). A nukleolusz nyújtja a 'legstabilabb' megoldást azáltal, hogy lexikografikusan minimalizálja a nem-növekvően rendezett hiányt az összes koalíció körében.

Habár a nukleolusz kiszámítása rendkívüli erőfeszítést igényel, a Kohlberg-kritérium egy hatékony módszert biztosít egy lehetséges megoldás ellenőrzésére nem túl nagy méretű játékokban (ahol a játékosok száma, n, legfeljebb 15). Ez a módszer azonban túl nagy kihívást jelent nagyobb játékokban, mivel akár exponenciálisan sok koalícióhalmaz kiegyensúlyozottságának ellenőrzését is igényelheti, illetve egy-egy ilyen koalícióhalmaz tartalmazhat akár exponenciálisan sok koalíciót is.

Az előadás során bemutatott munka célja kettős. Egyrészt, bevezetjük a Kohlberg-kritérium egy hatékony verzióját, mely során legfeljebb (n-1) koalícióhalmaz ellenőrzése szükséges. Másodrészt, ezen eredményre alapozva bevezetünk egy új, konstruktív algoritmust a nukleolusz hatékony kiszámítására. Továbbá biztosítjuk a nagy méretű koalícióhalmazok kompakt reprezentációját és egy hatékony, gyors algoritmust a kiegyensúlyozottság ellenőrzésére. A numerikus tesztek alapján az új, konstruktív algoritmus felülmúlja mind a klasszikus LP-sorozat, mind a 'korszerű' pivot algoritmusokat.

Minden kedves érdeklődőt szeretettel várunk!