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

Research news 12 December 2024

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

Date and place

Oral defense scheduled on Friday 20 December 2024 at 2pm
Venue: Orange Gardens, 46 Av. de la République, 92320 Châtillon
Venue: Orange Gardens

Discipline

Computer Science

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

Mots clés associés
thesis defence