Games and graphs – GAG

Two-player games certainly belong to the most complex problems in the field of combinatorics. One can indeed figure out this complexity when trying to answer the following question: whatever the strategy of my opponent is, does there exist a move that would lead me to victory? This hardness as well as the natural appeal of games made their interest grow, and led to the creation of a dedicated theory which is still under construction today. For a better understanding of our project topic, we point out that combinatorial game theory (CGT) is very different from the so-called "economic" game theory introduced by Von Neumann and Morgenstern, which allows hidden information, more than 2 players, negotiations or coalitions between the players.
Whereas combinatorial game theory is well established in North America or in Israel, such competitiveness has not been detected in France yet. One can find a few relevant results coming from French researchers, but to the best of our knowledge, there has never been a strong collaboration between French teams. Recently, a little more activity on the topic was observed: three PhD theses on combinatorial games were defended in 2006 (Grenoble), 2011 and 2013 (Bordeaux), and some first common results with international specialists of the field were recently published. Another PhD thesis is currently running, and a first collaboration has emerged thanks to a CNRS PEPS project. However, this activity is poor compared to the other kinds of games such as economical, stochastic or algorithmic games. In our opinion, this ANR project will be the key to strengthen the current national interest, and by the same time to amplify the scope of our results obtained inside the PEPS project. A "young researcher" proposal is also an opportunity for the coordinator to gather almost all the growing national community of young researchers working on the topic, with the support of three confirmed researchers.
Our objectives will be realized by producing strong results about well-known hard problems, the introduction of a new framework, collaborations with the best experts, and the organization of a worldwide meeting.
In this proposal, we choose to put graph theory in the heart of the combinatorial game problematic. Given any game, it is indeed easy to represent it by a digraph (which we call the game graph), where the vertices are the game positions, and the edges are the allowed moves. In the context of impartial 2-player games, finding a winning strategy is equivalent to finding a kernel (stable and absorbing set) in the game graph. However, the problem of finding a kernel is hard in general; moreover, there are some types of combinatorial games (misère, partisan) for which graph theory has never been considered as a tool. Our goal is thus to provide a graph theoretical toolbox to help in solving games in a more general context, including most of the major issues in combinatorial games. In particular, we plan to have applications of this toolbox in the following “key” problems:
- misère games, which are considered as the current hot topic of the domain. General results are also expected, like an equivalent of the Sprague-Grundy theory for misère impartial games.
- rewrite games on graphs, and in particular octal games or removal games on heaps.
- study of the link between CGT and some graph optimization parameters (e.g. game chromatic number, game domination number...), that are currently widely studied problems.
Analysis of game complexity for computing winning strategies and research of efficient algorithms are also strong objectives of this project.