game

un jeu (game) est un triplet $G = \{I,S_i,u_i\}$ où :
- $I$ est un ensemble de joueurs
- $S_i$ sont les stratégies (ou plus intuitivement les coups) disponibles de chaque joueur $i$ parmis $I$
- $u_i$ sont les scores pour chaque joueur $i$ parmis $I$

Pour rendre ceci plus accessible, prenons un exemple de jeu "humain", puis formalisons le comme un jeu formel décrit ci dessus.

Notre jeu : deux enfants doivent crier soit "BUH" soit "BEE". Le premier enfant gagne si il crie la même chose que l'autre. Le second enfant lui, gagne lorsqu'il crie le mot opposé.

Les joueurs $I$ sont les deux enfants. Nommons les $bobby$ et $watson$, ainsi on se retrouve avec $$I=\{bobby,watson\}$$

Il faut maintenant décrire les stratégies disponibles pour chaque enfant pour déterminer $S_{bobby}$ et $S_{watson}$. Dans notre petit jeu, il se trouve qu'ils ont tous deux les mêmes stratégies : crier "BUH" ou "BEE". Donc $$ S_{bobby} = \{BUH,BEE\} ; S_{watson} = \{BUH,BEE\} $$

Finalement les score $u_{bobby}$ et $u_{watson}$. disons qu'un gain revient à $1$ point de victoire, et qu'une perte à $0$. Les scores $u_{...}$ dépendant entièrement des choix de $bobby$ et $watson$, il faut établir une grille de scénarios possibles. À gauche on met toutes les stratégies de $bobby$, en haut on met toutes les stratégies de $watson$. On remarque que si on avait un joueur de plus, on aurait eu une figure en 3D en ajoutant les stratégies du 3ème joueur.

$bobby$ \ $watson$

BUH

BEE

BUH

$u_{bobby}=1 ; u_{watson}=0$

$u_{bobby}=0 ; u_{watson}=1$

BEE

$u_{bobby}=0 ; u_{watson}=1$

$u_{bobby}=1 ; u_{watson}=0$

il faut voir $u_{...}$ comme une fonction qui prend en argument les stratégies de tous les joueurs, et qui en retourne le score.

il n'est pas nécessaire ques les stratégies des joueurs soient identiques : on peut créer des jeux où un joueur a $2$ stratégies, alors que le second a $200$ qui n'ont rien à voir. Dans ce cas, la figure précédente devient une grille de $200\times 2$

Un profile de stratégie est une sélection de stratégies par les joueurs.

par exemple, dans le jeu précédent, $(BUH,BUH)$ où on a mis dans l'ordre la stratégie de $bobby$, puis celle de $watson$, est un profile de stratégie.

Dans un game $G$, pour un joueur $i$, on peut définir le best response correspondance pour un choix de stratégie fixé de tous les autres joueurs que $i$. On le note $BR_i(s_1,...,s_{i-1},s_{i+1},...,s_I)$ (où $s_k \in S_k$ une stratégie parmis les stratégies disponibles pour chaque joueur concurrent).

C'est à dire que étant donné que tous les joueurs ont choisi leur coup, quel est le coup qui donne le meilleur score (ou éventuellement les meilleurs score si plusieurs coups ont le même score maximal).

Un équilibre de Nash est un profile de stratégie où "tous les joueurs font de leur mieux en même temps" de la façon suivante : chaque joueur pris individuellement, en changeant sa stratégie personnelle ne peut que baisser son score.

Autrement dit, pour chaque joueur $i$, sa stratégie fait partie de la best reponse correspondance, étant donné le choix des stratégies des autres joueurs

Cet équilibre n'est pas forcément unique. Pire encore, en considérant d'autres versions d'optimalités, on peut constater que la solution obtenue peut avoir un score assez mauvais pour tout le monde.

un jeu particulier

Le but ici est de comprendre l'illustration en page 5 de ce document

Un ordinal $2\times2$ game est un jeu $G$ avec les contraintes suivantes :
- nous avons deux joueurs $I=\{j_1,j_2\}$
- deux stratégies par joueurs $\begin{cases}S_{j_1}=\{A,B\}\\S_{j_2}=\{C,D\}\end{cases}$ (je les nommes différemment pour la clareté)

Comme il y a seulement $4$ profiles de stratégies possibles qui sont $(A,C), (B,C), (A,D), (B,D)$, on peut demander à chaque joueur de mettre un ordre de préférence sur chaque scénario : on met un score de $1$ sur le scénario le moins désiré, puis $2$, puis $3$, puis $4$ pour le préféré. Les valeurs choisies par les deux joueurs détermineront alors notre fonction score (attention, le choix de l'ordre de préférence ne fait pas partie du jeu, il sert à définir le jeu).

Eh bien comme on a pas décidé ce que valent les scores $u_{j_1}$ et $u_{j_2}$, essayons de les regarder tous en même temps ! Robinson-Goforth topology propose une visualization de tous ces jeux en même temps, en mettant tous les jeux dans une grande grille, où les voisins sont choisi pour être conceptuellement proche (d'où le mot "topologie")

Quelques observations de base : comptons le nombre de jeux possibles. Il y a $4\cdot3\cdot2=24$ choix possible d'ordre de préférence, pour chaque joueur. Ainsi on a au total $24 \cdot 24 = 576$ jeux possibles. En notant qu'échanger les joueurs $j_1$ et $j_2$, on a une symétrie, on peut constater qu'on a pas besoin de regarder tous ces jeux, la moitié est redondante.