Détermination (théorie des ensembles)

La détermination est un sous-champ de la théorie des ensembles, une branche des mathématiques, qui s'intéresse aux conditions dans lesquelles un joueur peut avoir ou non une stratégie gagnante dans un jeu, à la complexité d'une telle stratégie quand elle existe, ainsi qu'aux conséquences de l'existence de telles stratégies. Les jeux étudiés en théorie des ensembles sont généralement des jeux de Gale-Stewart, c'est-à-dire des jeux à deux joueurs à où les joueurs font une suite infinie de coups et où aucun match nul n'est possible. Le domaine de la théorie des jeux étudie des types de jeux plus généraux, comme les jeux avec match nul possible tels que le tic-tac-toe, les échecs ou , ainsi que les jeux à information imparfaite comme le poker. Le premier jeu que nous allons considérer est le jeu à deux joueurs à information parfaite de longueur ω, dans lequel les joueurs jouent des entiers naturels. Ces jeux sont souvent appelés jeux de Gale–Stewart. Dans ce jeu, il y a deux joueurs, souvent nommés I et II, qui choisissent à tour de rôle des entiers naturels, le joueur I commence. Ils jouent une infinité de fois chacun. Quand ils ont fini, ils ont obtenu une suite infinie d'entiers naturels. Une condition prédéterminée décide alors quel joueur a gagné en fonction de la suite ainsi obtenue. Plus formellement, considérons un sous-ensemble A de l'ensemble des suites d'entiers naturels. On appelle GA le jeu suivant : Le joueur I joue un entier naturel , puis II joue un entier naturel , I joue un entier naturel , et ainsi de suite. Le joueur I gagne le jeu si et seulement si la suite infinie appartient à A. Dans le cas contraire, le joueur II gagne. L'ensemble A s'appelle alors l'ensemble de gain de GA. Le but du joueur I est donc de s'assurer que la suite créée par les deux joueurs appartienne à l'ensemble A et le but du joueur II est de l'en empêcher. Le jeu est à information parfaite : chaque joueur connaît tous les mouvements qui précèdent chacun de ses mouvements et connaît également la condition de victoire.