Nhat Thang Le will be defend his thesis on "Algorithmic Aspects of Markov Processes and Their Applications", on Thursday, October 30th, 2025 at 03:00 pm at Toulouse School of Economics (Auditorium 4).
This thesis will be accessible also online via Teams; to attend the meeting, please contact the candidate.
Memberships are:
- Mr. Jan Maas – Institute of Science and Technology of Austria (Referee)
- Mr. Zhenji Ren – LaMME, Université d’Évry, Paris-Saclay (Referee)
- Mr. Pierre Del Moral – INRIA Bordeaux (Examiner)
- Mrs. Aurélia Deshayes – Université Paris-Est Créteil (Examiner)
- Mr. Laurent Miclo – Institut de Mathématiques de Toulouse, CNRS (Thesis Advisor)
- Mr. Stéphane Villeneuve – Toulouse School of Economics (Thesis Co-Advisor)
Abstract:
This thesis presents two applications of Markov processes.
The first part focuses on finite optimization, where we propose a new swarm dynamic formulated in the framework of nonlinear Markov chains. This dynamic serves as the foundation for a particle approximation algorithm designed to approximate the nonlinear Markov evolution. The underlying idea is that the interacting particles progressively concentrate on the set of optimizers of the target function. A key result we establish is that, by choosing a temperature schedule of the form βt ≈ t^α with α∈(0,1/2), the measure of the set of global optimizers converges to 1. This contrasts with the classical ln(t) temperature schedule used in simulated annealing algorithms.
The second part introduces a novel and efficient algorithm for computing both the value function and the Nash equilibrium in a class of zero-sum optimal stopping games involving two players, commonly known as Dynkin games. In such games, the players observe the evolution of a Markov process on a finite state space and may choose to stop the game at any time. When the game stops, a payoff is made from one player to the other. The proposed algorithm demonstrates strong practical efficiency and opens a promising direction for future applied research, complementing the already well-established theoretical literature on this topic. In particular, the algorithm terminates in strictly fewer than N^2 steps, where N denotes the size of the underlying state space. Moreover, each step requires only the computation of a matrix inverse, making the overall computational complexity entirely dependent on that of matrix inversion algorithms.