<  Back to the Polytechnique Montréal portal

Optimisation du positionnement des annonces textuelles en marketing interactif

Koukla Azeuli Nkamegni

PhD thesis (2017)

[img]
Preview
Download (647kB)
Cite this document: Azeuli Nkamegni, K. (2017). Optimisation du positionnement des annonces textuelles en marketing interactif (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/2906/
Show abstract Hide abstract

Abstract

RÉSUMÉ : 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.----------ABSTRACT : When a user types a text in the search field of a search engine, during the loading of the page, an auction takes place to determine which text ads will appear along with the search results and in which order. The text typed by the user must be associated with at least one of the keywords chosen by an advertiser for that advertiser to be eligible to participate in that auction. In this thesis, we only consider the first ten positions which are all on the first page as all the others have very little impact on the ad performance. So, the highest an ad is placed on the result page, the better it is ranked, the more each click will cost and the more clicks it will receive. However, the cost-per-click billed to the advertiser never exceeds his bid (the maximal amount he is willing to pay per click). Moreover, the advertiser can set a periodical budget. A period might be a day, a week or a month. That budget is to be respected by the search engine. The advertiser must find the best bidding strategy that will help them maximize the performance of their ad campaigns while respecting their budget. Thus, in the third chapter, a new model to determine which position to aim for on search engines using partial users’ navigation history available to advertisers is proposed. For a given advertiser, we represent as a graph the partial navigation history of users who interacted with any element of a campaign such as clicking on text ads or banners, visiting a page of the advertiser’s website containing a web tracker, etc. We modeled the problem assuming that an increase of traffic at one vertex implies a decrease for all vertices sharing the same parent(s) and vice versa. Based on that, we reorganize the flow within the graph to maximize the expected profits from conversions tracked online. To solve the problem, we designed five algorithms. Four of them are based on the tabu search algorithm. In the most basic one, we change the position of one keyword by one unit then recalculate the flow using the functions mentioned earlier. The keyword which position is to be changed is chosen so that the change is the most profitable but respects the budget. Changing the position of that keyword then becomes tabu for a given number of iterations. The three other tabu algorithms are variations of the basic one. In the first variation, we allow the position of the chosen keyword to be changed by more than one unit. In the second, the change can lead to expenses greater than the budget. In the last one, both variations are combined. The fifth algorithm is a greedy one. During every iteration, for each keyword, we determine whether keeping it at the same position or changing its position by one unit is more profitable. If changing is chosen, we then determine the number of units that makes the change the most profitable. Exceeding the budget is allowed with a penalty. This algorithm turned out to be the fastest with results similar in value to those of the tabu algorithms. The profit of a campaign is only one of the possible measures of its efficiency. In our second article, we analyze how different changes impact the campaign management by comparing the results obtained with different objective-functions. The first change analyzed was the use of a different objective-function. We compared the values of the performance indicators obtained when optimizing each one of them. The analysis revealed that the profit and the costs are the most sensitive to change. Also, visits maximization has the most negative impact than other objective-functions on performance indicators other than visits. The second change we tested was the variation of budget. Profit maximization was not very sensitive to that. For the other objective-functions, it had more impact but ±10% or 20% did not necessarily translate to a variation of ±10% or 20% in value for any of them. The last change was the variation of the cost-per-click. We randomly changed the cost-perclick of every keyword and compared the values of the performance indicators before and after the change. For profit maximization, less than 7% of the keywords saw their best positions change by one unit and the positions of other keywords did not change at all. The impact was more significant for the other objective-functions.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Michel Gamache and Alain Hertz
Date Deposited: 03 Apr 2018 15:12
Last Modified: 27 Jun 2019 16:47
PolyPublie URL: https://publications.polymtl.ca/2906/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only