Games that pay

Speaker(s)

Krzysztof Żyndul

Affiliation

MIMUW

Language of the talk

Polish

Date

Oct. 14, 2025, 11 a.m.

Room

room 4060

Title in English

Games that pay

Seminar

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.

---