Leírás
Bonylultságelmélet szeminárium
Absztrakt:
Tarski tétele egy fixponttétel, aminek fontos szerepe van a közgazdasági
játékok elméletében, például ez a tétel garantálja a Nash-egyensúly létezését
szupermoduláris játékokban. A tétel szerint ha adott egy f monoton növő
függvény, ami a {1,2,...,N}^d rácsból önmagába képez, akkor f-nek van
fixpontja. Ez rögtön látszik, ha tekintjük az 1...1, f(1...1),
f(f(1...1), ... sorozatot, ami a monotonitás miatt legfeljebb dN lépésben
stabilizálódik, vagyis ezt algoritmusként használva O(dN) lépésben tudunk
találni egy Tarski-fixpontot. Ennél gyorsabb algoritmusok is ismertek,
legutóbb Fearnley és Savani adott egy O((logN)^(d-1)) idejűt. Etessami és
szerzőtársai a Tarski-fixpont keresésének bonyolultságát vizsgálták, és
megmutatták, hogy a probléma benne van a PLS és a PPAD osztályok metszetében.
For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).