Game Theory
Computer Science
1 Career
- Since 2016 Computer Science Track Representative, Graduate School, Institute of Science and Technology Austria (ISTA)
- Since 2014 Professor, Institute of Science and Technology Austria (ISTA)
- 2009 – 2014 Assistant Professor, Institute of Science and Technology Austria (ISTA)
- 2008 – 2009 Postdoc, University of California, Santa Cruz, USA
- 2007 PhD, University of California, Berkeley, USA
1.1 Selected Distinctions
- Conference organization:
- 2014 Conference chair of CSL-LICS 2014, and part of organizing committee of Vienna Summer of Logic 2014
- Editorship:
- Since 2018 Information and Computation (I&C)
- 2014 – 2020 Information Processing Letters (IPL)
1.2 Selected Grants
- 2026 – 2029 WWTF research grant, PROMPT, Co-Investigators: L. Kovacs and E. Bartocci from TU Wien. Awarded overall: € 879,000, awarded to RG: € 293,000.
- 2025 – 2029 FWF Cluster of Excellene (BILAI).
Awarded overall: € 19,700,000, awarded to RG: € 612,000. - 2019 – 2025 ERC Consolidator Grant: ForM-SMArt – 863818. Awarded overall: € 2,000,000.
1.3 Tech Transfer (Patents, Spin-Offs)
N/A
1.4 Selected Publications
- K. Chatterjee, R. Saona, and B. Ziliotto, “Finite-memory strategies in pomdps with long-run average objectives,” Math. Oper. Res., vol. 47, no. 1, pp. 100–119, 2022. DOI: 10.1287/MOOR.2020.1116. [Online]. Available: https://doi.org/10.1287/moor.2020.1116.
- A. Asadi, K. Chatterjee, J. Svoboda, and R. S. Urmeneta, “Deterministic sub-exponential algorithm for discounted-sum games with unary weights,” in Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024, P. Sobocinski, U. D. Lago, and J. Esparza, Eds., ACM, 2024, 6:1–6:12. DOI: 10.1145/3661814.3662080. [Online]. Available: https://doi.org/10.1145/3661814.3662080.
- J. Svoboda and K. Chatterjee, “Density amplifiers of cooperation for spatial games,” Proceedings of the National Academy of Sciences, vol. 121, no. 50, e2405605121, 2024. DOI: 10.1073/pnas. eprint: https://www.pnas.org/doi/pdf/10.1073/pnas.2405605121. [Online]. Available: https://www.pnas.org/doi/abs/10.1073/pnas.2405605121.
- J. Svoboda and K. Chatterjee, “Promoters of cooperation in evolutionary games,” Proceedings
of the National Academy of Sciences, vol. 122, no. 51, e2524109122, 2025. DOI: 10.1073/pnas. eprint: https://www.pnas.org/doi/pdf/10.1073/pnas.2524109122. [Online]. Available: https://www.pnas.org/doi/abs/10.1073/pnas.2524109122. - L. Schmid, F. Ekbatani, C. Hilbe, and K. Chatterjee, “Quantitative assessment can stabilize indirect reciprocity under imperfect information,” Nature Communications, vol. 14, no. 1, p. 2086, Apr. 2023, issn: 2041-1723. DOI: 10.1038/s41467-023-37817-x. [Online]. Available:
https://doi.org/10.1038/s41467-023-37817-x.
2 Group Members
- Ali Asadi, PhD Student since 2021
- Ehsan Goharshadi, PhD Student since 2022
- Mehrdad Karrabi, PhD Student since 2021
- Ruichen Luo, PhD Student since 2023
- Satya Prakash Nayak, Postdoc since 2026
3 Research
Game theory provides the mathematical foundations for decision-making and is applicable in a wide range of disciplines from economics, to computer science, to biology. The research focus of our group is algorithmic and computational aspects of game theory in sequential-decision making. Sequential decision making is relevant in formal analysis of reactive systems (or systems that interact with other agents or environment); in planning problems in artificial intelligence; and are relevant even beyond computer science in evolutionary game theory. The work of our group covers a wide range of topics, such as, (a) improved algorithms and complexity of classical game theoretic models such as stochastic games and Markov decision processes; (b) automated methods for analysis of infinite-state stochastic models such as probabilistic programs; (c) applications of the game theoretic methods in robust reinforcement learning; and (d) algorithmic aspects of evolutionary game theory.
3.1 Current Scientific Projects/Directions
- Algorithmic methods for stochastic games
- Robust reinforcement learning
- Automated methods for Probabilistic Program Analysis
3.2 Research in Focus
We highlight our achievements in two different areas. First, in the area of sequential-decision making, a fundamental model is partially-observable Markov decision processes (POMDPs). A widely-known and long-time open conjecture from Bertsekas 1998 was the existence of finite-memory approximately optimal strategies for average-reward payoff for this model. We resolved this conjecture and establish computational complexity for this problem in our MOR 2021 paper. Second, the models of spatial games and evolutionary games on graphs are widely applicable from physics to biology. The existence of networks or graphs, that can promote cooperative behavior in such models has been a long-standing open problem since May-Nowak paper in 1997 on spatial games. We resolved the open conjectures by presenting the first networks to provably improve cooperative behavior for spatial games (PNAS 2024) and for evolutionary games on graphs (PNAS 2025).