FLASH INFORMATIQUE FI



public averti Ecole de printemps 2010 de la CUSO


Conférence universitaire de Suisse occidentale



University Conference of Western Switzerland


Jacques MENU


Cette école de la [CUSO-Game theory and computer science.
Après un rappel des concepts fondamentaux comme les équilibres de Nash, les orateurs ont présenté des évolutions récentes du domaine. Parmi celles-ci, en 2009, la minimisation du regret itérée et la prise en compte du coût du calcul (au sens informatique) dans le choix des stratégies de jeu.
Des travaux dans les domaines de la sécurité et des systèmes distribués ont été présentés.
Les informations sur les intervenants, ainsi que certaines présentations, sont accessibles ici.
Les références bibliographiques figurent dans ces présentations. Plutôt que de faire un tour exhaustif des sujets abordés, il nous a paru intéressant de décrire le concept d’équilibre de Nash et de montrer une approche intéressante présentée lors de cette école.

Equilibres de Nash

John F. Nash a reçu le prix Nobel d’économie en 1994 pour ses travaux bien qu’il soit mathématicien, parce que la théorie des jeux a des applications très importantes en économie.
Dit de manière informelle, un équilibre de Nash caractérise un profil de stratégies (une par joueur) dans laquelle aucun joueur ne peut gagner plus en déviant unilatéralement. Cela suppose que chaque joueur a une croyance correcte de ce que fait chacun des autres : il joue de la meilleure façon possible en fonction de ces croyances.
Cette notion a des limitations, mais elle permet d’analyser les jeux et prédire ce que font certains joueurs.
Il y a par exemple des jeux où s’en tenir à un équilibre de Nash donne des résultats décevants, comme on le voit ci-dessous. Si le jeu a plusieurs tels équilibres, lequel choisir ? Un autre problème est : comment avoir une bonne idée de comment jouent les autres, dans un jeu qui n’est joué qu’une fois par exemple ?

Le dilemme du voyageur

Ce jeu proposé par Basu en 1994 (Traveler’s dilemma, en anglais), est intéressant.
Les règles sont :

  • deux voyageurs ont perdu leurs bagages, identiques, lors d’un voyage en avion ;
  • la compagnie d’aviation leur propose de les indemniser d’un montant compris entre 2 et 100, la monnaie n’ayant pas d’importance ;
  • tous deux annoncent leur demande sans connaître celle de l’autre ;
  • s’ils demandent le même montant, il l’obtiennent ;
  • sinon, ils obtiennent tous deux le plus bas des deux montants, diminué pour celui qui demande le plus d’un montant fixé p > 1 (la pénalité), et augmenté du même montant p pour celui qui demande le moins. On récompense donc le moins gourmand des deux, et on pénalise l’autre.

Quelle est la stratégie à adopter, c’est à dire combien chacun a-t-il intérêt à demander ?
Si on demande 99, on gagne parfois plus, mais toujours au moins autant que si on demande 100 (nous vous laissons vérifier ce point). On dit que 99 domine faiblement 100.
On devrait donc, par induction, choisir de demander 2. C’est en fait le seul équilibre de Nash de ce jeu.

Comment jouent les spécialistes ?

Lors d’une conférence de la Game Theory Society, réunissant des spécialistes de théorie des jeux, les participants ont joué à ce jeu avec des résultats étonnants [Becker, Carter & Naeve, 2005].
Avec une pénalité p = 2, parmi 45 joueurs, 3 seulement ont demandé 2, 38 ont demandé au moins 90, et 33 ont demandé au moins 95. Le meilleur gain a en fait été obtenu en demandant 97.
Peu de ces spécialistes ont donc recherché un équilibre de Nash dans ce cas. Notons que l’approche illustrée ci-dessus et conduisant au choix de 2 ne tient pas compte de la valeur de p.
Que se passe-t’il si on varie la pénalité p et qu’on joue de manière répétitive ? Une expérience [Capra, Goeree, Gomez & Holt, 1999] montre que, dans ces conditions, si p est voisin de 2, les gens demandent beaucoup et s’y tiennent. Si p est grand, les joueurs démarrent en demandant moins et convergent rapidement vers l’équilibre de Nash.

Au-delà des équilibres de Nash

Le concept de minimisation du regret (regret minimization) a été introduit en théorie de la décision vers 1950. Le regret pour un choix dans un état du jeu est la différence entre le gain découlant de ce choix et le meilleur gain possible.
Joe Halpern et Rafael Pass, de Cornell University, ont introduit le concept de minimisation itérative du regret (iterated regret minimization) pour mieux jouer dans des jeux du type du dilemme du voyageur, en se rapprochant du comportement des joueurs humains illustré ci-dessus.
Dans ce contexte, chaque joueur essaie de jouer au mieux, indépendamment de ce que font les autres. Plus précisément, il essaie de minimiser le regret étant donnée l’incertitude sur la stratégie des autres joueurs.
Avec p=2, le regret de jouer une valeur allant de 96 à 100 est 3. Le regret est supérieur à 3 pour les valeurs inférieures à 96. Que se passe-t-il en itérant des parties où tout le monde ne joue qu’entre 96 et 100 ? 97 a un regret de 2 par rapport aux autres valeurs dans cet intervalle, ces dernières ayant un regret de 3. C’est donc 97 qui est la stratégie gagnante, comme dans l’expérience de 2005.
Avec des pénalités plus grandes que 50, seulement 2 minimise le regret, et l’on retrouve les résultats observés dans l’expérience de 1999.

En conclusion

Participer à un telle école de printemps ouvre des perspectives sur les évolutions possibles dans nos domaines d’activité. C’est aussi l’occasion d’échanges fructueux avec des collègues proches géographiquement, mais que nous ne rencontrons que peu en cours d’année.

Références



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.