Optimisation du positionnement des annonces textuelles en marketing interactif

Lorsqu'un utilisateur tape du texte dans le champ réservé à cet effet dans un moteur de recherche, pendant le chargement de la page des résultats, une enchère a lieu pour déterminer quelles annonces textuelles seront affichées et dans quel ordre. Le texte tapé par l'utilisateur doit pouvoir être associé à au moins un des mots-clés choisis par un annonceur pour que ce dernier soit éligible à participer à cette enchère. Plus une annonce est affichée haut sur la page, mieux elle est classée et; mieux elle est classée, plus l'annonceur devra payer pour chaque clic sur ladite annonce et plus les utilisateurs cliqueront dessus. Toutefois, le montant facturé par le moteur de recherche à un annonceur pour chaque clic ne dépasse jamais l'enchère de cet annonceur. De plus, l'annonceur peut fixer un budget périodique (par jour, semaine ou mois) que le moteur de recherche devra respecter. Les annonceurs doivent donc établir une stratégie d'enchère qui leur permettra de maximiser la performance de leurs campagnes tout en respectant leur budget. Malheureusement, ils n'ont accès qu'à une quantité limitée d'informations pour le faire. Dans le cadre de ce projet de recherche, un modèle d'optimisation est proposé. Il permet de déterminer la meilleure position pour chaque mot-clé avec pour objectif d'optimiser les profits générés par une ou plusieurs campagnes d'un annonceur ou d'autres indices de performance de campagne tels que les revenus ou les conversions. Ce modèle, présenté dans le troisième chapitre, est basé sur les données de navigation partielle des utilisateurs. Elles sont représentées par un graphe et le problème est formulé comme un problème de flot ou de flot à coût minimum selon l'objectif utilisé. Le modèle n'étant pas linéaire, nous avons également développé cinq algorithmes pour résoudre ce problème. Quatre d'entre eux sont basés sur l'algorithme tabou. Dans la version élémentaire de l'algorithme, on modifie d'une unité la position d'un mot-clé et on recalcule le flot en utilisant des formules liant la position d'un mot-clé au nombre de clics espérés sur celui-ci ainsi qu'au coût-par-clic moyen de ce mot-clé. Le mot-clé dont la position est changée est choisi de sorte que la modification soit la plus profitable possible tout en respectant les contraintes de budget. Par la suite, il devient tabou de modifier à nouveau la position du même mot-clé pendant un nombre prédéterminé d'itérations. Les trois autres algorithmes sont des variantes du premier. Dans la première variante, la position peut être modifiée de plus d'une unité. Dans la seconde, on accepte avec une pénalité que le budget soit dépassé. Finalement, dans la troisième version, les variantes des deux premières versions sont implémentées. Le cinquième algorithme est basé sur l'algorithme glouton. À chaque itération, pour chaque mot-clé, on détermine s'il est préférable de maintenir sa position ou de la modifier d'une unité. Si changer de position est plus profitable, alors on détermine quelle position est la plus profitable et on effectue le changement. Ce changement peut être de plus d'une unité. Les dépassements de budget sont permis mais pénalisés. Cet algorithme s'est avéré être le plus rapide avec des résultats comparables à ceux obtenus avec les tabous. Dans le quatrième chapitre, on propose une étude comparative sur l'impact de différentes modifications, celles-ci étant apportées soit au modèle soit à un paramètre. La première étude consiste à modifier la fonction-objectif et de mesurer l'impact de ce changement sur les résultats. Nous avons comparé les valeurs de différentes mesures de performances lorsque l'objectif est d'optimiser une d'elles à la fois. L'analyse révèle que le profit et les coûts sont les plus sensibles au changement et que la maximisation des visites est l'objectif ayant l'impact le plus négatif sur les autres mesures de performance. Une seconde étude analyse l'impact de la variation du budget sur les résultats de la campagne. Dans cette étude, on constate que la maximisation du profit est peu sensible à la variation de budget et que, pour les autres objectifs, une variation de ±10% ou 20% ne se traduit pas nécessairement en une variation de performance de ±10% ou 20%. Finalement, la dernière modification analysée est la variation du coût-par-clic sur l'ensemble des mots-clés. Pour cette analyse, les coûts-par-clic de tous les mots-clés sont aléatoirement modifiés afin de voir si ces changements ont un impact significatif sur les valeurs des indices de performance et sur les positions des mots-clés. Dans le cas de la maximisation des profits, moins de 7% des mots-clés se sont retrouvé à des positions différentes au final et la différence était seulement d'une unité. Pour le reste des objectifs, les variations sont plus importantes.