[PhD defence] 20/12/2024 - Omar BOUFOUS: "Correlated Equilibria and Learning" (UPR LIA)

Omar Boufous will submit his thesis on 20 December 2024 on the subject of "Correlated Equilibria and Learning".

Laboratory

UPR 4128 LIA - Avignon Computing Laboratory

Composition of the jury

MR RACHID ELAZOUZI	Avignon University	Thesis supervisor
Mr Balakrishna PRABHU	LAAS, CNRS, Toulouse	Examiner
Mr Maël LE TREUST	CNRS, UMR IRISA, Rennes	Examiner
Mr Eitan ALTMAN	INRIA, Sophia Antipolis	Thesis co-director
Mr Mikaël TOUATI	Orange	Thesis co-supervisor
Mr Mustapha BOUHTOU	Orange	Thesis co-supervisor
Mr Essaid SABIR	University of Quebec	Rapporteur
Ms Johanne COHEN	LISN, CNRS	Rapporteur

Summary

In this thesis, we study the problem of learning correlated equilibria and introduce a new concept of solution that takes into account the constraints on correlated strategies and extends the existing framework of correlated equilibria in finite non-cooperative games. In the first part, we present the definitions of correlated equilibrium and its main properties, while introducing essential concepts such as regret, which will be used in the following chapters of the manuscript. In the second part, we propose an algorithm that combines regret minimisation with an action recommendation scheme to stabilise the dynamics of regret minimisation. We show that the learning process can be modelled as a non-homogeneous Markov chain defined on a countable state space. A numerical study shows that all players play an approximate correlated equilibrium probability distribution with high probability in the long run. We show that this convergence is also observed in dynamic contexts such as games with a variable number of players. In the third part, we define constrained correlated equilibria through the generalised Nash equilibria of an extended game with a correlation device. We propose several characterisations of equilibrium strategies. Moreover, we consider a special case of constraints defined on the set of probability distributions induced by correlated strategies and show that canonical correlation devices are sufficient to characterise the set of constrained correlated equilibrium distributions. We show that this set may not be convex and show a sufficient existence condition. In the case of linear constraints, we also show that the problem of computing a constrained correlated equilibrium probability distribution can be formulated as a mixed integer linear program.

Keywords Game theory, Correlated equilibrium, Learning