Research topics

Understandable, accountable, and trustworthy AI

Computational evolution, variational MARL and XAI

The multi-population replicator dynamics (RD) is a dynamic approach to coevolving populations and multi-player games. In general, not every equilibrium is a Nash equilibrium of the underlying game, and convergence is not guaranteed. In particular, no interior equilibrium can be asymptotically stable in the multi-population RD, resulting, e.g., in cyclic orbits around a single interior NE. We introduce a new notion of equilibria of RD, called mutation limits, which is invariant under the specific choice of mutation parameters. We prove the existence of mutation limits for a large class of games, and consider a particularly interesting subclass, called attracting mutation limits, which offer approximate solution even if the original dynamic is not convergent. Thus, mutation stabilises the system in certain cases and makes attracting mutation limits near-attainable. We observe that mutation limits have some similarity to Q-learning in multi-agent reinforcement learning. We are interested in investigating such relationship in the context of variational principles.


Featured publication:

Bauer, J., Broom, M. and Alonso, E. (2019). The stabilization of equilibria in evolutionary game dynamics through mutation: mutation limits in evolutionary games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2231). doi:10.1098/rspa.2019.0355.

Parity games

We are interested in studying the problem of solving parity games. Solving parity games is equivalent to do model-checking on some fixpoint logics which in turn is used for computer systems verification. A long-standing open problem on parity games asks whether they can be solved in polynomial time. Recent exciting breakthroughs have achieved quasi-polynomial time. Together with researchers from the University of Warwick, the University of Warsaw (Poland) and the University of Bordeaux (France), we have proved that many of the recently introduced quasi-polynomial algorithms to solve parity games can be put under a common framework and that under this framework, no one can hope to reach a better bound than quasi-polynomial time. This shows that new techniques still need to be developed in the quest of a polynomial time algorithm for solving parity games.


Featured publication:

W. Czerwiński, L. Daviaud, N. Fijalkow, M. Jurdziński, R. Lazić, P. Parys (2019). Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. Proceedings of SODA 2019.