Games that pay

Prelegent(ci)

Krzysztof Żyndul

Afiliacja

MIMUW

Język referatu

polski

Termin

14 października 2025 11:00

Pokój

p. 4060

Tytuł w języku angielskim

Games that pay

Seminarium

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

Referat będzie poświęcony mojej pracy magisterskiej pt. „Algorithmic Problems for Games on Weighted Graphs”. Praca dotyczy gier rozgrywanych na grafach z wagami, które stanowią ważny model w teorii gier i weryfikacji systemów. W szczególności zajmuję się tzw. grami o średniej wypłacie (mean-payoff games), które od wielu lat pozostają przedmiotem intensywnych badań w teorii gier. Problem ich rozwiązania należy do klasy NP /\ co-NP, lecz nie znamy efektywnego algorytmu.

Podczas referatu skupię się na moich dotychczasowych wynikach. Dotyczą one gier typu lasso. W tego rodzaju grach analizowany jest całkowity zysk do momentu zamknięcia pierwszej pętli. Pozornie niewielka modyfikacja funkcji wypłaty powoduje, że problem rozwiązania tych gier staje się PSPACE-zupełny.

---