Bref introduction à la théorie des jeux algorithmiques

...

Le filtrage bayésien du spam est une technique puissante pour traiter le courrier électronique indésirable. Elle s'adapte aux habitudes de courrier des uns et des autres et produit un taux de faux positifs suffisamment bas pour être acceptable. Wikipédia (2016).

Fonctionnement

Certains mots ont des probabilités d'apparaître dans un spam et dans un courrier légitime. Par exemple, la plupart des gens rencontreront fréquemment le mot « Viagra » dans leurs spams, mais ils le rencontreront rarement dans leurs courriers légitimes. Le filtre ne connaît pas à l'avance ces probabilités, c'est pourquoi il lui faut un temps d'apprentissage pour les évaluer. L'apprentissage est à la charge de l'utilisateur, qui doit indiquer manuellement si un message est un spam ou non. Pour chaque mot de chaque message « appris », le filtre ajustera les probabilités de rencontrer ce mot dans un spam ou un courrier légitime et les stockera dans sa base de données. Par exemple, les filtres bayésien ont de fortes chances d'avoir une forte probabilité de spam pour le mot « Viagra », mais une très faible probabilité pour les mots rencontrés dans les courriers légitimes, comme les noms des amis et des parents de l'utilisateur.

Après l'apprentissage, les probabilités des mots (également appelées fonctions de vraisemblance) sont utilisées pour calculer la probabilité qu'un message (l'ensemble de ces mots) soit un spam. Chaque mot du message, ou du moins chaque mot « intéressant » du message, contribue à la probabilité que le message soit un spam. Cette contribution est calculée en utilisant le théorème de Bayes. Une fois que le calcul pour le message en entier est terminé, on compare sa probabilité d'être un spam à une valeur arbitraire (95 % par exemple) pour marquer ou non le message comme spam.

Comme dans n'importe quelle autre technique de filtrage du spam, les messages marqués comme spam peuvent être automatiquement déplacés dans un dossier « détritus », ou même supprimés sur le champ. Certains logiciels mettent en place des mécanismes de quarantaine qui définissent un intervalle de temps pendant lequel l'utilisateur a l'opportunité de réexaminer la décision du logiciel.

L'apprentissage initial peut souvent être affiné si jamais de mauvaises décisions du logiciel sont identifiées (faux positifs ou faux négatifs). Cela permet au logiciel de s'adapter à la nature évolutive du spam.

Certains filtres anti-spam combinent les résultats du filtrage bayésien du spam à d'autres méthodes heuristiques (règles prédéfinies concernant le contenu du message, examen de l'enveloppe du message, etc.), ce qui conduit à un filtrage encore plus précis, parfois aux dépens de l'adaptivité.

- Efficacité des équilibres

Dans de nombreux jeux, on peut définir deux sortes d'objectifs, un objectif personnel, que chaque joueur essaye de maximiser et un objectif global comme un indicateur du bien commun. L'efficacité des équilibres est une branche de la théorie algorithmique des jeux qui consiste à comparer la valeur de l'objectif global selon que les joueurs jouent pour optimiser leur objectif personnel ou qu'ils coopèrent pour maximiser l'objectif global.

- Application informatique

- Routage réseau p2p

- Bitcoin Lightning Network

L’objectif pour le Bitcoin Lightning Network c’est de permettre à une transaction de trouver son chemin sur un réseau décentralisé tout en optimisant les coûts, la vitesse et la quantité de données stockées par les nœuds.

- Complexité du calcul des équilibres

Un concept fondamental dans les jeux est celui d'équilibre, notamment d'équilibre de Nash. Ces équilibres sont définis de façon non-constructive, et la question se pose de savoir si, étant donné un jeu, on peut calculer de façon centralisée et efficace un équilibre.

Algorithme MinMax

L'algorithme minimax est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas).

Pseudo code

minmax(situation, profondeur, joueur)

situation la situation courante (racine de l’arbre de jeu)

profondeur le nombre de coups d’anticipation

joueur min ou MAX

appel :minmax(situation initiale,profondeur,MAX)

minmax(situation, prof, joueur) =

si prof = 0 ou situation est terminale

retourner φ (situation)

sinon situFilles = les situations filles l égales de situation

si joueur = MAX

retourner max fille ∈ situFilles {minmax(fille, prof−1 , min)}

sinon // joueur = min

retourner min fille ∈ situFilles { minmax (fille , prof −1 , MAX )}

fin si

fin si

Complexité

Soit b le facteur de branchement (nombre moyen de

successeurs), d la profondeur de l'arbre.

La complexité de Min-Max est O(bd)

Algorithme de Lemke-Howson

L'algorithme de Lemke-Howson est un algorithme qui calcule l'équilibre de Nash d'un jeu bi matriciel, nommé d'après ses inventeurs, Carlton E. Lemke et J. T. Howson. On dit qu'il est «le plus connu parmi les algorithmes combinatoires pour trouver un équilibre de Nash».

Pseudo code

ENTREE un jeu non dégénere

Prendre un équilibre (x;y) = (0;0) ϵ P×Q

Prendre

...