Détermination (théorie des ensembles) — Wikipédia

Ne doit pas être confondu avec Axiome de détermination.

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 à information parfaite (en) 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 les échecs infinis (en), ainsi que les jeux à information imparfaite comme le poker.

Notions de base[modifier | modifier le code]

Jeux[modifier | modifier le code]

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^[1].

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 G_A le jeu suivant :

Le joueur I joue un entier naturel ${\displaystyle a_{0}}$_, puis II joue un entier naturel ${\displaystyle b_{0}}$_, I joue un entier naturel ${\displaystyle a_{1}}$_, et ainsi de suite. Le joueur I gagne le jeu si et seulement si la suite infinie ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )}$ appartient à A. Dans le cas contraire, le joueur II gagne.

L'ensemble A s'appelle alors l'ensemble de gain de G_A. 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.

Stratégies[modifier | modifier le code]

De manière informelle, une stratégie pour un joueur est une manière de jouer dans laquelle ses coups sont entièrement déterminés par les coups précédents.

Plus formellement, une stratégie pour le joueur I (pour un jeu au sens de la sous-section précédente) est une fonction qui accepte comme argument toute suite finie de nombres naturels de longueur paire et qui retourne un nombre naturel. Si σ est une telle stratégie et ${\displaystyle (a_{0},b_{0},\ldots ,a_{n},b_{n})}$ est une suite de coups, alors ${\displaystyle \sigma (a_{0},b_{0},\ldots ,a_{n},b_{n})}$ est le prochain coup que I va faire, s'il suit la stratégie σ. Les stratégies pour II sont les mêmes, en remplaçant « pair » par « impair ».

Nous n'avons pour l'instant rien dit sur la pertinence des stratégies. Une stratégie peut tout à fait obliger un joueur à faire de mauvais coups, cela reste quand même une stratégie. En réalité, il n'est même pas nécessaire de connaître la condition de victoire du jeu pour savoir quelles sont les stratégies possibles.

Stratégies gagnantes[modifier | modifier le code]

Une stratégie est gagnante si le joueur qui la suit gagne nécessairement, peu importe ce que joue son adversaire.

Autrement dit, soit σ une stratégie pour I dans le jeu G_A. On dit que σ est une stratégie gagnante pour I si, pour toute suite ${\displaystyle (b_{0},b_{1},\ldots )}$ d'entiers naturels joués par II, la suite de coups produits par la stratégie σ en réponse à ${\displaystyle (b_{0},b_{1},\ldots )}$, à savoir ${\displaystyle a_{0}=\sigma ()}$ puis ${\displaystyle a_{1}=\sigma (a_{0},b_{0})}$ puis ${\displaystyle a_{2}=\sigma (a_{0},b_{0},a_{1},b_{1})}$ et ainsi de suite, permet à I de gagner, c'est-à-dire que ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )\in A}$.

Jeux déterminés[modifier | modifier le code]

Un jeu est dit déterminé s'il existe une stratégie gagnante pour l'un des deux joueurs. Notez qu'il ne peut y avoir de stratégie gagnante pour les deux joueurs pour le même jeu, car s'il en existait, les deux stratégies pourraient être jouées l'une contre l'autre. Le résultat obtenu serait alors, par hypothèse, une victoire pour les deux joueurs, ce qui est impossible^[2].

Le plus souvent, on ne s'intéresse pas à un unique jeu, mais à une classe de jeux. Une classe de jeux est dite déterminée si, pour tous les jeux dans cette classe, il existe une stratégie gagnante pour l'un des joueurs (pas nécessairement le même joueur pour chaque instance)^[3].

Détermination à partir de considérations élémentaires[modifier | modifier le code]

Tous les jeux finis à information parfaite sans match nul sont déterminés : c'est le théorème de Zermelo.

Pour les jeux finis à information parfaite avec match nul, on a un résultat analogue : l'un des deux joueurs a une stratégie non-perdante, c'est-à-dire qu'en suivant cette stratégie, le joueur ne perd jamais, il obtient soit un match nul soit une victoire. Un bon nombre de jeux de la vie courante sont dans cette catégorie : tic-tac-toe, ⁣⁣échecs⁣⁣⁣ (cela suppose que la règle des 50 coups soit appliquée), Puissance 4 ...

Dans le formalisme des jeux de Gale-Stewart, le fait qu'un jeu soit fini correspond au fait que l'ensemble de gain A soit un ouvert-fermé pour la topologie usuelle sur l'espace de Baire. Autrement dit, pour déterminer le gagnant d'une partie ${\displaystyle (a_{0},b_{0},a_{1},b_{1},\ldots )}$, il suffit de connaître un nombre fini de coups.

La preuve que de tels jeux sont déterminés est assez simple : le joueur I joue simplement pour ne pas perdre ; c'est-à-dire qu'il joue pour s'assurer que le joueur II n'a pas de stratégie gagnante après son coup. Si I ne peut pas le faire, cela signifie que le joueur II a eu une stratégie gagnante depuis le début. D'autre part, si le joueur I peut jouer ainsi, il doit gagner, car la partie sera terminée après un nombre fini de coups et il ne peut pas avoir perdu à ce moment-là.

Cette preuve n'exige pas que le jeu soit toujours terminé dans un nombre fini de coups, mais seulement dans un nombre fini de coups lorsque II gagne. Cette condition correspond au fait que l'ensemble A soit un fermé dans l'espace de Baire. Le fait que tous les jeux fermés sont déterminés s'appelle le théorème de Gale-Stewart. Notez que par symétrie, tous les jeux ouverts sont également déterminés (un jeu est ouvert si le joueur I ne peut gagner uniquement en un nombre fini de coups).

Détermination dans ZFC[modifier | modifier le code]

Le théorème de Gale-Stewart nous dit que lorsque l'ensemble de gain A est un ouvert ou un fermé de l'espace de Baire, alors le jeu associé est déterminé. On peut se demander ce qu'il en est lorsque l'on choisit des ensembles de gain de plus en plus complexes, par exemple selon la hiérarchie borélienne. Par la suite, on identifiera la complexité d'un jeu G_A à celle de l'ensemble de gain A vu comme partie de l'espace de Baire. Un jeu ouvert est donc un jeu pour lequel l'ensemble de gain A est ouvert, et ainsi de suite.

La détermination pour le deuxième niveau des jeux de la hiérarchie borélienne a été démontrée par Wolfe en 1955. Lors des vingt années suivantes, des recherches supplémentaires utilisant des arguments de plus en plus complexes ont permis d'établir que les troisième et quatrième niveaux de la hiérarchie borélienne étaient déterminés.

En 1975, Donald A. Martin a prouvé que tous les jeux boréliens étaient déterminés, c'est-à-dire que si A est un sous-ensemble borélien de l'espace de Baire, alors G_A est déterminé. Ce résultat, connu sous le nom de théorème de détermination borélienne (en), est le meilleur résultat de détermination possible prouvable dans ZFC, en ce sens que la détermination de la classe de Wadge (en) immédiatement supérieure ne peut pas être prouvée dans ZFC.

En 1971, avant que Martin obtienne sa preuve, Harvey Friedman montrait que toute preuve de la détermination borélienne devait utiliser l'axiome de remplacement de manière essentielle, afin de pouvoir itérer l'axiome de l'ensemble des parties de manière transfinie. Le travail de Friedman donne un résultat niveau par niveau détaillant le nombre d'itérations de l'axiome de l'ensemble des parties nécessaire pour garantir la détermination à chaque niveau de la hiérarchie borélienne.

Pour chaque entier naturel n, ZFC \ P (où P désigne l'axiome de l'ensemble des parties) prouve la détermination du n-ième niveau de la hiérarchie des différences des ensembles ${\displaystyle \mathbf {\Pi } _{3}^{0}}$, mais ZFC \ P ne prouve pas que pour tout entier n, le n-ième niveau de la hiérarchie des différences des ensembles ${\displaystyle \Pi _{3}^{0}}$ est déterminé. Voir l'article mathématiques inversées pour d'autres relations entre la détermination et les sous-systèmes de l'arithmétique du second ordre^{[réf. nécessaire]}.

Détermination et grands cardinaux[modifier | modifier le code]

Il y a des liens étroits entre la détermination et les grands cardinaux. En général, des axiomes de grands cardinaux plus forts permettent de prouver la détermination de classes (en) de jeux plus grandes, plus élevées dans la hiérarchie de Wadge (en). À l'inverse, la détermination de ces classes de jeux permet de prouver l’existence de modèles intérieurs (en) d’axiomes de grands cardinaux un peu plus faibles que ceux utilisés pour prouver la détermination de ces classes en premier lieu.

Cardinaux mesurables[modifier | modifier le code]

Il résulte de l'existence d'un cardinal mesurable que chaque jeu analytique (en) (également appelé jeu ${\displaystyle \mathbf {\Sigma } _{1}^{1}}$) est déterminé, ou, de manière équivalente, que chaque jeu coanalytique (ou ${\displaystyle \mathbf {\Pi } _{1}^{1}}$) est déterminé (voir hiérarchie projective (en) pour les définitions).

En réalité, un cardinal mesurable est plus que suffisant. Un principe plus faible — l'existence de 0^# (en) — suffit à prouver la détermination coanalytique, et un peu plus : le résultat précis est que l'existence de 0^# est équivalente à la détermination de tous les niveaux de la hiérarchie des différences en dessous du niveau ${\displaystyle \omega ^{2}}$, c'est-à-dire la détermination ${\displaystyle \omega .n-\mathbf {\Pi } _{1}^{1}}$ pour tout entier ${\displaystyle n}$.

D'un cardinal mesurable, nous pouvons très légèrement améliorer cette détermination jusqu'à la détermination ${\displaystyle \omega ^{2}-\mathbf {\Pi } _{1}^{1}}$.

De l'existence de plusieurs cardinaux mesurables, on peut prouver la détermination de plusieurs niveaux de la hiérarchie des différences sur ${\displaystyle \mathbf {\Pi } _{1}^{1}}$_.

Preuve de détermination à partir de dièses[modifier | modifier le code]

Pour chaque nombre réel r, la détermination ${\displaystyle \Sigma _{1}^{1}(r)}$ est équivalente à l'existence de r^#. Pour illustrer comment les grands cardinaux conduisent au déterminisme, voici une preuve de la détermination ${\displaystyle \Sigma _{1}^{1}(r)}$ supposant l'existence de r^#.

Soit A un sous-ensemble ${\displaystyle \Sigma _{1}^{1}(r)}$ de l'espace de Baire. Il existe un arbre T sur ${\displaystyle (\omega ,\omega )}$, constructible à partir de r, tel que A = p[T] (c'est-à-dire que pour toute suite ${\displaystyle x}$ de l'espace de Baire, on a ${\displaystyle x\in A}$ si et seulement s'il existe y tel que ${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...)}$ est un chemin à travers T).

Étant donné une partie partielle s, soit ${\displaystyle T_{s}}$ le sous-arbre de T cohérent avec s et tel que ${\displaystyle \max(y_{0},y_{1},\ldots ,y_{len(s)-1})<len(s)}$. Cette dernière condition garantit que ${\displaystyle T_{s}}$ est fini. La cohérence signifie que chaque chemin à travers ${\displaystyle T_{s}}$ est de la forme ${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))}$ où ${\displaystyle (x_{0},x_{1},...,x_{i})}$ est un segment initial de s.

Pour prouver que A est déterminé, définissons un jeu auxiliaire comme suit :

En plus des coups ordinaires, le joueur 2 doit jouer une application de ${\displaystyle T_{s}}$ dans les ordinaux (sous un ordinal suffisamment grand κ) tels que :

• chaque nouveau coup étend l'application précédente et
• l'ordre des ordinaux est conforme à l'ordre de Kleene-Brouwer sur ${\displaystyle T_{s}}$.

Rappelons que l'ordre de Kleene-Brouwer est semblable à l'ordre lexicographique, sauf que si s étend strictement t alors s < t . C’est un bon ordre si et seulement si l'arbre est bien-fondé.

Ce jeu auxiliaire est un jeu ouvert. Preuve : Si le joueur II ne perd pas à un stade fini, alors l’union de tous ${\displaystyle T_{s}}$ (qui est l’arbre qui correspond au jeu) est bien fondé et le résultat des coups non auxiliaires n’est donc pas dans A.

Ainsi, le jeu auxiliaire est déterminé. Preuve : Par induction transfinie, calculez pour chaque ordinal α l'ensemble des positions avec lesquelles le joueur I peut forcer une victoire en α étapes. Une stratégie pour le joueur I consiste à réduire α à chaque position (par exemple, en choisissant le plus petit α et en choisissant le plus petit coup en cas d'égalité), et une stratégie pour le joueur II consiste à choisir le plus petit coup ne menant pas à une position avec un α assigné. Notez que ${\displaystyle L(r)}$ contient l’ensemble des positions gagnantes ainsi que les stratégies gagnantes indiquées ci-dessus.

Une stratégie gagnante pour le joueur II dans le jeu d'origine conduit à une stratégie gagnante dans le jeu auxiliaire : le sous-arbre de T correspondant à la stratégie gagnante est bien fondé, ainsi le joueur II peut choisir des ordinaux basés sur l'ordre de Kleene-Brouwer de l'arbre. En outre, trivialement, une stratégie gagnante pour le joueur II dans le jeu auxiliaire donne une stratégie gagnante pour le joueur II dans le jeu original.

Il reste à montrer que, grâce à r^#, la stratégie gagnante susmentionnée pour le joueur I dans le jeu auxiliaire peut être convertie en une stratégie gagnante dans le jeu original. Si la réponse auxiliaire utilise uniquement des ordinaux indiscernables, alors (par indiscernabilité) les coups du joueur I ne dépendent pas des coups auxiliaires, de sorte que la stratégie peut être convertie en une stratégie pour le jeu d'origine (car le joueur II peut jouer avec des indiscernables aussi longtemps que nécessaire). Supposons que le joueur I perd dans le jeu d'origine. L'arbre correspondant est alors bien fondé. Par conséquent, le joueur II peut gagner le jeu auxiliaire grâce à des coups auxiliaires basés sur les indiscernables (puisque le type d'ordre des indiscernables dépasse l'ordre Kleene-Brouwer de l'arbre), ce qui contredit le fait que le joueur I remporte le jeu auxiliaire.

Cardinaux de Woodin[modifier | modifier le code]

L'existence d'un cardinal de Woodin avec un cardinal mesurable au-dessus implique la détermination ${\displaystyle \mathbf {\Pi } _{2}^{1}}$. Plus généralement, l'existence de n cardinaux de Woodin avec un cardinal mesurable au-dessus d'eux entraîne la détermination ${\displaystyle \mathbf {\Pi } _{n+1}^{1}}$. À partir de la détermination ${\displaystyle \mathbf {\Pi } _{n+1}^{1}}$, on peut prouver l'existence d'un modèle interne transitif contenant n cardinaux de Woodin. La détermination ${\displaystyle \Delta _{2}^{1}}$ (lightface) est équiconsistant à l'existence d’un cardinal de Woodin. Si la détermination ${\displaystyle \Delta _{2}^{1}}$ est vérifiée, alors pour un cône de Turing de x (c'est-à-dire pour tout réel x de degré de Turing suffisamment élevé), ${\displaystyle L[x]}$ vérifie la détermination OD (c'est-à-dire la détermination des jeux avec des entiers de longueur ${\displaystyle \omega }$ et dont l'ensemble de gain est définissable à partir des ordinaux), et dans ${\displaystyle {\text{HOD}}^{L[x]}}$, ${\displaystyle \omega _{2}^{L[x]}}$ est un cardinal de Woodin.

Détermination projective[modifier | modifier le code]

L'existence d'une infinité de cardinaux de Woodin entraîne la détermination projective, c'est-à-dire que chaque jeu dont l'ensemble de gain est un ensemble projectif (en) est déterminé. Du déterminisme projectif, il en résulte que, pour tout entier naturel n, il existe un modèle interne transitif ayant n cardinaux de Woodin.

Axiome de détermination[modifier | modifier le code]

L'axiome de détermination, ou AD, affirme que chaque jeu à deux joueurs à information parfaite de longueur ω, dans laquelle les joueurs jouent des entiers naturels, est déterminé.

AD est faux dans ZFC. En effet, grâce à l'axiome de choix, on peut prouver l’existence d’un jeu non déterminé. Cependant, s'il y a une infinité de cardinaux de Woodin avec un cardinal mesurable au-dessus d'eux, alors L(R) (en) est un modèle de ZF qui satisfait également AD.

Conséquences du déterminisme[modifier | modifier le code]

Propriétés de régularité pour des ensembles de réels[modifier | modifier le code]

Si A est un sous-ensemble de l'espace de Baire tel que le jeu de Banach-Mazur (en) pour A soit déterminé, alors soit II dispose d'une stratégie gagnante, auquel cas A est maigre, soit I a une stratégie gagnante, auquel cas A est comaigre dans un voisinage ouvert.

Cela n'implique pas forcément que A possède la propriété de Baire, mais cela s'en rapproche : une simple modification de l'argument montre que si Γ est une classe d'ensembles adéquate (en) telle que chaque jeu de Γ soit déterminé, alors chaque ensemble de réels de Γ a la propriété de Baire.

Ce résultat n'est pas optimal. En considérant le jeu déplié de Banach-Mazur, nous pouvons montrer que la détermination de Γ (pour Γ avec des propriétés de fermeture suffisantes) implique que chaque ensemble de réels qui est la projection d'un ensemble dans Γ a la propriété de Baire. Ainsi, par exemple, l’existence d’un cardinal mesurable implique la détermination ${\displaystyle \mathbf {\Pi } _{1}^{1}}$, ce qui implique que chaque jeu ${\displaystyle \mathbf {\Sigma } _{2}^{1}}$ de réels a la propriété de Baire.

En considérant d’autres jeux, nous pouvons montrer que la détermination ${\displaystyle \mathbf {\Pi } _{n}^{1}}$ implique que chaque ensemble de réels ${\displaystyle \mathbf {\Sigma } _{n+1}^{1}}$ a la propriété de Baire, est Lebesgue-mesurable (en fait, universellement mesurable (en)) et possède la propriété de l'ensemble parfait.

Théorèmes de périodicité[modifier | modifier le code]

• Le premier théorème de périodicité implique que, pour chaque entier naturel n, si la détermination ${\displaystyle \mathbf {\Delta } _{2n+1}^{1}}$ est vérifiée, alors ${\displaystyle \mathbf {\Pi } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Sigma } _{2n+2}^{1}}$ ont la propriété du pré-bon ordre (et que ${\displaystyle \mathbf {\Sigma } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Pi } _{2n+2}^{1}}$ n'ont pas la propriété du pré-bon ordre, mais ont plutôt la propriété de séparation).
• Le second théorème de périodicité implique que, pour chaque entier naturel n, si la détermination ${\displaystyle \mathbf {\Delta } _{2n+1}^{1}}$ est vérifiée, alors ${\displaystyle \mathbf {\Pi } _{2n+1}^{1}}$ et ${\displaystyle \mathbf {\Sigma } _{2n}^{1}}$ ont la propriété d'échelle (en)^[4]. En particulier, si la détermination projective est vérifiée, alors chaque relation projective a une uniformisation (en) projective.
• Le troisième théorème de périodicité donne une condition suffisante pour qu'un jeu ait une stratégie gagnante définissable.

Applications à la décidabilité de certaines théories du second ordre[modifier | modifier le code]

En 1969, Michael O. Rabin a prouvé que la théorie du second ordre de n successeurs est décidable^[5]. Un élément clé de la preuve consiste à montrer la détermination des jeux de parité, qui se situent au troisième niveau de la hiérarchie borélienne.

Détermination de Wadge[modifier | modifier le code]

La détermination de Wadge est l’affirmation que pour toutes les paires A, B de sous-ensembles de l'espace de Baire, le jeu de Wadge (en) G(A, B) est déterminé. De même, pour une classe d'ensembles (en) ${\displaystyle \Gamma }$, la détermination de Wadge pour ${\displaystyle \Gamma }$ est l'affirmation que pour tous les ensembles A, B dans ${\displaystyle \Gamma }$, le jeu de Wadge G(A, B) est déterminé.

La détermination de Wadge implique le principe d'ordre semi linéaire pour l'ordre de Wadge (en). Une autre conséquence de la détermination de Wadge est la propriété de l'ensemble parfait.

En général, la détermination de Wadge pour ${\displaystyle \Gamma }$ est une conséquence de la détermination des combinaisons booléennes d'ensembles de ${\displaystyle \Gamma }$. Dans la hiérarchie projective, la détermination de Wadge ${\displaystyle \mathbf {\Pi } _{1}^{1}}$ est équivalente à la détermination ${\displaystyle \mathbf {\Pi } _{1}^{1}}$, résultat prouvé par Harrington. Ce résultat a été étendu par Hjorth, qui a prouvé que la détermination de Wadge ${\displaystyle \mathbf {\Pi } _{2}^{1}}$ (et en fait le principe d'ordre semi linéaire pour ${\displaystyle \mathbf {\Pi } _{2}^{1}}$) implique la détermination ${\displaystyle \mathbf {\Pi } _{2}^{1}}$.

Jeux plus généraux[modifier | modifier le code]

Jeux dans lesquels les objets joués ne sont pas des entiers naturels[modifier | modifier le code]

La détermination des jeux sur les ordinaux de longueur ${\displaystyle \omega }$ et dont l'ensemble de gain est définissable par ordinaux implique que pour chaque cardinal régulier κ> ω, il n'y a pas de sous-ensembles de ${\displaystyle \kappa }$ disjoints, stationnaires, formés d'éléments de cofinalité ${\displaystyle \omega }$ et définissable par des ordinaux. La force de cohérence de cette hypothèse de détermination est inconnue, mais elle devrait être très élevée.

Jeux sur les arbres[modifier | modifier le code]

Jeux longs[modifier | modifier le code]

L'existence de ${\displaystyle \omega _{1}}$ cardinaux de Woodin implique que pour chaque ordinal dénombrable α, tous les jeux sur des entiers de longueur α et avec ensemble de gain projectif sont déterminés. Grosso modo, l'existence de α cardinaux de Woodin correspond à la détermination des jeux sur des réels de longueur α (avec un ensemble de gain simple). En supposant que ${\displaystyle \kappa }$ est une limite de cardinaux de Woodin avec ${\displaystyle o(\kappa )=\kappa ^{++}}$et qu'il existe ${\displaystyle \omega }$ cardinaux de Woodin supérieurs à κ, alors les jeux de durée dénombrable variable se terminant dès que sa longueur est admissible par rapport à la ligne de jeu et avec ensemble de gain projectif sont déterminés. En supposant qu'une certaine conjecture d'itérabilité puisse être prouvée, l'existence d'un cardinal de Woodin mesurable implique la détermination des jeux ouverts de longueur ${\displaystyle \omega _{1}}$ et avec ensemble de gain projectif. (Dans ces jeux, une condition de gain pour le premier joueur est décidée à une étape dénombrable, raison pour laquelle le gain peut être codé comme un ensemble de réels).

Relativement à l'existence d'un cardinal de Woodin limite de cardinaux Woodin et à un cardinal mesurable au-dessus d'eux, il est cohérent que chaque jeu sur les entiers de longueur ${\displaystyle \omega _{1}}$ avec un ensemble de gain définissable par ordinaux est déterminé. Il est conjecturé que cette hypothèse de détermination est équiconsistant avec un cardinal de Woodin limite de cardinaux de Woodin. L'ordinal ${\displaystyle \omega _{1}}$ est maximal dans la mesure où il existe des jeux indéterminés sur les entiers de longueur ${\displaystyle \omega _{1}+\omega }$ dont l'ensemble de gain est définissable par ordinaux.

Jeux à information imparfaite[modifier | modifier le code]

Dans la plupart des jeux intéressants à information imparfaite (en), une stratégie gagnante sera une stratégie mixte : c'est-à-dire qu'elle donnera une probabilité pour les différentes réponses à une même situation. Si les stratégies des deux joueurs sont des stratégies mixtes, alors le résultat du jeu ne peut pas être certainement décidé à l'avance (comme c'est le cas pour les stratégies pures, puisque celles-ci sont déterministes). Cependant, la distribution de probabilités des résultats pour des stratégies mixtes opposées peut être calculée. Un jeu qui nécessite des stratégies mixtes est dit déterminé s'il existe une stratégie qui donne une espérance minimale (sur l'ensemble des contre-stratégies possibles) qui dépasse une valeur donnée. Avec cette définition, tous les jeux finis à deux joueurs à somme nulle sont clairement déterminés. Cependant, la détermination des jeux infinis à information imparfaite (jeux de Blackwell) est moins claire^[6].

En 1969, David Blackwell a prouvé que certains jeux infinis à information imparfaite (maintenant appelés « jeux de Blackwell ») étaient déterminés, et en 1998, Donald A. Martin a prouvé que le déterminisme ordinaire (pour les jeux à information parfaite) pour une classe grasse d'ensembles (en) implique la détermination de Blackwell pour cette classe d'ensembles. Ceci, combiné au théorème de détermination borélienne de Martin, implique que tous les jeux de Blackwell avec des fonctions de paiement boréliennes sont déterminés^[7],[8]. Martin a conjecturé que la détermination ordinaire et la détermination de Blackwell pour les jeux infinis sont équivalents dans un sens fort (c'est-à-dire que la détermination de Blackwell pour une classe grasse d'ensembles implique à son tour la détermination ordinaire pour cette classe d'ensembles), mais en 2010, il n'a toujours pas été prouvé que la détermination de Blackwell implique la détermination des jeux à information parfaite^[9].

Notes et références[modifier | modifier le code]

• Portail de l’économie
• Portail de l'informatique théorique