Bref introduction à la théorie des jeux algorithmiques

Table des matières

I.        Introduction        2

II.        Objectif généraux        3

III.        Quelques notions de base        4

IV.        Description et historique        5

V.        Quelques sous-domaines principaux de la théorie des jeux algorithmiques        6

A.        Les mécanismes d'incitation        6

1.        Application informatique        6

B.        Efficacité des équilibres        9

1.        Application informatique        9

C.        Complexité du calcul des équilibres        9

Algorithme MinMax        9

Algorithme de Lemke-Howson        10

VI.        Cas pratique: Gambit Open source        11

VII.        Conclusion        14

VIII.        Bibliographie        15

1. Introduction

La théorie des jeux est une discipline visant à modéliser des situations où des acteurs doivent prendre des décisions ayant des conséquences mutuelles et potentiellement conflictuelles. Ses applications traditionnelles sont l’économie, la politique et la biologie. Suite au développement, entres autres, d'internet et du commerce électronique elle occupe une place  importante en informatique. Cet exposé présentera donc l’approche algorithmique (computationnel) de la théorie de jeux.

1. Objectif généraux

Introduire la théorie des jeux algorithmiques et exposer ses développements récents à travers différent approche.

1. Quelques notions de base

Intelligence artificielle: c'est l'étude de comment programmer les ordinateurs pour qu'ils réalisent des tâches pour lesquelles les êtres humains sont actuellement meilleurs. Rich & Knight (1991).

L’aide à la décision: c'est l’ensemble des techniques permettant, pour une personne donnée, d’opter pour la meilleure prise de décision possible. Wikipédia (2016).

La théorie des jeux:  est un domaine mathématique  qui permet d'analyser les situations dans lesquelles l'action optimale pour un agent dépend des anticipations qu'il forme sur la décision d'un autre agent. Wikipédia (2016).

L'algorithmique: est la science qui s’intéresse à l’art de construire des algorithmes ainsi qu’a caractériser leur validité, leur robustesse, leur réutilisabilité, leur complexité ou leur efficacité. Jacques Tisseau (2009).

1. Description et historique

L'émergence d'Internet a motivé l'étude des phénomènes de compétitions et de coopération sur de grands réseaux, et c'est l'origine de la théorie algorithmique des jeux.  Ce domaine est relativement récent et on peut situer son essor dans les années 2000. 

1. Quelques sous-domaines principaux de la théorie des jeux algorithmiques

1.  Les mécanismes d'incitation

La théorie des mécanismes d'incitation consiste à définir des mécanismes, c'est-à-dire des règles de jeux, pour assurer que des joueurs rationnels arrivent à un certain objectif.

1. Application informatique

1. Algorithme d'enchères

• Google Adwords

Définition

Google AdWords ou AdWords est la régie publicitaire de Google créée le 23 octobre 2000 aux États-Unis. Celui-ci affiche des annonces ou bannières publicitaires soit sur Google soit sur le réseau partenaires Display, qui sont ciblées en fonction des mots-clés que tape l'internaute ou en fonction de son comportement de navigation.

Les annonceurs paient lorsque l'internaute clique sur la publicité selon un système d'enchère et de qualité : plus l'annonce sera pertinente pour l'utilisateur, plus le prix au clic sera bas et l'annonce en évidence. Ceci afin d'inciter les publicitaires à fournir des renseignements pertinents par rapport à la demande de l'utilisateur.

« AdWords » provient de « Ad » pour Advertising : Publicité et Words : mots. Wikipédia (2016).

Fonctionnement

Lorsqu'un internaute utilise Google, deux listes de résultats sont affichées : au centre de la page, les résultats du moteur de recherche lui-même, classé selon des critères « objectifs » - nommés résultats naturels (cf.  Googlebot et le système PageRank); et en haut de page, les résultats provenant de la régie AdWords, nommés liens commandités. Google tire ainsi profit de son moteur de recherche en vendant cet espace publicitaire sous la forme de clic aux annonceurs souhaitant apparaître à la suite d'une « recherche » effectuée par un internaute.

1. Algorithme mécanisme Bayésien

• Filtrage bayésien du spam

Définition

Le filtrage bayésien du spam (en référence au théorème de Bayes) est une technique statistique de détection de pourriels s'appuyant sur la classification naïve bayésienne.

Les filtres bayésiens fonctionnent en établissant une corrélation entre la présence de certains éléments (en général des mots, parfois d'autres choses) dans un message et le fait qu'ils apparaissent en général dans des messages indésirables (spam) ou dans des messages légitimes (ham) pour calculer la probabilité que ce message soit un spam.

...