Research
Most of my research activities concern the algorithmic side of game theory and its applications in computer
science. At the moment, I am particularly interested in stochastic games with partial
observation and I am working on problems like
the decidability of distributed games,
games with a parametric number of players
or cooperation and competition in bridge.
I am also interested in various topics including
social choice theory and practice,
precision farming,
logics for handling
probabilities and
controlling humanoïd robots with MDPs.
PhD advisor of Soumyajit Paul (with Olivier Ly and Srivathsan Balagaru),
PhD co-advisor of Simon Mauras (with Claire Mathieu),
PhD advisor of Edon Kelmendi (with François Dufour), Quentin
Rouxel (with Olivier Ly) and Ludovic Hofer (with Olivier Ly). Formerly,
PhD advisor of Youssouf Oualhadj (with Anca Muscholl).
Other Activities
Preprints
Papers
The
complete up-to-date list.
Papers before 2017
Some links to the pdf versions for papers from 2004 to 2017,
before open-access became the rule.
-
[37]
On the Controller Synthesis Problem for Distributed Systems with Causal Memory
.
Accepted for FSTTCS 2017.
-
[36]
Qualitative Determinacy and Decidability of Stochastic Games with
Signals.
Co-authored with
Nathalie Bertrand and Blaise Genest.
J. ACM 64(5): 33:1-33:48 (2017)
-
[35] Controlling a Population.
Co-authored with
Nathalie Bertrand, Miheer Dewaskar, Blaise Genest.
Accepted for CONCUR 2017: 12:1-12:16.
-
[34]
Emptiness of Zero Automata Is Decidable
.
Co-authored with
Mikolaj Bojanczyk,Edon Kelmendi.
ICALP 2017: 106:1-106:13
-
[33]
Stamina: Stabilisation Monoids in Automata Theory.
Co-authored with
Nathanaël Fijalkow, Edon Kelmendi, Denis
Kuperberg.
Published in CIAA 2017.
-
[32]
Deciding Maxmin Reachability in Half-Blind Stochastic Games.
Co-authored with Edon Kelmendi.
Accepted for SAGT
2016: 52-63.
-
[31]
Deciding the value 1 problem for probabilistic leaktight automata.
co-authored with
Nathanaël Fijalkow, Edon Kelmendi, Youssouf Oualhadj.
Published in Logical Methods in Computer Science 11(2) (2015).
-
[30]
Randomness for free.,
co-authored with
Krishnendu Chatterjee, Laurent Doyen, Thomas
A. Henzinger.
Published in Inf. Comput. 245: 3-16 (2015).
-
[29]
A Fully Autonomous Robot for Putting Posts for Trellising Vineyard
with Centimetric Accuracy,
co-authored with
Olivier Ly, Gregoire Passault and Gerald Baron
. Accepted for ICARSC 2015.
-
[28]
Perfect-Information Stochastic Mean-Payoff Parity Games
,
co-authored with Krishnendu Chatterjee, Laurent Doyen and Youssouf Oualhadj.
Accepted for FOSSACS'14.
-
[27]
Deciding the Value 1 Problem for #-acyclic Partially Observable Markov Decision Processes
,
co-authored with Youssouf Oualhadj. Accepted for SOFSEM'13.
-
[26]
Asynchronous Games over Tree Architectures
,
co-authored with Blaise Genest, Anca Muscholl and Igor Walukiewicz. Accepted for ICALP'13.
-
[25]
A Class of Probabilistic Automata with a Decidable Value 1 Problem,
co-authored with
Nathanaël Fijalkow
and
Youssouf Oualhadj. Accepted for LICS'12.
-
[24]
Subgame Perfection for Equilibria in Quantitative Reachability Games,
co-authored with Thomas Brihaye, Véronique Bruyère and Julie De Pril. Accepted for FOSSACS'12.
-
[22]
Blackwell-Optimal Strategies in Priority Mean-Payoff Games, co-authored with Wieslaw Zielonka.
Accepted for Gandalf'2010. Selected for the journal special issue.
-
[21]
Randomness for Free
, co-authored with Krishnendu Chatterjee, Laurent Doyen and Thomas Henzinger. Accepted for MFCS'10.
-
[20]
Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata
, co-authored with Blaise Genest, Anca Muscholl and Igor Walukiewicz. Accepted for ICALP'10.
-
[19]
Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
, co-authored with Youssouf Oualhadj. Accepted for ICALP'10.
-
[16]
Solving Simple Stochastic Tail Games
, co-authored with Florian Horn. Accepted for SODA'10.
-
[15]
Solving Simple Stochastic Games with Few Random Vertices
co-authored with Florian Horn. LMCS, vol. 5(2), special issue of FOSSACS'08.
The conference version is [10]
-
[14]
Qualitative Determinacy and Decidability of Stochastic Games with Signals,
co-authored with Nathalie Bertrand and Blaise Genest. Accepted for LICS'09.
-
[11]
"Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games, in
"Logic and Automata: History and Perspectives. Volume 2 of Texts in Logic and Games, pages 331-355, 2007. Amsterdam University Press.
-
[10]
"Simple Stochastic Games with Few Random Vertices are Easy to
Solve"
, co-authored with Florian Horn. Accepted for FOSSACS'08.
-
[9]
"Perfect Information Stochastic Priority Games"
, co-authored with Wiesław Zielonka. Accepted for ICALP'07.
-
[8]
"Limits of Multi-Discounted Markov Decision Processes"
, co-authored with Wiesław Zielonka. Accepted for LICS'07.
-
[6]
"Pure stationary optimal strategies in Markov decision processes"
and its
full version
. Accepted for STACS'07.
-
[5]
"Deterministic Priority Mean Payoff Games as Limits of Discounted Games"
, co-authored with Wiesław Zielonka. Accepted for ICALP'06.
-
[4]
"Discounting Infinite Games, but How and Why ?"
, co-authored with Wiesław Zielonka. Invited paper for GDV'04.
-
[3]
"Games Where You Can Play Optimally Without Any Memory"
, co-authored with Wiesław Zielonka. Accepted for CONCUR'05.
-
[2]
"When can you play positionally ?"
and its
full version
, co-authored with Wiesław Zielonka. Accepted for MFCS'04.
-
[1]
"Parity and Exploration Games on Infinite Graphs"
and its
full version
, Accepted for CSL'04.
PhD thesis
I used to be a PhD student under the supervision of
Wiesław Zielonka.
If you can read french and if you are interested in game theory, then have a look at my PhD thesis:
Code
I enjoy coding for solving real-life problems, with impact.
- BipBip is a collaborative project in the field of precision agriculture,
part of Challenge Rose,
in which we develop a robot for mechanical intra-row weeding.
With Steve Nguyen and Olivier Ly we develop a ROS-based onboard control system,
mostly C++.
- Carte interactive Parcoursup 2019
is a map I developed with my fellow colleague David Auber
. This map provides information to french highschool students in order to help them formulate wishes on Parcoursup.
- Modeles de Parcoursup is a C++-model of Parcoursup.
Some details available on this video.
- Algorithmes-de-parcoursup
is an open-source project which led to the production of
two algorithms and their Java implementation.
This piece of software is
used by the french government in order to deal with College admission in France.
The Gale-Shapley algorithm is the standard method in practice for large matching markets, but must be adapted to the constraints of each situation.
Together with Claire Matthieu, we designed a college admission procedure which respect legal regulations
and governemental constraints in a setting with the following features:
- Lack of trust in the platform: students wants to keep control rather than leaving it to a computer:
with sometimes more than 50 wishes,
the students prefer to express their preferences once they know their options, rather than ranking all these possible options in advance.
- Transparency: the final result must not be given as a black box but come with an “explanation” that helps rebuild trust.
- Quotas: schools have a legal obligation to respect certain quotas of student types. The types and quotas vary from school to school.
- Housing: schools provide housing to some of their students, allocated according to need.
Some students can only afford to attend if housing is provided. The offers must thus take into account both the students’ academic ranking and their ranking according to need.
- Simplicity: to be socially acceptable, the designed algorithm shall be elementary and simple.
- Determinacy: the use of a random device is forbidden.
- Stamina is a tool which computes
stabilization monoids, compute star-height of regular languages, decide the value 1 problem for probabilistic
automata or decide whether a counter-automaton is bounded.
The code, mostly C++.
- Marmotte is a website that
dematerializes most of the tasks of members
of Comité
National de la Recherche Scientifique
(CNRS competition, evaluation of research units and researchers, expertise)
and improves the diffusion of
information among the Comité National.
The code, mostly php.
- The Rhoban project is a good
opportunity to produce some real-time algorithms for image
processing and robotic control, and play
soccer. Rhoban System
is the eponym Spin-off of LaBRI in which the algorithms are adapted
and used
to solve real-world problems and developp smart systems for agriculture.
Teaching
CV
My CV is available
here.
About quantitative (as opposed to qualitative)
evaluation of research
The San Francisco Declaration on Research Assessment (DORA) .
Two convincing critics of evaluation of publications and researchers using metrics.
A technical one, in french, written by INRIA computer scientists.
Another one, "The Mismeasurement of Science" less technical and more acid, written by a Cambridge biologist.
The mitigated opinion of the french academy of science.
My ha-index: 84
The webpage of parents d'élèves de l'école Maternelle Paul Antin.
