Jeux combinatoires dans les graphes / Gabriel Renault ; sous la direction de Paul Dorbec et de Eric Sopena

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Théorie des jeux

Théorie des graphes

Dorbec, Paul (1980-.... ; enseignant-chercheur en informatique) (Directeur de thèse / thesis advisor)

Sopena, Eric (1961-....) (Directeur de thèse / thesis advisor)

Gravier, Sylvain (19..-.... ; informaticien) (Membre du jury / opponent)

Cazenave, Tristan (19..-....) (Membre du jury / opponent)

Duchêne, Eric (1981-.... ; auteur en informatique) (Membre du jury / opponent)

Université Bordeaux-I (1971-2013) (Organisme de soutenance / degree-grantor)

École doctorale de mathématiques et informatique (Talence, Gironde ; 1991-....) (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire bordelais de recherche en informatique (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Dans cette thèse, nous étudions les jeux combinatoires sousdifférentes contraintes. Un jeu combinatoire est un jeu à deux joueurs, sanshasard, avec information complète et fini acyclique. D’abord, nous regardonsles jeux impartiaux en version normale, en particulier les jeux VertexNimet Timber. Puis nous considérons les jeux partisans en version normale, oùnous prouvons des résultats sur les jeux Timbush, Toppling Dominoeset Col. Ensuite, nous examinons ces jeux en version misère, et étudionsles jeux misères modulo l’univers des jeux dicots et modulo l’univers desjeux dead-endings. Enfin, nous parlons du jeu de domination qui, s’il n’estpas combinatoire, peut être étudié en utilisant des outils de théorie des jeuxcombinatoires.

Résumé / Abstract : In this thesis, we study combinatorial games under differentconventions. A combinatorial game is a finite acyclic two-player game withcomplete information and no chance. First, we look at impartial gamesin normal play and in particular at the games VertexNim and Timber.Then, we consider partizan games in normal play, with results on the gamesTimbush, Toppling Dominoes and Col. Next, we look at all these gamesin misère play, and study misère games modulo the dicot universe and modulothe dead-ending universe. Finally, we talk about the domination game which,despite not being a combinatorial game, may be studied with combinatorialgames theory tools.