2010. november 27., szombat

Automated mechanism design

Többeknek feltűnt már, hogy mindenről írtam már, csak arról nem, amiért konkrétan a PhD szól és a fizetést is kapom: a kutatásról. Idáig nem is volt nagyon mit, mivel lassan körvonalazódik a téma, s a felettesem szerint az első év arról szól, hogy megtanuljam azon matematikai eszközöket, amik a kutatáshoz szükségesek és mindent elolvassak, aminek köze lehet a projekthez, illetve azt is, aminek nem, mert az is szélesíti a látóköröm. Az irány alapvetően az algoritmikus játékelmélet lenne, aminél muszáj hangsúlyozni az algoritmikus részt, mert különben nem lehetnénk az operáció kutatási csoportban. Ez kicsit korlátozza is a többi csoporttárssal való együttműködést, mert az operációkutatás játékelméleti aspektusával egyedül a tanárom 3 tanonca foglalkozik (én + az iráni Hossein + a kóreai Csing Vung, akinek értelemszerűen nem ez a neve, de az eredetit nem tudom megjegyezni). Közölünk Hossein van itt a legrégebben, utána következik Csing Vung és én vagyok a legújabb. Csing Vung egyszer mondta is, hogy neki Hossein a jövője. Erre reagáltam, hogy remélem nekem egyikőtök sem lesz az, hehe.
Egyelőre több fő téma is terítéken van, de az első iránycsapás az automatikus mechanizmus tervezésben történt. A mechanizmus tervezés röviden és kevésbé tudományosan játékok kereteinek, szabályainak tervezését jelenti. Ezen szabályokat igyekszünk úgy megkonstruálni, hogy miközben játékosok önös érdekeik szerint cselekedve, saját hasznosságuk maximalizálása szerint játszanak, mégis a mi céljainknak megfelelő eredményt érjék el a játék végén. A játék lehet aukció, közbeszerzés, válási osztozkodás vagy bármilyen más szituáció, ahol több szereplő kerül interakcióba egymással. A mi célunk lehet például a nép jólét, bevétel maximalizálás vagy bármi más nemes vagy nemtelen ügy. Külön figyelnünk kell arra, hogy a játékosoknak megérje részt venni a mókában, illetve, hogy őszintén, a saját preferenciáik kinyilvánításával tegyék. Ez elég összetett probléma, különböző típusú estekhez eltérő optimális megoldás tartozik, vagy még nincs is rá egy. Az automatikus mechanizmus tervezés mindezt azzal fejelné meg, hogy írunk egy programot, aminek csak beadnánk, hogy mi a játék, kik a szereplők, mi a célunk és ő megadná nekünk korlátos időn belül az optimális mechanizmust problémaosztálytól függetlenül. Ez elég elegáns megoldás, én magam is írtam ilyen programot, nagyon szép eredményeket ad, de nagyon hamar kapacitás problémákba ütközünk. A probléma exponenciálisan nő az inputtal így a valóság reprezentálása  erősen korlátozott. A projekt célja tehát az tömörebb reprezentálás, gyorsabb megoldás keresés, illetve  pontos közelítő algoritmusok meghatározása. Előre!

1 megjegyzés: