>> Sommaire

Informatique
Vers de meilleurs algorithmes capables de se "battre" en eux

http://www.bulletins-electroniques.com/actualites/68493.htm

Deux touristes se promènent dans la savanne Africaine et ils entendent un lion rugir un petit peu plus loin. Immédiatement, l'un des deux ouvre son sac et sort ses chaussures de course. "Mais tu es fou" lui dit son ami, "tu ne pourras jamais courir plus vite que le lion!". Le deuxième répond alors, "Pas grave, il suffit que je cours plus vite que toi!".

Traditionnellement en informatique, l'objectif d'un algorithme est de fournir la solution optimale et de tenter de minimiser le temps de calcul pour obtenir cette solution. Cependant à part dans des problèmes mathématiques bien définis pour lesquels une solution optimale existe vraiment, la plaisanterie ci-dessus démontre que dans une situation pratique il n'est pas toujours avantageux de trouver une solution "parfaite", mais simplement de mettre en place une stratégie supérieure à celle proposée par la compétition. Un groupe de mathématiciens travaillant au département de recherche et développement de la branche Israelienne de Microsoft ainsi que au Techion à Haifa vient de faire des progrés importants dans la compréhension des propriétés des algorithmes, non pas "optimaux" mais plutôt "compétitifs".

De manière à mieux illustrer le coeur du sujet, imaginons qu'une séries de 10 morceaux d'informations (page webs par exemple) soient organisées en une liste allant de la page la plus populaire (n1) jusqu'à la page la moins populaire (n10) dans le sens le plus naturel (n1 > n2 > ... > n9 > n10). Une telle organisation correspond à un algorithme "glouton". En l'absence de compétition, il est évident que cette organisation est optimale. Imaginons maintenant une compétition entre deux agents dont le but est de fournir un "moteur de recherche" permettant aux utilisateurs de retrouver les informations qu'ils souhaitent le plus rapidemenent possible. Dans ce cas, il est clair que l'organisation "naive" proposée ci-dessus représente un cas très spécial qui n'est "optimal" que dans un sens abstrait. Si la page la plus populaire représente la demande de 40% des utilistateurs, l'organisation présentée ci-dessus laisse 60% des utilisateurs insatisfaits. Cela signifie que dans un environnement compétitif, il suffit qu'une compagnie offre un "moteur de recherche" qui donne plus d'importance à des pages un peu moins populaires (et donc devient non-optimal) pour en fait se rapprocher de la demande des utilisateurs. Typiquement, après plusieurs étapes de réajustement, il est attendu que tous les compétiteurs finissent par converger vers un une solution "équilibrée". Il s'agit d'une situation dans laquelle les agents, ayant finalement compris leurs stratégies réciproques, ne peuvent plus changer de stratégie sans affaiblir leur propre position. En théorie des jeux, on parle d'équilibre de "Nash".

Pouvoir déterminer à l'avance quelle sera la solution d'"équilibre", représente donc un problème d'importance capitale. Malheureusement, il est extrèmenent difficile d'aborder ce genre de question de manière satisfaisante car la complexité du temps de calcul augmente exponenetiellement avec la taille des informations. Un groupe de chercheurs de Microsoft Israel et du Technion viennent de prouver un certains nombres de théorèmes mathématiques qui ouvrent une nouvelle avenue de recherche dans ce domaine. En se basant sur un modèle simplifiée ne contenant que 2 participants (situation déjà non-triviale en terme de complexité), les mathématiciens ont développé une théorie probabilistique permettant de prouver l'existence ou non, de stratégies compétitives capables de "battre" la stratégie optimale (mais sans compétition). Dans quelques examples particuliers, ils ont même réussi à construire explicitement des stratégies compétitives.

Ces travaux offrent une excursion dans un domaine des mathématiques encore très peu étudiées. Les applications possibles des techniques mises en place par Microsoft Israel vont bien au-delà de l'informatique et des mathématiques. Par exemple, des questions du genre: "Sous quelles conditions est-ce que la compétition entre plusieurs stratégies engendre une amélioration ou une dégradation du niveau de performance attendue?", intéressent également de nombreuses autres disciplines allant de la politique à l'économie.

>> Suivant

<< Précédent



Partager cette page :

Tweet

Partager

Version imprimable >>

Transmettre cette info par email >>

Recommander ce site à un collègue / ami >>



S'abonner au
BE Israël >>



FAQ / foire aux questions >>

Conditions d'utilisation >>

Vous pouvez en apprendre en plus en consultant l'article original intitulé "Dueling Algorithms" en suivant le lien suivant : http://arxiv.org/pdf/1101.2883v1

Code brève
ADIT : 68493

d'après Laurent Boue, VI Chercheur

BE Israël numéro 76 (13/12/2011) - Ambassade de France en Israël / ADIT - http://www.bulletins-electroniques.com/actualites/68493.htm